NYOJ-91

2344 ワード
C++ 南陽OJ
タイトル:
階乗の和
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:3
説明
負以外の整数nを与えて、nがいくつかの数(これらの数は繰り返し使用できず、正の数)の乗算の和であるかどうかを判断します.例えば、9=1!+2!+3!、もしそうであれば、Yesを出力します.そうでなければ、Noを出力します.
入力
第1行には、mグループのテストデータがあることを示す整数0各テストデータのセットには正の整数n<1000000がある.
しゅつりょく
条件を満たしていればYesを出力し、そうでなければNoを出力する.
サンプル入力
2
9
10

サンプル出力
Yes
No

この問題は単純な累積ではなく、問題を見極めるには、いくつかの数の階乗の和であることに注意しなければならない.例えば、25=1!+4!出力Yes
欲張りアルゴリズムで解決できる.
ACコード
#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    int m;
    cin >> m;
    long long n;
    long long res = 0;
    while(m--)
    {
        cin >> n;
        if(1 == n)
        {
            cout << "Yes" << endl;
        }
        else
        {
            long j = 1;
            int a[101] = {0}, i, k;
            memset(a, -1, 100);
            for(res = n; res > 0;)
            {
                for(i = 1, j = 1; j <= res; ++i)
                {
                    j = i * j;
                }
                --i;
                j = j / i;
                --i;//        res   
                 //          ，       1       res -1
                 for(k = 0;k < 100; ++k)
                {
                    if(a[k] == i)
                    {
                        if(i == 1)
                        {
                            res = -1;
                            break;
                        }
                        j = j / i;
                        a[k + 1] = i - 1;
                        break;
                    }
                    else if(a[k] == -1)
                    {
                        a[k] = i;
                        break;
                    }
                }
                res -= j;
            }

            if(0 == res)
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
    }

    return 0;
}

欲張りアルゴリズムの紹介はこのブログを参考にすることができます.http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html
不安定なテストを書いてはいけない3つの理由
【１ヶ月で学ぶ！】Back-end Developperへの道 #12日目 : Testingとは、CI/CDとは