Translation of all tasks.

200. Prosjek

Slavko and Mirko learned about the mean in school today. So, related to the topic, Slavko asks Mirko some queries. There are 2 types of queries:

1)Add X into the array. What is the mean of the array now?

2)I added an element into the array and the mean is now A/B. What element did I add?

Help Mirko and answer Slavko's queries!

300. Pitagora(easy)

Find a number A given numbers B and C such that A^2+B^2=C^2. All 3 of those numbers are integers.

500. Jedi

It's the time of the First Order's uprising. The evil Kylo Ren wants to find a map that leads to the Resistance's hero, Luke Skywalker. Kylo Ren currently has an incomplete map, a matrix of size N*M filled with star systems which are rectangles filled with #. An R*S portion of the map is cut out; that part is covered with ! in the input.

Kylo Ren currently has Q possible matrixes that represent the cut out part of the map, and as he has some work to do in getting Tie/SF Fighters he asks you for help. For each possible matrix you have to determine whether the map is correct. A correct map is one where no 2 star systems share an edge and all # are a part of exactly 1 star system.

550. Cancer

The only thing you need to know are the formulas written in the statement.

560. Pranker

Ivica got a string for Easter. Sadly, his little brother played with the string a bit. In each move, he took 2 letters of the string and swapped them. Ivica's string is unstable and a letter falls out of the string if it's swapped 2 times. Ivica can predict what moves will his little brother make so he asks you to tell him what will the string look like after the modifications!

600. Sjecanje

You know the answers to the queries from the task Prosjek. Reconstruct the questions! All constraints from that task also apply here, except A,B,X<=10^6, not 100.

650. Rodjendan

Today is Ivana's birthday. On the party are N enraged children. When 2 children with angers A and B meet, violence with power of A*B arises. The total violence of the party is the sum of all violences of the pairs of children. Optimally rearrange the children into pairs such that the violence is minimized! N is even.

700. Pitagora(hard)

Find a number A given numbers B and C such that A^2+B^2=C^2. All 3 of those numbers are integers.

You can only use 28 bytes when declaring variables. If I see that you submitted a code using more than 28 bytes for declaration, i'll set the official solution to be "cout<<HiddenNumber;" and rejudge your solution,

750. Yoda

Yoda and Luke Skywalker are peacefully sitting on an infinite tree that I don't know the name of. The root of the tree has the ID 1, and each node has N children with IDs X*N, X*N+1, X*N+2, ..., X*N+N-1, where X is the ID of the parent. This is what the first 3 depths of a tree with N=3 look like:(image from statement)

Yoda was suddenly attacked by villains and Luke wants to save him. Help Luke and tell him the distance between him and Yoda!

Input: N, the ID of the node Yoda is on, the ID of the node Luke is on.

Output: The distance.

800. Supertrokuti

Ivica became interested in N-dimensional "triangles". He also likes positive integers and hates large numbers. So he wants you to make him as many "Pythagora's (N+1)-tuples"; more precisely, make integers A1, A2, ..., AN and B such that B<=X, A1^2+A2^2+...+AN^2=B^2 and A1<=A2<=...<=AN.

Input: Numbers N and K.

Output: The number of found tuples, and in each row after N+1 numbers A1, A2, ..., AN and B.

Scoring: Let's say your solution finds K tuples and the author's solution finds L tuples. In that case, if K<=L, you get (see formula from statement) points. If K>L, you get 30 points. If any of the tuples is invalid, you get 0 points.

1000. Neboder

Jambaxx wants to find a rectangle as large as possible in a city with many skyscrapers arranged in a line. If there are multiple such rectangles, choose the one with minimum max(width,height)/min(width,height). If there are still multiple possible rectangles, choose the one with the leftmost edge being as far left as possible. If there are still multiple solutions, choose the one with the smallest height.

Input: N, the number of skyscrapers and the height of each skyscraper.

Output: The area of the largest rectangle, the index of the leftmost skyscraper it passes through and the height and the width.

1100. Decimale

Darth Vader became a teacher in unknown conditions. Today Q students asked him: "What will be the mean of my marks if I get a mark Z?" By coincidence, all Q pupils have the same mean if rounded to N decimal places. To answer that question, Darth Vader needs to know the amount of marks the student has. Sadly, he doesn't know that, but he approximately knows the numerator and denominator of the decimal part of the mean. Help him find how many marks does each of his students have! If there are multiple solutions, output the minimal one.

