{"id":1264,"date":"2024-11-16T09:00:00","date_gmt":"2024-11-16T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=1264"},"modified":"2024-10-19T12:35:14","modified_gmt":"2024-10-19T04:35:14","slug":"zerojudge-a364","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-a364\/","title":{"rendered":"ZeroJudge A364: Special Carry Problem"},"content":{"rendered":"

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.<\/p>\n\n\n\n

Sample Inputs\/Outputs<\/h2>\n\n\n\n
Sample Input(s)<\/th>Sample Output(s)<\/th><\/tr><\/thead>
The first line contains an integer m (1 \u2264 m \u2264 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.<\/td>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.<\/td><\/tr>
4
0
1
2
200<\/td>		210
310
320
1187<\/td><\/tr>
3
18
19
20<\/td>		542
543
610<\/td><\/tr><\/tbody><\/table>
ZeroJudge A364 Sample Test Cases<\/figcaption><\/figure>\n\n\n\n

Thought Process<\/h2>\n\n\n\n

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.<\/p>\n\n\n\n

Sample Code\uff0dZeroJudge A364: Special Carry Problem<\/a><\/h3>\n\n\n\n
#include <iostream>\nusing namespace std;\n\nbool ok = false;\n\nint calc (const int a, const int b) {\n    if (a < b) return 0;\n    int result = 1, divisor = 1;;\n    for (int i = 0; i<b; i++) {\n        result *= a-i;\n        divisor *= i+1;\n    }\n    return result\/divisor;\n}\n\nint cCalc(const int A, const int B, const int C) {\n    return calc(A, 3) + calc(B, 2) + calc(C, 1);\n}\n\nvoid DFS(const int A, const int B, const int C, const int target) {\n    if (ok) return;\n    const int result = cCalc(A, B, C);\n    if (result > target) return;\n    if (result == target) {\n        cout << A << B << C << endl;\n        ok = true;\n        return;\n    }\n    if (A+1 > B && B > C) DFS(A+1, B, C, target);\n    if (A > B+1 && B+1 > C) DFS(A, B+1, C, target);\n    if (A > B && B > C+1) DFS(A, B, C+1, target);\n    if (A+1 > B+1 && B+1 > C) DFS(A+1, B+1, C, target);\n    if (A > B+1 && B+1 > C+1) DFS(A, B+1, C+1, target);\n    if (A+1 > B && B > C+1) DFS(A+1, B, C+1, target);\n    DFS(A+1, B+1, C+1, target);\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    int M;\n    cin >> M;\n    for (int i = 0; i < M; i++) {\n        int N;\n        cin >> N;\n        ok = false;\n        DFS(2, 1, 0, N);\n    }\n}\n\n\/\/ZeroJudge A364\n\/\/Dr. SeanXD<\/code><\/pre><\/div>","protected":false},"excerpt":{"rendered":"
\u5728\u4e00\u500b\u795e\u79d8\u7684\u570b\u5bb6\uff0c\u4ed6\u5011\u6709\u4e0d\u540c\u7684\u6587\u660e\uff0c\u4ed6\u5011\u6240\u4f7f\u7528\u7684\u6578\u5b57\u8868\u793a\u6cd5\u8ddf\u5e38\u898b\u7684 \u5341\u9032\u4f4d\u6cd5\u4e0d\u4e00\u6a23\u3002\u5c0d\u65bc\u4e00\u500b\u5341\u9032\u4f4d\u7684\u6578\u5b57 N\uff0c […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[29],"tags":[21,8,34,13,9],"class_list":["post-1264","post","type-post","status-publish","format-standard","hentry","category-zerojudge-","tag-dfs","tag-8","tag-34","tag-13","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1264","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/comments?post=1264"}],"version-history":[{"count":3,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1264\/revisions"}],"predecessor-version":[{"id":1267,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1264\/revisions\/1267"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=1264"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=1264"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=1264"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}