Time Limit: 4 seconds
Perry the Pirate is sailing the seven seas! He has a map consisting
of
It remains for him to plan out his next journey. He decides that he
will sail through some (possibly empty) path of sea routes starting at
island
There is one small problem though: Perry doesn’t know what island
he’s currently on! Thus, for every possible starting island
The first line of input contains two space-separated integers
The second line of input contains
The next
It is guaranteed that there is at most one sea route between any pair of islands and each sea route connects two distinct islands.
Marks Awarded | Bounds on |
Bounds on |
Additional constraints |
---|---|---|---|
5 marks | None | ||
5 marks | For all |
||
7 marks | Exactly one path of sea routes between any pair of islands | ||
8 marks | None |
Output
4 5
6 5 9 2
1 2 0
3 2 3
4 3 6
1 3 5
2 4 2
6
6
9
4
For the first and third islands, it is best to just stay and open the chest on the island itself.
For the second island, Perry can travel to the first island and open
the chest there. This has a net profit of
For the fourth island, Perry can to travel to the second and then the
third island and open the chest there. This has a net profit of
Time Limit: 4 seconds
Troy is fleshing out the details of his latest initiative, HackCCO!
Everyone knows that the biggest appeal of any hackathon is the free
food. As such, to ensure the unparalleled success of HackCCO, Troy
ordered a comically large cart stacked with
After the pizza cart arrives, Troy needs to arrange them into some number of stacks on a long table. To do this, he takes the pizzas one-by-one from the top of the cart and moves them onto the table, each time either placing the pizza on top of another stack of pizzas or forming a new stack on the table.
The
Of course, hungry coders are not happy coders, so Troy doesn’t want anyone to leave the table hungry. Thus, he asks you to help him find an arrangement of pizzas on the table such that it is possible for nobody to leave hungry. Furthermore, out of all such arrangements, Troy wants you to find one that creates the smallest number of stacks on the table (after all, tables can only get so long). Help him find such an arrangement or determine that it’s impossible!
The first line of input contains a single integer
The second line of input contains
The third line of input contains
Marks Awarded | Bounds on |
Additional constraints |
---|---|---|
3 marks | ||
4 marks | All |
|
5 marks | All |
|
6 marks | None | |
7 marks | None |
[Post-CCO edit: Subtasks 4 and 5 may not be solvable efficiently. CCO competitors were judged only on subtasks 1-3.]
If it is impossible to arrange the pizzas as desired, output
-1
.
Otherwise, your output should consist of three lines. On the first
line output
7
1 2 3 2 2 1 3
2 3 1 2 3 2 1
2
1 2 1 2 1 2 2
1 2 2 2 1 2 1
An illustration of the arrangement of pizzas on the table is shown below where red, yellow, and blue boxes represent pizzas of flavours
2
1 2
1 1
-1
Time Limit: 6 seconds
In Ontario, there are
Alice and Bob are travelling together, starting at city
Alice and Bob will alternate turns, starting with Alice. On Alice’s
turn, she must drive along exactly
Eventually, it will be Alice’s turn, but it will be impossible for
her to drive along exactly
Alice wants to end up in a city with as large a number as possible, while Bob wants to end up in a city with a small number. What is the city that Alice and Bob end their journey in when they both play optimally?
The first line of input contains four space-separated integers,
The next
Marks Awarded | Bounds on |
Additional Constraints |
---|---|---|
1 mark | ||
4 marks | There are at most two roads connected to
any city, and at most one road connected to
city |
|
5 marks | No additional constraints. | |
3 marks | No additional constraints. | |
4 marks | ||
6 marks | No additional constraints. | |
2 marks | No additional constraints. |
Output the city that Alice and Bob end their journey in, assuming they both play optimally.
9 6 2 1
1 3
1 6
2 4
2 5
2 7
3 9
4 6
4 8
2
On Alice’s first turn, she has three options: Drive to city
If Alice drives to city
If Alice drives to city
If Alice drives to city
In all cases, Bob can force the game to end in city
7 2 3 2
2 7
7 3
3 1
1 4
4 5
5 6
3
Time Limit: 1 second
Ondrej and Edward are spies and they are going to take down the evil
organization AQT. To do so, they will need to infiltrate into the AQT
base. The base can be modelled as a tree with
Their plan to meet up is as follows. At every odd minute, Ondrej can choose to stay at his current room or move to an adjacent room. At every even minute, Edward can choose to stay at his current room or move to an adjacent room.
A strategy is defined as the following. Let
Ondrej and Edward want to meet up as fast as possible, relative to
the distance between their two starting rooms. The distance
The first line of input will contain
The next
First output a positive number
Then, output Ondrej’s strategy, followed by Edward’s strategy.
To output an agent’s strategy, output
If the output is invalid or there exists a test case and a pair of
different rooms
Otherwise, let
Score | Bounds on |
---|---|
3 | |
6 | |
8 | |
10 | |
12 | |
15 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
25 |
5
0 2
3 2
1 4
2 4
8
2 2 4 4 1 1 1 1
1 1 1 1 1 1 1 1
3 3 2 2 3 3 2 2
3 3 2 2 0 0 2 2
4 4 4 4 2 2 2 2
0 2 2 3 3 3 3 2
1 4 4 2 2 0 0 0
2 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3
4 1 1 1 1 4 4 4
Note that this is an invalid test case as
Time Limit: 4 seconds
In an array containing only positive integers, we say an integer is heavy if it appears more than once in the array, and light otherwise.
An array is good if the integers in the array alternate between light and heavy.
Given an array
The first line of input contains a single integer,
The next line contains
Marks Awarded | Bounds on |
Additional Constraints |
---|---|---|
3 marks | For each |
|
4 marks | No additional constraints. | |
5 marks | If |
|
6 marks | Any number appears at most twice in the array. | |
7 marks | No additional constraints. |
The number of ways to partition the array into good contiguous
subarrays, modulo
5
1 2 3 2 3
4
There are four valid partitions of [1, 2, 3, 2, 3]:
[1], [2], [3], [2], [3]
[1], [2, 3, 2], [3]
[1], [2], [3, 2, 3]
[1, 2, 3, 2], [3]
5
1 2 1 3 1
6
Time Limit: 4 seconds
The "Dormi’s Fone Service" is now the only telephone service provider
in CCOland. There are
There is an issue where the phone lines are faulty, and each phone line only exists for a single interval of time. Two houses can call each other at a certain time if there is a path of phone lines that starts at one of the houses and ends in the other house at that time.
We would like to process
1 x y
: Add a phone line between houses
2 x y
: Remove the phone line between houses
3 t
: Compute the number of pairs of different houses
that can call each other at some time between the current query and
Also, some test cases may be encrypted. For the test cases that are
encrypted, the arguments x
, y
, or
t
are given as the bitwise xor of the true argument and the
answer to the last query of type 3
(if there have been no
queries of type 3
, then the arguments are unchanged).
The first line of input will contain
The second line contains two space-separated integers
The next
For the 1
and 2
queries and 3
queries.
Marks Awarded | Bounds on |
Bounds on |
Encrypted? |
---|---|---|---|
3 marks | |||
2 marks | |||
4 marks | |||
2 marks | |||
4 marks | |||
5 marks | |||
5 marks |
For each query of type 3
, output the answer to the query
on a new line.
0
4 12
3 0
1 1 2
3 0
1 1 3
3 0
3 5
2 2 1
3 0
3 8
1 1 4
3 0
3 11
0
1
3
3
1
3
3
5
This test case is not encrypted.
For the
For the
For the
For the
For the
For the
For the
1
4 12
3 0
1 1 2
3 0
1 0 2
3 1
3 6
2 1 2
3 3
3 9
1 2 7
3 3
3 8
0
1
3
3
1
3
3
5
Encrypted version of sample 1.