| Problem description | | Progress |
|
Темы:
Binary search
Scanning line
In the waiting room at the station there are N rows of M seats. So that those who are waiting do not get bored, K powerful Wi-Fi routers are installed instead of some chairs. Those who are waiting try to take places closer to the routers, as then they will be able to watch videos from Youtube or VK with a higher resolution, without delay. If the passenger is seated in seat number c in row r, and the i-th router is seated in seat Ci in row Ri, then the distance to the i-th router is calculated as max(|r−Ri|,|c−Ci|), where |x| – the absolute value of x. Seats in the waiting room were given priority from 1 to N⋅M−K, smaller numbers received seats with a shorter distance to the nearest router, among seats with the same distance to routers, the seats in the row with the smaller number are considered more comfortable, and among them &mdash ; with the lower number in the row. The figure shows seat priority in a waiting room with 4 rows of 7 seats, in which 2 routers are installed (their positions are marked in black). Armchairs located at a distance of 1 from the routers are highlighted in dark gray, light gray — at a distance of 2, white — 3.
Write a program that calculates the distance to the nearest router from a chair with some given priority.
The first line of input contains four integers — number of rows N (2 ≤ N ≤ 109) and seats in row M (2 ≤ M ≤ 109), number of routers K (1 ≤ K < 100, K < N⋅ M), number of requests Q (1 < Q < 100). This is followed by K lines containing two integers — location of routers: row number Ri (1 ≤ Ri ≤ N) and location number in row Ci (1 ≤ Сi ≤M). None of them match. This is followed by a line containing Q integers ranging from 1 to N⋅M−K – seat priorities.
Output for each query on a separate line one integer — distance to the nearest router from a chair with a given priority.
| Input |
Output |
|
4 7 2 4
2 5
4 4
1 6 16 26
|
1
1
2
3
|
| |
![]()
|
|
Темы:
Scanning line
There are N rectangles on the plane with vertices at points with integer coordinates and sides parallel to the coordinate axes. It is necessary to find the area of their union.
Input
The first line of the input file contains the number N (0≤N≤1500). The next N lines contain 4 integers x1, y1, x2, y2 — first the coordinates of the lower left corner of the rectangle, then the upper right (0≤x1≤x2≤109, 0≤y1≤y2≤109). Note that rectangles can degenerate into lines and even into points.
Output
Output a single number — answer to the problem.
| Input |
Output |
|
3
1 1 3 5
5 2 7 4
2 4 6 7
|
23 |
|
2
0 0 2 2
1 3 2 4
|
5 |
| |
![]()
|
|
Темы:
Scanning line
Tom Sawyer persuaded n of his friends to help him in the difficult task of painting the fence surrounding Aunt Polly's house. The fence consists of k consecutive boards, numbered from 1 to k, and after the k-th board comes the first one again.
Tom's friends are very fastidious, the i-th friend agrees to participate in painting only if he is allowed to paint a section of exactly ai consecutive boards. Tom has only one brush, so his friends will paint in turn and at once the entire segment allotted to them. The only thing left for Tom to do is choose the order in which to invite his friends, as well as choose the desired number of consecutive boards for each.
At the same time, each of Tom's friends is ready to paint both an unpainted fence board and a board that has already been painted by one of his predecessors. However, friends get more pleasure from painting an unpainted board. Tom wants to choose a number x and distribute the fence sections to be painted in such a way that each of his friends paints at least x unpainted planks. Tom loves his friends very much and wants each of them to get the most out of painting the fence, so he tries to maximize x.
Help Tom understand how much joy he can bring to his friends.
Input data format
The first line of the input file contains two integers n (1 ≤ n ≤ 105 ) and k (1 ≤ k ≤ 109 ). The next line contains n integers — values ai (1 ≤ ai ≤ k).
Output data format
Print one number — maximum possible value of x.
| Input |
Output |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
Explanation
In the first example x = 5 because one of the friends just doesn't want to paint more than five boards. He will come first, paint his five, after which another 10 unpainted boards will go to Tom's second friend. The remaining 85 boards will have to be painted by Tom himself.
In the second example, x = 2 can be reached, for example, like this. First, the third friend paints boards 4 to 6 (3 unpainted boards). Then the fourth friend paints boards 1 to 5 (3 unpainted boards). Then the second friend paints boards 1 to 8 (2 unpainted boards). Finally, the first friend paints boards 6 to 10 and 1 to 2 (2 unpainted boards, note that the fence goes in a cycle and these boards form a consecutive segment).
| |
![]()
|
|
Темы:
Scanning line
A certain set of segments with integer coordinates of ends \([L_i, R_i]\) is given on a line. Among the given set, choose a subset of segments that completely covers the segment \([0, M]\), (M — natural number) containing the smallest number of segments.
Input
The first line contains the constant M (\(1<=M<=5000\)). Each subsequent line contains a pair of numbers Li and Ri (\(|L_i|,|R_i| < 50000\)), which specifies the coordinates of the left and right ends of the segments. The list ends with a pair of zeros. The total number of segments does not exceed 100,000.
Output
In the first line of the output file print the minimum number of segments required to cover the segment \([0; M]\). Next, output a list of the covering subset, sorted in ascending order by the coordinates of the left ends of the segments. The list of segments is output in the same format as in the input. The trailing two zeros are not required. If the segment \([0; M]\) is the original set of segments \([L_i, R_i]\)< /span> is not possible, a single phrase “No solution” should be output.
Examples
| # |
Input |
Output |
| 1 |
1
-1 0
-5 -3
2 5
0 0
|
No solution |
| 2 |
1
-1 0
0 1
0 0
|
1
0 1
|
| |
![]()
|
|
Темы:
Count sort
Greedy Algorithm
Scanning line
The new President of Far Far Away began his work with a complete revision of the country's public transport system. As a result, on the basis of sociological surveys of the population, an ideal daily schedule of intercity buses was compiled, approved by the Parliament of the Republic.
Moreover, it was decided to replace the entire bus fleet with the same new, very expensive, but much more reliable, beautiful and comfortable cars.
The bus network of the country covers N cities, numbered with integers from 1 to N.
The ideal schedule contains M daily flights, the i-th flight starts in city Fi at time Xi and ends in some other city Gi at time Yi. The duration of each flight is non-zero and strictly less than 24 hours. Flight i is performed by one of the buses located at time Xi in the city Fi.
New buses do not require repairs and can operate around the clock, so a bus that arrives at some point in time in a certain city is always ready at the same time or later to go to service any other flight from this city. The bus can leave the city only on a scheduled flight.
It is assumed that the schedule will operate indefinitely, so it may not be possible to serve it with any finite number of buses.
Determine the smallest number of new buses sufficient to keep the schedule running for an unlimited period of time.
Input
The first line contains integers N and M (1 ≤ N, M ≤ 100 000) — number of cities and bus routes respectively.
Each of the following M lines contains a description of the bus route: departure city number Fi, departure time Xi, destination city number Gi (Fi ≠ Gi), arrival time Yi, separated from each other by one space. Arrival and departure times are specified in the HH:MM format, where HH — hours from 00 to 23, MM — minutes from 00 to 59.
Imprint
Print one number — the minimum required number of buses. If the schedule cannot be served for an unlimited period of time by a finite number of buses, print the number -1.
Examples
| # |
Input |
Output |
| 1 |
4 6
1 10:00 2 12:00
1 10:00 3 09:00
3 12:00 4 23:00
2 11:00 4 13:00
4 12:00 1 11:00
4 12:00 1 10:30 |
8 |
| |
![]()
|
|
Темы:
Scanning line
Count sort
A new airport began to operate at the airport in the city of Che. On the first day of work, a file was recorded with the time of arrival and departure of aircraft. Aircraft that departed the next day were not recorded in the file. Determine the maximum number of planes that were at the airport at the same time and during what maximum period of time (in minutes) such a number of planes were at the airport. Only planes, information about which is recorded in the file, are taken into account.
Input
The first line contains the number N - the total number of planes for the whole day. Each of the following N lines contains a pair of values, where the first value in the pair indicates the time of arrival of the aircraft, and the second value indicates the time of departure (arrival and departure times are in the range from 00:00 to 23 :59, and it is guaranteed that the arrival time is less than the departure time) . All data in the lines is separated by a single space.
If the time coincides, it is considered that the arrival occurs earlier than the departure.
In your answer, write down two integers separated by a space: first, the maximum number of aircraft that were at the airport at the same time, then the maximum period of time (in minutes) during which there were such a number of transit aircraft at the airport.
If the plane arrived at 12:00 and departed at 12:01, then it is considered that it stayed at the airport for 2 minutes.
Assignment file
Examples
| # |
Input |
Output |
| 1 |
6
09:00 10:07
10:20 11:35
12:00 pm 5:00 pm
11:00 11:30
11:20 12:30
11:30 18:15
| 4 1 |
| |
![]()
|
|
Темы:
Scanning line
Having delved into the study of physics in quarantine, the cows discovered "mu-particles"
They are currently experimenting with N "mu-particles" (1 ≤N ≤ 105). Particle i has a "spin" described by two integers xi and yi in the range −109…10 9 inclusive. Sometimes two "mu-particles" interact. This can only happen to particles with spins (xi,yi) and (xj,yj) that have xi≤xj and yi≤yj. Under these conditions, exactly one of these particles disappears (and nothing happens to the other). At most one interaction can happen at any given time.
The cows want to know the minimum number of "mu-particles" that can remain after some arbitrary sequence of interactions.
Input
The first line contains one integer N, the initial number of "mu-particles". Each of the following N lines contains two space-separated integers defining the spin of this particle. All spins are different.
Imprint
One integer, the minimum number of "mu-particles" that can remain after some arbitrary sequence of interactions.
Examples
| # |
Input |
Output |
Note |
| 1 |
4
10
0 1
-1 0
0 -1
| 1 |
One of the possible interaction sequences:
Particles 1 and 4 interact, particle 1 disappears.
Particles 2 and 4 interact, particle 4 disappears.
Particles 2 and 3 interact, particle 3 disappears.
Only particle 2 remains. |
| 2 |
3
0 0
1 1
-1 3
| 2 |
Particle 3 cannot interact with any of the other particles, so it must remain. One of particles 1 and 2 should also remain. |
| |
![]()
|
|
Темы:
Scanning line
Farmer John continues to fight for the health of his cows.
There are N cows (1≤N≤1000) cows, some of which are sick. The cows are lined up (on the number line), cow i is at position xi. The FD knows that if another cow is within radius R of the sick cow, then she also gets sick. And then the cows that are within R radius of this one, etc. get sick.
Unfortunately, the FD does not know the exact value of R. However, he does know which of his cows are sick. Based on these data, determine the minimum number of cows initially infected with the disease.
Input
The first line of input contains N. Each of the next N lines describes one cow with two numbers x and s, where x is the position of the cow and s is 0 for a healthy cow and 1 for a sick one. At least 1 cow is sick. And all the cows that could become sick from the spread of the disease are already sick.
Imprint
Determine the minimum number of cows that were initially sick before any spread of the disease.
Examples
| # |
Input |
Output |
| 1 |
6
7 1
1 1
15 1
3 1
10 0
6 1
| 3 |
| |
![]()
|