First Round SOI 2017

Subtask 1: Warm up (25 points)

Mouse Amir always starts with an easy task. He picks two random numbers: $n_{0}, n_{1}$ and a target value $R$. Amir now tests if he can reach the value $R$ by adding the two numbers or subtracting the second number from the first number.

3
2 5
2 3
2 5
8 3
2 6
2 8

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

Subtask 2: One subtraction (25 points)

Mouse Amir is quite good at mental arithmetics. Adding a few dozen numbers is a piece of cake. However, he doesn’t like to subtract numbers. As before, he thinks of a series of numbers and tries to insert an operator between them. Using all numbers, is it possible to reach $R$ with at most one subtraction?

3
2 5
2 3
3 5
3 8 10
3 5
8 3 10

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

Subtask 3: Two subtractions (25 points)

Mouse Amir realises that with more subtractions it is more likely to build an equation. As before, he thinks of a series of numbers and tries to insert an operator between them. Using all numbers, is it possible to reach $R$ with at most two subtraction?

2
3 5
16 8 3
3 8
16 10 2

Case #1: YES
Case #2: YES

Subtask 4: Countless possibilities (25 points)

Mouse Stofl learns about Amir’s game and they start playing it together. Unlike the previous tasks, the number of subtractions is unlimited. As before, all the numbers have to be used.

Mouse Stofl is a MOI (Mouse Olympiad in Informatics) participant. By reading the provided scripts and attending the workshops he learned about an elegant solution.

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

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

Subtask 1 (20 points)

You have to choose $C$ times a superhero on which the device is applied. You can choose one hero several times.

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Case #1: 15
Case #2: 15
Case #3: 17

Subtask 2 (20 points)

You have to choose exactly $C$ different superheroes.

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Case #1: 15
Case #2: 9
Case #3: -3

Subtask 3 (20 points)

You have to choose $C$ continuous heroes on which the device should be applied. The heroes stand in a line which means the first and the last one are not neighbors.

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Case #1: 5
Case #2: 9
Case #3: -3

Subtask 4 (20 points)

You can choose any number of continuous superheroes.

3
5 4 -3 1 2 -7
5 1 2 3 4 5
5 -7 1 2 3 4

Case #1: 11
Case #2: 15
Case #3: 17

Subtask 5 (20 points)

Same as subtask 4 but there are more superheroes.

Subtask 1: At most one move (10 points)

All cups are either red or blue. Stofl needs to put all red cups to the left of the blue cups. Is it possible with $\le 1$ move? The colors red and blue are represented by the numbers 0 and 1 in the input.

3
5
0 0 1 0 1
5
1 1 1 0 1
4
0 0 0 0

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

Subtask 2: Two colors (20 points)

Again, all cups are either red or blue and Stofl needs to put all red cups to the left of the blue cups. But this time he wants to know the minimum number of swaps he needs to perform.

3
5
0 0 1 0 1
5
1 1 1 0 1
4
0 0 0 0

Case #1: 1
Case #2: 3
Case #3: 0

Subtask 3: Different colors (20 points)

This time each cup has a different color, and Stofl needs to order them like the rainbow. For the numbers in the input, this means that he needs to sort them in increasing order.

2
3
10 5 6
4
1 2 4 3

Case #1: 2
Case #2: 1

Subtask 4: General case (20 points)

Everything is the same as in subtask 3, except that there can be multiple cups of the same color.

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

Case #1: 3
Case #2: 2

Subtask 5: Many cups (30 points)

Now, Stofl needs to order a huge amount of cups. The desired order is as in subtasks 3 and 4.

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

Case #1: 3
Case #2: 4

Subtask 1: Small Values with Termination Guarantee (10 points)

Compute the result of funny(a, b) for a few small input values. It is guaranteed that funny(a, b) returns a result for all values $(a,b)$ given in the input.

Input

The first line of the input contains a number $T$, the number of pairs $(a,b)$ that you should compute funny(a, b) for. $T$ lines, follow, each containing two integers $a$ and $b$, separated by single spaces.

Output

Print one line in the format “Case #i: R” for each test case, where $i$ is the number of the test case (the first test case is assigned the number $i = 1$), and $R$ is the result of funny(a, b).

3
1 2
20 11
100 64

Case #1: 1
Case #2: 9
Case #3: 36

Subtask 2: Small Values (10 points)

