Croatian Open Competition in Informatics

Round 2, November 9th 2024

Tasks
Task Time limit Memory limit Score

Paradoks 1 sekunda 512 MiB 50

Igre 2 seconds 512 MiB 70
Različitost 2 seconds 512 MiB 90
Blistavost 4 seconds 1024 MiB 120
Trokuti 4 seconds 512 MiB 120

Total 450
 Croatian Open Competition in Informatics Task Paradoks
Round 2, November 9th 2024 1 sekunda / 512 MiB / 50 points

Task Paradoks
One full moon evening, when the clock struck midnight, five friends found them-
selves ready to play a game as mysterious as that night.
They sat in a circle, in clockwise order: Igor, Lea, Marino, Sonja, and Viktor.
The game consists of N rounds. The first round is started by Sonja, and each
subsequent round is started by the winner of the previous round.
Each player holds N cards in their hand. All cards are colorless and have a natural
number between 1 and 9 on them. When a player plays a card, they choose the color for that card. They
may choose one of four colors (red, blue, yellow, green) provided that such a card (combination of that
number and color) has not already been played in the game. In the rest of the text, the term "playing a
blue card," for example, refers to the procedure of playing the card and declaring it to be blue.
In each round, the players, in clockwise order, play one card each until the turn reaches the player who
started the round, i.e., until each player has played one card. The first card played in a round determines
the so-called round color, and all subsequent players are required to play cards of that color. If any player
fails to play a card of the current round color, it is assumed that the player has no such color card in their
hand – and they are prohibited from playing that color card for the rest of the game.
The winner of each round is:

• The person who played the red card with the highest number.
• If no red cards were played, the person who played the highest number of the round color.

Sometimes, players make a move that they should not have: either they play a card that has already been
played or play a card of a color they previously declared they no longer have. This play is called a paradox
(in Croatian: "paradoks"). When a paradox occurs, the play is completely ignored in calculating the
round’s winner and the rest of the game. For example, if a card is played for the first time as a paradox,
for the rest of the game, it is treated as though it has not yet been played. It is guaranteed that the first
player in a round will never play a paradox in that round.
Our heroes haven’t seen each other for a long time and haven’t been paying close attention to the game,
so they ask for your help. Write a program that, for the sequentially listed played cards by round, prints
how many paradoxes occurred and lists them in the order they happened. For each paradox, print the
round in which it occurred and the player who caused it.

Input
The first line of input contains a natural number N (1 ≤ N ≤ 10), the number of rounds.
In the next N lines of input, there are 5 words, each 2 characters long, representing the cards played in
that round, in the order they were played. (Caution: the first player in each round is not necessarily the
same.)
The first character of each word represents the color of the card the player played and will be one of the
following letters: ’C’ –red, ’P’ – blue, ’Y’ – yellow, ’Z’ – green. The second character of each word will be
a natural number between 1 and 9 (inclusive), representing the number on the card.
For example, the word ’Y5’ would represent a yellow card with the number 5.

Output
Print a single number a, the number of paradoxes that occurred.
In next a lines, for each of the a paradoxes, print the round number and the name of the player who

1 of 9
 Croatian Open Competition in Informatics Task Paradoks
Round 2, November 9th 2024 1 sekunda / 512 MiB / 50 points

caused it, in uppercase letters.

Paradoxes should be printed in the order they occurred.

Scoring

Subtask Points Constraints

1 10 Sonja will be the winner of all rounds, and all paradoxes will
occur due to repeating a card that has already been played.
2 10 All paradoxes that occur will be caused by repeating a card
that has already been played.
3 30 No additional constraints.

Examples
input input input
4 3 1
Y5 Z3 Y6 C2 Y1 P1 Y9 Z5 Y1 Z5 Y4 P9 Y8 Z5 Z3
Z4 Z7 Z2 Y2 P3 P5 Y7 Z3 Y8 P1
Z6 Z7 Z1 Y2 C2 C6 Y8 P5 Z1 Z8 output
P6 P8 P8 Z7 Y9 0
output
output
4
6 1 MARINO
2 VIKTOR 2 MARINO
3 SONJA 3 VIKTOR
3 LEA 3 IGOR
4 VIKTOR
4 IGOR
4 LEA

Clarification of the first example:

