NOIP C++1008選択数
1856 ワード
タイトルの説明
Description
n個の整数x 1,x 2,...,xn,および1個の整数k(k説明の入力
Input Description
キーボード入力、フォーマット:n,k(1<=n<=20,k出力の説明
Output Description
画面出力、フォーマットは:整数(条件を満たす種数)です.
サンプル入力
Sample Input
4 3 3 7 12 19
サンプル出力Sample Output
1
実行結果
考え方:この問題は明らかに遡及している.まず、すべての配列の可能性を挙げますが、「3+7+12」と「3+12+7」は同じであることが考えられます.だから、最初の数を選ぶたびに、この数の後ろのものを選ばないで、繰り返さないようにすることができます.
コードは次のとおりです.
Description
n個の整数x 1,x 2,...,xn,および1個の整数k(k
Input Description
キーボード入力、フォーマット:n,k(1<=n<=20,k
Output Description
画面出力、フォーマットは:整数(条件を満たす種数)です.
サンプル入力
Sample Input
4 3 3 7 12 19
サンプル出力Sample Output
1
実行結果
#xs1.in :AC : 256kB : 1ms
#xs2.in :AC : 256kB : 0ms
#xs3.in :AC : 256kB : 0ms
#xs4.in :AC : 256kB : 1ms
#xs5.in :AC : 256kB : 20ms 考え方:この問題は明らかに遡及している.まず、すべての配列の可能性を挙げますが、「3+7+12」と「3+12+7」は同じであることが考えられます.だから、最初の数を選ぶたびに、この数の後ろのものを選ばないで、繰り返さないようにすることができます.
コードは次のとおりです.
# include
# include
using namespace std;
int n, k, kase = 0;
bool vis[25];
long long sum = 0, s[25];
bool prime(long long s) {
for(long long i = 2; i <= sqrt(s); i++)
if(s % i == 0) return 0;
return 1;
}
void search(int x, int y) { // ，y 。
for(int i = y; i <= n; i++) {
if(!vis[i]) {
sum += s[i]; vis[i] = 1;
if(x == k && prime(sum)) kase++;
else search(x + 1, i);
sum -= s[i]; vis[i] = 0;
}
}
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> s[i];
search(1, 1);
cout << kase;
return 0;
}