ZeroJudge A364: Special Carry Problem

在一個神秘的國家，他們有不同的文明，他們所使用的數字表示法跟常見的 十進位法不一樣。對於一個十進位的數字 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。為幫助了解這個神秘國度的文化， 請寫一程式來將十進位數轉換成這個神秘的進位法。

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains an integer m (1 ≤ m ≤ 10), representing the number of decimal numbers to convert. The following m lines (from the 2nd line to the (m+1)th line) each contain an integer between 0 and 500, representing the decimal numbers to be converted.For each decimal number, output the corresponding abc representation on a separate line without any spaces. Note that a, b, and c may consist of more than one digit. If there are multiple valid representations, output the lexicographically smallest representation, which means choosing the smallest possible values for a and b.
4
0
1
2
200		210
310
320
1187
3
18
19
20		542
543
610
ZeroJudge A364 Sample Test Cases

Thought Process

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

Sample Code－ZeroJudge A364: Special Carry Problem

#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
Tags

Related Posts

Comments