First Round SOI 2015

Subtask 1: Two Regions (10 points)

For this subtask it holds that $M=2$, and your program should decide if there is a possible splitting. Input —– The first line of the input contains a single integer $T$, the number of test cases. $T$ test cases follow. Each test case consists of a single line containing the two integers $N_{1}$ and $N_{2}$, separated by a single space.

2
1 1
1 2

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

Subtask 2: More Regions (30 points)

For this subtask, $M$ can take on other values, and your program should decide, if there is a possible splitting. Input —– The first line of the input contains a single integer $T$. $T$ test cases follow. Each test case consists of a single line with the integer $M$, describing the number of regions, followed by the $M$ numbers $N_i$, separated by single spaces.

2
3 2 1 1
3 4 2 1

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

Subtask 3: Explicit Scheme (40 points)

For this subtask, you program should print an explicit splitting of mice into rooms, if there is such a splitting. Input —– The first line of the input contains a single integer $T$. $T$ test cases follow. Each test case consists of a single line with the integer $M$, describing the number of regions, followed by the $M$ numbers $N_i$, separated by single spaces.

3
4 1 1 1 1
3 2 1 1
2 1 2

Case #1:
1 3
2 1
3 4
4 2
Case #2:
1 2
2 1
3 1
1 3
Case #3: IMPOSSIBLE

Subtask 4: More Categories (20 points)

The OCKCC is thinking about inviting $K\cdot N_i$ mice from each region, where $K\geq 1$. As the scheme, according to which the mice where splitted up into rooms has made a lot of sense so far, it should now be applied in a more general form. This means that for $K=2$, this new scheme is identical with the previous scheme. From each region there will visit $N_i$ mice from $K$ different categories (like experts for sheep’s cheese, goat’s cheese, spicy cheese, mild cheese, …). The categories are numbered from $1$ to $K$. Those mice should then be split up into $K$-bed rooms such that in each room there are no two mice from the same region and no two mice from the same category. (In particular, in each room there is exactly one mouse from each category.) Input —– The first line of the input contains a single integer $T$. $T$ test cases follow. Each test case consists of a single line with the integers $M$ and $K$, the number of regions and the number of categories respectively, followed by the $M$ integers $N_i$, separated by single spaces.

3
3 2 2 1 1
3 3 2 1 1
3 3 1 1 1

Case #1:
1 2
2 1
3 1
1 3
Case #2: IMPOSSIBLE
Case #3:
3 1 2
1 2 3
2 3 1

Subtask 1: Two words (20 points)

At first. Stofl wants to compose a poem of length $2$. To do this he wants to know for two words whether one occurs in the other. Help him answer this question.

Input

The first line contains the number $T$, the number of poems that Stofl wants to compose. After that $T$ lines, each containing two words, follow.

Output

For each of the $T$ inputs you have to output a single line. Each line should start with “Case #i:”, followed by “YES”, if one of the two words occurs in the other and “NO”, if not.

Constraints

• Each word consists of at most $10\,000$ small letters from a to z.
• $T = 100$, i.e. there are exactly $100$ poems.

Examples

3
bach belauschen
belauschen bach
bach dach

Case #1: YES
Case #2: YES
Case #3: NO

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 2: Short poems (30 points)

Stofl now has an entire list of words in front of him and tries to find two of them that build a poem. Determine whether there are two words in the list that build a poem.

Input

The first line contains the number $T$, the number of poems that Stofl wants to compose. $T$ inputs follow, each of them structured like this: The first line contains the number $N$. The next $N$ lines each contain a word $W_i$.

Output

For each of the $T$ inputs you have to output a single line. Each line should start with “Case #i:”, followed by “YES”, if a poem of length $2$ exists abd “NO”, if not.

Constraints

• $1 \le N \leq 400$, i.e. there are at most $400$ different words.
• Each word consists of at most $100$ small letters from a to z.
• $T = 100$, i.e. there are exactly $100$ poems.

Examples

2
5
bach
dachs
belauschen
obacht
dach
4
bach
dach
fach
sache

Case #1: YES
Case #2: NO

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 3: Long poems (50 points)

