首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7464

硬币(2024.3四级) 宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个:…

硬币(2024.3四级)

宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个: 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物, 想买来送给朋友 Alice, 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的, 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零, 只接受恰好 X 元。

时间限制: 1000

内存限制: 262144

输入

第一行包含两个正整数 n 和 x。 (1 <= n <= 200, 1 <= x <= 10000) 

第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 <= ai <= 10000)

输出

第一行是一个整数, 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值(从小到大排列) 。


样例输入

5 18
1 2 3 5 10

样例输出

2
5 10


提示

输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币, 则第一行输出 0, 第二行输出空行。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; int val[210] = {0}; int ways[10000] = {0}; int ans[210] = {0}; int cal(int x, int y) {   if (x &lt; 0)     return 0;   return ways[x] - cal(x - y, y); } int main() {   int N, Max;   cin &gt;&gt; N &gt;&gt; Max;   for (int i = 1; i &lt;= N; ++i)     cin &gt;&gt; val[i];   ways[0] = 1;   for (int i = 1; i &lt;= N; ++i)     for (int j = Max; j &gt;= val[i]; --j)       ways[j] += ways[j - val[i]];   int cnt = 0;   for (int i = 1; i &lt;= N; ++i)     if (cal(Max, val[i]) == 0)       ans[cnt++] = val[i];   cout &lt;&lt; cnt &lt;&lt; endl;   if (cnt == 0)     cout &lt;&lt; ' ' &lt;&lt; endl;   else {     cout &lt;&lt; ans[0];     for (int i = 1; i &lt; cnt; ++i)       cout &lt;&lt; ' ' &lt;&lt; ans[i];   }   return 0; }</pre><p><br/></p>
这道题暂未补解析。