ZeroJudge A364: 神秘的進位問題

在一個神秘的國家，他們有不同的文明，他們所使用的數字表示法跟常見的 十進位法不一樣。對於一個十進位的數字 N，他們會表示成 abc，其中 a > b > c >= 0 ，且滿足 N= C(a, 3) + C(b, 2) + C(c, 1) ， C 為二項係數，即 C(m, n) = m!/(n!(m-n)!)，但當 m < n 時，C(m, n) = 0。為幫助了解這個神秘國度的文化， 請寫一程式來將十進位數轉換成這個神秘的進位法。

範例測資

範例輸入範例輸出
第一行有一個整數 m，1 ≤ m ≤ 10，代表要轉換的十進位數的個數。接下來的 m 行（第 2 行至第 (m+1) 行）：每一行都有一個介於 0 和 500 之間的整數，代表要轉換的十進位數。針對每一個十進位數分別在一行輸出對應的 abc，其間不需留空白，注意 a、 b 和 c 未必是只有一位數，若答案不唯一時請輸出字典順序最小的表示法，即盡 可能取小的 a 及 b 值。
4
0
1
2
200		210
310
320
1187
3
18
19
20		542
543
610
ZeroJudge A364 範例測資

解題思路

可以使用 DFS 來跑所有可能，包括只增加其中一個數字或是兩個數字或是全部都加，但是需要確保 a > b > c，所以一開始在呼叫 DFS 時，a = 2、b = 1、c = 0。

範例程式碼－ZeroJudge A364: 神秘的進位問題

#include <iostream>
using namespace std;

bool ok = false;

int calc (const int a, const int b) {
    if (a < b) return 0;
    int result = 1, divisor = 1;;
    for (int i = 0; i<b; i++) {
        result *= a-i;
        divisor *= i+1;
    }
    return result/divisor;
}

int cCalc(const int A, const int B, const int C) {
    return calc(A, 3) + calc(B, 2) + calc(C, 1);
}

void DFS(const int A, const int B, const int C, const int target) {
    if (ok) return;
    const int result = cCalc(A, B, C);
    if (result > target) return;
    if (result == target) {
        cout << A << B << C << endl;
        ok = true;
        return;
    }
    if (A+1 > B && B > C) DFS(A+1, B, C, target);
    if (A > B+1 && B+1 > C) DFS(A, B+1, C, target);
    if (A > B && B > C+1) DFS(A, B, C+1, target);
    if (A+1 > B+1 && B+1 > C) DFS(A+1, B+1, C, target);
    if (A > B+1 && B+1 > C+1) DFS(A, B+1, C+1, target);
    if (A+1 > B && B > C+1) DFS(A+1, B, C+1, target);
    DFS(A+1, B+1, C+1, target);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int N;
        cin >> N;
        ok = false;
        DFS(2, 1, 0, N);
    }
}

//ZeroJudge A364
//Dr. SeanXD
標籤

相關文章

發佈留言