First Round SOI 2015

Overview

This contest is over.

TaskTotalSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
congress‒/100‒/10‒/30‒/40‒/20
wordchain‒/100‒/20‒/30‒/50
audio‒/100‒/20‒/40‒/40
yurt‒/100‒/20‒/20‒/30‒/30
river‒/100‒/20‒/15‒/15‒/20‒/30
bazaar‒/100‒/100

Cheese Congress (practical task)

The Kazhakh Cheese Congress (KCC) hosts mice from MM different regions of the country. The regions are numbered from 11 to NN. From each region ii, there will be visiting NiN_i experts for sheep’s cheese and NiN_i experts for goat’s cheese. The participants of the congress are traditionally hosted in ZZ two-bed rooms. ZZ is the sum of all NiN_i such that all rooms are fully occupied. The rooms are numbered from 11 to ZZ. To encourage communication, the Organizing Committee of the Kazhakh Cheese Congress (OCKCC) aims to split up the participants into rooms according to a certain scheme: In each room there should be hosted an expert for sheep’s cheese and an expert for goat’s cheese, and those two mice should be from different regions. Can you help the OCKCC to accomplish this task?

Subtask 1: Two Regions (10 points)

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

Output

For the ii-th of the TT inputs, print “Case #i:”, followed by “POSSIBLE” if splitting is possible and “IMPOSSIBLE” otherwise.

Constraints

  • 1N1,N210000001\leq N_{1},N_{2}\leq 1\,000\,000
  • T=100T = 100, i.e. there are exactly 100100 test cases

Examples

Input:

2
1 1
1 2

Output:

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

Comment:

The first example results in two two-bed rooms. One room hosts the goat’s cheese expert from region 1 and the sheep’s cheese expert from region 2 and the other room hosts the sheep’s cheese expert from region 1 and the goat’s cheese expert from region 2. The second example does not admit a splitting where no two experts from region 2 are hosted in the same room.

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 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.

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.


            

        

Subtask 2: More Regions (30 points)

For this subtask, MM 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 TT. TT test cases follow. Each test case consists of a single line with the integer MM, describing the number of regions, followed by the MM numbers NiN_i, separated by single spaces.

Output

For the ii-th of the TT inputs, print “Case #i:”, followed by “POSSIBLE” if splitting is possible and “IMPOSSIBLE” otherwise.

Constraints

  • 1M400001\leq M\leq 40\,000
  • 1Ni10000001\leq N_i\leq 1\,000\,000
  • T=100T = 100, d.h. es gibt genau 100100 Testfälle

Examples

Input:

2
3 2 1 1
3 4 2 1

Output:

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

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 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.

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.


            

        

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 TT. TT test cases follow. Each test case consists of a single line with the integer MM, describing the number of regions, followed by the MM numbers NiN_i, separated by single spaces.

Output

For the ii-th test case, print “Case #i: IMPOSSIBLE”, if there is no possible splitting. Otherwise print the line “Case #i:”, followed by ZZ lines, where the ii-th such line contains the integers AiA_i and BiB_i. Each of those lines describes the mice hosted in one of the ZZ two-bed rooms: The ii-th room hosts an expert for sheep’s cheese from region AiA_i together with an expert for goat’s cheese from region BiB_i.

There can be many different possible splittings. In this case, your program should print an arbitrary possible splitting.

Constraints

  • 1M2001\leq M\leq 200
  • 1Ni2001\leq N_i\leq 200
  • T=100T = 100, i.e. there are exactly 100100 test cases

Examples

Input:

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

Output:

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

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 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.

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.


            

        

Subtask 4: More Categories (20 points)

The OCKCC is thinking about inviting KNiK\cdot N_i mice from each region, where K1K\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=2K=2, this new scheme is identical with the previous scheme. From each region there will visit NiN_i mice from KK different categories (like experts for sheep’s cheese, goat’s cheese, spicy cheese, mild cheese, …). The categories are numbered from 11 to KK. Those mice should then be split up into KK-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 TT. TT test cases follow. Each test case consists of a single line with the integers MM and KK, the number of regions and the number of categories respectively, followed by the MM integers NiN_i, separated by single spaces.

