| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 727051 |
2023-04-20T01:27:53 Z |
josanneo22 |
Bowling (BOI15_bow) |
C++17 |
|
12 ms |
388 KB |
/* Baltic Olympiad in Informatics 2015
* Problem: BOW/Bowling
* Almost model solution (without long longs, passes only first three subtasks)
* Author: Karol Pokorski
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10;
const int MAXSEQ = 21;
const int maxFrameScore[11] = {0, 10, 30, 60, 90, 120, 150, 180, 210, 240, 300};
const int MAXSCORE = 300;
int seqScore[MAXN], dp[MAXN][MAXSCORE+1][3][2];
char seqMoves[MAXSEQ+1];
int main() {
int numQueries;
scanf("%d", &numQueries);
while (numQueries--) {
int numFrames;
scanf("%d", &numFrames);
scanf("%s", seqMoves);
for (int i = 0; i < numFrames; i++)
scanf("%d", &seqScore[i]);
for (int frame = 0; frame < numFrames; frame++)
for (int score = 0; score <= MAXSCORE; score++)
for (int bonus1 = 0; bonus1 <= 2; bonus1++)
for (int bonus2 = 0; bonus2 <= 1; bonus2++)
dp[frame][score][bonus1][bonus2] = 0;
dp[0][0][0][0] = 1;
// first n-1 frames
for (int frame = 0; frame < numFrames-1; frame++) {
char firstMove = seqMoves[2*frame], secondMove = seqMoves[2*frame+1];
int prev0Score = seqScore[frame];
int prev1Score = (frame > 0) ? seqScore[frame-1] : -1;
int prev2Score = (frame > 1) ? seqScore[frame-2] : -1;
for (int score = 0; score <= maxFrameScore[frame]; score++)
for (int bonus1 = 0; bonus1 <= 2; bonus1++)
for (int bonus2 = 0; bonus2 <= 1; bonus2++) {
if (dp[frame][score][bonus1][bonus2] == 0) continue;
for (int move1 = 0; move1 <= 10; move1++) {
if ((firstMove >= '0') && (firstMove <= '9') && (move1 != firstMove-'0')) continue;
if ((firstMove == 'x') && (move1 != 10)) continue;
if ((secondMove == '/') && (move1 == 10)) continue;
for (int move2 = 0; move1+move2 <= 10; move2++) {
if ((secondMove >= '0') && (secondMove <= '9') && (move2 != secondMove-'0')) continue;
if ((secondMove == '/') && (move1+move2 != 10)) continue;
if ((secondMove == '-') && (move1 != 10)) continue;
if ((move1+move2 == 10) && (secondMove >= '0') && (secondMove <= '9')) continue;
int prev1Bonus = 0, prev2Bonus = 0;
if (bonus2 == 1) prev1Bonus = move1;
if (bonus1 == 1) prev2Bonus = move1;
if (bonus1 == 2) prev2Bonus = move1+move2;
int nowScore = score + prev1Bonus + prev2Bonus + (move1+move2);
int nowPrev1Score = nowScore - (move1+move2);
int newBonus1, newBonus2;
if (move1 == 10) { newBonus1 = 2; newBonus2 = max(bonus1-1, 0); }
else if (move1 + move2 == 10) { newBonus1 = 1; newBonus2 = 0; }
else { newBonus1 = 0; newBonus2 = 0; }
if (bonus2 == 1) {
int nowPrev2Score = nowPrev1Score - (move1+move2) - 10;
if ((prev2Score != -1) && (nowPrev2Score != prev2Score)) {
continue;
}
}
if ((bonus1 == 1) || ((bonus1 == 2) && (move1 != 10))) {
if ((prev1Score != -1) && (nowPrev1Score != prev1Score)) {
continue;
}
}
if (move1+move2 != 10) {
if ((prev0Score != -1) && (nowScore != prev0Score)) {
continue;
}
}
dp[frame+1][nowScore][newBonus1][newBonus2] += dp[frame][score][bonus1][bonus2];
}
}
}
}
// last frame
int result = 0;
char firstMove = seqMoves[2*(numFrames-1)], secondMove = seqMoves[2*(numFrames-1)+1], thirdMove = seqMoves[2*(numFrames-1)+2];
int prev0Score = seqScore[numFrames-1];
int prev1Score = (numFrames > 1) ? seqScore[numFrames-2] : -1;
int prev2Score = (numFrames > 2) ? seqScore[numFrames-3] : -1;
for (int score = 0; score <= MAXSCORE; score++)
for (int bonus1 = 0; bonus1 <= 2; bonus1++)
for (int bonus2 = 0; bonus2 <= 1; bonus2++) {
if (dp[numFrames-1][score][bonus1][bonus2] == 0) continue;
for (int move1 = 0; move1 <= 10; move1++) {
if ((firstMove >= '0') && (firstMove <= '9') && (move1 != firstMove-'0')) continue;
if ((firstMove == 'x') && (move1 != 10)) continue;
if ((secondMove == '/') && (move1 == 10)) continue;
for (int move2 = 0; move2 <= 10; move2++) {
if ((secondMove >= '0') && (secondMove <= '9') && (move2 != secondMove-'0')) continue;
if ((secondMove == 'x') && (move2 != 10)) continue;
if ((secondMove == '/') && (move1+move2 != 10)) continue;
if ((thirdMove == '/') && (move2 == 10)) continue;
if ((move1 != 10) && (move1+move2 > 10)) continue;
if ((move1+move2 == 10) && (move1 != 10) && (secondMove >= '0') && (secondMove <= '9')) continue;
//moje poprawki
if ((secondMove == 'x') && (move1 != 10)) continue;
//koniec moich poprawek
int move3Max = ((move1 == 10) || (move1+move2 == 10)) ? 10 : 0;
for (int move3 = 0; move3 <= move3Max; move3++) {
if ((thirdMove >= '0') && (thirdMove <= '9') && (move3 != thirdMove-'0')) continue;
if ((thirdMove == 'x') && (move3 != 10)) continue;
if ((thirdMove == '/') && (move2+move3 != 10)) continue;
if ((move2 != 10) && (move1+move2 != 10) && (move2+move3 > 10)) continue;
if ((thirdMove == '-') && (move1+move2 >= 10)) continue;
//usuwam, bo zle
//if ((move2+move3 == 10) && (thirdMove >= '0') && (thirdMove <= '9')) continue;
if ((thirdMove == '/') && (move1+move2 == 10) && (move1 != 10)) continue;
//moje poprawki
if (thirdMove == 'x') {
if(move2 != 10 && ((move1 == 10 && move2 == 0) || (move1 + move2 < 10))) {
continue;
}
}
if ((thirdMove == '0') && move1 + move2 < 10) continue;
if ((move1 == 10 || move1 + move2 != 10)&&(move2 != 10) &&(move2+move3 == 10) && (thirdMove >= '0') && (thirdMove <= '9')) continue;
//koniec moich poprawek
int prev1Bonus = 0, prev2Bonus = 0;
if (bonus2 == 1) prev1Bonus = move1;
if (bonus1 == 1) prev2Bonus = move1;
if (bonus1 == 2) prev2Bonus = move1+move2;
int nowScore = score + prev1Bonus + prev2Bonus + (move1+move2+move3);
int nowPrev1Score = nowScore - (move1+move2+move3);
if (bonus2 == 1) {
int nowPrev2Score = nowPrev1Score - (move1+move2) - 10;
if ((prev2Score != -1) && (nowPrev2Score != prev2Score)) {
continue;
}
}
if (bonus1 >= 1) {
if ((prev1Score != -1) && (nowPrev1Score != prev1Score)) {
continue;
}
}
{
if ((prev0Score != -1) && (nowScore != prev0Score))
continue;
}
result += dp[numFrames-1][score][bonus1][bonus2];
}
}
}
}
printf("%d\n", result);
}
return 0;
}
Compilation message
bow.cpp: In function 'int main()':
bow.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d", &numQueries);
| ~~~~~^~~~~~~~~~~~~~~~~~~
bow.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf("%d", &numFrames);
| ~~~~~^~~~~~~~~~~~~~~~~~
bow.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%s", seqMoves);
| ~~~~~^~~~~~~~~~~~~~~~
bow.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf("%d", &seqScore[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
288 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
284 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
2 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
288 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
352 KB |
Output is correct |
| 2 |
Correct |
3 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
296 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
288 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Correct |
3 ms |
340 KB |
Output is correct |
| 8 |
Correct |
3 ms |
340 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
8 ms |
360 KB |
Output is correct |
| 11 |
Correct |
8 ms |
340 KB |
Output is correct |
| 12 |
Correct |
7 ms |
340 KB |
Output is correct |
| 13 |
Correct |
10 ms |
388 KB |
Output is correct |
| 14 |
Correct |
4 ms |
288 KB |
Output is correct |
| 15 |
Correct |
3 ms |
292 KB |
Output is correct |
| 16 |
Correct |
4 ms |
340 KB |
Output is correct |
| 17 |
Correct |
3 ms |
340 KB |
Output is correct |
| 18 |
Correct |
9 ms |
340 KB |
Output is correct |
| 19 |
Correct |
10 ms |
340 KB |
Output is correct |
| 20 |
Correct |
12 ms |
356 KB |
Output is correct |
| 21 |
Correct |
11 ms |
356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
288 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
284 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
2 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
288 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
4 ms |
352 KB |
Output is correct |
| 17 |
Correct |
3 ms |
340 KB |
Output is correct |
| 18 |
Correct |
3 ms |
296 KB |
Output is correct |
| 19 |
Correct |
2 ms |
340 KB |
Output is correct |
| 20 |
Correct |
2 ms |
288 KB |
Output is correct |
| 21 |
Correct |
2 ms |
340 KB |
Output is correct |
| 22 |
Correct |
3 ms |
340 KB |
Output is correct |
| 23 |
Correct |
3 ms |
340 KB |
Output is correct |
| 24 |
Correct |
2 ms |
340 KB |
Output is correct |
| 25 |
Correct |
8 ms |
360 KB |
Output is correct |
| 26 |
Correct |
8 ms |
340 KB |
Output is correct |
| 27 |
Correct |
7 ms |
340 KB |
Output is correct |
| 28 |
Correct |
10 ms |
388 KB |
Output is correct |
| 29 |
Correct |
4 ms |
288 KB |
Output is correct |
| 30 |
Correct |
3 ms |
292 KB |
Output is correct |
| 31 |
Correct |
4 ms |
340 KB |
Output is correct |
| 32 |
Correct |
3 ms |
340 KB |
Output is correct |
| 33 |
Correct |
9 ms |
340 KB |
Output is correct |
| 34 |
Correct |
10 ms |
340 KB |
Output is correct |
| 35 |
Correct |
12 ms |
356 KB |
Output is correct |
| 36 |
Correct |
11 ms |
356 KB |
Output is correct |
| 37 |
Incorrect |
7 ms |
340 KB |
Output isn't correct |
| 38 |
Halted |
0 ms |
0 KB |
- |