The course of the game is shown in the picture below (on the next page).
In round 1, Viktor and Lea did not play yellow cards (the color of the round), so it is assumed that they
have no yellow cards left in their hands and are prohibited from declaring any card as yellow for the rest
of the game. This is the reason for Viktor’s paradox in round 2 and Lea’s paradox in the last round.
Notice: that in round 2, due to the paradox, Viktor’s move is ignored, and we don’t draw any further
conclusions. Also, the card Y2 is not considered played, which is why Igor does not get a paradox for
playing that card in round 3.
All the paradoxes in rounds 3 and 4 (except the last one) happened because a card was played that had
already been played earlier in the game.

2 of 9
Croatian Open Competition in Informatics Task Paradoks
Round 2, November 9th 2024 1 sekunda / 512 MiB / 50 points

3 of 9
 Croatian Open Competition in Informatics Task Igre
Round 2, November 9th 2024 2 seconds / 512 MiB / 70 points

Task Igre
Kile has returned from a board game fair. He brought home n games. Before
playing a game, it is necessary to learn its rules. Learning the rules of the i-th
game takes pi minutes. Once the rules are learned, it is possible to play the game.
Playing the i-th game takes ti minutes. Each game also has its own rating oi .
In the coming days, Kile has planned to spend at most d minutes on board games.
He is interested in finding out the maximum sum of the ratings of the games he
can play. Each game can be played an arbitrary number of times.

Input
The first line contains integers n and d (1 ≤ n, d ≤ 5000), the number of games and the time planned to
spend on playing games.
The i-th of the following n lines contains integers pi , ti and oi (0 ≤ pi ≤ 5000, 1 ≤ ti ≤ 5000, 1 ≤ oi ≤ 109 ),
time required to learn the rules, time required to play and the rating of i-th game.

Output
In the first and only line, output the maximum sum of the ratings of the games played.

Scoring

Subtask Points Constraints

1 6 n=1
2 13 n ≤ 10
3 23 pi = 0 for all i = 1, ..., n
4 28 No additional constraints.

Examples
input input input
3 10 4 13 3 10
2 3 5 0 6 5 1 1 1
5 1 5 0 3 4 3 2 3
3 2 5 0 2 3 2 3 5
0 4 4
output output
output
25 11
19

Clarification of the third example:

One way to achieve a total score of 11 is as follows: in the first minute, Kile learns to play the first game,
then plays it once. After that, he spends two minutes learning to play the third game, and in the last 6
minutes, he plays it twice. This way, the total score of the games played is: 1 + 5 + 5 = 11.

4 of 9
 Croatian Open Competition in Informatics Task Različitost
Round 2, November 9th 2024 2 seconds / 512 MiB / 90 points

Task Različitost
Two infinite periodic sequences of integers, ai and bi , are given, defined by their periods of lengths n
and m, respectively. This means that the natural numbers n and m are given, as well as the numbers
a1 , a2 , . . . , an and b1 , b2 , . . . , bm , for which ai = ai+n and bi = bi+m hold for every natural number i.
Additionally, given a natural number k, we define the "diversity" of these two sequences as the sum ai ⊕ bi
for each i = 1, 2, . . . , k. (Here, ⊕ denotes the bitwise exclusive OR operation, which produces ones in
the positions where the binary digits of the two numbers differ. For example, 5 ⊕ 3 = (101)2 ⊕ (011)2 =
(110)2 = 6.)
Your task is to calculate the diversity of the given sequences.

Input
In the first line, there are n, m, and k (1 ≤ n, m ≤ 2 · 105 , 1 ≤ k ≤ 1018 ), which are the numbers from the
task description.
In the second line, there are n integers a1 , . . . , an (0 ≤ ai ≤ 1018 , i = 1, 2, . . . , n).
In the third line, there are m integers b1 , . . . , bm (0 ≤ bi ≤ 1018 , i = 1, 2, . . . , m).

Output
Because the answer can be very large, output the remainder of the answer when divided by 109 + 7 in a
single line.

Scoring

Subtask Points Constraints

1 25 k ≤ 2 · 105
2 13 n=m
3 9 n=1
4 43 No additional constraints.

Examples
input input

3 2 10 10 5 30
1 6 4 5 16 2 10 7 2 4 20 5 12
5 2 4 11 14 23 5

output output

33 435

5 of 9
 Croatian Open Competition in Informatics Task Blistavost