Output

For the II-th test case, print “Case #i: IMPOSSIBLE”, if there is no possible splitting. Otherwise print the line “Case #i:”, followed by ZZ lines, where the ii-th such line contains KK integers Ri,jR_{i,j}. Each of those lines describes the mice hosted in one of the ZZ KK-bed rooms: Within the ii-th room, the expert of category jj is from region Ri,jR_{i,j}.

Constraints

  • 1M2001\leq M\leq 200
  • 1KNi4001\leq K\cdot N_i\leq 400
  • T=100T = 100, i.e. there are exactly 100100 test cases

Examples

Input:

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

Output:

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

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 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.

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.


            

        

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Word chain (practical task)

Mouse Stofl wants to compose some novel poems that consist of nice word chains. His fancy idea is that he wants to use words that occur inside other words.

A word occurs in another word if all its letters appear in the same order inside the other word. For example: “Bach” occurs in “belauschen” but not in “hab”.

Subtask 1: Two words (20 points)

At first. Stofl wants to compose a poem of length 22. 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 TT, the number of poems that Stofl wants to compose. After that TT lines, each containing two words, follow.

Output

For each of the TT 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 1000010\,000 small letters from a to z.
  • T=100T = 100, i.e. there are exactly 100100 poems.

Examples

Input:

3
bach belauschen
belauschen bach
bach dach

Output:

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.

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.

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.


            

        

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 TT, the number of poems that Stofl wants to compose. TT inputs follow, each of them structured like this: The first line contains the number NN. The next NN lines each contain a word WiW_i.

Output

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

Constraints

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

Examples

Input:

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

Output:

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.

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.

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.


            

        

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 TT, the number of poems that Stofl wants to compose. TT inputs follow, each of them structured like this: The first line contains the number NN. The next NN lines each contain a word WiW_i.

Ouptut

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

Constraints

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

Examples

Input:

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

Output:

Case #1: 4
Case #2: 1

Comment:

The only poem of length 4 in the first example is: „ah, bach, belauschen, belauschend“.

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 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.

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.


            

        

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Audio (practical task)

Stofl is listening to a boring audio file. The talker speaks very slowly and Stofl wonders, if he might shorten the long sounds, in order to be done faster.

A “sound” is an interference of waves of different periods, resulting in a new wave with a longer period.

Stofl knows from his physics class, that the period of the resulting wave is given by the smallest common multiple of the single periods.

Subtask 1: Single Interference (20 Punkte)

Given NN periods PjP_j, compute the period of the resulting wave for multiple test cases.

Input

The first line of the input contains the integer LL, the number of test cases. LL lines follow. Each line starts with an integer NN, the number of single waves. NN numbers P1P_{1} up to PNP_N follow, the single periods. Those are separated by single spaces.

Output

For the ii-th test case, print “Case #i:”, followed by the number PrP_r, the resulting period.

Constraints

  • 1N100001\leq N\leq 10000
  • It is guaranteed that 1Pr2631\leq P_r\leq 2^{63}
  • L=100L=100 i.e. there are exactly 100100 test cases

Examples

Input:

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

Output:

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

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 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.

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.


            

        

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 55 ms is playing for 124124 ms in total, it goes through 2424 full periods with a remainder of 44 ms. (124/5=24124/5 = 24, with remainder 44). The sound character would however be preserved by playing only one period and 44 ms of the remainder, therefore the section could be shortened from 124124 ms to 5+4=95+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 NN single waves, having periods PeP_e, a starting time TsT_s and an ending time TeT_e and interfere accordingly. Your task is to shorten multiple files as described above. The resulting audio files will consist of KK sections (KK may differ for different files), in a certain order. Each section consists of a certain period PrP_r and takes time TrT_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.)

