Train driver Ivan Ivanovich's locomotive broke down while the train was traveling along an inclined section of the track. As a result, the train came to a halt and is currently being held in place by its pneumatic brakes. However, air is gradually leaking from the braking system through the seals...
To prevent the train from rolling away, Ivan Ivanovich decides to place wheel chocks under the train cars. Using a specific formula (which accounts for the incline angle and the mass of the train) he calculates that he needs to place one chock under each car. There are $$$n$$$ cars in the train.
The wheel chocks are stored in the locomotive. Ivan Ivanovich can carry no more than two chocks at a time. Traveling from the locomotive to car $$$i$$$ (or vice versa) takes $$$t \cdot i$$$ seconds.
Determine the minimum amount of time required for him to place all the chocks and return to the locomotive.
For example, if $$$n=4$$$ and $$$t=10$$$, it will take him 120 seconds. One possible sequence of actions for Ivan Ivanovich is as follows: he takes two chocks, walks to the second car (placing one chock under the first car along the way), returns to the locomotive, picks up two more chocks, walks to the fourth car (placing one chock under the third car along the way), and then returns.
An alternative approach, which also results in a total time of 120 seconds, is to first walk to the fourth car (placing a chock under the third car along the way), return, then walk to the second car (placing a chock under the first car along the way), and return once more.
Two integers, $$$n$$$ and $$$t$$$, are provided, each on a separate line ($$$1 \le n \le 10^9$$$, $$$1 \le t \le 10$$$).
Output a single integer — the minimum number of seconds.
Subtask 1 (up to 40 points): $$$n \le 1000$$$
Subtask 2 (up to 60 points): no additional constraints.
410
120
The answer for the second subtask may exceed the capacity of a 32-bit data type. It is recommended to use a 64-bit data type—for example, 'long long' in C++, 'int64' in Pascal, or 'long' in Java and C#. In Python, no additional steps are required.
Four points $$$A$$$, $$$B$$$, $$$C$$$ and $$$D$$$ are marked on a plane. No three of them lie on the same line.
A straight line is drawn through points $$$A$$$ and $$$B$$$. Find the coordinates of a point $$$M$$$ on this line such that the length of the polyline $$$CMD$$$ is minimized.
Each of the four input lines contains a pair of integers $$$x_i$$$, $$$y_i$$$, representing the coordinates of points $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$, respectively ($$$-1000 \le x_i, y_i \le 1000$$$).
Output two real numbers $$$x_m$$$ and $$$y_m$$$ — the coordinates of point $$$M$$$. The relative or absolute error for each coordinate in your answer must not exceed $$$10^{-3}$$$.
Each test case is worth an equal number of points. The maximum score for the problem is 100.
2 1-3 -11 2-3 3
0.678160951 0.471264380
In Python, you can read two space-separated integers as follows: x, y = map(int, input().split())
A gas station has N fuel pumps, all of which are initially free.
Cars arrive at the gas station from time to time and join a single common queue. As soon as a pump becomes available, the first car in the queue moves to it to refuel. Refueling takes T seconds.
After refueling, the car moves aside to free up the pump, and the driver joins a queue for the checkout counter (since the online payment system is down again). There is only one checkout counter. Processing a payment at the counter takes V seconds.
For each car, determine the time at which it leaves the gas station. You may assume that all movements of cars and drivers occur instantaneously.
The first line contains four space-separated integers:
- F (1 ≤ F ≤ 105) — the number of cars.
- N (1 ≤ N ≤ 10) — the number of fuel pumps.
- T (1 ≤ T ≤ 100) — the time required to refuel one car.
- V (1 ≤ V ≤ 100) — the time required to process a payment at the checkout counter.
Each of the following F lines contains a single integer X (1 ≤ X ≤ 109) — the arrival time of a car. All arrival times are distinct and are given in ascending order.
For each car, output the time at which it leaves the gas station.
Subtask 1 (up to 25 points): F ≤ 100, X ≤ 105
Subtask 2 (up to 36 points): F ≤ 1000, X ≤ 109
Subtask 3 (up to 39 points): F ≤ 105, X ≤ 109
The number of points for a single test may vary between subtasks.
4 2 10 100
1
2
500
510
111
211
610
710
7 2 5 1
1
2
3
4
500
510
520
7
8
12
13
506
516
526
In Python, you can read 4 integers separated by spaces as follows: f, n, t, v = map(int, input().split())
There are two points on the plane: $$$A$$$ and $$$B_0$$$. The length of segment $$$AB_0$$$ is 1.
From point $$$B_0$$$, a segment $$$B_0B_1$$$ of length $$$c_1$$$ is drawn perpendicular to segment $$$AB_0$$$ counter-clockwise. Similarly, from each point $$$B_i$$$, a segment $$$B_{i-1}B_i$$$ of length $$$c_i$$$ is drawn perpendicular to segment $$$AB_{i-1}$$$ counter-clockwise, $$$i = 1..N$$$. There are $$$N$$$ segments in total.
It is required to find at what distance $$$X$$$ from point $$$A$$$ the last point $$$B_N$$$ is located, that is, the length of segment $$$AB_N$$$. It is guaranteed that $$$X$$$ is an integer.
The first line contains one integer $$$N$$$. The second line contains $$$N$$$ integers separated by spaces — the lengths of the segments $$$c_i$$$.
Print one number $$$X$$$ — the length of segment $$$AB_N$$$.
Subtask 1 (up to 20 points): $$$1 \leq N \leq 10, 1 \leq c_i \leq 100$$$
Subtask 2 (up to 20 points): $$$1 \leq N \leq 10, 1 \leq c_i \leq 10^8$$$
Subtask 3 (up to 20 points): $$$1 \leq N \leq 10^4, 1 \leq c_i \leq 10^8$$$
Subtask 4 (up to 20 points): $$$1 \leq N \leq 10, 1 \leq c_i \leq 10^{15}$$$
Subtask 5 (up to 20 points): $$$1 \leq N \leq 10^4, 1 \leq c_i \leq 10^{15}$$$
22 2
3
31 1 1
2
An example of a spiral with 2 segments ($$$N = 2$$$) is shown below.
A reminder for Python programmers: you can input a set of space-separated integers like this:
c = [int(x) for x in input().split()]
You are given an $$$n \times m$$$ rectangular grid of colored balls, where each ball can be one of three colors. In a single step, you may swap any two balls. Determine the minimum number of steps required to arrange the balls such that the grid is partitioned into single-colored rectangles — one rectangle for each color present.
The first line of the input contains two integers $$$n$$$ and $$$m$$$. The following $$$n$$$ lines each contain $$$m$$$ integers (1, 2, or 3), representing the colors of the balls.
Output a single integer: the minimum number of steps required. If no solution exists, output -1.
Subtask 1 (up to 20 points): $$$1 \le n, m \le 10$$$; the balls can only be of color 1 or 2.
Subtask 2 (up to 20 points): $$$1 \le n, m \le 1000$$$; the balls can only be of color 1 or 2.
Subtask 3 (up to 24 points): $$$1 \le n, m \le 10$$$; the balls can be of color 1, 2, or 3.
Subtask 4 (up to 36 points): $$$1 \le n, m \le 1000$$$; the balls can be of color 1, 2, or 3.
3 41 2 1 12 1 1 33 3 3 1
2
2 21 11 1
0
2 31 1 11 1 2
-1
In the first example, it is sufficient to swap the first two balls in the first row and the last two balls in the last column.
A note for those using Python: You can read a sequence of space-separated integers as follows:
c = [int(x) for x in input().split()]