首页 > 代码库 > 第六届湘潭市程序设计竞赛 -Happy Number

第六届湘潭市程序设计竞赛 -Happy Number



Happy Number

Accepted : 110 Submit : 263
Time Limit : 1000 MS Memory Limit : 65536 KB 


Problem Description

Recently, Mr. Xie learn the concept of happy number. A happy number is a number contain all digit 7 or only 1 digit other than 7. For example, 777 is a happy number because 777 contail all digit 7, 7177 and 87777 both happy number because only 1 digit other than 7. Whereas 887,799 9807,12345, all of them are not happy number. Now Mr. xie want to know for a given integer n, how many number among [1,n] are happy numbers, but counting them one by one is slow, can you help him?

Input

First line an integer t indicate there are t testcases(1≤t≤100). Then t lines follow, each line an integer n(1≤n≤106, n don‘t have leading zero).

Output

Output case number first, then the answer.

Sample Input

5
1
7
17
20
30

Sample Output

Case 1: 1
Case 2: 7
Case 3: 10
Case 4: 10
Case 5: 11


开始不敢做,怕暴力超时,后来写了暴力,但是 调代码又出问题,日

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
const int N = 1010;
using namespace std;
int l=0;
int main()
{
   int t,n;
   scanf("%d",&t);
   for(int i = 1;i<=t;i++)
   {
       int sum = 0,p = 0,pp = 0,ppp = 0,wz,mo;
       scanf("%d",&n);
       if(n<10)
       {
           printf("Case %d: %d\n",i,n);
           continue;
       }
       else if(n>=10)
       {
           wz = 0;
           int j;
           for( j = 10;j<=n;j++)
           {
               p = j;
               pp = 0,ppp = 0;
               wz = 0;
               while(p)
               {
                   mo = p % 10;
                   wz++;
                   if(mo==7)
                        pp++;

                   else
                        ppp++;
                    if(ppp>=2)
                        break;
                    p /= 10;
               }
               if(ppp==1 && pp==wz-1)
                        sum++;
                else if(ppp==0 && pp==wz)
                        sum++;
           }
           sum += 9;
           printf("Case %d: %d\n",i,sum);
       }

   }
    return 0;
}