Input

The first line of the input contains the number LL, the number of files to be shortened. LL files follow: Each file is initiated by a line with the number NN, the number of single waves. The following NN lines describe a single wave each: They contain for each single wave the integers PeP_e, TsT_s and TeT_e, the period, the starting time and the ending time of this single wave.

Output

You should print the resulting audio files as follows: The first line of the ii-th audio file contains “Case #i:”. The next line of a file contains two numbers KK, the number of sections of this file and TsT_s, the time at which the first section starts. The following KK lines describe the sections in the order in which they will be played. One line consists of the two numbers PrP_r and TrT_r, i.e. the resulting period and the duration of the section.

Constraints

  • 1N10001\leq N\leq 1000
  • For all single waves it holds that 0Ts<Te1090\leq T_s< T_e\leq 10^{9}.
  • It is guaranteed that 1Pr2631\leq P_r\leq 2^{63}.
  • L=100L=100 i.e. there are exactly 100100 files.

Examples

Input:

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

Output:

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

Comment:

Explanation of the first file: From time 0 to 1 only the wave with period 2 is active, which can’t be shortened. From time 1 to 20 are two waves with periods 2 and 6 active, which results in a wave with period 6. The 20=3·6+1 seconds can be reduced to 6+1=7 seconds. From time 20 to 120, the resulting period is 30 (from periods 6 and 30), so the 100=3·30 + 10 seconds can be reduced to 30+10=40. From 120 to 150 only the wave with period 6 is active, which can be reduced to 6 seconds.

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 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.

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.


            

        

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 ii-th section of the file, print PrP_r modulo MM, where M=109+7=1000000007M=10^{9}+7=1000000007 and PrP_r is the period of the ii-th section of the file. aa modulo bb corresponds to the positive integer remainder of the division of aa by bb. In other words, 0a0\leq a modulo b<bb<b, and if aa modulo b=cb = c, then there is an integer dd such that a=db+ca=d\cdot b+c.

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

Input

The first line of the input contains the number LL, the number of files. LL files follow: Each file is initiated by a line with the number NN, the number of single waves. The following NN lines describe a single wave each: They contain for each single wave the numbers PeP_e, TsT_s and TeT_e, the period, the starting time and the ending time of the single wave.

Output

The first line of the ii-th output contains”Case #i:”. The next line of a file contains the two numbers KK, the number of sections of this file and TsT_s, the time at which the first section starts. The following KK lines describe the sections in the order, in which they are played. A line consists of the single number PrP_r modulo MM, i.e. the resulting period modulo MM.

Constraints

  • 1N100000001\leq N\leq 10\,000\,000
  • For all single waves, it holds that Pe220P_e\leq 2^{20} and 0Ts<Te1090\leq T_s<T_e\leq 10^{9}.
  • L=100L=100 i.e. there are extactly 100100 files

Input:

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

Output:

Case #1:
3 1
0
2
3

Grading

Since the input file for this subtask is huge, we will correct this task by hand. In order to allow you to test your solution on small inputs, we still provide a judging system. Please note, that the automated response is not final and you will be awarded points (if any) only after the submission deadline.

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 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.

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.


            

        

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Yurt (theoretical task)

The nomadic people in Kazakhstan often live in yurts. A yurt is a traditional, big, round tent. On your trip you discovered a big campground. It has NN spots, numbered from 11 to NN. On each spot, exactly one yurt is located. Also the yurts are numbered from 11 to NN, such that a yurt and a spot always go together. But the yurts got mixed up as they were assembled in a hurry in the middle of the night. Now not necessarily all yurts are standing on the spot with the same number. Your task is to sort the yurts, so that they are in the right order again. You can do this step by step, always tearing down, switching and reassembling two yurts in each step. You can never dismount more than two yurts at once, so only swap two yurts at a time. Your goal is to use as few swaps as possible to bring the yurts into the correct order.

