#include <iostream>
using namespace std;
const int MAX = 1e5 + 1;
const int INF = 1e7 + 1;
int m, q;
int p[MAX];
int dp[INF];
int comp[INF];
int getMin(int x){
if (x == 0) return 0;
if (dp[x] == 0){
dp[x] = INF;
for (int i = 0; i < m; i++) {
if (x % p[i] != 0) dp[x] = min(dp[x], 1 + getMin((x / p[i]) * p[i]));
}
}
return dp[x];
}
void solve(){
int n;
cin >> n;
int ans = getMin(n);
if (ans == INF) cout << "oo\n";
else cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> q;
for (int i = 0; i < m; i++){
cin >> p[i];
}
for (int i = 0; i < q; i++){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
5 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
856 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
44 ms |
604 KB |
Output is correct |
| 14 |
Correct |
43 ms |
348 KB |
Output is correct |
| 15 |
Correct |
2 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
4 ms |
348 KB |
Output is correct |
| 18 |
Correct |
5 ms |
536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
43348 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1038 ms |
56144 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1028 ms |
143040 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1057 ms |
67672 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1020 ms |
48720 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1070 ms |
25692 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1052 ms |
43368 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1047 ms |
27480 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1063 ms |
38740 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1028 ms |
143108 KB |
Time limit exceeded |
| 11 |
Runtime error |
204 ms |
262144 KB |
Execution killed with signal 9 |
| 12 |
Execution timed out |
1016 ms |
109560 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1053 ms |
72532 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1058 ms |
67668 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1035 ms |
77648 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1071 ms |
56304 KB |
Time limit exceeded |
| 17 |
Runtime error |
204 ms |
262144 KB |
Execution killed with signal 9 |
| 18 |
Execution timed out |
1036 ms |
213244 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
203 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Execution timed out |
1049 ms |
16220 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1070 ms |
212008 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1042 ms |
143952 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1040 ms |
36532 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1053 ms |
206676 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1054 ms |
64080 KB |
Time limit exceeded |
| 8 |
Runtime error |
199 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
202 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Execution timed out |
1037 ms |
11864 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1027 ms |
76368 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1044 ms |
158848 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1034 ms |
107856 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1052 ms |
179540 KB |
Time limit exceeded |
| 15 |
Runtime error |
199 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Execution timed out |
1071 ms |
170260 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1044 ms |
25164 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1028 ms |
16240 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1058 ms |
43860 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1047 ms |
211980 KB |
Time limit exceeded |
| 21 |
Runtime error |
200 ms |
262144 KB |
Execution killed with signal 9 |
| 22 |
Execution timed out |
1094 ms |
215704 KB |
Time limit exceeded |
| 23 |
Execution timed out |
1038 ms |
40324 KB |
Time limit exceeded |
| 24 |
Execution timed out |
1061 ms |
30300 KB |
Time limit exceeded |
| 25 |
Execution timed out |
1057 ms |
8540 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1078 ms |
143896 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1055 ms |
212564 KB |
Time limit exceeded |
| 28 |
Execution timed out |
1045 ms |
87632 KB |
Time limit exceeded |
| 29 |
Execution timed out |
1079 ms |
91548 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1063 ms |
66716 KB |
Time limit exceeded |
| 31 |
Execution timed out |
1072 ms |
61012 KB |
Time limit exceeded |
| 32 |
Execution timed out |
1054 ms |
71404 KB |
Time limit exceeded |
| 33 |
Execution timed out |
1018 ms |
44632 KB |
Time limit exceeded |
| 34 |
Execution timed out |
1041 ms |
64080 KB |
Time limit exceeded |
| 35 |
Execution timed out |
1085 ms |
54360 KB |
Time limit exceeded |
| 36 |
Execution timed out |
1037 ms |
36432 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1064 ms |
36444 KB |
Time limit exceeded |
| 38 |
Execution timed out |
1065 ms |
206676 KB |
Time limit exceeded |
| 39 |
Execution timed out |
1043 ms |
44124 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1056 ms |
80364 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1069 ms |
82728 KB |
Time limit exceeded |
| 42 |
Runtime error |
197 ms |
262144 KB |
Execution killed with signal 9 |
