Já que trabalharemos apenas com quantidades primas de números, vamos computar previamente todos os primos até 
(Limite da questão) utilizando um crivo de Erastóstenes. Então, com todos os primos já computados podemos reduzir o problema ao problema da mochila.
Portanto, basta testar, utilizando programação dinâmica colocar quantidades primas de cada objeto e, após comprar todos os objetos, checar se gasto uma quantidade prima de dinheiro. Código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 1e4 + 10; | |
| bool primo[maxn]; | |
| int n, m, dp[maxn][110]; | |
| vector<int> v, p; | |
| void crivo() // Crivo de Erastótenes para computar todos os primos ate 10^4 | |
| { | |
| memset(primo, 1, sizeof(primo)); | |
| primo[1] = 0; | |
| primo[0] = 0; | |
| for(int i = 2; i <= 100; i++) | |
| for(int j = i * i; j * j < maxn; j += i) | |
| primo[j] = 0; | |
| for(int i = 2; i <= n; i++) | |
| if(primo[i]) p.push_back(i); // lista com todos os primos | |
| } | |
| bool solve(int dinheiro, int obj) | |
| { | |
| if(dinheiro > n) return 0; // se o dinheiro gasto é maior que o dinheiro total, então é impossível | |
| if(obj == m) // já comprei todos os objetos; | |
| { | |
| if(primo[dinheiro]) return true; // caso a quantidade gasta seja prima | |
| else return false; // caso contrário | |
| } | |
| if(dp[dinheiro][obj] != -1) return dp[dinheiro][obj]; | |
| for(auto i : p) // percorro todos os primos e tento comprar uma quantidade prima do objeto atual | |
| { | |
| if(i > v[obj]) break; | |
| if(solve(dinheiro + i*v[obj], obj + 1)) return dp[dinheiro + i*v[obj]][obj + 1] = 1; | |
| // se eu consigo comprar todos os objetos e gastar uma quantidade | |
| } | |
| return dp[dinheiro][obj] = 0; // caso não seja possível comprar todos e gastar uma quantidade prima | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false), cin.tie(nullptr); // otimização de entrada | |
| memset(dp, -1, sizeof(dp)); | |
| cin >> n >> m; | |
| for(int i = 0; i < m; i++) | |
| { | |
| int a; | |
| cin >> a; | |
| v.push_back(a); | |
| } | |
| crivo(); | |
| if(solve(0,0)) cout << "festa dos primos\n"; | |
| else cout << "não é a festa dos primos\n"; | |
| return 0; | |
| } |