After a resounding financial success, the owner of the Nikola company decided to offer the Berland Police Department unmanned vehicles equipped with a radar that will measure the speed of passing cars. According to the CEO, such cars will help maintain discipline on the roads of the state.
The unmanned vehicle moves at a speed of $$$x$$$ km/h, and the speed limit is $$$y$$$ km/h $$$(y \ge x)$$$. The main issue with the radar is that it measures the speed of passing cars relative to it, and also does not distinguish whether the car is overtaking a police car (or even moving towards it) or vice versa — the radar only records the speed.
You were asked to write a program that determines how many times the speed limit was broken — that is, when a vehicle's speed (relative to the ground) was strictly greater than the speed limit.
Since the data is ambiguous and the same result can be counted differently depending on the direction of movement and/or the actual speed of the car, output the minimum possible number of offenses and the maximum possible number of offenses recorded by the car.
The first line contains the number $$$ n $$$ $$$ (1 \le n \le 10 ^ 5) $$$ — the number of speed measurements made by the car.
The second line contains the number $$$ x $$$ $$$ (1 \le x \le 10 ^ 5) $$$ — the speed of the car.
The third line contains the number $$$y$$$ $$$ (1 \le y \le 10 ^ 5) $$$ — the speed limit. It is guaranteed that $$$ x \le y $$$.
The next $$$n$$$ lines contain one integer each, $$$s_i$$$ $$$ (1 \le s_i \le 10 ^ 5) $$$ — the speeds recorded by the radar.
Output two numbers separated by a space — the minimum possible and maximum possible number of recorded speed limit violations, respectively.
| № | Points | Limits | Dependencies | Grading policy |
| 1 | 100 | - | - | each test |
2 50 70 60 15
0 1
If the first car was moving in the same direction as the police car, then its speed was $$$ 50 + 60 = 110$$$ km/h — a speed limit violation. But it could also move in the opposite direction: then its speed was only $$$ 10$$$ km/h.
The speed of the second car relative to the ground is $$$ 50 + 15 = 65$$$ km/h — below the speed limit or $$$ 50 - 15 = 35$$$ km/h — also below the speed limit (in both cases, the car was moving in the direction of the police car).
Despite the global pandemic, Santa Claus decided to give gifts to children for the New Year. It turned out that gifts should be given to $$$n$$$ boys and $$$m$$$ girls. He creates gifts with spells and a magic wand; moreover, it turned out that he spends different amounts of time on gifts for boys and gifts for girls — $$$x$$$ minutes and $$$y$$$ minutes on one gift, respectively.
In addition, there are gifts that Santa Claus considers universal — suitable for both girls and boys — it also takes him a certain amount of time to prepare them, and it is $$$z$$$ minutes.
But, unfortunately, it turned out that his magic sleigh can only hold $$$k$$$ gifts that are suitable for both boys and girls at the same time. Knowing this, help Santa Claus find out the minimum amount of time he will need to spend on preparing gifts.
The first line contains an integer $$$n$$$ — the number of boys.
The second line contains an integer $$$m$$$ — the number of girls.
The third line contains an integer $$$x$$$ — the amount of time it takes to create a gift for boys.
The fourth line contains an integer $$$y$$$ — the amount of time it takes to create a gift for girls.
The fifth line contains an integer $$$z$$$ — the amount of time it takes to create a gift suitable for both boys and girls.
The sixth line contains an integer $$$k$$$ — the largest number of 'universal' gifts that Santa Claus can take with him.
The numbers do not exceed $$$10^9$$$.
Output a single number — the minimum amount of time that Santa Claus needs to prepare the gifts for every child.
| № | Points | Limits | Dependencies | Grading policy |
| 1 | 17 | $$$k = 0$$$ | - | each test |
| 2 | 24 | $$$m = 0$$$ | - | each test |
| 3 | 34 | $$$n, m, k, x, y, z \le 100$$$ | - | each test |
| 4 | 10 | $$$n, m, k, x, y, z \le 10^5$$$ | - | each test |
| 5 | 15 | $$$n, m, k, x, y, z \le 10^9$$$ | - | each test |
9 17 4 3 2 10
68
10 10 5 7 6 500
110
In the first example, it is optimal to replace all gifts for boys with universal ones, and also to give a universal gift to one girl. Total $$$ 9 \ cdot 2 + 1 \ cdot 2 + 16 \ cdot 3 = 68 $$$ minutes.
In the second example, it is optimal to replace only gifts for girls, because Santa Claus can prepare gifts for boys quickly.
The family of Diana, a nanotechnologist, is getting ready for Christmas. In order to surprise both of her best friends — Vova and Grisha — she decided to bake a pie, shaped like a $$$n$$$-sided regular polygon.
Suddenly, Diana recalled that Vova enjoys $$$a$$$-sided pies (not necessarily regular), and Grisha enjoys $$$b$$$-sided pies. Is it possible for her to split the pie with a single knife cut into two non-empty parts so that one has exactly $$$a$$$ sides, and the other has exactly $$$b$$$ sides?
The first line contains a single positive integer $$$n$$$ $$$(3 \le n \le 10^9)$$$ — the number of sides in the pie.
The second line contains a single positive integer $$$a$$$ $$$(3 \le a \le 10^9)$$$ — the number of sides that appeals to Vova.
The third line contains a single positive integer $$$b$$$ $$$(3 \le b \le 10^9)$$$ — the number of sides that appeals to Grisha.
Output YES if Diana can split the pie so that both guests will enjoy it, and NO otherwise.
| № | Points | Limits | Dependencies | Grading policy |
| 1 | 18 | $$$n = 3$$$ | - | complete |
| 2 | 22 | $$$n \le 5$$$ | 1 | complete |
| 3 | 45 | $$$n \le 100$$$ | 1, 2 | complete |
| 4 | 15 | $$$n \le 10^9$$$ | 1, 2, 3 | complete |
4 3 3
YES
4 4 4
YES
Diana can cut a square pie into two triangular parts by splitting it along the diagonal. The resulting parts won't be regular polygons — in fact, they will be right triangles — but this is not important, according to the statement.
Also, she can cut a square pie into two rectangular ones, splitting it parallel to two of its sides.
Matroskin the Cat decided to apply to a university and prepared the necessary documents for it [here the Russian version contained an allusion known only to Russians — Matroskin is a famous Soviet cartoon character]. He had $$$m$$$ documents in total, and numbered them $$$1$$$ to $$$m$$$: each document got its unique number.
Unfortunately he tripped along the way to the university (Novembers are really cold in certain parts of Russia), and dropped the documents. After having gathered them, he realized that he had lost one document. He cannot determine quickly which one it was exactly, but he can count the sum of the numbers of documents that remained.
Apart from that, it must be told that Matroskin applied to $$$t$$$ universities and ran into this problem $$$t$$$ times. Every time — with a different set of documents. Help Matroskin find out which documents he should promptly recover!
The first line contains a number $$$(1 \le t \le 10^5)$$$ — number of universities, where Matroskin decided to apply to.
The next $$$t$$$ lines contain one number $$$n_i$$$ $$$(1 \le n_i \le 10^9)$$$ — the sum of numbers on the documents that Matroskin hadn't lost.
Output one number for each test case, separating them with spaces or line breaks — the number of the document Matroskin had lost on the street. If there are several possible answers, output any of them.
| № | Points | Limits | Dependencies | Grading policy |
| 1 | 44 | $$$n \le 1000, t = 1$$$ | - | each test |
| 2 | 25 | $$$n \le 10^9, t = 1$$$ | - | complete |
| 3 | 31 | $$$n \le 10^9, t \le 10^5$$$ | - | complete |
1 4
2
2 4 6
2 4
The first example could describe the following situation: Matroskin had three documents with him and lost the second one.
Vasya had a burning desire to become a participant of the final stage of the All-Russian Olympiad in Informatics. He wanted it so much that he lied to his friend Petya that he had participated in it. What's more, he said to him: 'I got the $$$a$$$-th place on the first day, the $$$b$$$-th place on the second day, and the $$$c$$$-th in the final standings, and didn't share these places with anyone!'
Since Vasya had lied to Petya countless times, he didn't believe him and asked to show the standings table. Help Vasya come up with such a standings table that all three requirements that the had previously announced are satisfied (he cannot do it himself since he didn't score even a hundred points [out of 800] on the regional stage).
The first line contains three integers $$$a, b, c$$$ $$$(1 \le a, b, c \le 50000)$$$ — Vasya's place on the first day, on the second day, and in the final standings (where participants are ranked by the sum of their daily results).
If it is impossible to construct the needed standings table, output -1.
If such a table exists, output $$$n$$$ ($$$n \le 5 \cdot 10 ^ 5$$$) on the first line — the number of participants. After that, on $$$n$$$ next lines, output three numbers: the $$$i + 1$$$-th line must contain the result of the $$$i$$$-th participant on the first day, on the second day and the total sum. You can output the results in any order. Vasya's position in all of the three columns must be unique. See the sample for better understanding.
| № | Points | Limits | Dependencies | Grading policy |
| 1 | 10 | $$$a = b = c$$$ | - | each test |
| 2 | 60 | $$$1 \le a, b, c \le 100$$$ | - | each test |
| 3 | 30 | $$$1 \le a, b, c \le 50000$$$ | - | each test |
4 1 2
5 100 200 300 130 160 290 110 155 265 56 72 128 240 180 420
In the sample we provide an example with five participants, with Vasya's results on the first line.
The newly opened Hotel Chevalier is accepting tourists. The hotel boasts $$$n$$$ rooms of various size, the $$$i$$$-th room accommodating $$$c_i$$$ people. $$$k$$$ groups would like to rent a room, the $$$j$$$-th group containing $$$p_j$$$ people and offering $$$m_j$$$ dollars for a room. A room is suitable for some group if and only if its capacity doesn't exceed the number of people in the group. Also, two groups cannot rent the same room.
Unfortunately, it may be possible that the hotel is not large enough to accommodate all groups. Help the hotel manager make the maximum possible revenue for the hotel by optimally assigning rooms to the groups.
The first line contains two integers $$$n$$$, $$$k$$$ $$$(1 \le n, k \le 150000)$$$ — the number of rooms in the hotel and the number of tourist groups.
The second line contains $$$n$$$ integers $$$c_i$$$ $$$(1 \le c_i \le 100000)$$$ — the room capacities.
The third line contains $$$k$$$ integers $$$p_i$$$ $$$(1 \le p_i \le 100000)$$$ — the number of tourists in each group.
The fourth line contains $$$k$$$ integers $$$m_i$$$ $$$(1 \le m_i \le 100000)$$$ — the amount of money the groups are willing to pay for a room.
Output a single number — the maximum possible amount of money the hotel can make after renting rooms to the tourist groups.
| № | Points | Limits | Dependencies | Grading policy |
| 1 | 20 | $$$n \le 10, k \le 10$$$ | - | complete |
| 2 | 14 | $$$c_i \le 2$$$ | - | complete |
| 3 | 19 | $$$m_i = 1$$$ | - | complete |
| 4 | 46 | $$$n \le 1000, k \le 1000$$$ | - | complete |
| 5 | 1 | $$$n \le 150000, k \le 150000$$$ | 1, 2, 3, 4 | complete |
2 4 3 5 2 4 5 6 9 10 8 22
19