Thursday, April 28, 2016

UVA 944 : Happy numbers - solution

Unknown
#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;
}

Unknown

Studying at Shahjalal University of Science and Technology, Sylhet.

0 comments:

Post a Comment

Coprights @ 2016,