Kuglice
레이팅 미적용의견: 0
Christmas time is approaching, the most beautiful time of the year. Our protag-
onists, Marin and Josip, have returned from Christmas shopping and have started
decorating their Christmas tree.
They bought \(n\) Christmas ornaments arranged next to each other in an elongated
box, and the \(i-th\) ornament has the color \(a\)\(i\). The box is open on both sides, so
the ornaments can be taken out from both the left and the right side of the box.
The box is transparent, so Marin and Josip can see the color of each ornament.
The illustration shows the initial state \(of\) the box \(in\) the second example. \(On\) his first move, Marin can
draw either \(an\) ornament \(of\) color 1 from the left end \(of\) the box \(or\) \(an\) ornament \(of\) color 3 from the right
end \(of\) the box.
Josip came up with a game that would make decorating the tree even more fun, although it’s already a
lot of fun by itself. The game works as follows: Marin and Josip take turns, and Marin starts the game.
The player in turn draws an ornament from the box (either from the left or the right end of the box) and
places it on the tree. If they draw an ornament whose color has not been drawn yet, the player scores a
point. The game ends when the last ornament is drawn from the box.
The winner of the game is the player who has scored more points, so both Marin and Josip want to
maximize their number of points. Since both of them are excellent players, they will play optimally. Your
task is to print the result at the end of the game.
Subtask 1 (17 points): \(a_{i} \le 2\) for all \(i = 1\), . . . , n
Subtask 2 (10 points): \(n \le 20\)
Subtask 3 (26 points): \(a_{i} \le 20\) for all \(i = 1\), . . . , n
Subtask 4 (15 points): \(n \le 300\)
Subtask 5 (42 points): No additional constraints.
The first line contains an integer \(n\) (\(1 \le n \le 3\,000\)), the number of ornaments in the box.
The second line contains \(n\) integers \(a@@RISE_MATH_BLOCK_0@@i \le n\)), the colors of the ornaments in the box.
In the first and only line, print the result of the game, i.e., two numbers connected by the character ’:’
(without quotes), Marin’s and Josip’s scores.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 17점 | \(a_{i} \le 2\) for all \(i = 1\), . . . , n |
2 | 10점 | \(n \le 20\) |
3 | 26점 | \(a_{i} \le 20\) for all \(i = 1\), . . . , n |
4 | 15점 | \(n \le 300\) |
5 | 42점 | No additional constraints. |
5
1 1 2 1 11:16
1 2 3 1 2 32:1Clarification of the first example:
Marin is first, and he draws an ornament of color 1 from the left end
of the box. Marin scores a point.
Josip draws an ornament of color 1 from the right end of the box, but he
does not score a point because a ball of color 1 has already been drawn.
Marin draws an ornament of color 1 from the left end of the box. He
does not score a point either because a ball of color 1 has already been
drawn.
Josip draws an ornament of color 2 from the left end of the box. This
is the first ball of color 2 drawn, so Josip scores a point.
Marin draws the last ornament (color 1) from the left end of the box,
but it does not earn him a point, and the game ends.
Marin has a total of 1 point (he drew the ornament of color 1 first), and
Josip also has a total of 1 point (he drew the ornament of color 2 first).
The final result is 1 : 1.
평가 및 의견
Kuglice
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Kuglice