Uva 11032 - Function Overloading

#include<bits/stdc++.h>
#define out(s) cout << s << "\n"
#define outs(s) cout << s << " "
#define sf scanf
#define pf printf
#define sze 10000019
using namespace std;

typedef long long LL;
typedef vector<LL> vll;

LL digit_arr[sze];

LL sum(LL n)
{
    LL s=0;

    while(n)
    {
        s+=(n%10);
        n/=10;
    }

    return s;
}

void digit_sum()
{
    LL i;

    for(i=1; i<10; i++)
    {
        digit_arr[i] = i;
    }

    for(i=10; i<=sze; i++)
    {
        LL cal = sum(i);

        if(cal > 9)
        {
            digit_arr[i] = cal;
        }

        else
        {
            digit_arr[i] = digit_arr[cal];
        }
    }

    //for(i=1;i<=20;i++)outs(digit_arr[i]);
}

LL fun_one(LL a)
{
    LL i, h = (a/2)+1;

    for(i=h; i<=a; i++)
    {
        if(i+digit_arr[i] == a)
        {
            return i;
        }
    }

    return -1;
}

bool flag[sze];
LL keep[sze];

void inti()
{
    memset(flag, false, sizeof(flag));

    //keep[1] = 1;
    //flag[2] = true;

    LL i, r;

    for(i=1; i<=sze; i++)
    {
        r = i+digit_arr[i];

        if(r<=sze)
        {
            flag[r] = true;
        }

        if(!flag[i])
        {
            keep[i] = 1;
        }
    }

//    for(i=1;i<=20;i++)
//    {
//        outs(keep[i]);
//    }
}

LL fun_two(LL a, LL b)
{
    LL cnt=0, i;

    for(i=a; i<=b; i++)
    {
        if(keep[i] == 1)
        {
            cnt++;
        }
    }

    return cnt;
    //out(cnt);
}

int main()
{
    digit_sum();
    inti();
    int t,tc=0;
    string s;

    cin >> t;
    getchar();

    while(t--)
    {
        getline(cin,s);
        //cin >> s1 >> s2;

        //int len = s.size();
        //len-=1;
        //out(s1.size());
        //out(s2.size());

        LL num[5],n;
        int len=0;

        stringstream ss(s);
        while(ss >> n)
        {
            num[len++] = n;
        }

        //out(len);
        //out(num[0]); out(num[1]);
        //return 0;

        cout << "Case " << ++tc << ": ";

        if(len==1)
        {
            cout << fun_one(num[0]) << "\n";
        }

        else
        {
            LL x = num[0], y=num[1];

            if(x < y)
            {
                cout << fun_two(x,y) << "\n";
            }

            else if(x > y)
            {
                cout << "-" << fun_two(y,x) << "\n";
            }

            else
            {
                cout << fun_two(x,y)  << "\n";
            }
        }
    }

    return 0;
}

Comments

Popular posts from this blog

SPOJ-CMG - Collecting Mango

LightOJ 1009 - Back to Underworld

LeetCode Palindrome Number