题目描述飞镖游戏中每支飞镖的得分可以是数字111到202020的普通、双倍或三倍区域即得分可为111到202020、2,4,…,402,4,\ldots,402,4,…,40、3,6,…,603,6,\ldots,603,6,…,60也可以是牛眼505050分或者脱靶000分。给定一个当前分数nnnn≤999n \le 999n≤999问用三支飞镖每支得分取自上述集合能否使总分恰好等于nnn。若可以需要分别计算不计顺序的组合数和计顺序的排列数。输入多个nnn以n≤0n \le 0n≤0结束。对于每个nnn输出结果并用一行707070个星号分隔不同分数的输出最后输出END OF OUTPUT。输入格式输入包含若干行每行一个整数nnnn≤999n \le 999n≤999表示当前分数。输入以n≤0n \le 0n≤0结束。输出格式对于每个正数nnn若存在三镖组合使其总分为nnn则输出NUMBER OF COMBINATIONS THAT SCORES n IS c. NUMBER OF PERMUTATIONS THAT SCORES n IS p.否则输出THE SCORE OF n CANNOT BE MADE WITH THREE DARTS.每种情况后都跟一行由707070个星号组成的分隔线。所有输出结束后单独输出一行END OF OUTPUT。样例输入162 175 2 68 211 114 -100样例输出NUMBER OF COMBINATIONS THAT SCORES 162 IS 7. NUMBER OF PERMUTATIONS THAT SCORES 162 IS 28. ********************************************************************** THE SCORE OF 175 CANNOT BE MADE WITH THREE DARTS. ********************************************************************** NUMBER OF COMBINATIONS THAT SCORES 2 IS 2. NUMBER OF PERMUTATIONS THAT SCORES 2 IS 6. ********************************************************************** NUMBER OF COMBINATIONS THAT SCORES 68 IS 187. NUMBER OF PERMUTATIONS THAT SCORES 68 IS 1056. ********************************************************************** NUMBER OF COMBINATIONS THAT SCORES 68 IS 187. NUMBER OF PERMUTATIONS THAT SCORES 68 IS 1056. ********************************************************************** NUMBER OF COMBINATIONS THAT SCORES 68 IS 187. NUMBER OF PERMUTATIONS THAT SCORES 68 IS 1056. ********************************************************************** THE SCORE OF 211 CANNOT BE MADE WITH THREE DARTS. ********************************************************************** NUMBER OF COMBINATIONS THAT SCORES 114 IS 82. NUMBER OF PERMUTATIONS THAT SCORES 114 IS 445. ********************************************************************** NUMBER OF COMBINATIONS THAT SCORES 114 IS 82. NUMBER OF PERMUTATIONS THAT SCORES 114 IS 445. ********************************************************************** END OF OUTPUT题目分析每支飞镖可能的得分共有626262种包括111到202020的普通分、双倍分、三倍分牛眼505050分以及000分。三镖的总分最大为3×601803 \times 60 1803×60180因此若n180n 180n180则必然无解。对于n≤180n \le 180n≤180可以枚举三镖的所有可能得分组合允许重复统计总和等于nnn的情况。因为每支飞镖得分集合大小仅为626262三重循环62323832862^3 238328623238328在nnn的测试次数不多时完全可行。统计时需区分组合数不考虑顺序和排列数考虑顺序。组合计数方法枚举三个下标i,j,ki, j, ki,j,k若对应得分之和等于nnn则根据三者的相等关系增加计数若三个值互不相同ijki j kijk则这一组无序组合对应666种排列组合数加111排列数加666。若恰有两个值相同如ijki j kijk或ijki j kijk则无序组合对应333种排列组合数加111排列数加333。若三个值全相等则无序组合对应111种排列组合数加111排列数加111。由于枚举顺序覆盖所有有序三元组上述计数方式恰好能正确统计。解题思路预先生成所有可能的单镖得分序列scores\textit{scores}scores包含0,1,…,20,2,4,…,40,3,6,…,60,500, 1,\ldots,20, 2,4,\ldots,40, 3,6,\ldots,60, 500,1,…,20,2,4,…,40,3,6,…,60,50。去重并排序。对每个查询nnn若n180n 180n180或n0n 0n0直接判定无解否则进行三重循环枚举。在循环内部根据三个索引的相等关系分别累加组合数和排列数。若累加后组合数为000则输出无法达到的消息否则输出组合数和排列数。每个结果后输出由707070个星号组成的分隔线。最后输出END OF OUTPUT。该算法预处理O(62log⁡62)O(62 \log 62)O(62log62)每组查询O(623)O(62^3)O(623)对于少量查询输入文件长度未知但通常不多足够高效。代码实现// Dart-a-Mania// UVa ID: 735// Verdict: Accepted// Submission Date: 2017-10-27// UVa Run Time: 0.320s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,sequence[62];for(inti1;i20;i)sequence[i-1]i,sequence[i19]2*i,sequence[39i]3*i;sequence[60]50,sequence[61]0;sort(sequence,sequence62);inttunique(sequence,sequence62)-sequence;while(cinn,n0){intc0,p0;if(n180){for(inti0;it;i)for(intj0;jt;j)for(intk0;kt;k)if(sequence[i]sequence[j]sequence[k]n){if(ijjk)p6,c;elseif(ijjk||ijjk)p3,c;elseif(ijjk)p1,c;}}if(c0){coutTHE SCORE OF n CANNOT BE MADE WITH THREE DARTS.\n;cout**********************************************************************\n;}else{coutNUMBER OF COMBINATIONS THAT SCORES n IS c.\n;coutNUMBER OF PERMUTATIONS THAT SCORES n IS p.\n;cout**********************************************************************\n;}}coutEND OF OUTPUT\n;return0;}总结本题利用枚举法直接求解因为单镖得分种类有限三重循环在可接受范围内。关键在于正确区分组合与排列通过三个索引的关系累加相应数量。注意n180n 180n180时无需枚举可直接判定无解。输出格式要求严格每个结果后跟星号线最后一行固定。该解法实现简单运行时间短是暴力枚举的典型应用。