Input: N, the mean, Q, and for each student:

A, B, C and D, A<=numerator<=B, C<=denominator<=D, sum of all D-C+1 is <=10000.

Output: In each of the Q rows, the minimum number of marks or -1 if there is no solution.

1300. Jambaxx

Jambaxx did some bad things and ended up in a black hole that teleported him into an unknown planet. In front of him are N obstacles he can step on, but he can't climb them due to the electric fence. After the obstacles Jambaxx can find a white hole that teleports him back to Earth. The obstacles are described by numbers W(width, in metres), D(distance from the start, in metres) and H(height, in centimetres). Jambaxx is constantly going forward at a speed of 1 m/s, he can jump at a speed of K m/s and the gravity of the planet is G m/s^2. In order for the white hole to be activated, Jambaxx must step on all the obstacles. He could also use some instructions, so for each obstacle tell him the leftmost x-coordinate where he can step on the obstacle. If he can't activate the white hole, tell him how many times does he need to use his magic powers to remove the rightmost obstacle.

Input: N(<=100), K(<=10^7), G(<=10^7), N times:

W, H, D(<=10^9)

Output: written in the statement.

Note 433 test cases, judging could take a long time.

1500. Sila

After a successful run from D'Qar, The Resistance has caught The First Order. After Poe Dameron jumped into the X-Wing and blew things up, he thought of an excellent plan. He sent Finn and Rose to find Master Codebreaker to help hack the Dreadnought shield passwords. By hacking, DJ found an array A of N nonnegative integers and 2 numbers, D and K. After some time, Master Codebreaker realized that the password is the number of ways to divide A into K parts such that the sum of elements in each part is less or equal to D. Master Codebreaker can solve this task, but can you?

As the password can be very large, and the shield defense isn't good enough, it's enough to output the solution modulo 10^9+7.

Input: N, K, D and A.

Output: Number of ways modulo 10^9+7.

1600. Minesweeper

This task is literally Minesweeper.

Input: N, M and K. The board is of size N*M and there are K bombs on it. 5<=N,M<=40, 1<=K<=N*M/4.

After that your program outputs the position on the board where the first "click" will happen.

Interaction:

The following repeats until otherwise stated:

The interactor prints the current state of the game; numbers say how many bombs are around the place, '*' says that your program identified the place as a bomb and '?' says that the state of the place is unknown.

Your program then prints the number of conclusions. If it's 0, your program must terminate right after printing 0.

Each conclusion consists of the row number, column number(both 0-indexed) and the conclusion which is either '.'(your program thinks the place isn't a bomb) or '*'(your program thinks the place is a bomb). If any of the conclusions is wrong, after outputting all the conclusions, instead of outputting the current state of the game, the interactor will say "Wrong" and your program must terminate.

If your program reads a state with no '?', your program must immediately terminate as the game is over.

Scoring: If there are P non-? fields at the end, you get (formula in statement) points for that test case.

In test cases worth about 10% of points, N=9, M=9, K=10.

In test cases worth about 20% of points, N=16, M=16, K=40.

In test cases worth about 25% of points, N=16, M=30, K=99.

In test cases worth about 5% of points, N,M<=8.

In test cases worth about 10% of points, N,M<=15.

In test cases worth about 10% of points, N,M<=25.

In the remaining test cases there are no additional limits.

2048. 2048

You need to play 2048. No point limit. There are 16 test cases, each with a different seed.

Interaction: First, the interactor puts a 4 and a 2 on a random place on the 4*4 matrix. The following procedure is repeated:

The interactor outputs the current state of the game. Example:

0 2 0 4

0 0 0 2

0 0 4 0

16 0 0 16

Your program outputs 'U', 'L', 'D' or 'R' that do the same thing they do in normal 2048.

Example if your program outputs R:

0 0 2 4

0 0 0 2

0 0 0 4

0 0 0 32

Then the interactor, on a random place, places a 2(75% chance) or 4(25% chance). If nothing was able to be put, the interactor outputs:

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

Then your program must terminate.

Scoring: If the sum of all numbers on the board is A, you get A/16 points for the test case.