Round 2, November 9th 2024 4 seconds / 1024 MiB / 120 points

Task Blistavost
In the heart of the Glass Valley lies a mysterious star temple, a place known for
its collection of magical crystals that shine like stars. Each crystal holds special
power and emits a radiant glow that illuminates the entire valley, as long as it
remains untouched.
The temple guardian’s nightly task is to touch ONLY the crystals located within the
specified ranges of the valley’s residents, while honoring all of their requirements.
Each resident’s request tells the guardian which range of crystals must NOT stop
shining BEFORE their bedtime, as they fear the darkness.
The guardian starts his journey at the temple entrance and must carefully coordinate their movements
to dim the crystals such that they stop shining at the correct moment. The crystals are arranged in a
line, spaced one meter apart from each other (the first crystal is one meter away from the entrance). The
guardian can move at a speed of one meter per second and may stop when needed. The time it takes for
the guardian to touch and dim a crystal is negligible. Given the residents’ requests, the temple guardian
wants to know the minimum number of seconds required to fulfill all requests (the guardian does not need
to return to the starting position).

Input
In the first line is an integer N (1 ≤ N ≤ 5000), number of residents’ requests.
In the next N lines are integers li , ri , ti (1 ≤ li ≤ ri ≤ 1e18, 1 ≤ ti ≤ 1e18), representing the left and right
bounds of the crystal range and the resident’s bedtime, respectively.

Output
In the first and only line output the minimum time in seconds required for the guardian to fulfill all the
requests.

Scoring

Subtask Points Constraints

1 20 n ≤ 18, li = ri for all i = 1, 2, . . . , n

2 25 li = 1 for all i = 1, 2, . . . , n
3 55 li = ri for all i = 1, 2, . . . , n
4 20 No additional constraints.

Examples
input input input
3 3 3
1 1 1 1 2 1 6 6 6
3 3 5 1 1 5 8 8 7
5 5 3 1 3 4 9 9 9

output output output

7 6 9

6 of 9
 Croatian Open Competition in Informatics Task Blistavost
Round 2, November 9th 2024 4 seconds / 1024 MiB / 120 points

Clarification of the second example:

The temple guardian will first take 3 seconds to reach the 3rd crystal. Then, he will wait for 1 second and
dim the 3rd crystal. After that, he will take 1 second to go to the 2nd crystal and dim it. Finally, he will
take 1 second to reach the 1st crystal and dim it. In total, his journey will last 6 seconds, which is the
minimum time required to fulfill all the requests.

7 of 9
 Croatian Open Competition in Informatics Task Trokuti
Round 2, November 9th 2024 4 seconds / 512 MiB / 120 points

Task Trokuti
An undirected graph with 6 · N vertices and M edges is given. An additional property of the graph is
that it can be partitioned into 2 · N disjoint triangles.
Find N disjoint triangles in the graph.

Input
In the first line, there is a natural number T (1 ≤ T ≤ 100), which indicates the number of test cases.
This is followed by T blocks of data.
In the first line of each block, there are natural numbers N and M (1 ≤ N ≤ 300, 0 ≤ M ≤ 106 ).
In the next M lines, there are two natural numbers x and y (1 ≤ x, y ≤ 6 · N ), which indicate that there
is an edge between vertices x and y.
The sum of all values of N across all test cases will not exceed 300.

Output
For each test case, output N lines, each line containing three natural numbers a, b, c (1 ≤ a, b, c ≤ 6 · N ),
which indicate that the vertices a, b, and c form a triangle.

Scoring

Subtask Points Constraints

1 13 M =6·N
2 18 N = 3, T = 1
3 18 N = 6, T = 1
4 71 No additional constraints.

8 of 9
 Croatian Open Competition in Informatics Task Trokuti
Round 2, November 9th 2024 4 seconds / 512 MiB / 120 points

Examples
input input
1 1
1 6 3 26
1 2 4 7
2 3 4 9
1 3 7 9
4 5 4 5
4 6 4 8
5 6 5 8
4 12
output 4 18
1 2 3 12 18
3 7
3 9
15 5
15 8
6 13
6 1
13 1
6 14
6 17
14 17
6 2
6 10
2 10
16 13
16 1
11 14
11 17

output

1 6 13
3 7 9
4 5 8

9 of 9