Compute the result of funny(a, b) for a few small input values. If for any reason, funny(a, b) does not return a result for certain input values $(a,b)$, print “NOTHING” instead. (Hence, in this case, R is not necessarily a number.)

Input

As in subtask 1.

Ausgabe

As in subtask 1, except that now “NOTHING” is an allowed result.

3
1 3
20 12
100 65

Case #1: 1
Case #2: 8
Case #3: NOTHING

Subtask 3: Larger Values with Termination Guarantee (10 points)

Compute the result of funny(a, b) also for larger input values now. It is guaranteed that funny(a, b) returns a result for all values $(a,b)$ given in the input.

Input

As in subtask 1.

Output

As in subtask 1.

3
1124615 3132478
20239832878787237 12563819465217352
1000000000000000000 18014398509481984

Case #1: 1124615
Case #2: 7676013413569885
Case #3: 9208081978490880

Subtask 4: Theoretical Justification for Subtask 3 (25 points)

Explain why your solution for subtask 3 is correct for all nonnegative integers $(a,b)$ (such that funny(a, b) returns a result). (Note that this means you also need to justify the correctness of your solution for numbers that exceed $10^{18}$.) Also analyze the running time of your solution. Try to keep the formulation of your arguments as clear and precise as possible. We don’t expect a strictly rigorous mathematical proof, but your arguments should be founded and build on each other.

For this theoretical subtask, you should assume that the data type long long can represent arbitrary integers, but also that the basic operations (such as <, <=, +, -, *, /, %, & and =) can be executed in constant time none the less.

For this subtask, you can only obtain points if your solution for subtask 3 is correct for all $(a,b)$ (where $a\ge 0$ and $b\ge 0$ are such that funny(a, b) returns a result), and if it has a running time of at most $\mathcal O(\log a + \log b)$. (You can submit for subtask 3 arbitrarily often, and we only consider the last correct submission, hence it is not an issue if your first solution to subtask 3 does not satisfy those criteria initially. For this subtask, we will only correct the last submission.)

Solutions that do not run in constant time will not score all points for this subtask.

The contest is over, you can no longer submit.

Subtask 5 (10 points)

Compute the result of funny(a, b) for large input values. If for any reason, funny(a, b) does not return a result for certain input values $(a,b)$, print “NOTHING” instead. (Hence, in this case, R is not necessarily a number.)

Input

As in subtask 2.

Ausgabe

As in subtask 2.

3
1124615 3132479
20239832878787237 12563819465217353
1000000000000000000 18014398509481985

Case #1: 1124615
Case #2: 7676013413569884
Case #3: NOTHING

Subtask 6 (35 points)

Explain why your solution for subtask 5 is correct for all nonnegative integers $(a,b)$. (Note that this means you also need to justify the correctness of your solution for numbers that exceed $10^{18}$.) Also analyze the running time of your solution. Try to keep the formulation of your arguments as clear and precise as possible. We don’t expect a strictly rigorous mathematical proof, but your arguments should be founded and build on each other.

For this theoretical subtask, you should assume that the data type long long can represent arbitrary integers, but also that the basic operations (such as <, <=, +, -, *, /, %, & and =) can be executed in constant time none the less.

For this subtask, you can only obtain points if your solution for subtask 5 is correct for all $(a,b)$ (with $a\ge 0$ and $b\ge 0$), and if it has a running time of at most $\mathcal O(\log a + \log b)$. (You can submit for subtask 5 arbitrarily often, and we only consider the last correct submission, hence it is not an issue if your first solution to subtask 5 does not satisfy those criteria initially. For this subtask, we will only correct the last submission.)

Solutions which take only constant time except for computing $x$ score more points than solutions that do not have this property. Full score is only given to solutions whose total running time is in $o(\log(\min(a,b)))$ (i.e. solutions whose running time grows strictly more slowly than logarithmic).

The contest is over, you can no longer submit.

Subtask 1: Two page thesis (10 points)

Determine whether Stofl can submit a dissertation thesis that has at least two pages.

3
6
1 3 5 4 2 6
3
3 1 2
2
2 1

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

Subtask 2: Longest thesis (20 points)

Determine the maximum number of pages that Stofl can submit.

3
6
1 3 5 4 2 6
7
5 6 1 3 4 2 7
2
2 1

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

Subtask 3: All the possibilities (20 points)

