2013年9月19日 星期四

2013/9/19 HSNU OJ 307 - 幸運碼

/* http://hoj.twbbs.org/judge/problem/view/307 */
#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

int lucky[70001]; queue<int> que; int inqueue[70001];

int main()
{
    lucky[1] = 1; int cnt = 1; int flag = 0;

    for(int i = 2; i <= 70000; i++)
    {
        int t = i;
       // cout<<i<<"\n"<<"---------------\n";
        while( 1 )
        {
            if( lucky[t] == 1 )
            {
                while( !que.empty() )
                {
                    if( que.front() <= 70000 ){ lucky[que.front()] = 1; inqueue[que.front()] = 0; }
                    que.pop();
                }
                break;
            }
            else if( lucky[t] == -1 || inqueue[t] == 1 )
            {
                while( !que.empty() )
                {
                    if( que.front() <= 70000 ){ lucky[que.front()] = -1; inqueue[que.front()] = 0; }
                    que.pop();
                }
                break;
            }

            que.push(t);

            if( t <= 70000 )
                inqueue[t] = 1;

            if( t < 10 )
                t = t*t;

            else
            {
                int s = 0;
                while( t != 0 ){ s += (t%10)*(t%10); t/=10; }
                t = s;
            }
            //cout<<t<<endl;
        }

        if( lucky[i] == 1 )
        {
            cnt++;
            if( cnt == 10 || cnt == 50 || cnt == 100 || cnt == 1000 || cnt == 10000 )
                cout<<i<<endl;
        }




        //getchar();
    }
}

沒有留言:

張貼留言