After Stofl mastered the art of short poems, he now tries to write longer ones. Each poem consists of one nice word chain. A word chain is nice if each word occurs in all subsequent words. “ah, bach, belauschen” is a nice word chain, because “ah” occurs “bach” as well as in “belauschen”, and “bach” occurs in “belauschen”. “ah, bach, brach, belauschen” on the other hand is not nice, because “brach” does not occur in “belauschen”.

Stofl wants to compose long poems and nice long word chains for that. Given a list of words, try to find the length of the longest word chain.

Input

The first line contains the number $T$, the number of poems that Stofl wants to compose. $T$ inputs follow, each of them structured like this: The first line contains the number $N$. The next $N$ lines each contain a word $W_i$.

Ouptut

For each of the $T$ inputs, you have to output “Case #i:” followed by $L$, the length (number of words) of the longest word chain.

Constraints

• $1 \le L \leq N \leq 400$, i.e. there are at most $400$ words and the solution is at most the number of words.
• Each word consists of at most $100$ small letters from a to z.
• $T = 100$, i.e. there are exactly $100$ poems.

Examples

2
8
bach
dachs
brach
belauschen
obacht
ah
belauschend
dach
3
bach
dach
fach

Case #1: 4
Case #2: 1

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 1: Single Interference (20 Punkte)

Given $N$ periods $P_j$, compute the period of the resulting wave for multiple test cases.

3
3 6 8 4
2 8 4
4 10 3 5 2

Case #1: 24
Case #2: 8
Case #3: 30

Subtask 2: Multiple Interferences (40 Punkte)

Stofl is thinking that a single sound can be shortened most (while keeping its character), by only playing one period in full, and attaching just the remainder of the wave.

If therefore a (resulting) wave of period $5$ ms is playing for $124$ ms in total, it goes through $24$ full periods with a remainder of $4$ ms. ($124/5 = 24$, with remainder $4$). The sound character would however be preserved by playing only one period and $4$ ms of the remainder, therefore the section could be shortened from $124$ ms to $5+4=9$ ms. Furthermore, Stofl only wants to hear relevant parts of the file. If a section of the file is completely silent, this section should therefore be removed from the file completely.

An audio file consists of $N$ single waves, having periods $P_e$, a starting time $T_s$ and an ending time $T_e$ and interfere accordingly. Your task is to shorten multiple files as described above. The resulting audio files will consist of $K$ sections ($K$ may differ for different files), in a certain order. Each section consists of a certain period $P_r$ and takes time $T_r$. Note, that two subsequent sections having the same period cannot be combined into one. (Because generally, the sound in one section will not be the same as the sound in the other section.)

Examples

3
3
15 20 120
2 0 20
6 1 150
2
7 2 101
11 23 123
2
2 1 2
3 3 10

Case #1:
4 0
2 1
6 7
30 40
6 6
Case #2:
3 2
7 7
77 78
11 11
Case #3:
2 1
2 1
3 4

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 3: Big Files and Big Periods (40 Punkte)

The task description for this subtask corresponds to the task description of subtask 2, but you do not have to print the entire file explicitly.

Rather, for the $i$-th section of the file, print $P_r$ modulo $M$, where $M=10^{9}+7=1000000007$ and $P_r$ is the period of the $i$-th section of the file. $a$ modulo $b$ corresponds to the positive integer remainder of the division of $a$ by $b$. In other words, $0\leq a$ modulo $b<b$, and if $a$ modulo $b = c$, then there is an integer $d$ such that $a=d\cdot b+c$.

(The shortened durations are no longer of any importance.)

1
4
1000000007 1 2
1000000008 1 4
1000000009 1 4
1000000010 3 4

Case #1:
3 1
0
2
3

Subtask 1: Practical part with few yurts (20 points)

In this subtask the campground includes at most $8$ yurts. It is your task to bring them in the correct order with as few swaps as possible. Your output gets accepted if you need at most $N$ swaps for $N$ yurts. So your program does not necessarily need to act optimally. For instance, if the tents are already in sorted order at the beginning, it is ok to do no swaps at all or to perform a few dummy swaps back and forth. You will think about the fact that $N$ swaps are always sufficient in subtask 3.

Input

