Ronzii's Blog

Just your average geek's blog

Unlucky Numbers using memoization

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long long print(int n,int map_size, int map[], long long pre[])
{
    if(pre[n]!=-1)
    {
        return pre[n];
    }
    if(n<=0)
    {
        return 0;
    }
    else
    {
        int r = (n-1)%map_size;
        int result = 10*(print((n-1)/map_size,map_size,map,pre))+map[r];
        pre[n] = result;
        return result;
    }
}

int main()
{
    long n;
    int map[] = { 2,4,7};
    int map_size = sizeof(map)/sizeof(int);
    long long pre[200000];
    memset(pre,-1,sizeof(pre));
    while(1)
    {
        scanf("%ld",&n);
        cout<<print(n,map_size,map,pre)<<endl;
    }
    return 0;
}
Advertisements

March 3, 2012 Posted by | C++ | , , | Leave a comment