A. Perfectionist
Xotira: 131 MB, Vaqt: 2000 msThere are n points on the plane. You can move a point from a coordinate \((x_1, y_1) \) to the coordinate \((x_2, y_2)\) за стоимость, равную \(\sqrt{(x_1 - x_2)^2 + (y_1 - y_2) ^ 2}\)
Your task is to minimize the total cost of moving all points in such a way that they lie on the same straight line. Note that you can move the points in any way you like.
The first line contains an integer \(n\) — number of points \((2 <= n <= 10^3)\). Next in \(n\) the lines list the coordinates of these points\(x_i\)and \(y_i\) — integers, modulo not exceeding \(10^6\)
Print the minimum total distance to which the points should be dragged, with an absolute or relative error of no more than \(10^{-6}\)
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 0 0 0 1 1 1 1 0 |
1.414214 |
B. The last game
Xotira: 64 MB, Vaqt: 2000 msBefore the start of the NERC 2022 championship, Rafael decided to distract his teammates Shahzod and Akmal. Since they were very nervous, Rafael came up with a game: he drew on a grid notebook 2 * n points with integer coordinates. Shahzoda and Akmal take turns coloring the points: Shahzoda paints them white, and Akmal paints them black. After they color all the points, they count their scores. Each player receives a number of points (a real number) equal to the sum of pairwise distances between the points colored with their color. The winner is the one who scores more points. It is assumed that the players play optimally. You need to output the difference between the number of points of the winner and the loser.
The first line contains a natural number n (1≤n≤500).
The next 2∗n lines contain the coordinates of points (x1,y1),(x2,y2),...,(xn,yn) with integer coordinates, where the absolute value of each coordinate does not exceed \(10^3\).
Print the difference between the number of points of the winner and the loser. The difference in points should be displayed with three digits after the decimal point.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 0 0 0 1 1 0 1 1 |
0.000 |
| 2 |
2 0 0 1 0 0 3 1 5 |
1.937 |
C. Degrees
Xotira: 130 MB, Vaqt: 2000 msFind the number of integers lying on the interval [A,B] that can be represented as the sum of exactly Y distinct powers of an integer X, where both X and the powers are integers.
For example, for A=15, B=20, Y=2, and X=2, the answer is 3 because:
\(17=2^4+2^0\)
\(18=2^4+2^1\)
\(20=2^4+2^2\)
The first line contains two integers A and B \((1 <= A <= B <= 2^{31} - 1)\). The next two lines contain integers \(Y\) and \(X\) \((1 <= Y <= 20, 2 <= X <= 10)\)
Print a single integer - the answer to the problem.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
15 20 2 2 |
3 |
D. Vectors
Xotira: 130 MB, Vaqt: 2000 msYou are given m vectors in n-dimensional space. Additionally, you are aware of the costs associated with each vector. Your task is to select n linearly independent vectors with the minimum total cost.
The first line contains two integers m and n, where 3≤n≤50 and n≤m≤2000.
The following m lines contain vectors. All coordinates of the vectors are integers, with absolute values not exceeding 2000.
The next m lines contain numbers ci, the cost of the i-th vector. The costs are positive integers, not exceeding 15000.
If it is not possible to select n linearly independent vectors, output 0. Otherwise, output the minimum sum of n linearly independent vectors.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 3 1 0 0 0 1 0 0 0 1 0 0 2 0 0 3 10 20 30 10 10 |
40 |
E. Beautiful numbers
Xotira: 32 MB, Vaqt: 2000 msA four-digit number \(ABCD \) is beautiful if \(AB^2 + CD^2 \)when divided by \(7\) gives a remainder of \(1\).
For example, the number \(2843 \) is beautiful because
\(28^2 + 43^2 = 2633 = 376 * 7 + 1.\)
You are given \(t\) four-digit numbers, print \(YES \)for each number if the number is beautiful and \(NO\), otherwise
The first line contains a natural number \(t (1 ≤ t ≤ 10^4)\). Then there are t four-digit numbers.
If the number is nice, print \(YES\), otherwise \(NO\).
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 2843 8243 0100 |
YES NO YES |
F. Dunes
Xotira: 32 MB, Vaqt: 1000 msGeographer Grigory Georgievich is studying the formation of sand dunes. He chose a very long dune and divided it into a huge number of sections, numbering them from \(1\) to \(10^9.\) Grigory Georgievich's theory states that initially the height of the sand relative to some arbitrary mark on all sections was zero. After that, there were n strong gusts of wind that could alter the landscape. Wind gust number \(i\) had a force of \(x_i\) and acted on sections from \(l_i\) to \(r_i\). As a result of this gust, the height of section number \(l_i\) increased by \(x_i\), the height of section number \(l_i+1\) decreased by \(x_i\), the next one increased again by \(x_i\), and so on until section number \(r_i\), inclusively. Knowing all the information about all \(n\) gusts of wind, Grigory Georgievich wants to determine the final stabilized height of some m sections that interest him. Help him
The first line of the input file contains two natural numbers \(n\) and \(m\) \((1≤n,m≤1000)\) — the number of wind gusts and the number of sections whose final height interests Grigory Georgievich. Each of the next \(n\) lines contains the description of the next wind gust — three integers \(l_i,r_i,x_i (1≤l_i≤r_i≤10^9; 1≤x_i≤1000)\). Each of the next \(m\) lines contains an integer \(q_i (1≤q_ i≤10^9)\) — the number of the section for which its final height needs to be determined. The section numbers are given in increasing order.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 6 1 6 7 3 7 2 1 2 3 6 7 8 |
7 -7 9 -9 2 0 |
G. The first game
Xotira: 132 MB, Vaqt: 3000 msOn the physical education class, first-graders Petia and Vasia are playing an exciting game. In front of the kids, there are \(n\) pillars of different heights. The boys have \(m\) rings, which they throw onto the pillars one by one, with Petia starting first. The boys found out that Petia can throw a ring onto a pillar only if the height of that pillar is not less than \(l_1\) and not greater than \(r_1\). He cannot throw a ring onto a pillar that is too high or too low. However, if the pillar has a suitable height, the throw is guaranteed to be successful. Similarly, Vasia can throw a ring only onto pillars with a height not less than \(l_2\) and not greater than \(r_2\), and he guarantees success on any such pillar. Phys-ed teacher Andrey Sergeevich promised to give an "A" grade to the one of the boys who throws more rings onto the pillars by the end of the game. Help the boys figure out who will win with optimal play.
There are two integers in the first line of the input file \(n\) и \(m\) — the number of columns and rings, respectively \((1 ≤ m ≤ n ≤ 10^5 )\). Сthe next two lines contain numbers \(l_1, r_1\) и \(l_2, r_2\) — the minimum and maximum height of the columns on which Petya and Vasya can throw rings, respectively\((1 ≤ l_1 ≤ r_1 ≤ 10^9 , 1 ≤ l_2 ≤ r_2 ≤ 10^9 )\). The last line contains \(n\) the numbers describing the height of the columns, the height of each column is a positive integer and does not exceed \(10^9\).
In the output file, output "Petya" if Petya wins, "Vasya" if Vasya wins, or "Draw" if, with optimal play, both boys throw an equal number of rings on the columns.
In the first example, Petya first throws the ring onto a column of height 2. In response, Vasya can throw a ring on columns 3 or 4 high, but whichever one he chooses, Petya will throw a third ring on a column 1 high and win — he threw 2 rings, and Vasya only one. In the second example, each player can throw a ring on any column, so both will throw two rings and the game will end in a draw. In the third example, Petya throws the ring on one of the two columns available to him with the first move, and Vasya throws the ring on the second of these columns with the second move. Now Petya has no columns on which he can throw the ring, he throws the third ring, but does not hit. Vasya throws the last ring on any of the columns of height 3 or 4.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 3 1 2 2 4 1 2 3 4 |
Petya |
| 2 |
4 4 1 4 1 4 1 2 3 4 |
Draw |
| 3 |
4 4 1 2 1 4 1 2 3 4 |
Vasya |
H. Merlin
Xotira: 132 MB, Vaqt: 3000 msOne day, returning to his tower, Merlin discovered that Morgana had put a curse on all his vessels with the elixir of wisdom. Merlin knows how to remove the curse, but the appropriate spell requires that all vessels to which it is applied have an equal amount of elixir. To achieve this, Merlin decided to act as follows. He selects several vessels and pours the entire elixir from the selected vessels into the remaining ones. He can distribute the transfused elixir between the remaining vessels in any way. After all the elixir has been removed from the selected vessels, Merlin breaks the emptied vessels (the curse can no longer be removed from them), throws out the fragments and applies a curse removal spell to the remaining vessels. Help the wizard find out what is the smallest number of vessels he will have to break in order to remove Morgana's curse.
The first line of the input file contains a number \(n (2 ≤ n ≤ 10^5 )\) —the number of vessels. The second line contains\(n\) numbers\(a_1, a_2, . . . , a_n (1 ≤ a_i ≤ 10^9 )\)— the number of liters of the elixir of wisdom in each vessel.
Output to the output file the minimum number of vessels that Merlin will have to break.
In the first example, you can, for example, pour 0.5 liters of elixir from the first vessel into the second and 1.5 liters into the third, after which you break the first vessel. In the second, the vessels initially contain an equal amount of elixir, you can not pour anything. In the third example, for example, you can pour 1 liter of elixir from the first vessel into the second, 2 liters each from the fifth into the second and third, 1 liter from the fifth into the fourth, and then break the first and fifth vessels.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 2 3 2 |
1 |
| 2 |
4 4 4 4 4 |
0 |
| 3 |
5 1 2 3 4 5 |
2 |