The first line contains the number $T$, the number of test cases. The following $T$ lines each describe a test case. Each line starts with $N$ the number of yurts, followed by $N$ space-separated numbers, $M_{1}$ to $M_N$, where $M_i$ is the number of the yurt, that is place on spot $i$ initially.

Output

For each test case print one line with a possible sequence of $N$ or less swaps. For the $t$-th test case start the line with “Case #t:”, followed by an even number of space-separated numbers $M_i$. These numbers mean that in your $i$-th swap the yurt on spot $M_{2i-1}$ get interchanged with the yur on spot $M_{2i}$. (Example: $5$ $2$ $3$ $6$ $4$ $3$ means that the yurts on spot $5$ and $2$ get swaped. After that the yurts on spot $3$ and $6$, and finally the ones on spots $4$ and $3$).

Constraints

• $3 \leq N \leq 8$, so there are between $3$ and $8$ yurts.
• You are allowed to perform at most $N$ swaps.
• $T = 100$, so there are $100$ test cases.

Beispiele

2
3 1 3 2
5 4 3 2 5 1

Case #1: 2 3
Case #2: 1 5 2 3 4 5

Illustration of the second example:

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 2: Practical part with many yurts (20 points)

In this subtask the campground includes at most $500$ yurts. It is your task to bring them in the correct order with as few swaps as possible. Your output gets accepted if you need at most $N$ swaps for $N$ yurts. So your program does not necessarily need to act optimally.

The format of the input and output is identical with subtask 1.

Constraints

• $3 \leq N \leq 500$, so there are between $3$ and $5\,000$ yurts.
• You are allowed to perform at most $N$ swaps.
• $T = 100$, so there are $100$ test cases.

Beispiele

2
5 4 3 2 5 1
10 10 2 3 4 5 6 7 8 9 1

Case #1: 1 5 2 3 4 5
Case #2: 2 3 3 4 2 4 3 4 1 10

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 3: Theoretical part: at most $N-1$ swap (30 points)

The mouse Stofl now claims, that it is always possible to bring $N$ yurts with strictly less than $N$ (so at most $N-1$) swaps into the correct order. Describe how your algorithm solves this task and explain why you need less than $N$ swaps for every possible initial placement.

We expect you to explain and justify your solution as continuous text. Try to convince you and us that your idea really works. For this and the next subtask your submission does not necessarily need to include a complete compilable program. A precise explanation, e.g. with pseudo code, is enough.

The contest is over, you can no longer submit.

Subtask 4: optimal number of swaps (30 points)

You are not happy with just doing it in less than $N$ swaps, as for some initial placements it is possible to do it much faster. Can you argue for your algorithm that it acts always optimally? You should justify why every imaginable strategy needs at least as many swaps as yours.

The contest is over, you can no longer submit.

Note: You can implement and explain different approaches for the subtasks, if you want. If you find a solution for subtask 4 it is possible that you can use the same approach to solve the other subtasks as well.

Subtask 1: Only river-crossing ferry connections (total 50 points)

In this first subtask we want to study the case when it is possible to choose the docks such that all ferry connections cross the river. To do this we first simplify the task by assuming the following: If one wants to travel from city $A$ to city $B$ only using ferries (independent of the river side at the start and end), then there is exactly one or zero ways to do this. This shall hold for every pair of cities $A$ and $B$. This also includes indirect connections: If there is a connection from $A$ to $C$ and from $C$ to $B$, you can for example assume that there is no direct connection from $A$ to $B$ but also no other city $D$, that is connected to both $A$ and $B$.

Examples

Input:

1
6 4
1 2
3 4
3 5
3 6

Output:

Case #1: LRLRRR

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download Input Submit C++ Solution

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Output

Check output

Problem mit Zeilenumbrüchen?

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.

Output

Source Code

Upload

Example

Input:

1
4 4
1 2
2 3
3 4
4 1

Output:

Case #1: LRLR

Can you find a better condition that describes exactly when it is possible that all ferry connections cross the river? Describe an algorithms that solves such instances and analyze it.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download Input Submit C++ Solution

Download input again

You have 1 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Output

Check output

Problem mit Zeilenumbrüchen?

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.

Output