This task consists of four subtasks, two practical ones (1, 2) and two theoretical (3, 4). For the practical subtasks you have to write a program that solves the task and you can test it directly on the site and get immediate feedback. For the theoretical tasks we expect an explanation and justification of your solution in text form. Try to convince you and us that your idea really works. Your solution for theoretical tasks does not have to contain a complete compilable program. A precise explanation for example with pseudo code is sufficient. Also analyze your runtime and memory complexity and justify why your program always terminates.

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

In this subtask the campground includes at most 88 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 NN swaps for NN 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 NN swaps are always sufficient in subtask 3.

Input

The first line contains the number TT, the number of test cases. The following TT lines each describe a test case. Each line starts with NN the number of yurts, followed by NN space-separated numbers, M1M_{1} to MNM_N, where MiM_i is the number of the yurt, that is place on spot ii initially.

Output

For each test case print one line with a possible sequence of NN or less swaps. For the tt-th test case start the line with “Case #t:”, followed by an even number of space-separated numbers MiM_i. These numbers mean that in your ii-th swap the yurt on spot M2i1M_{2i-1} get interchanged with the yur on spot M2iM_{2i}. (Example: 55 22 33 66 44 33 means that the yurts on spot 55 and 22 get swaped. After that the yurts on spot 33 and 66, and finally the ones on spots 44 and 33).

Constraints

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

Beispiele

Input:

2
3 1 3 2
5 4 3 2 5 1

Output:

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

Illustration of the second example:

yurt_sample1

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 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.

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.


            

        

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

In this subtask the campground includes at most 500500 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 NN swaps for NN yurts. So your program does not necessarily need to act optimally.

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

Constraints

  • 3N5003 \leq N \leq 500, so there are between 33 and 50005\,000 yurts.
  • You are allowed to perform at most NN swaps.
  • T=100T = 100, so there are 100100 test cases.

Beispiele

Input:

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

Output:

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.

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.

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.


            

        

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

The mouse Stofl now claims, that it is always possible to bring NN yurts with strictly less than NN (so at most N1N-1) swaps into the correct order. Describe how your algorithm solves this task and explain why you need less than NN 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 NN 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.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

River (theoretical task)

In Kazakhstan there are some gigantic rivers. The river Irtysch for example is over 40004\,000 kilometers long. It originates in China, flows through Kazakhstan and leads into the Ob in Russia. Along the Irtysch there are numerous cities. They are numbered from 11 to NN. Each city has two districts, one on the left and one of the right side of the stream with a bridge that connects the two districts. Unfortunately, at a recent flooding all NN bridges collapsed.

To temporarily reestablish some connections across the river some ferries between given pairs of cities are planned. In order for the ferries to be able to land in the cities, each city has to construct exactly one dock. In each city, this dock can be built either on the left or each side of the city. Each city should have a dock, even if there is no ferry connection including it.

No new bridges across the river are planned. If one wants to cross the river one does have to use the ferry. In order for it to be as easy as possible to cross the river as many ferry connections as possible should cross the river, i.e. depart and land on different river sides. A ferry connection from city AA to city BB crosses the river for example, if the dock in AA is on the left and in BB is on the right side of the river. But if both docks are on the same side than this ferry does not cross the river.

Now the mayors of these cities have to decide on which side to construct their docks. Can you help them build their docks so that as many ferries as possible cross the river?

This task consists of a total of five subtasks, two practical (1a, 2a) and three theoretical ones (1b, 1c, 2b). For the practical subtasks you have to write a program that solves the task and you can test it directly on the site and get immediate feedback. For the theoretical tasks we expect an explanation and justification of your solution in text form. Try to convince you and us that your idea really works. Your solution for theoretical tasks does not have to contain a complete compilable program. A precise explanation for example with pseudo code is sufficient. Also analyze your runtime and memory complexity and justify why your program always terminates.

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 AA to city BB 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 AA and BB. This also includes indirect connections: If there is a connection from AA to CC and from CC to BB, you can for example assume that there is no direct connection from AA to BB but also no other city DD, that is connected to both AA and BB.

