#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int n, k;
int a[N];
int res;
bool is_prime(int x){
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
void dfs(int u, int cnt, int sum){
if (cnt + n - u + 1 < k) return;
if (cnt == k){
if (is_prime(sum)) res ++ ;
return;
}
dfs(u + 1, cnt + 1, sum + a[u]);
dfs(u + 1, cnt, sum);
}
int main(){
cin >> n >> k;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
dfs(1, 0, 0);
cout << res << endl;
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1100;
int cnt;
int primes[N];
map<int,int> ver;
int g[N][N];
int dist[N];
bool st[N];
bool is_prime(int x){
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
bool get(int a, int b){
int p = primes[a], q = primes[b];
int cnt = 0;
while (p){
int x = p % 10;
int y = q % 10;
if (x != y) cnt ++ ;
p /= 10;
q /= 10;
}
if (cnt == 1) return true;
return false;
}
void dijkstra(int a, int b){
a = ver[a], b = ver[b];
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
dist[a] = 0;
for (int i = 0; i < cnt; i ++ ){
int t = -1;
for (int j = 0; j < cnt; j ++ )
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
for (int j = 0; j < cnt; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if (dist[b] == 0x3f3f3f3f) puts("Impossible");
else cout << dist[b] << endl;
}
int main(){
for (int i = 1000; i <= 9999; i ++ )
if (is_prime(i))
primes[cnt ++ ] = i, ver[i] = cnt-1;
memset(g, 0x3f, sizeof g);
for (int i = 1; i < cnt; i ++ )
for (int j = 0; j < i; j ++ )
if (get(i, j))
g[i][j] = g[j][i] = 1;
int T;
cin >> T;
while (T -- ){
int a, b;
cin >> a >> b;
dijkstra(a, b);
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int g[N][N];
bool col[N], dg[N<<1], udg[N<<1];
int res;
void dfs(int u, int sum){
if (u == 8){
res = max(res, sum);
return;
}
for (int i = 0; i < 8; i ++ )
if (!col[i] && !dg[i-u+8] && !udg[i+u]){
col[i] = dg[i-u+8] = udg[i+u] = true;
dfs(u+1, sum + g[u][i]);
col[i] = dg[i-u+8] = udg[i+u] = false;
}
}
int main(){
int T;
cin >> T;
while (T -- ){
for (int i = 0; i < 8; i ++ )
for (int j = 0; j < 8; j ++ )
cin >> g[i][j];
res = 0;
dfs(0, 0);
cout << res << endl;
}
return 0;
}