Source Code

Upload

Subtask 2: at least half of it river-crossing (total 50 points)

Now let’s get rid off all conditions and let’s look at an arbitrary set of ferry connections. Mouse Stofle already found an example, where it is not possible to let all connections cross the river:

Example

Input:

1
4 4
1 2
2 3
1 3
2 4

Output:

Case #1: LRRL

However you pick the docks at most three of the four connections will cross the river.

Stofl claims that it is possible to always pick the docks, such that at least half of all connections cross the river for any set of ferry connections. Is that really true? Can you find an algorithm that does that and can you argue why?

1
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Case #1: LRLRL

The game

There are in total $A$ auctions. During each auction $D$ diamonds are auctioned. (This allows your program to analyze the strategies of the other programs and to develop a counter strategy). In each auction you have $G$ gold nuggets you are allowed to spend.

An auction consists of $D$ bid rounds. In each of those rounds each player bids covered his bid $B$ (i.e. the other players don’t know what your bid is). The player with the highest bid receives a diamond. If multiple players have the same highest bid then the diamonds will be sawed up resulting in one piece of the same size for every of those players. Every player has to pay their bid every round no matter who won. The sum of all bids of one player during one auction may not exceed $G$.

Input / Output

Your program will be started by a game server. It has to read from stdin and output the moves to stdout.

On game start you receive one line with four space separated integers: $N$, the number of players (incl. your program); $A$, the number of auctions; $D$, the number of bid rounds per auction (which corresponds to the number of diamonds); and $G$, the number of gold nuggets per auction you are allowed to spend.

Afterwards $A$ auctions are played. In each there are $D$ bid rounds. A bid round looks like this:

1. You output an integer $B$, the amount if gold nuggets you want to bid on the active diamond. 1. You receive one line with $N-1$ space separated integers, the bids of the other players for the active diamond. The order of the players stays the same during the whole game.

As soon as $A$ auctions were played your program should exit.

Examples

> 3 1 3 1000
< 100
> 20 80
< 50
> 70 80
< 25
> 120 80

Explanation: There are 3 players in total. In the first round you bid 100 gold nuggets, the other two players bid 20 and 80 gold nuggets respectively. You receive one diamond. After the three rounds each player owns one diamond.

Constraints

• $2 \leq N \leq 10$
• $1 \leq A \leq 1000$
• $1 \leq D \leq 1000$
• $1 \leq G \leq 10^{9}$

Evaluation

The evaluation for the creativity task is different from the one for the other tasks. You get

• 30 % of the points for a program which plays the game correctly i.e. it respects the rules and plays at least as good as the sample bots.

  Important: It is not allowed to simply submit the code of a sample bot. However it is allowed and recommended to use them as an example how to properly perform input/output in your programming language.

• The remaining 70% of the points will be rewarded according to the performance during the tournament on the SOI day.

So please optimize your program not only so that it wins against the sample bots, then we will also test it against the submissions of the other participants.

This year you are allowed to submit multiple programs (maximum 3 per participant) and your best program will be used for the ranking. Bundle these programs in a zip archive and submit that. The last submission counts for this task!

This year you are allowed to submit multiple programs (maximum 3 per participant, your last 3 submissions count) and your best program will be used for the ranking. We want to encourage you with this to implement riskier strategies as well as to try out several different strategies.

Hints

For interactive tasks it is important to flush the output buffer after every round to ensure that the server can see your output.

Use the following commands:

• C/C++: fflush(stdout);
• C++: cout << flush;
• Pascal: flush(output);
• There are similar commands in other languages.

Furthermore it is important that your program does not wait for more characters than the server provides you as input. Especially spaces and line breaks in C format strings are a frequent source of errors. For example if you read the last variable of the input with scanf("\%d ", &x);, the scanf function will wait for the next char which is not a space or a line break. However you will only receive such a char after you provided your next move. To solve this use instead scanf("\%d", &x); (no whitespaces after \%d).

Sample bots, server and visualization

During the first round we will provide the following material:

• sample bots in various programming languages.
• a server program you can use to let your program compete against itself or another program.
• a visualization to view simulated games.

You can download them here.

The contest is over, you can no longer submit.