```
// P1036 [NOIP 2002 普及组] 选数
// 已知 n 个整数 x  1 ​  ,x  2 ​  ,⋯,x  n ​  ，以及 1 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k=3，4 个整数分别为 3,7,12,19 时，可得全部的组合与它们的和为
#include <bits/stdc++.h>

inline bool isprime(int x) { // 判断一个数是否是素数
if (x == 1) return false; // 注意这步特判是必需的
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}

const int N = 25;
int a[N], ans, n, k;

void dfs(int now, int sum, int sid) {
// 现在已经选了 now 个数，当前总和为 sum
// sid 是这次选数的起始下标，即我们从 a[sid] 开始选数枚举
if (now == k) {
if (isprime(sum))
++ans;
return ;
}
for (int i = sid; i <= n - k + now + 1; ++i)
dfs(now + 1, sum + a[i], i + 1);
return ;
}

int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
dfs(0, 0, 1);
printf("%d\n", ans);
return 0;
}

// P1706 全排列问题
// 按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
#include <bits/stdc++.h>

inline bool isprime(int x) { 
if (x == 1) return false; // 注意这步特判是必需的
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}

const int N = 25;
int a[N], ans, n, k;

void dfs(int now, int sum, int sid) {
// 现在已经选了 now 个数，当前总和为 sum
// sid 是这次选数的起始下标，即我们从 a[sid] 开始选数枚举
if (now == k) {
if (isprime(sum))
++ans;
return ;
}
for (int i = sid; i <= n - k + now + 1; ++i)
dfs(now + 1, sum + a[i], i + 1);
return ;
}

int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
dfs(0, 0, 1);
printf("%d\n", ans);
return 0;
}

// 混合牛奶，由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。
#include<algorithm>
#include<iostream>
using namespace std;
struct farm {
int price;
int count;
}a[5005];
bool compare(const farm& a, const farm& b) {
return a.price < b.price;
}
long long n, m;
int main()
{
cin >> n >> m;
long long res = 0;
for (int i = 1; i <= m; i++) cin >> a[i].price>> a[i].count;
sort(a + 1, a + 1 + m, compare);
for (int i = 1; i <= m; i++) {
if (n >= a[i].count) {
res += a[i].price * a[i].count;
n =n-a[i].count;
}
else {
res += a[i].price * n;
break;
}
}
cout << res;

return 0;
}

// 田忌赛马
#include <bits/stdc++.h>
using namespace std;

const int maxn=2005;
int t[maxn],q[maxn];
int money,tlow,qlow,thigh,qhigh;

int main() {
int n;
cin>>n;
for(int i=0; i<n; i++) cin>>t[i];
for(int i=0; i<n; i++) cin>>q[i];
sort(t,t+n);
sort(q,q+n);

tlow=qlow=0;
thigh=qhigh=n-1;

while(tlow<=thigh) {
if(t[thigh]>q[qhigh]) {
money+=200;
thigh--;
qhigh--;
} else if(t[thigh]<q[qhigh]) {
money-=200;
tlow++;
qhigh--;
} else {
if(t[tlow]>q[qlow]) {
money+=200;
tlow++;
qlow++;
} else {
if(t[tlow]<q[qhigh]) money-=200;
tlow++;
qhigh--;
}
}
}
cout<<money<<endl;

return 0;
}