In Subtask 2 you helped Stofl compute the maximum number $M$ of pages he can submit. He is going to do exactly that: he wants to submit a thesis that has exactly $M$ pages. Sometimes there can be multiple ways to produce a valid $M$-page thesis. Compute how many theses can Stofl choose from.

3
6
1 3 2 5 4 6
7
5 6 1 3 4 2 7
2
2 1

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

Subtask 4: Reconstruction (20 points)

Stofl has already submitted his thesis. He remembers that the printout had $N$ pages. He also remembers that he did exactly what we described above: he removed some (possibly zero) pages to produce the longest possible valid thesis. The last thing he remembers is the value $K$ you computed in subtask 3 – the number of possibilities he had when choosing which pages to keep. (He remembers the exact value $K$, not the value $(K \textvisiblespace\mathrm{mod}\textvisiblespace (10^{9}+ 7))$.)

Stofl would now like to reconstruct the printout he got at the very beginning. Help him: find some permutation of the pages $1,2,{\dots},N$ such that there are exactly $K$ ways to create the longest possible valid thesis.

3
6 4
7 1
2 2

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

Subtask 5: Reconstruction with Few Pages (30 points)

A few years later Stofl thinks back the story of Subtask 4, where he tried to reconstruct the printout. He still knows $K$ (the number of possibilities he had when choosing which pages to keep), but he can’t remember the value of $N$.

Given only $K$, he wants to find some $N$ such that there is a permutation of the pages $1,2,{\dots},N$ that has exactly $K$ ways to create the longest possible valid thesis. But not only that, he wants to find a small value for $N$.

This is a theoretical subtask.

Describe an algorithm that takes a value $K$ and produces a value $N$ and some permutation of $1,2,{\dots},N$ that has exactly $K$ longest possible valid theses. Explain why it is correct and what it’s time and space complexity is.

Then analyze how $N$ depends on $K$. Let’s define the function $f(K)=N$ as the result of your algorithm. In order to score points, your function has to satisfy $f(K) \le C\cdot\log(K)+D$ some constants $C$ and $D$. Pick some values for $C$ and $D$ and prove that the inequality holds. (Formulated differently $f$ satisfies $f(K)=\mathcal O(log(k))$ and we are interested in $C=\max (f(K)/log(K))$.) Try to make your $C$ as small as possible.

The contest is over, you can no longer submit.

Task

Write a program to control the ships of mouse Stofl or the submarines of mouse Joël respectively. There will be two programs playing against each other: one of them controls the ships and the other one the submarines.

The map we play on is given as a rectangular grid. Each field is water or land. Additionally some water fields are marked as starting points or destination points. On each field there is at most one object (= ship or submarine) per player.

Each ship starts on a starting field and each submarine starts on a destination field. The goal of the player controlling the ships is that as many ships as possible reach any destination field. The goal of the other player (controlling the submarines) is to prevent the ships from reaching a destination point by sinking them.

The two players take turns and the ships start. In each turn each object can perform exactly one action:

