XTU OJ 1210 Happy Number(暴力+打表)
4592 ワード
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
Sample Output
試合でこの問題を見たとき、counting them one by one is slowという言葉を見て、暴力がタイムアウトする可能性があると思って、その時はその方面に考えていなかったが、その後は大丈夫だったので、この問題に専念して、暴力+時計で試してみた.試合の時はやはり思い切ってやってみましょう.考えがあるだけで実現しなければなりません.考えが間違っていても、私たちは勇敢にやってみましょう.絶えず探求してこそ進歩する.
この問題の構想は表を打つことで、データ量はまだあまり大きくないので、表を打つことはできます.
以下はacコードです.
もう一つの書き方は、メモリが上より少ないような気がします.
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
試合でこの問題を見たとき、counting them one by one is slowという言葉を見て、暴力がタイムアウトする可能性があると思って、その時はその方面に考えていなかったが、その後は大丈夫だったので、この問題に専念して、暴力+時計で試してみた.試合の時はやはり思い切ってやってみましょう.考えがあるだけで実現しなければなりません.考えが間違っていても、私たちは勇敢にやってみましょう.絶えず探求してこそ進歩する.
この問題の構想は表を打つことで、データ量はまだあまり大きくないので、表を打つことはできます.
以下はacコードです.
#include "stdio.h"
#include "string.h"
const int maxn=1000000+10;
int a[maxn];
void init() //
{
int i;
for(i=0;i<=9;i++) // , i 1, , , ;
{ // 0
a[i]=1;
a[i*10+7]=1; //
a[7*10+i]=1;
a[i*100+7*10+7]=1;//
a[7*100+i*10+7]=1;
a[7*100+7*10+i]=1;
a[i*1000+7*100+7*10+7]=1;//
a[7*1000+i*100+7*10+7]=1;
a[7*1000+7*100+i*10+7]=1;
a[7*1000+7*100+7*10+i]=1;
a[i*10000+7*1000+7*100+7*10+7]=1;
a[7*10000+i*1000+7*100+7*10+7]=1;
a[7*10000+7*1000+i*100+7*10+7]=1;
a[7*10000+7*1000+7*100+i*10+7]=1;
a[7*10000+7*1000+7*100+7*10+i]=1;
a[i*100000+7*10000+7*1000+7*100+7*10+7]=1;
a[7*100000+i*10000+7*1000+7*100+7*10+7]=1;
a[7*100000+7*10000+i*1000+7*100+7*10+7]=1;
a[7*100000+7*10000+7*1000+i*100+7*10+7]=1;
a[7*100000+7*10000+7*1000+7*100+i*10+7]=1;
a[7*100000+7*10000+7*1000+7*100+7*10+i]=1;
}
}
int main()
{
memset(a,0,sizeof(a));
init();
int t,i,count,n,j;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
count=0;
scanf("%d",&n);
for(j=1;j<=n;j++)
{
if(a[j]==1)
count++;
}
printf("Case %d: ",i);
printf("%d
",count);
}
return 0;
}
もう一つの書き方は、メモリが上より少ないような気がします.
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
int main()
{
// freopen("a.txt","r",stdin);
int t, n, i, j;
int p[200] = {1,2,3,4,5,6,7,8,9,17,27,37,47,57,67,70,71,72,
73,74,75,76,77,78,79,87,97,177,277,377,477,577,
677,707,717,727,737,747,757,767,770,771,772,773,
774,775,776,777,778,779,787,797,877,977,1777,2777,
3777,4777,5777,6777,7077,7177,7277,7377,7477,7577,7677,
7707,7717,7727,7737,7747,7757,7767,7770,7771,7772,7773,7774,
7775,7776,7777,7778,7779,7787,7797,7877,7977,8777,9777,17777,
27777,37777,47777,57777,67777,70777,71777,72777,73777,74777,75777,
76777,77077,77177,77277,77377,77477,77577,77677,77707,77717,77727,
77737,77747,77757,77767,77770,77771,77772,77773,77774,77775,77776,
77777,77778,77779,77787,77797,77877,77977,78777,79777,87777,97777,
177777,277777,377777,477777,577777,677777,707777,717777,727777,737777,
747777,757777,767777,770777,771777,772777,773777,774777,775777,776777,
777077,777177,777277,777377,777477,777577,777677,777707,777717,777727,
777737,777747,777757,777767,777770,777771,777772,777773,777774,777775,
777776,777777,777778,777779,777787,777797,777877,777977,778777,779777,
787777,797777,877777,977777};
cin >> t;
for(i = 1; i <= t; ++ i)
{
cin >> n;
for(j = 0; p[j] <= n && j < 189; ++ j);
printf("Case %d: %d
",i,j);
}
return 0;
}