#include<bits/stdc++.h> using namespace std; int happy[410]; bool unhappy[410]; int digit_add(int n) { int sum=0; while (n) { int a=n%10; sum+=a*a; n/=10; } return sum; } int ishappy(int n) { bool visit[410]; memset(visit,false,410); visit[n]=true; int count=0; while (1) { count++; n=digit_add(n); if (n==1) return count; if (happy[n]) return happy[n]+count; if (visit[n]) return 0; if (unhappy[n]) return 0; visit[n]=true; } } void preset() { memset(happy, 0, 410); memset(unhappy,false,410); for (int i=1;i<410;i++) { int temp=ishappy(i); if (temp==0) for (int j=i;j<410;j*=10) unhappy[j]=true; else for (int j=i;j<410;j*=10) happy[j]=temp; } return; } int main() { int l,h,t=0; preset(); while (scanf("%d%d",&l,&h)!=EOF) { if (t) printf("\n"); for (int i=l;i<=h;i++) { if (i==1) { printf("1 1\n"); continue; } int n=digit_add(i); if (n==1) printf("%d 2\n",i); else if (happy[n]) printf("%d %d\n",i,happy[n]+2); } t=1; } return 0; }
Thursday, April 28, 2016
UVA 944 : Happy numbers - solution
Unknown
Studying at Shahjalal University of Science and Technology, Sylhet.
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment