UTPC Contest 10-06-23 Div. 2 (Beginner)
A. Noodle Restauarant
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a new noodle restaurant in town, in the shape of a square. There are $$$n$$$ tables on each side of the restaurant, totaling $$$n^2$$$ tables. For the annual inspection, the inspector wants to know what the product of the annual revenue is of all the tables on the 4 corners.

Input

The first input line will contain a single integer $$$n$$$ ($$$2 \leq n \leq 50$$$), representing the number of tables on each side of the restaurant. The following $$$n$$$ lines will each contain $$$n$$$ space-separated positive integers, representing the annual revenue of each table in the restaurant. All annual revenues will be between 1 dollar and 1000 dollars.

Output

Output the product of the annual revenue of all the tables on the 4 corners in dollars.

Examples
Input
2
7 3
5 1
Output
105
Input
3
1 3 4
3 1 4
5 7 2
Output
40

B. Noodle Tug of War
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the spirited Noodle Tug of War event, a lively gathering of noodle enthusiasts takes place, where participants engage in a thrilling match, pulling on a long, stretchy noodle. The noodle represents the central element of this exciting event, symbolizing the unity and elation that noodles bring to people of all backgrounds. The entertainment score of the event is a crucial measure of the event's liveliness and vigor.

This year, $$$N$$$ ($$$1 \leq N \leq 10^5$$$) noodle enthusiasts are participating in this event. Each enthusiast has some strength score, where the $$$i$$$-th participant has a strength score $$$1 \leq \text{Strength}[i] \leq 10^4$$$.

The entertainment score of the event is determined by the product of the sum of strengths on the left and right sides of the noodle at the chosen splitting point. As the event organizer, you would like to maximize the event's entertainment score by splitting the noodle enthusiasts into two groups at a single index.

Given the number $$$N$$$ of participants and each participant's strength score, find the maximum value of $$$ \left(\sum_{i=1}^{k} \text{Strength}[i]\right) \times \left(\sum_{j=k+1}^{N} \text{Strength}[j]\right) $$$ for any valid index $$$k$$$ (1-indexed).

Note that teams of size $$$N = 1$$$ are possible. In this case, there will be one team with a single participant with some strength $$$x$$$ and another team has no members. This event is quite uninteresting, so the score is $$$x \cdot 0 = 0$$$.

Input

The first line contains a single integer, $$$N$$$ ($$$1 \leq N \leq 10^5$$$): the number of noodle enthusiasts participating in the Noodle Tug of War.

The next line contains $$$N$$$ space-separated integers ($$$1 \leq \text{Strength}[i] \leq 10^4$$$): the strength of each noodle enthusiast.

Output

Output a single integer, the maximum possible entertainment score.

Examples
Input
5
1 2 3 4 5
Output
54
Input
4
3 2 5 1
Output
30
Note

In the first example, we have the solution $$$(1 + 2 + 3)(4 + 5) = 54$$$

In the second example, we have the solution $$$(3 + 2)(5 + 1) = 30$$$

C. Hatter's Party
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Hatter has $$$N$$$ strands of noodles, and wants to prepare some number of noodle dishes for his lunch party. The $$$i^{th}$$$ strand has flavor level $$$f_i$$$.

Each dish must have at least $$$K$$$ strands of noodles. The flavor of a dish is the maximum flavor value out of the noodle strands in the dish.

Mr. Hatter wants to know what is the maximum sum of flavors across all dishes he can prepare, assuming he prepares the dishes optimally?

Input

The first line of input contains $$$N, K$$$, the total number of noodle strands and the number of strands of noodles required to make a dish. $$$(1 \leq N \leq 10^5$$$ and $$$1 \leq K \leq N)$$$

The next $$$N$$$ lines each contain $$$f_i$$$, the flavor value of the $$$i^{th}$$$ noodle strand. $$$(0 \leq f_i \leq 10^9)$$$

Output

Please output $$$1$$$ integer, the maximum sum of flavors across all dishes Mr. Hatter can prepare.

Examples
Input
2 1
76
100
Output
176
Input
4 2
1
5
3
1
Output
8
Input
9 3
10
9
9
9
9
1
1
1
1
Output
28

D. Noodling with Knights
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After eating a bunch of noodles, the mad hatters decide that it's time to play a quick game of chess. They play a special variant of chess where the board is completely empty except for a single knight. Furthermore, they decide that this game is too boring, so they want to play on arbitrary-sized square chess boards, not just $$$8 \times 8$$$.

Given a chess board of size $$$N \times N$$$, and a knight starting at position $$$(x_1, y_1)$$$, how many steps at minimum would it take for it to reach position $$$(x_2, y_2)$$$?

If the position is not reachable, output $$$-1$$$.

Constraints:

$$$0 \lt N \lt 800$$$

$$$0 \lt x_i, y_i \lt N$$$

Input

The first line of the input will contain just one number, N. The second line will contain two integers, $$$x_1$$$ and $$$y_1$$$, the starting position of the knight. The third line will contain three integers $$$x_2$$$ and $$$y_2$$$, the end position of the knight.

Output

The output will consist of a single integer, which is the minimum number of moves the knight needs to make to reach the end position.

If the position is not reachable, output -1.

Examples
Input
1
0 0
0 0
Output
0
Input
4
1 2
2 2
Output
3
Input
9
8 2
4 1
Output
3

E. Riddle Me This (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Mad Hatter has moved past unsolvable riddles, and is now dabbling in unsolvable ciphers. On your recent trip through the looking-glass, he has presented you with a set of $$$N$$$ ciphers (which he has no idea how to solve). A cipher of length $$$s_i$$$ is a permutation of the integers $$$1..s_i$$$.

We consider a cipher solved if it is in ascending order. We can also perform an arbitrary number of rotations on these ciphers, in which we take the last element and move it to the front of the cipher. For example, here is a demonstration of how to solve this cipher:

  1. Original cipher: $$$[3, 4, 1, 2]$$$
  2. One rotation: $$$[2, 3, 4, 1]$$$
  3. Two rotations: $$$[1, 2, 3, 4]$$$, which is now in ascending order, so this cipher is solved.

However, these looking-glass ciphers have a special property: each cipher is entangled with another cipher, such that rotations performed on the first cipher will automatically be applied to the other cipher! Luckily, you've brought your looking-glass snare wand, which allows you to choose how to entangle the ciphers. Specifically, every cipher must be entangled with exactly one other cipher.

After you have entangled all ciphers, you will proceed to solve as many ciphers as you can by performing rotations on each pair of entangled ciphers. How many ciphers can you solve, if you entangle the ciphers optimally?

This is the easy version of this problem. The only difference between the two versions are the constraints on the input. In this version, $$$N \le 10^3$$$, and $$$s_1 = s_2 = ... = s_N \le 10^3$$$ (all ciphers are the same length).

Input

The first line of input will contain a single integer $$$N$$$ denoting the number of ciphers. It is guaranteed that $$$N$$$ is even. ($$$2 \le N \le 10^3$$$)

The next $$$N$$$ lines represent the ciphers, permutations of length $$$s_1,...,s_N$$$. ($$$1 \le s_i \le 10^3$$$) Each line contains $$$s_i$$$ (the length of the permutation), followed by the permutation itself. In this version, $$$s_1 = s_2 = ... = s_N$$$.

Output

Output a single integer, the number of ciphers you can solve if you provide an optimal initial entanglement.

Example
Input
4
4 1 4 2 3
4 3 4 1 2
4 2 3 4 1
4 2 3 4 1
Output
3

F. Noodles and Random Walk
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a noodle with a length of $$$0$$$ at time $$$t = 0$$$ seconds. Every second, the noodle will either grow or shrink by $$$1$$$. The noodle does this for $$$T$$$ seconds. A noodle can have negative length.

Calculate the number of ways that the maximum length of the noodle for times $$$0\leq t\leq T$$$ is exactly $$$M$$$. Output this $$$\text{mod}\: 10^9 + 7$$$.

Input

The first line contains $$$N (1\leq N\leq 10^5)$$$, the number of test cases.

Then, each of the next $$$N$$$ lines will contain two numbers, $$$T (1\leq T\leq 2000)$$$, the time that the noodle can either grow or shrink, and $$$M(1\leq T\leq 2000)$$$, the maximum length of the noodle.

Output

For each of the $$$N$$$ lines, output the number of ways that the maximum length of the noodle for times $$$0\leq t\leq T$$$ is exactly $$$M$$$ on a new line.

Example
Input
3
1 1
4 2
6 3
Output
1
4
6
Note

For the first case, we can achieve maximum of $$$1$$$ using. $$$(0, 1)$$$

For the second test case: $$$(0, 1, 2, 1, 0), (0, 1, 2, 1, 2), (0, -1, 0, 1, 2), (0, 1, 0, 1, 2)$$$.

For the third test case: $$$(0, 1, 2, 3, 2, 3, 2), (0, 1, 2, 3, 2, 1, 2), (0, 1, 2, 3, 2, 1, 0), (0, 1, 2, 1, 2, 3, 2), (0, -1, 0, 1, 2, 3, 2), (0, 1, 0, 1, 2, 3, 2)$$$

G. Spaghetti Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The infamous hat-wearing pasta-making brothers, Lario and Muigi, have decided to settle their rivalry once and for all with a game of wits – and spaghetti.

The game works as follows: Lario and Muigi take turns modifying a pile of spaghetti.

Lario goes first. Lario can make $$$n$$$ different types of spaghetti bundles, where the $$$i$$$th type of bundle contains $$$a_i$$$ strands of spaghetti. On his turn, Lario can choose a type of spaghetti bundle to make, adding $$$a_i$$$ strands to it.

Muigi is trying to assemble his own $$$m$$$ types of spaghetti bundles, where the $$$j$$$th type of bundle contains $$$b_j$$$ strands of spaghetti. On his turn, Muigi can take $$$b_j$$$ strands from the pile to assemble a spaghetti bundle of his own, as long as the pile has at least $$$b_j$$$ strands to begin with.

Note that either brother can choose to skip their turn by adding or removing $$$0$$$ strands from the pile.

The game lasts 100 rounds. If Lario can get the pile to have at least $$$t$$$ strands of spaghetti in that time, then he wins the spaghetti game. Otherwise, Muigi wins, having successfully stopped Lario.

Here's where you come in: You are the maddest hatter, and have the ability to mind control anyone wearing a hat. You don't really care which brother comes out on top, but you do love chaos and winning. In fact, you're set on taking over one of Lario and Muigi, and leading them to victory. Are you up to the task?

Note that this is an interactive problem, which has different input / output format. Read below for details.

Interaction

The first line of input contains three integers, $$$n$$$, $$$m$$$, and $$$t$$$ ($$$1 \leq n, m, t \leq 100$$$). $$$n$$$ and $$$m$$$ are the number of Lario's bundles and Muigi's bundles, respectively. $$$t$$$ is the number of strands in the pile for Lario to win.

The second line contains $$$n$$$ integers, $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$), representing the number of strands in each of Lario's bundles.

The third line contains $$$m$$$ integers, $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_j \leq 100$$$), representing the number of strands in each of Muigi's bundles.

Afterwards, your program should output either "Lario" or "Muigi", depending on which brother you would like to take control of. To pass the test case, you must win as your chosen brother.

Then, you will play the spaghetti game with the judge. When it is your turn, you must output a single integer on its own line; if you are Lario, it must be some $$$a_i$$$ (or $$$0$$$), and if you are Muigi, it must be some $$$b_j$$$ (or $$$0$$$). Otherwise, you will receive Wrong Answer as a verdict. When it is the judges turn, they will output one of $$$a_i$$$ (or $$$0$$$) if they are Lario, or one of $$$b_j$$$ (or $$$0$$$) if they are Muigi.

The game will automatically end once the pile has at least $$$t$$$ strands, or 100 rounds have passed (that is, both Lario and Muigi have each taken 100 actions). Your program should terminate once this happens, otherwise you may get undefined verdicts.

Remember to flush your output after printing each move. This can be done with cout.flush() in C++, System.out.flush() in Java, and stdout.flush() in Python.

Example
Input
3 3 20
3 6 15
2 8 15


0

8

2
Output
Lario
6

6

3

15
Note

In this example, you control Lario. The game plays as follows:

  • Lario adds 6 strands to the pile. The pile has 6 strands of spaghetti.
  • Muigi skips his turn. The pile has 6 strands of spaghetti.
  • Lario adds 6 strands to the pile. The pile has 12 strands of spaghetti.
  • Muigi removes 8 strands from the pile. The pile has 4 strands of spaghetti.
  • Lario adds 3 strands to the pile. The pile has 7 strands of spaghetti.
  • Muigi removes 2 strands from the pile. The pile has 5 strands of spaghetti.
  • Lario adds 15 strands from the pile. The pile has 20 strands of spaghetti, so Lario wins.