Croatian Open Competition in Informatics
Round 3, December 12th 2024
Tasks
Task Time limit Memory limit Score
Autobus 1 second 512 MiB 50
Karte 1 second 512 MiB 70
Bojanje 1 second 512 MiB 90
Stablo 2 seconds 512 MiB 120
Procesor 1 sekunda 512 MiB 120
Total 450
Croatian Open Competition in Informatics Task Autobus
Round 3, December 7th 2024 1 second / 512 MiB / 50 points
Task Autobus
Mr. Malnar decided to visit one of the few cities he has not yet visited, Wroclaw
(Pol. Wrocław), located in the southwest of Poland. Since he hadn’t traveled by
bus for a long time, he missed the experience; however, he was disappointed to
learn that there is no direct bus line between Zagreb and Wroclaw.
The best alternative is transferring in the Austrian city of Graz. Mr. Malnar
found a timetable, i.e., a list of bus lines operating on the routes Zagreb-Graz and
Graz-Wroclaw. A bus on a specific route runs daily, departing exactly at the start
of the departure time minute and arriving precisely at the end of the last minute of the arrival time. The
time required for transferring is negligible, i.e., it is possible to board a bus if you arrive at the destination
before the bus you wish to transfer to departs (the arrival time of the first bus must be strictly less than
the departure time of the second bus).
Determine the shortest time required to travel from Zagreb to Wroclaw.
Input
The first line contains a positive integer n (1 ≤ n ≤ 200), the number of bus lines.
In the next n lines, the names of two cities connected by the symbol "-" are given in order, the first
representing the departure city and the second the destination city, followed by the departure time and
arrival time in the format h:mm--h:mm, where h represents the hours, and mm represents the minutes of
that time. Note that two digits for minutes will always be shown. If the number of minutes is a single
digit, a leading zero will be included. It is guaranteed that each trip (without transfers) will last at most
24 hours.
Output
If it is possible to travel from Zagreb to Wroclaw, print the travel time in the first line in the format h:mm
(described above).
If it is not possible, print "NEMOGUCE" (without quotes, Croatian for "IMPOSSIBLE") in the first line.
Scoring
Subtask Points Constraints
1 9 n≤3
2 19 There exists exactly one bus line on route Zagreb-Graz.
3 22 No additional constraints.
1 of 9
Croatian Open Competition in Informatics Task Autobus
Round 3, December 7th 2024 1 second / 512 MiB / 50 points
Examples
input input
4 3
Zagreb-Graz 15:30--23:59 Zagreb-Graz 6:05--16:40
Graz-Wroclaw 10:42--19:15 Zagreb-Graz 20:00--21:40
Zagreb-Graz 14:13--20:19 Zagreb-Graz 9:56--22:36
Graz-Wroclaw 2:25--5:00
output
output
NEMOGUCE
13:31
2 of 9
Croatian Open Competition in Informatics Task Karte
Round 3, December 7th 2024 1 second / 512 MiB / 70 points
Task Karte
On Vito’s table, there are N red cards labeled with numbers from 1 to N and M blue cards labeled with
numbers from 1 to M . Each pair of red and blue cards (c, p) (where c represents a red card and p a blue
card) can create a COMBO move.
The strength of a deck of cards is defined as:
strength = (number of COMBO moves) − X · (number of red cards) − Y · (number of blue cards)
where the number of COMBO moves is the number of pairs (c, p) such that the red card c and the blue
card p are in the chosen deck. Vito can include any card from the table in his deck. Help Vito find the
value of the strongest deck he can build. Vito can also choose an empty deck of cards.
Input Data
The first line contains 4 natural numbers N, M, X, Y (1 ≤ N, M ≤ 21, 0 ≤ X, Y ≤ 30).
In the next N lines, there is a sequence of M characters (0 or 1), where the j-th character indicates
whether the i-th red card and the j-th blue card create a COMBO move.
Output Data
In the first and only line, output the value of the strongest deck of cards that Vito can build.
Scoring
Subtask Points Constraints
1 18 Y =0
2 11 1 ≤ N, M ≤ 9
3 24 1 ≤ N, M ≤ 15
4 17 No additional constraints.
Sample Cases
input input input
2 2 0 0 3 3 1 0 3 3 1 1
11 111 111
10 111 101
000 011
output
output output
3
4 1
Explanation of the first sample case: Vito will choose all the cards from the table, creating 3 COMBO
moves.
Explanation of the second sample case: Vito will select the first 2 red cards and all 3 blue cards,
creating 6 COMBO moves. The deck strength is 4 because Vito selected 2 red cards, so the number of
COMBO moves, i.e., 6, is reduced by 2.
3 of 9
Croatian Open Competition in Informatics Task Bojanje
Round 3, December 7th 2024 1 second / 512 MiB / 90 points
Task Bojanje
Marin, having become exceptionally skilled in competitive programming, decided to find a new hobby to
keep himself entertained while waiting for you to catch up. While you were solving previous problems,
Marin discovered a great love for painting.
He took a blank white canvas and two colors, red and blue. He began painting perfectly horizontal and
vertical strokes on the canvas, from one edge to the opposite edge. The canvas can be imagined as an
n · n grid, where rows and columns are numbered from 1 to n, and it starts completely white. Each of
Marin’s strokes can be imagined as choosing one of the two colors and a row or column, then coloring all
the cells in that row/column with the chosen color, regardless of what was previously on the field. Marin
will make a finite number of strokes and complete his painting.
However, his friend Stjepan found a painting that resembles Marin’s but is unsure if it is really his. The
painting he found can again be imagined as an n x n grid where each cell is white, blue, or red. The
painting is possibly Marin’s if there exists a sequence of strokes on a blank canvas, as described above,
that produces an image identical to the one found. Stjepan has asked you to help him determine whether
the painting might be Marin’s and, if so, to find a sequence of strokes that produces the found painting.
Input
The first line contains a positive integer n (1 ≤ n ≤ 2000).
In the next n lines, there are n integers ai,j (0 ≤ ai,j ≤ 2), where each represents the color in the i-th row
and j-th column (0 if white, 1 if red, and 2 if blue).
Output
If the painting is possibly Marin’s, then in the first line, print the number of strokes K (0 ≤ K ≤ 4000).
In the next K lines, you should print three integers. The first will indicate whether the i-th stroke was on
a row or a column (1 for a row, 2 for a column). The second number will indicate the index of the row or
column where the stroke is performed, and the third number will indicate the color in the same way as
described in the Input section.
If the painting is certainly not Marin’s, print "-1" (without quotes) in the first and only line.
Scoring
Subtask Points Constraints
1 15 ai,j ≤ 1
2 35 n ≤ 100
3 40 No additional constraints.
4 of 9
Croatian Open Competition in Informatics Task Bojanje
Round 3, December 7th 2024 1 second / 512 MiB / 90 points
Examples
input input input
3 3 4
0 0 1 1 1 2 0 1 2 1
1 1 1 2 1 1 2 2 2 1
0 0 1 2 1 1 0 1 2 1
1 1 2 1
output output
output
2 -1
2 3 1 5
1 2 1 2 2 1
1 2 2
2 4 1
1 4 1
2 3 2
5 of 9
Croatian Open Competition in Informatics Task Stablo
Round 3, December 7th 2024 2 seconds / 512 MiB / 120 points
Task Stablo
Toni decided to create a task for HONI (and COCI). Since he doesn’t like kids, he decided to make the
task as difficult as possible. He came up with a complex problem involving a tree that constantly changes,
solely to make contestants suffer as much as possible.
You are given a weightless tree with N nodes, where the root of the tree is node 1. Each node has an
associated value v[i]. The structure of the tree is defined using an array p[i], where for each i from 1 to
N − 1, p[i] denotes the parent of i + 1.
A function f (y) is defined for a node y in the tree as:
X
f (y) = d(x, y) · v[x]
x∈Sy
where d(x, y) denotes the distance between nodes x and y, while Sy contains all nodes for which y is an
ancestor.
You are given Q queries with two nodes x and y. For each query, the following transformation must be
simulated in the tree, and the function f (y) needs to be calculated:
1. Attach all nodes for which x is the parent to the parent of x
2. Remove x from the tree
3. Insert node x back into the tree, between y and the descendant of y from whose subtree x was
removed.
If y is the parent of x, the tree remains unchanged. It is always true that x is in the subtree of y. For
each query, the value of f (y) must be calculated after the tree is temporarily modified according to the
procedure described above. The tree modifications are not permanent, i.e. after each query, the tree
returns to its original state.
Input
The first line contains two integers N and Q (1 ≤ N, Q ≤ 5 · 105 ), the number of nodes in the tree and
the number of queries, respectively.
The second line contains N integers v[i] (1 ≤ v[i] ≤ 106 ), representing the value of each node.
The third line contains N − 1 integers p[i] (1 ≤ p[i] ≤ i), where p[i] denotes the parent of node i + 1.
Each of the next Q lines contains two integers x and y (1 ≤ x, y ≤ N ), denoting the nodes involved in the
operation described above.
Output
In the next Q lines output the value of the function f (y) on the modified tree.
Scoring
Subtask Points Constraints
1 21 1 ≤ N, Q ≤ 1000
2 37 Tree is a chain, p[i] = i for every i from 1 to N − 1
3 22 Each node will be the parent of at most 20 nodes
4 40 No additional constraints.
6 of 9
Croatian Open Competition in Informatics Task Stablo
Round 3, December 7th 2024 2 seconds / 512 MiB / 120 points
Examples
input input input
3 1 3 2 5 3
1 2 3 4 5 6 2 5 2 2 2
1 2 1 1 1 2 3 2
3 1 2 1 4 3
3 1 3 2
output 5 1
output
7 output
11
11 2
8
26
Clarification of the first example: After applying the operation on a tree, node 3 is at a distance of 1
from node 1, and node 2 is at a distance of 2 from node 1. The result is 3 + 2 · 2 = 7.
7 of 9
Croatian Open Competition in Informatics Task Procesor
Round 3, December 7th 2024 1 sekunda / 512 MiB / 120 points
Task Procesor
Initially, Fran has an empty array a. Fran processes n queries of the form x — he appends x elements to
the end of a. After each query, Fran wants to determine the smallest element in the array a, and once he
identifies it, he removes it from the array without altering the indices of the other elements.
Your task is to determine the smallest element of the array for each query by asking questions.
Interaction
This is an interactive task. Your goal is to write a program that responds to the queries.
The input begins with a single line containing n — the number of queries (1 ≤ n ≤ 40). Then, n queries
follow, each starting with xi — the number of elements added to the array (1 ≤ xi ≤ 2000).
After each query, your program may ask questions of the form ? i j. The interactor will respond with 0 if
ai < aj , or 1 if ai > aj . You may assume all elements in the array are distinct. i =
̸ j must hold, and
indices i and j must not correspond to already removed elements.
After determining the smallest element, you must print ! x, which indicates that ax is the smallest element
in the array a (excluding already removed elements). The index x must not correspond to an already
removed element.
You may ask questions multiple times, and after printing the smallest element, the next query begins.
Once you determine the smallest element, the interaction continues with subsequent queries. After the
last query, the interaction ends, and your solution is evaluated based on the number of questions asked.
The total length of the array will not exceed 2000.
Scoring
Your program will earn points based on the number of questions asked. Let q be the total number of
questions your program asked.
• If q ≤ 2700, your program will earn 120 points.
• If 2700 < q ≤ 7000, your program will earn 75 points.
• If 7000 < q ≤ 2 · 104 , your program will earn 35 points.
• If 2 · 104 < q ≤ 8 · 104 , your program will earn 15 points.
8 of 9
Croatian Open Competition in Informatics Task Procesor
Round 3, December 7th 2024 1 sekunda / 512 MiB / 120 points
Sample Cases
input
3
3
output
? 1 2
? 1 3
? 2 3
! 2
? 1 4
! 4
? 1 5
! 1
Explanation of the Sample Case:
The final array is of the form 3, 2, 4, 1, 5.
The first query outputs 1 because a1 > a2 .
The second query outputs 0 because a1 < a3 .
The third query outputs 0 because a2 < a3 .
After this, it can be determined that a2 is the smallest current element, so the output is ! 2. The
interaction continues with the subsequent queries.
9 of 9