ZeroJudge A364: Special Carry Problem

In a mysterious country, they have a different civilization, and the way they represent numbers is unlike the common decimal system. For a decimal number N, they express it as abc, where a > b > c >= 0, and it satisfies N = C(a, 3) + C(b, 2) + C(c, 1), where C is a binomial coefficient, i.e., C(m, n) = (m!)/[n! (m-n)!]. However, when m < n , C(m, n) = 0 . To help understand the culture of this mysterious country, please write a program that converts a decimal number into this mysterious numeral system.

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

You can use Depth-First Search (DFS) to explore all possible combinations, including increasing just one number, two numbers, or all three. However, you need to ensure that a > b > c. To start the DFS, initialize the values with a = 2, b = 1, and 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