SRM 504.5 div1 easy:TheNumbersWithLuckyLastDigit

SRM 504.5の練習会に参加。結果はeasyとmedをそこそこ高得点で通してhappyでした。

問題

TopCoder Statistics - Problem Statement

解法

まずある程度以上の数は必ず作ることがわかります(4と7は互いに素なのである程度大きい数からは連続して作れるようになる)。

また,ある数を作ることができる場合,それを作るのに必要な数の個数は1の位のみに依存します。よって,適当なdpというほどでもないdpを作って1の位と比べればOKです。

以下ソースコード

int dp[10];

class TheNumbersWithLuckyLastDigit {
public:
    int find(int n) {
        if (n <= 3 || (5 <= n && n <= 6) || (9 <= n && n <= 10) || n == 13) return -1;
        int last = n%10;
        memset(dp, -1, sizeof(dp));
        dp[4] = 1, dp[7] = 1;
        while (1) {
            bool update = false;
            for (int i = 0; i < 10; i++) {
                if (dp[i] == -1) continue;
                {
                    int next = (i+4)%10;
                    if (dp[next] == -1) {
                        update = true;
                        dp[next] = dp[i]+1;
                    }
                }
                {
                    int next = (i+7)%10;
                    if (dp[next] == -1) {
                        update = true;
                        dp[next] = dp[i]+1;
                    }
                }
            }
            if (!update) break;
        }
        for (int i = 0; i < 10; i++) {
            cout << i << "  " << dp[i] << endl;
        }
        return dp[last];
    }
};