Max arrived at a self-service car wash to wash his car. He can choose one of three available payment rates.
- Fixed amount — pay $$$X$$$ rubles for the entire wash regardless of the time and water used;
- Pay-per-minute — pay $$$Y$$$ rubles for each minute spent washing;
- Pay-per-liter — pay $$$Z$$$ rubles for each liter of water used during the wash.
Max knows that he will completely wash the car in $$$T$$$ minutes, using $$$V$$$ liters of water in the process.
Help Max determine the minimum amount of rubles needed to pay for the car wash if he chooses the rate optimally.
The first line contains an integer $$$X$$$ ($$$1 \le X \le 10^4$$$) — the fixed payment rate for the car wash.
The second line contains an integer $$$Y$$$ ($$$1 \le Y \le 10^4$$$) — the cost per minute of washing.
The third line contains an integer $$$Z$$$ ($$$1 \le Z \le 10^4$$$) — the cost per liter of water.
The fourth line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of minutes required to wash the car.
The fifth line contains an integer $$$V$$$ ($$$1 \le V \le 10^4$$$) — the volume of water in liters required to wash the car.
Output a single integer — the minimum amount of rubles to pay for the car wash.
Solutions that work correctly for $$$T = 1$$$, $$$V = 1$$$ will be scored with $$$20$$$ points.
11111
1
20010181415
140
In the first example, the total costs for all rates are the same and equal to $$$1$$$.
In the second example, the most advantageous option is to pay by the second rate, paying for $$$14$$$ liters of water at $$$10$$$ rubles per liter.
Once in America, a city hosted a congress of three parties, attended by $$$a$$$, $$$b$$$, and $$$c$$$ delegates from the first, second, and third parties, respectively. All delegates want to spend the night in the best hotel "California," and since the total number of arrivals turned out to be $$$3 \times n$$$, the hotel manager decided to allocate $$$n$$$ triple rooms for them.
The porter (a secret supporter of the first party) can assign the guests to the rooms at his discretion. He knows that if two representatives of one party end up in one room with one representative of another party, then those two will convince the third to join their party.
What is the maximum number of members of the first party that can be in the hotel as a result of such accommodation?
Three lines of input contain three non-negative integers: $$$a$$$, $$$b$$$, and $$$c$$$ ($$$0 \le a, b, c \le 10^{8}$$$, $$$a + b + c \ge 3$$$). It is guaranteed that their sum is divisible by 3.
Output a single non-negative integer—the answer to the problem.
Solutions that work correctly for $$$a \lt b$$$ and $$$c = 0$$$ will be scored 40 points.
321
4
In the example, $$$a = 3$$$, $$$b = 2$$$, and $$$c = 1$$$. Since $$$a + b + c = 6 = 3 \times 2$$$, there are two available triple rooms.
If all three delegates of party $$$a$$$ are placed in one room, they will remain three in the morning.
If two delegates of party $$$a$$$ are placed in one room with a representative of party $$$c$$$, and the second room contains two representatives of party $$$b$$$ and a third delegate of party $$$a$$$, then the representative of party $$$c$$$ will join party $$$a$$$, and the representative of party $$$a$$$ from the second room will join party $$$b$$$. In total, there will still be three people in party $$$a$$$.
However, if two delegates of party $$$a$$$ are placed in one room with a representative of party $$$b$$$, and the second room contains one representative from each party, then the representative of party $$$b$$$ from the first room will join party $$$a$$$, and there will be no changes in the second room. In total, there will be four people in party $$$a$$$.
We have considered all options for distributing the delegates among the rooms, and the best result is 4.
On an infinite field, a robot stands at the coordinates $$$(0; 0)$$$. It needs to reach the point with coordinates $$$(a; b)$$$. In one step, the robot can move one unit up, down, left, or right. Due to the design constraints, the robot can only move in a "zigzag" manner—meaning if the previous step was horizontal, the next one must be vertical, and vice versa. Construct the shortest path for the robot from the starting point to the destination.
Two integers $$$a$$$ and $$$b$$$ are given, each on a separate line ($$$0 \le a, b \le 1000$$$, $$$a + b \gt 0$$$).
Output the coordinates of the robot after each step. Each pair of coordinates should be printed on a separate line, separated by a space. The initial coordinates do not need to be printed. If there are multiple correct answers, you may output any of them.
Solutions that work correctly for $$$a \le 5$$$ and $$$b \le 5$$$ will be scored 40 points.
13
1 0 1 1 0 1 0 2 1 2 1 3
Illustration for the example:
Elephant Semyon is a member of the sports club "CycloForces". In this club, all participants are assigned levels. To achieve level $$$K$$$, one must participate in at least $$$K$$$ races, each at least $$$K$$$ kilometers long. The level increases whenever possible.
Elephant Semyon remembers the distances of all his races. Help him determine his level.
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of races.
Each of the following $$$n$$$ lines contains a single integer $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the length of the next race.
Output a single integer — the rating of Elephant Semyon.
Solutions that work correctly for $$$n \le 15$$$ will be scored 20 points.
Solutions that work correctly for $$$n \le 1000$$$ will be scored 50 points.
Solutions that work correctly for $$$a_i \le 10^5$$$ will be scored 80 points.
531415
3
In the example, Elephant Semyon completed $$$5$$$ races. Among them, there are $$$3$$$ races with a distance of at least $$$3$$$ kilometers each (these are the races of $$$3$$$, $$$4$$$, and $$$5$$$ km), so Elephant Semyon's level can be $$$3$$$. It can be shown that he has not yet reached the next level.
Petya returned from school and realized that he forgot to buy bread. He also understood that he needed to act quickly: in $$$n$$$ minutes, a broadcast of an important match of his favorite football team will begin.
The journey from Petya's home to the bakery takes $$$t$$$ minutes, and it will take him the same amount of time to return. Buying bread will take one minute. It is guaranteed that $$$2 \cdot t + 1 \le n$$$.
Petya was already ready to go for the bread, but it started to drizzle. According to the weather forecast, it will rain for the next $$$n$$$ minutes, and for each $$$j$$$-th minute, the amount of precipitation $$$d_j$$$ that will fall during that minute is known.
Petya wants the total amount of precipitation that will fall while he is outside to be as low as possible.
Petya can delay leaving home, and he can wait a bit in the bakery and not leave immediately after making the purchase. The main thing is that he must return home no later than $$$n$$$ minutes. Your task is to determine the minimum possible total amount of precipitation that will fall while Petya is outside.
The first line contains an integer $$$n$$$ $$$(n \le 3 \cdot 10^5)$$$ — the maximum time by which Petya must be home.
The second line contains an integer $$$t$$$ ($$$t\ge 1$$$, $$$2t+1\le n$$$) — the time it takes Petya to walk from home to the bakery or back.
Each of the following $$$n$$$ lines contains one integer $$$d_j$$$ $$$(1 \le d_j \le 10^3, \, j = 1, 2, \ldots, n)$$$ — the amount of precipitation that will fall in the $$$j$$$-th minute.
Output an integer — the minimum possible total amount of precipitation that will fall while Petya is outside.
Solutions that work correctly for $$$n \le 100$$$ will be scored with 40 points.
184521421113211412312162
15
In the example from the statement, Petya should leave home in the 3rd minute. The amount of precipitation that will fall during his time outside will be $$$1 + 4 + 2 + 1 = 8$$$. He will make the purchase in the 7th minute, after which, starting from minute $$$\#8$$$, he can head back.
The best solution for him would be to wait until the 13th minute: if he leaves the bakery at that moment, the amount of precipitation that will fall during his time outside will be $$$3 + 1 + 2 + 1 = 7$$$.
The total amount of precipitation will be $$$15$$$. It can be verified that in other cases, the amount of precipitation will be greater.