• Stay.
• Move. The Euclidean distance between the two fields can be at most $r_m$ (i.e. $(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_m^{2}$) and the destination field has to be free. It is allowed to jump accros land tiles.
• Attack (only submarine). The Euclidean distance between the submarine and the attacked field can be at most $r_a$ (i.e. $(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_a^{2}$).

The submarines can see a ship only if the ship is at most $r_v$ away from the submarine. The ships can see a submarine only if the the submarine sunk a ship in this turn. If a submarine attacks a field on which a ship is located the ship will sink immediately. If a ship lands on a destination field it disappears immediately and other ships can land in the same turn on the same field. Sunken ships as well as ships located on a destination field can’t be moved or attacked anymore.

Protocol

The communication between program and server is handled using Stdin / Stdout. All coordinates are 0-based and the origin is in the top left corner. The y-coordinates get bigger going down.

At the start the program receives general information about the game:

One line with $m$ $s$ $t$ $r_m^{2}$ $r_v^{2}$ $r_a^{2}$: the side $m$ it should control (0 = ships, 1 = submarines), the number of ships $s$, the number of submarines $t$, the three radii for moving, viewing and attacking each squared (you get the distances squared such that you can calculate only using integers instead of decimal numbers: $(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_m^{2}$). On the next line there is $w$ $h$, the width $w$ and the height $h$ of the map. This is followed by $h$ lines with $w$ characters each (# = land, . = water, s = starting field, d = destination field).

Afterwards the program prints for each of its objects (= ship or submarine) a valid starting field $x$ $y$ (i.e. a field s for a ship and a field d for a submarine), one object per line (i.e. $s$ or $t$ lines).

The protocol depends on the side the program plays for the turns. At the End of the game you will get -1 for $s_l$ or $s_v$ respectively and your program should exit correctly.

To display a debug point you can print D x y anytime. Such an output is of course not an action.

Limits

• $0 \le m \le 1$
• $1 \le s, t \le 1000$
• $1 \le r_m, r_v, r_a \le 10^{6}$
• $2 \le w, h \le 1000$

Your program should finish a game with this limits within a “reasonable time” (i.e. within minutes and not hours). Takes a program too long to come up with an answer it loses the current game.

Sample

> 1 10 2 9 25 9
> 100 100
[...]
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss.............................................dddd.............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss.............................................dddd.............................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
[...]
< 52 49
< 49 52
> 0
< M 54 47
< M 47 52
> 0
< M 51 47
< M 47 55
[...]
> 1
> 49 37
< M 49 44
< M 52 65
[...]
> 0
< M 52 47
< M 49 70
> 1
> 50 43
< M 52 45
< M 50 68
> 2
> 51 44
> 50 43
< A 51 44
< M 51 68
> 1
> 49 42
< M 53 45
< M 50 67
[...]
> 0
< M 26 65
< M 45 73
> 0
< M 25 64
< M 47 75
> 0
< M 23 66
< M 49 75
> -1

Subtask 1: find a path (25 points)

We forget about mouse Joël for the moment and we only help mouse Stofl. Write a program that can steer all ships to the destination. The submarines won’t attack. Use :SUB1 as a submarine command to test your program.

Use the following settings in submarine.txt:

map path/to/downloaded/map.txt
log logconfig.txt
ship_count 10
submarine_count 3
ship_command path/to/your/program.exe
submarine_command :sub1
radius_move 9
radius_view 25
radius_attack 9
time_limit 50
round_limit 10000
sleep_time 100
---

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: destroy all ships (25 points)

Now we want to help mouse Joël. All ships move randomly and won’t move on a destination field. Destroy all ships. Use :SUB2 as a ship command to test your program.

Use the following settings in submarine.txt:

map path/to/downloaded/map.txt
log logconfig.txt
ship_count 10
submarine_count 3
ship_command :sub2
submarine_command path/to/your/program.exe
radius_move 9
radius_view 25
radius_attack 9
time_limit 50
round_limit 10000
sleep_time 100
---

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: creativity tournament (50 points)

You play against the other participants of the SOI. At SOI-Day the programs will compete in a tournament to determine the best one. Your program has to be able to play both sides.

You can find the played tournament here.

The contest is over, you can no longer submit.

Maps

To test your program we added a few maps to the server. Those maps are not necessarily the ones we use for the tournament.

Tips

It is important for interactive tasks to flush the output buffer after every turn to make sure the server can see your output.

Use the following commands:

• C/C++: fflush(stdout);
• C++: cout << flush; (not necessary if you read afterwards)
• Pascal: flush(output);
• There are similar commands in other languages.

Furthermore it is important that you don’t wait for more characters than the server gives you as an input. For example spaces or line endings in C format strings are a common source for errors. For example if you read the last variable in the input with “scanf("%d ", &x);” it will wait for the next character that is not a space or a line break. You will receive such a character only after you printed your next turn. To solve this use “scanf("%d", &x);” instead (no non-printable characters after the “%d”).

Sample bots, server and visualization

During the first round we provide the following material:

• Sample bots in different programming languages.
• A server program you can use to test your program against your own or other programs.
• A visualization to display simulated games.
• Some maps to test your bot.

You can download them here.

Quick start

To run the server you need Java (version 7 or higher). The server program is located in the file submarine.jar and the remaining files are configuration files, sample maps and sample bots.

If you double click on submarine.jar the game as specified in submarine.txt will be simulated. You can start the server using a console (Windows: cmd, Mac: terminal, Linux: Shell) to be able to pass arguments (java -jar submarine.jar arguments). You can find the available arguments (and many more information) in the file usage.md.

You can adjust most settings in the file submarine.txt like for example which program you want to execute. Most of them should be easy to understand but you can find more information in usage.md.

FAQ