{"id":786,"date":"2024-07-20T09:00:00","date_gmt":"2024-07-20T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=786"},"modified":"2024-06-07T12:35:28","modified_gmt":"2024-06-07T04:35:28","slug":"itsa-202405-1","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/itsa-202405-1\/","title":{"rendered":"ITSA 202405 #1: Changing Coins"},"content":{"rendered":"\n\n\n<p>\u5c0f\u660e\u60f3\u8a2d\u8a08\u4e00\u63db\u5e63\u6a5f\uff0c\u53ef\u4ee5\u88dd\u5728\u8ca9\u8ce3\u6a5f\u88e1\u7528\u65bc\u627e\u96f6\u9322\u7528\uff0c\u9019\u53f0\u63db\u5e63\u6a5f<strong>\u53ef\u4ee5\u63db\u51fa\u300c50\u5143\u300110\u5143\u30015\u5143\u3001\u53ca1\u5143\u300d<\/strong>\u56db\u7a2e\u786c\u5e63\uff0c\u4f46\u56e0\u70ba\u8981\u8003\u616e\u8ca9\u8ce3\u6a5f\u5167\u7684\u786c\u5e63\u72c0\u6cc1\uff0c\u6240\u4ee5<strong>\u627e\u9322\u6642\u6703\u5148\u5c07\u63db\u5e63\u7684\u72c0\u6cc1\u90fd\u5148\u7b97\u51fa\u4f86\uff0c\u4ee5\u7b26\u5408\u6240\u6709\u72c0\u6cc1\u3002<\/strong><br>\u8acb\u60a8\u5beb\u4e00\u500b\u7a0b\u5f0f\uff0c\u8f38\u5165\u4e00\u500b\u91d1\u984d\uff0c\u8a72\u7a0b\u5f0f\u6703<strong>\u5217\u51fa\u5404\u7a2e\u53ef\u80fd\u7684\u63db\u5e63\u7d50\u679c<\/strong>\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>\u7bc4\u4f8b\u8f38\u5165<\/th><th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead><tbody><tr><td>\u8f38\u5165\u53ea\u6709 1 \u884c\uff0c\u70ba 1 \u500b\u6b63\u6574\u6578 N (1 \u2264 N \u2264 100\uff09\uff0c\u8868\u793a\u8981\u627e\u7684\u91d1\u984d\u6578\u3002<\/td><td>\u6bcf\u7a2e\u63db\u5e63\u7d50\u679c\u8acb\u8f38\u51fa4\u500b\u6b63\u6574\u6578\uff0c\u6b63\u6574\u6578\u9593\u7528\u7a7a\u767d\u9694\u958b\u3002<br>\u7b2c1\u500b\u6b63\u6574\u6578\u8868\u793a\u8981\u5e7e\u500b50\u5143\u786c\u5e63\u3002<br>\u7b2c2\u500b\u6b63\u6574\u6578\u8868\u793a\u8981\u5e7e\u500b 10\u5143\u786c\u5e63\u3002<br>\u7b2c3\u500b\u6b63\u6574\u6578\u8868\u793a\u8981\u5e7e\u500b5\u5143\u786c\u5e63\u3002<br>\u7b2c4\u500b\u6b63\u6574\u6578\u8868\u793a\u8981\u5e7e\u500b1\u5143\u786c\u5e63\u3002<br>\u8acb\u8f38\u51fa\u6240\u6709\u53ef\u80fd\u7684\u63db\u5e63\u7d50\u679c\uff0c<strong>\u8acb\u4f9d\u6700\u5927\u5e63\u503c\u5230\u6700\u5c0f\u5e63\u503c\u4e4b\u6578\u91cf\u5c0f\u5230\u5927\u9806\u5e8f\u8f38\u51fa<\/strong>\uff0c\u4f8b\u5982\u5148\u8f38\u51fa50\u5143\u786c\u5e630\u500b\u7684\u63db\u5e63\u7d50\u679c\uff0c\u5982\u6709\u76f8\u540c\u7684\u5247\u8003\u616e10\u5143\u786c\u5e63\u6578\uff0c\u63a5\u8457\u6bd4\u8f035\u5143\u30011\u5143\uff0c\u4ee5\u6b64\u985e\u63a8\u3002<br><strong>\u6bcf\u884c\u8f38\u51fa\u6700\u5f8c\u5fc5\u6709\u63db\u884c\u7b26\u865f\u3002<\/strong><\/td><\/tr><tr><td>11<\/td><td>0 0 0 11<br>0 0 1 6<br>0 0 2 1<br>0 1 0 1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n<p>\u4f7f\u7528\u905e\u8ff4\u7684\u65b9\u5f0f\u4f86\u5c07\u6240\u6709\u53ef\u80fd\u8a08\u7b97\u51fa\u4f86\uff0c\u5ba3\u544a\u4e00\u500b void DFS\uff0c\u53c3\u6578\u9700\u8981\u4e00\u500b Vector&lt;int> coin \u4ee3\u8868 4 \u7a2e\u786c\u5e63\u7684\u6578\u91cf\u3001int value \u4ee3\u8868\u76ee\u524d\u9084\u5dee\u591a\u5c11\u584a\u9322\u3001int types \u4ee3\u8868\u76ee\u524d\u9019\u500b\u905e\u8ff4\u8981\u52a0\u7684\u786c\u5e63\u7a2e\u985e\u3002\u7136\u5f8c\u53ef\u4ee5\u5ba3\u544a\u4e00\u500b\u5168\u57df\u9663\u5217 int type[4] = {50, 10, 5, 1}\u3002<\/p>\n\n\n\n<p>\u5728\u905e\u8ff4\u4e2d\uff0c\u5982\u679c value == 0\uff0c\u5c31\u4ee3\u8868\u5df2\u7d93\u52a0\u5230 N \u4e86\uff0c\u5c31\u53ef\u4ee5\u628a coin \u4e2d\u7684\u8cc7\u6599\u9032\u884c\u8f38\u51fa\uff0c\u9700\u8981\u6ce8\u610f\u7684\u662f\u6700\u5f8c\u4e00\u500b\u8cc7\u6599\u5f8c\u9762\u4e0d\u80fd\u6709\u7a7a\u683c\u5b57\u5143\u3002\u53e6\u5916\uff0c\u5982\u679c types == 4 \u4e14 value != 0\uff0c\u4ee3\u8868\u5df2\u7d93\u628a\u6240\u6709\u7684\u786c\u5e63\u90fd\u52a0\u904e\u4e86\u4f46\u662f\u6c92\u6709\u8fa6\u6cd5\u52a0\u5230 N\uff0c\u5c31\u76f4\u63a5 return\u3002<\/p>\n\n\n\n<p>\u5728\u905e\u8ff4\u4e2d\u8dd1\u4e00\u500b For\u8ff4\u5708\uff0c\u5f9e 0 \u8dd1\u5230 value\/type[types]\uff0c\u4ee3\u8868\u5269\u4e0b\u9700\u8981\u52a0\u7684\u9322\u53ef\u4ee5\u4f7f\u7528\u591a\u5c11\u500b\u76ee\u524d types \u7684\u786c\u5e63\u3002\u8209\u4f8b\u4f86\u8aaa\uff0c\u5982\u679c value \u662f 11\uff0c\u7136\u5f8c type[types] \u662f 1\uff0c\u4ee3\u8868\u53ef\u4ee5\u4f7f\u7528 0 \u5230 11 \u500b 1 \u5143\u786c\u5e63\u3002\u5c07 coin[types] \u8a2d\u5b9a\u70ba i\uff0c\u4ee3\u8868\u76ee\u524d\u786c\u5e63\u7a2e\u985e\u4f7f\u7528\u7684\u6578\u91cf\uff0c\u4e26\u4e14\u547c\u53eb DFS\uff0c\u53c3\u6578\u8981\u4f7f\u7528 coin\u3001\u5269\u4e0b\u7684\u9322 &#8211; \u76ee\u524d\u4f7f\u7528\u7684\u786c\u5e63*i\u3001types+1\uff0c\u4ee3\u8868\u8981\u5c07\u53bb\u5224\u65b7\u4e0b\u4e00\u7a2e\u786c\u5e63\u53ef\u4ee5\u4f7f\u7528\u591a\u5c11\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0d<a href=\"https:\/\/e-tutor.itsa.org.tw\/mod\/programming\/view.php?a=43165\" target=\"_blank\" rel=\"noreferrer noopener\">ITSA 202405 #1\uff1a\u63db\u5e63\u6a5f<\/a><\/h3>\n\n\n\n<div class=\"hcb_wrap\"><pre class=\"prism line-numbers lang-cpp\" data-lang=\"C++\"><code>#include &lt;iostream&gt;\n#include &lt;vector&gt;\nusing namespace std;\n\nint N;\nconst int type[4] = {50, 10, 5, 1};\n\nvoid DFS(vector&lt;int&gt;coin, const int value , const int types) {\n    if (value == 0) {\n        for (int i = 0; i&lt;4; i++) {\n            cout &lt;&lt; coin[i];\n            if (i != 3) cout &lt;&lt; &quot; &quot;;\n        }\n        cout &lt;&lt; &quot;\\n&quot;;\n        return;\n    }\n    if(types == 4) return;\n    for (int i = 0; i&lt;=value\/type[types]; i++) {\n        coin[types] = i;\n        DFS(coin, value - type[types]*i, types+1);\n    }\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    cout.sync_with_stdio(0);\n    cout.tie(0);\n    cin &gt;&gt; N;\n    vector&lt;int&gt;tmp;\n    for (int i = 0; i&lt;4; i++) tmp.push_back(0);\n    DFS(tmp, N , 0);\n}\n\n\/\/ITSA 202405 #1\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u5c0f\u660e\u60f3\u8a2d\u8a08\u4e00\u63db\u5e63\u6a5f\uff0c\u53ef\u4ee5\u88dd\u5728\u8ca9\u8ce3\u6a5f\u88e1\u7528\u65bc\u627e\u96f6\u9322\u7528\uff0c\u9019\u53f0\u63db\u5e63\u6a5f\u53ef\u4ee5\u63db\u51fa\u300c50\u5143\u300110\u5143\u30015\u5143\u3001\u53ca1\u5143\u300d\u56db\u7a2e\u786c\u5e63\uff0c [&hellip;]<\/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":[36],"tags":[21,20,8,9],"class_list":["post-786","post","type-post","status-publish","format-standard","hentry","category-itsa","tag-dfs","tag-20","tag-8","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/786","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=786"}],"version-history":[{"count":1,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/786\/revisions"}],"predecessor-version":[{"id":787,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/786\/revisions\/787"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=786"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=786"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=786"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}