river_simplification

Subtask 1a: Implementation (20 points)

Can you write a program that constructs the docks under this simplification such that all ferry connection cross the river?

Input

The first line contains the number TT, the number of test cases. The following TT test cases are all formatted like this: one the first line there are the numbers NN and MM separated by a space, being the number of cities NN and the number of ferry connections MM. After that follow MM lines, each containing two space-separated numbers aa and bb, describing that there is a ferry connection from city aa to city bb.

Ausgabe

For each of the TT test cases output “Case #t:” followed by NN letters, each LL or RR. The letter ii-th of these letters indicates on which side the dock in city ii should get built.

Constraints

  • 1N10001 \leq N \leq 1\,000
  • 0M10000 \leq M \leq 1\,000
  • T=100T = 100

Examples

Input:

1
6 4
1 2
3 4
3 5
3 6

Output:

Case #1: LRLRRR
river_sample1a

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 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.

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.


            

        

Subtask 1b: Justification (15 points)

Please argue why your program from subtask 1a is correct? Why can you guarantee that always all connections cross the river? What is the runtime and memory complexity of your program?

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 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.

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.


            

        

Subtask 1c: Relaxation of the condition (15 points)

Your friend mouse stofl has found this new example and is surprised that it does not satisfy our condition from above (there are two paths from city 11 to city 44, either directly or through the cities 22 and 33), but it is possible that all connections cross the river nevertheless.

Example

Input:

1
4 4
1 2
2 3
3 4
4 1

Output:

Case #1: LRLR
river_sample1c

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 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.

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.


            

        

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
river_sample2a

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?

Subtask 2a: Implementation (20 points)

Write a program, that picks the docks such that at least half of all the ferry connections cross the river.

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

Constraints

  • 1N10001 \leq N \leq 1\,000
  • 0M10000 \leq M \leq 1\,000
  • T=100T = 100

Example

Input:

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

Output:

Case #1: LRLRL

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 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.

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.


            

        

Subtask 2b: Justification (30 points)

Argue why your algorithm from subtask 2a is correct. Analyze its runtime and memory consumptions.

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 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.

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.


            

        

Note: You can implement and describe different approaches for each subtask if you want, of course.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Bazaar (creativity task)

This summer mouse Stofl was in Alamaty, the biggest city in Kasachstan. He was really impressed by the bazaar where he bought some diamonds. Those diamonds are sold using a special auction: every potential buyer chooses an amount of gold nuggets he wants to bid. The highest bid gets a diamond, but everyone has to pay their bid. To make it a bit more interesting and to prevent the richest from getting all the diamonds there is an additional rule: every person is only allowed to spend a given amount of gold nuggets during an auction.

Mouse Stofl will travel again to Alamaty to cheer for the swiss IOI team. He wants to visit the diamonds auction again. Help him to buy as much diamonds as possible with the allowed amount of gold nuggets.

The game

There are in total AA auctions. During each auction DD 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 GG gold nuggets you are allowed to spend.

An auction consists of DD bid rounds. In each of those rounds each player bids covered his bid BB (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 GG.

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: NN, the number of players (incl. your program); AA, the number of auctions; DD, the number of bid rounds per auction (which corresponds to the number of diamonds); and GG, the number of gold nuggets per auction you are allowed to spend.

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

1. You output an integer BB, the amount if gold nuggets you want to bid on the active diamond. 1. You receive one line with N1N-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 AA 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

  • 2N102 \leq N \leq 10
  • 1A10001 \leq A \leq 1000
  • 1D10001 \leq D \leq 1000
  • 1G1091 \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.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Ranking

RankUsernameTotal (600)congress (100)wordchain (100)audio (100)yurt (100)river (100)bazaar (100)
loading ...