| Problem description | | Progress |
|
Темы:
Binary search by answer
This morning the jury decided to add one more Very Easy Problem to the Olympiad version. The executive secretary of the Organizing Committee printed its condition in one copy, and now he needs to make N more copies before the start of the Olympiad. He has M photocopiers at his disposal, each of which copies a sheet in х seconds. (You can use all copiers at the same time. You can copy not only from the original, but also from a copy.) Help him figure out what the minimum time is for this.
The program should run faster than linear search
Input data format
The first line contains yes natural numbers N, M separated by a space (1 ≤ N, M ≤ 2< span style="color: rgb(0, 0, 0); font-family: verdana; font-size: 14px;">•108), the second line contains speed of all copiers - x (1 ≤ x ≤ 10 )
Output data format
Print one number – the minimum time in seconds required to obtain N copies.
| |
![]()
|
|
Темы:
Binary search by answer
Given N wire lengths L1, L2 , ..., LN centimetres. It is required by cutting to get equal segments of the greatest possible length, expressed as an integer number of centimeters. If you can't get K segments even 1 cm long, output 0.
Limits: 1 <= N <= 10,000, 1 <= K <= 10,000, 100 <= Li <= 10,000,000, all integers.
Input: The first line contains numbers N and К. In the following N lines - L1, L2, ..., LN, one number per line.
Output: Output one number - the resulting length of the segments.
Examples
input
4 11
802
743
457
539
output
200
| |
![]()
|
Темы:
Binary search by answer
Roman collects numbers he finds interesting. For example, now he finds interesting positive numbers, the record of which in the base k number system ends with an odd number of zeros. For example, for k = 2, such numbers are 210 = 102, 2410 = 110002.
In order to complete his collection, Roman wants to find the n-th such number in ascending order. Since he took n large enough, he cannot do it manually. Help Roman — write a program that will find the number it needs to complete the collection.
Input: The first line contains two integers (1 <= n <=1015, 2 <= k <= 10 ).
Output: Print the n-th number in ascending order whose notation in base k number system ends with an odd number of zeros. This number must be printed in decimal.
| |
![]()
|
|
Темы:
Binary search by answer
Gromozek from the planet Plague is impressionable, vulnerable, easily discouraged and begins to cry, along the way exhaling acrid smoke from his nostrils.
Gromozeka brought from his home planet N pieces of chewing tapes, which are so loved by earthly children. He wants to share all the tapes between K children. But it turns out that if the size of the chewing tape is different for children, they will begin to swear and quarrel. At this point, Gromozeka will become discouraged.
Help Gromozeka divide all the chewing tapes so that they can make K of the same pieces. The joy of children is directly proportional to the length of the chewing tapes. Gromozeka wants the children to get as much joy as possible.
Input
The first line contains two numbers - N (1 <= N <= 10001) and K (1 <= K <= 10001). Further, in each of the subsequent N lines, one number is written - the length of each brought chewing tape. The length of the tape is given in centimeters. All lengths are between 1 and 107 centimeters inclusive.
Imprint
Print a single integer - the maximum length of the chewing tape in centimeters. In case Gromozeka becomes discouraged, print 0.
Examples
| # |
Input |
Output |
| 1 |
4 11
802
743
457
539 |
200 |
| |
![]()
|
Темы:
Binary search by answer
Binary search for function value
Найдите такое число x, что x2+√x=C , с точностью не менее 6 знаков после точки.
Входные данные
В единственной строке содержится вещественное число 1 <=C <=1010.
Выходные данные
Выведите одно число — искомый x.
| Ввод |
Вывод |
| 2.0000000000 |
1.000000000 |
| 18.0000000000 |
4.000000000 |
| |
![]()
|
|
Темы:
Dijkstra's algorithm
Binary search by answer
For the next Summer Computer School, it was decided to prepare circles for both schoolchildren and all teachers.
Having a habit of doing important things at the very last moment, the designer finished the layout two days before school started. It will take another day for the manufacturer to make mugs and put an image on them. It only takes 24 hours for NATO to take the mugs from the factory to LKSH.
An order for 10,000,000 mugs (namely, that's how many the organizers ordered), of course, cannot be taken away in one flight. However, for the first flight I want to bring the maximum number of mugs. One heavy truck was ordered for transportation. But there is one caveat: on some roads there is a limit on the weight of the car. Therefore, if the car is loaded with mugs to the eyeballs, then it may not be possible to use the shortest route, but you will have to take a detour. It may even happen that because of this, the truck will not have time to reach the camp on time, and this cannot be allowed. So, how many mugs can be loaded into the car in order to have time to bring this valuable cargo on time, and without violating the rules of the road?
Input
The first line contains the numbers n (1≤n≤500) and m - the number of nodes in the road map and the number of roads, respectively. The next m lines contain information about the roads. Each road is described on a separate line as follows. First, the numbers of the junction points that are connected by this road are given, then the time it takes to travel along this road, and finally, the maximum weight of a car that is allowed to drive on this road. It is known that all roads connect different points, and for each pair of points there is at most one road directly connecting them. All numbers are separated by one or more spaces.
Nodal points are numbered from 1 to n. At the same time, the plant for the production of mugs has number 1, and LKSH - number n. Travel time on the road is given in minutes and does not exceed 1440 (24 hours). The mass limit is given in grams and does not exceed one billion. In addition, it is known that one mug weighs 100 grams, and an empty truck - 3 tons.
Output
Print a single number - the maximum number of mugs that can be brought on the first flight, spending no more than 24 hours.
Examples
| # |
Input |
Output |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |
| |
![]()
|
|
Темы:
Binary search by answer
This morning the jury decided to add one more Very Easy Problem to the Olympiad version. The executive secretary of the Organizing Committee printed its condition in one copy, and now he needs to make more N copies before the start of the Olympiad. He has two copiers at his disposal, one of which copies a sheet in x seconds, and the other – for y.
It is allowed to use both one copier, and both at the same time. You can copy not only from the original, but also from a copy. Help him figure out the minimum time it takes.
Input: The input is three natural numbers N, x and y separated by spaces (\(1 <= N <= 2 \cdot 10^8,\ 1 <= x, y <= 10\) ).
Output: print a single number – the minimum time in seconds required to obtain N copies.
Examples
| # |
Input |
Output |
| 1 |
4 1 1 |
3 |
| 2 |
5 1 2 |
4 |
| |
![]()
|
|
Темы:
Binary search by answer
When Petya was at school, he often participated in olympiads in computer science, mathematics and physics. Since he was a fairly capable boy and studied hard, he received diplomas at many of these Olympiads. By the end of school, he had accumulated n diplomas, and, as it turned out, they all had the same size: w — wide and h — in height. Now Petya is studying at one of the best Russian universities and lives in a hostel with his classmates. He decided to decorate his room by hanging his diplomas for school olympiads on one of the walls. Since it is rather difficult to attach diplomas to a concrete wall, he decided to buy a special cork board to attach it to the wall, and to it — diplomas. In order to make this design look more beautiful, Petya wants the board to be square and take up as little space as possible on the wall. Each diploma must be placed strictly in a rectangle measuring w by h. Diplomas must not be rotated 90 degrees. Rectangles corresponding to different diplomas must not have common interior points. It is required to write a program that will calculate the minimum size of the side of the board that Petya needs to place all his diplomas.
.png)
Input: 3 integers are input: w, h, n (\(1<=w,\ h,\ n <= 10^9\) ).
Output: You must output the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
2 3 10 |
9 |
| 2 |
1 1 1 |
1 |
| |
![]()
|
|
Темы:
Binary search by answer
Farmer Nikolai hired two lumberjacks: Dmitry and Fedor, to cut down the forest, in the place of which there should be a cornfield. X trees grow in the forest.
Dmitry cuts A trees a day, but every K day he rests and does not cut a single tree. Thus, Dmitry rests on the K-th, 2K-th, 3K-th day, etc.
Fedor cuts down B trees a day, but every M-th day he rests and does not cut a single tree. Thus, Fedor rests on the M-th, 2M-th, 3M-th day, etc.
The lumberjacks work in parallel and thus, on days when none of them rests, they cut down A + B trees, on days when only Fedor — A trees, and on days when only Dmitry — B trees. On days when both loggers rest, not a single tree is cut down.
Farmer Nikolai wants to know how many days it will take the loggers to cut down all the trees and he can sow the cornfield. It is required to write a program that given integers A, K, B, M and X< /code> determines how many days it takes for all trees in the forest to be cut down.
Input: five space-separated integers are input: A, K, B, M and X (\(1 <= A,\ B <= 10^9 \) , \(2 <= K,\ M <= 10^{18}\), \(1 <= X <= 10^{18}\)).
Input: print a single integer — desired number of days.
Examples
| # |
Input |
Output |
| 1 |
2 4 3 3 25 |
7 |
Explanation for example
In the example above, lumberjacks cut down 25 trees in 7 days as follows:
- 1st day: Dmitry cuts down 2 trees, Fedor cuts down 3 trees, total 5 trees;
- 2nd day: Dmitry cuts down 2 trees, Fedor cuts down 3 trees, total 10 trees;
- 3rd day: Dmitry cuts down 2 trees, Fedor rests, total 12 trees;
- 4th day: Dmitry rests, Fedor cuts down 3 trees, total 15 trees;
- 5th day: Dmitry cuts down 2 trees, Fedor cuts down 3 trees, total 20 trees;
- 6th day: Dmitry cuts down 2 trees, Fedor rests, total 22 trees;
- 7th day: Dmitry cuts down 2 trees, Fedor cuts down the remaining 1 tree, in total all 25 trees are cut down.
| |
![]()
|
|
Темы:
Binary search by answer
There are stalls on the straight line, in which it is necessary to place the cows so that the minimum distance between the cows is as large as possible.
Input:
- numbers N are entered in the first line (\(2 < N < 10001\)) – number of stalls, and K (\(1 < K < N \)) – number of cows;
- the second line contains N natural numbers in ascending order – stable coordinates (coordinates do not exceed \(10^9\)).
Output: print a single number – the largest possible distance allowed.
Examples
| # |
Input |
Output |
| 1 |
6 3
2 5 7 11 15 20
|
9 |
| |
![]()
|
|
Темы:
Binary search by answer
Vers needs to prepare a report on the last sortie. She has already composed the text in her head, it remains only to write it down. The report will consist of two parts: the first will contain n words, ith of which consists of ai letters, the second — m words, the jth of which consists of bj letters. The Kriya language does not contain any punctuation marks. Vers must write the report on a checkered roll of paper, w cells wide. Since the report consists of two parts, she will divide the roll into two parts of the whole width with a vertical line, after which she will write the first part on the left side, and on the right — second.
Both parts of the report are written in the same way, each on its own part of the roll. One letter of the word occupies exactly one cell. The first word is written in the first line of the roll, starting from the leftmost cell of this part of the roll. Each next word, if possible, should be written on the same line as the previous one and be separated from it by exactly one empty cell.
Otherwise, it is written on the next line, starting from the leftmost cell. If the width of a part of the roll is less than the length of some word that should be written in this part, it is impossible to write this part of the report on a part of the roll of such a width.
It is guaranteed that a vertical bar can be drawn so that both parts of the report can be written. Vers wants to draw a vertical line so that the length of the roll, which is enough to write a report, is minimal. Help her find that minimum length.
Input:
- the first line contains three integers w, n and m — roll width, number of words in the first and second parts of the report (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- the next line gives n integers ai — length of the i-th word of the first part of the report \(1 <= a_i <= 10^9\);
- the next line gives m integers bj — length of the jth word of the second part of the report \(1 <= b_j <= 10^9\).
It is guaranteed that it is possible to draw a line so that both parts of the report can be written.
Input: in a single line print a single integer — the minimum length of the roll, which is enough to write a report.
Examples
| # |
Input |
Output |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Note
In the sample test, the roll can be divided into two parts by drawing a line between the 7th and 8th column of cells, and then writing two words per line in both parts of the report.
| |
![]()
|
Темы:
Binary search by answer
Elementary geometry
quadtree
При игре в лапту одна команда ловит мяч и пытается осалить им бегущего. Игрок другой команды должен, перед тем как бежать, ударить мяч в поле. Известно, на какое максимальное расстояние он может ударить, а также скорости и начальные координаты игроков другой команды. Требуется выбрать направление и силу удара так, чтобы минимальное время, которое потребуется другой команде, чтобы поднять мяч с земли, было наибольшим. (Пока мяч летит, игроки стоят на местах.)
Выходные данные
Выведите сначала время, которое потребуется игрокам, чтобы добежать до мяча, а затем координаты точки, в которую нужно выбить мяч. Если таких точек несколько, выведите координаты любой из них. Время и координаты нужно вывести с точностью 10–3.
Оценка задачи
1 балл получат программы, которые верно работают, когда в поле не более двух соперников.
| Ввод |
Вывод |
|
10 2
1 1 1
-1 1 1
|
9.05539
0.00000 10.00000
|
| |
![]()
|
|
Темы:
Binary search by answer
Sorting algorithms
Besi has published N articles (1 <= N <= 105). ith article cited ci times (0 <= ci <= ;105).
h-index is the largest number of h such that there are at least h articles, each of which is cited by at least h code> times. For example, there are 4 articles with the number of citations (1,100,2,3), then the h-index is 2, and with the number of citations (1,100,3,3) h- index is 3.
To increase her h-index, Besi plans to write K review articles (0 <= K <= 105), each of which cites several of her past articles. Besi has the right to cite no more than L articles in each review (0 <= L <= 105). Of course, no article can be cited more than once in one review (however, an article can be cited in several reviews).
Help Besi determine the maximum h-index she can reach after writing these review articles. Besi cannot quote a review in any of her reviews.
Input data
The first line contains N, K, L. The second line contains N space-separated integers c1, ...,cN.
Imprint
Maximum h-index.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4 4 1
1 100 1 1
| 3 |
In this example, Besi can write 4 review articles, each of which can cite no more than 1 article. If you quote the first and third articles 2 times, its h-index becomes 3. |
| 2 |
4 1 4
1 100 1 1
| 2 |
In this second example, Besi can write at most one article. If Besi cites any of her 1st, 2nd or 4th articles at least once, her h-index will become 2. |
| |
![]()
|
|
Темы:
Binary search by answer
"Long" arithmetic
Given an increasing sequence of integers 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... It is formed as follows: one odd number is taken, then two even ones, then three odd ones, and so on . Output the N-th element of this sequence.
Input
One integer N (1 ≤ N ≤ 10100).
Imprint
Print one integer - the N-th element of the sequence.
Examples
| # |
Input |
Output |
| 1 |
1 |
1 |
| 2 |
4 |
5 |
| |
![]()
|
|
Темы:
Binary search in an array
Binary search by answer
Greedy Algorithm
In order to improve the landscape architecture and environmental situation, the municipal administration has developed a draft program for greening the central avenue. According to the project, on one side of the avenue, it is planned to plant trees of K different species in a row, for which tree seedlings were purchased, and ai seedlings were purchased.
To achieve the aesthetic perfection of the planted row of trees, it is required that among any P consecutive trees, all trees be of different species. If the number of trees in a row is less than P, then they must all be different.
It is required to write a program that finds the maximum number of trees in an aesthetically perfect row planted from purchased seedlings.
Input
The first line contains two integers: K — number of different tree species (1 ≤ K ≤ 100,000), and P — the required number of consecutive trees of different species (2 ≤ P ≤ K). The next K lines of input data contain integers ai, specifying the number of purchased tree seedlings of the i-th type (1 ≤ ai ≤ 109), by one number per line.
Imprint
Print a single number — the maximum number of trees that, planted in a row in some order, achieves aesthetic perfection.
Examples
| # |
Input |
Output |
| 1 |
3 3
1
200
1 |
4 |
| |
![]()
|
|
Темы:
Heuristic methods
Binary search by answer
Quick sort
Greedy Algorithm
The New Year is coming soon and Santa Claus has already started preparing his magical reindeer team, on which he delivers gifts to children. It is known that the team is driven by several magical deer, each of which is ridden by two elves.
But the magical deer – obstinate animals, so not any two elves can ride any deer. Namely, each deer is characterized by some obstinacy ai, and each elf – temperament bi. Two elves j and k can ride the i-th reindeer if and only if either bj < ai < bk or bk < ai < bj.
To make his appearance as spectacular as possible, Santa Claus wants his team to have as many reindeer as possible. About every deer Santa knows his obstinacy, and about every elf – his temperament.
Help Santa figure out the maximum number of reindeer he can include in his team, which reindeer he should choose, and which elves should ride them.
Input
The first line contains two integers m and n – the number of deer and elves, respectively ( 1 ≤ m, n ≤ 100,000).
The second line contains m integers ai – deer obstinacy ( 0 ≤ ai ≤ 109). The third line contains n integers bi – elves temperament ( 0 ≤ bi ≤ 109).
Imprint
In the first line print a single number k – the maximum number of reindeer that Santa Claus can include in his team. In the next k lines print three integers each: di, ei, 1, ei, 2 – for each reindeer in the team print its number and the numbers of the elves that will ride it. If there are several solutions, print any one.
Both elves and deer are numbered, starting from one, in the order in which they are given in the input.
Examples
| # |
Input |
Output |
| 1 |
4 6
2 3 4 5
1 3 2 2 5 2
| 2
1 1 2
3 4 5
|
| |
![]()
|
|
Темы:
Binary search by answer
The sick cows decided to help Farmer John.
In order to limit disease transmission, N (2 ≤ N ≤ 105) FD cows decided to practice "social distancing" and "distributed" on the farm. The farm is represented as a straight line, with M intervals (1 ≤ M ≤ 105) that do not have common points, on which grass grows. The cows want to spread out at points with different coordinates, each point covered with grass, so as to maximize the value of D. Where D represents the distance between the nearest pair of cows. Help the cows determine the highest D value.
Input
The first line of input contains N and M. Each of the next M lines describes an interval with two integers a and b, where 0 ≤ a≤ b ≤1018. No two intervals overlap or touch at their endpoints. A cow standing at the end point of the interval is considered to be standing on grass.
Imprint
Print the largest possible value of D such that all pairs of cows are at least D units apart. It is guaranteed that there is a solution with D>0.
Examples
| # |
Input |
Output |
| 1 |
5 3
0 2
47
9 9
| 2 |
| |
![]()
|
|
Темы:
hash
Prefix sums(minimums, ...)
Binary search
Binary search by answer
Tom Sawyer and Huckleberry Finn read a newspaper clipping aloud together. But it so happened that Tom Sawyer began to read from the i-th character, and Huckleberry Finn from the j-th.
How many letters can they read before they find they started from different places, or until they both read to the end?
Input:
The first line contains the string S (1 <= |S| <= 105), consisting of lowercase Latin letters - an inscription from a newspaper clipping.
The next line contains a natural number q - the number of requests.
The next q lines contain two natural numbers i and j each - the positions from which Tom Sawyer and Huckleberry Finn start reading, respectively.
Output:
Print q lines, each of which should contain one integer - the number of characters that match when reading substrings starting with the i-th and j-th characters.
Examples:
| Input |
Output |
abacaba
4
15
3 5
4 2
26 |
3
1
0
2 |
| |
![]()
|
|
Темы:
Binary search by answer
Strings
"Two Pointers"
In this problem, you need to find the longest substring of the given string, such that each character occurs in it no more than k times.
Input
The first line contains two integers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , where n – the number of characters in the string. The second line contains n characters – the given string, consisting only of lowercase Latin letters.
Imprint
In the output file print two numbers – the length of the searched substring and the number of its first character. If there are several solutions, print any one.
Examples
| # |
Input |
Output |
| 1 |
3 1
abb |
2 1 |
| 2 |
5 2
ababa |
4 1 |
| |
![]()
|
|
Темы:
Binary search
Binary search by answer
Error
| |
![]()
|
|
Темы:
Binary search
Binary search by answer
Error
| |
![]()
|
|
Темы:
Binary search by answer
Gromozeka and Alice came up with the rules of the game of endless Jenga.
In endless Jenga, each turn consists of one of two actions of the player's choice:
- if there is at least one bar in the tower, then you can pull out and remove from the tower exactly one bar (the number of bars in the tower decreases by 1);
- put on the tower the number of bars 1 more than the last time before this.
The first move always places one block into an empty tower. Formally speaking, after the first move, the tower consists of one bar. If after some move the tower turned out to be empty (it does not have a single bar), then a bar can only be placed in such a tower. Alice and Gromozeka have an infinite number of bars to install on the tower.
For example, you can perform the following sequence of actions while playing:
1) install one bar on the tower;
2) install two bars on the tower;
3) remove one block from the tower;
4) remove one block from the tower;
5) install three bars on the tower;
6) remove one block from the tower;
7) install four bars on the tower;
8) remove one block from the tower;
9) install five bars on the tower.
After 9 moves, the number of bars in the tower will eventually be 11, and during the game 4 bars were removed from the tower.
It is known that Alice and Gromozeka made n moves in the invented game, and after all the moves made, the number of bars in the tower was equal to k. Find the total number of bars removed by Alice and Gromozeka from the tower in all n moves. It is guaranteed that given n and k answer exists.
Input
The first line of the input contains two integers n and k (1<=n<=109 ; 0<=k<=109) - the total number of moves and the number of bars in the tower after n moves. It is guaranteed that for the given n and k answer exists.
Output
Print a single integer - the number of bars that Alice and Gromozeka pulled out together during the game. Please note that there cannot be multiple correct answers in this problem - the answer is uniquely determined by the input data.
Examples
| # |
Input |
Output |
| 1 |
1 1
|
0
|
| 2 |
9 11
|
4
|
| 3 |
50
|
3
|
| 4 |
3 2
|
1
|
| |
![]()
|
|
Темы:
Binary search by answer
Crew members of the Pegasus spacecraft landed on the third planet of the Medusa System to study mirror colors. Their ship landed at the beginning of a narrow field of a flower farm. Mirror flowers begin to sprout after midnight. The kind farm workers provided the crew with a plan for the germination of flowers in the form of a germination point and time. The crew of the ship needs to leave the planet at the next midnight. The ship's exploration team can move around the planet at a maximum speed of vmax. The group needs time d to study one flower. It is necessary to explore the flower all at once, it will not be possible to return to it later. Flowers germinate the later, the farther they are located from the beginning of the field. At one point, only one flower sprouts, and each flower sprouts at its own moment in time. No two flowers sprouted at the same time.
The crew team wants to determine the point in time when the research team can return to the ship by examining all the flowers in as little time as possible.
Input
The program receives several lines as input. The first line contains 2 integers separated by one space: vmax (in cm/min) and d (in minutes) , 0 < vmax <= 200, 0 <= d <= 500.
The second line contains a single number N – number of flowers (in pieces). 0 <= N <= 1400 if d = 0, otherwise 0 <= N <= 200.
Then there are N lines, each of which contains two numbers separated by a space: integer xi – the distance from the flower to the beginning of the field (in centimeters), 0 <= xi <= 32767, and the number ti – moment of flower germination (in hh:mm format). The pairs are listed in ascending order of distance.
Imprint
Print the time the research team returned to the ship (in hh:mm format), rounded up to whole minutes.
Notes
1. There are 60 minutes in an hour, 24 hours in a day.
2. Time in a day changes from 00:00 to 23:59.
3. We can assume that the research team does not change direction until they reach the last flower.
Examples
| # |
Input |
Output |
| 1 |
3 1
1
100 00:01
|
01:08
|
| |
![]()
|
|
Темы:
Binary search by answer
N students were invited to programming camp. Evening leisure, it was decided to spend in the form of a relay race. To conduct the relay race, it is necessary to divide all students into R teams of C people in each. According to the head of the training camp, the team will be more successful in the relay, the less the growth of students in one team will differ.
Number of failures of the team will be the difference between the growth of the tallest and the lowest members of this team (if there is only one person in the team, then this difference is 0).
The counselors decided to form teams so that the maximum number of failures of the formed teams was minimal. While the counselors are busy resettling students in houses, help them and calculate the smallest possible value of the maximum number of failures of the formed teams.
Consider the following example. Let there be 8 people at the training camp, whose height in centimeters is 170, 205, 225, 190, 260, 130, 225, 160, and it is necessary to form two teams of three people each. Then one of the options is this:
Team 1: students with height 225, 205, 225
Team 2: students with a height of 160, 190, 170
In this case, the number of failures of the first command will be equal to 20, and the number of failures of the second — 30. The maximum number of failures will be 30, and this will be the best possible result.
Input
The first line of the input contains three natural numbers N, R and C - nbsp;number of students at the training camp, number of teams and number of people in each team (1 <= R·C <= N <= 100 000).
Next, enter N integers — the growth of each N students. The student's height is a natural number not exceeding 1,000,000,000.
Imprint
Print one number - the smallest possible value of the maximum number of failed commands.
Examples
| # |
Input |
Output |
| 1 |
8 2 3
170
205
225
190
260
130
225
160
|
30
|
| |
![]()
|
|
Темы:
Binary search by answer
Vasily lives along a long avenue. A bus runs along the avenue in a straight line. From the metro to Vasily's house N bus stops. We will assume that the metro is located at the zero stop, at the point with coordinate 0.
Coming out of the metro, Vasily is in a hurry to go home, but Vasily does not like to wait for the bus at the bus stop. Since Vasily never waits for a bus, having approached the stop and not seeing the bus, he goes further along the avenue. In the event that Vasily notices the bus, he either returns to the stop or continues on his way to the next stop.
Vasily walks at a speed U, the bus travels at a speed V. Find the minimum distance L that must be seen before the zero stop, so that he can walk at his own speed towards the house without fear that the bus will overtake him between stops.
Input
The first line of the input contains three numbers N, U and V (N <= 1000, ;U and V – positive real numbers), the second line contains N real numbers – X1, X2,... Xn (0 < X1 < X2 <…<Xn <106), separated by spaces.
Imprint
In the output file, your program should output the number L with an accuracy of 10-4.
Examples
| # |
Input |
Output |
| 1 |
1 1 10
2
|
9.0000
|
| 2 |
5 1 10
1 2 4 8 16
|
28.0000
|
| |
![]()
|
|
Темы:
Binary search by answer
Let's define the function mex as follows: mex(A) — is the minimum positive integer that is not in the set A.
For example, mex of set {1, 2, 3, 5, 100} is 4, and mex of set {2, 3, 4, 5} is 1 .
You have a set of numbers A, consisting of n positive integers, and a positive number k. Then you performed the following operation k times: added to the set A one more number equal to mex(A), thereby increasing the size each time set A by one.
Given a set A and a number k determine the last number that was added to the set.
Input
The first line contains two integers n and k (1<=n<=100000, 1<=k<=109) &mdash ; the number of numbers in the set and the number of addition operations.
The second line contains n distinct integers a1, a2, ..., an (1<=ai<=100000) — elements of set A.
Imprint
Print a single integer — the last number that was added to the set.
Note
In the first example, the mex of the set {1, 2, 4, 5} is equal to 3, after adding mex to the set, it will become equal to {1, 2, 3, 4, 5}.
Examples
| # |
Input |
Output |
| 1 |
4 1
4 2 1 5
|
3
|
| 2 |
7 10
1 3 20 2 7 45 5
|
15
|
| |
![]()
|
|
Темы:
Binary search by answer
On the numerical axis, in the interval from L to R, Vasily drew N vertical sticks. After thinking, Vasily decided that he needed an empty gap on the number axis with a width of at least W.
Help Vasily determine what is the minimum number of sticks that Vasily needs to erase and which ones.
After Vasily erases a certain number of sticks, there should be a gap with a width greater than or equal to W. The gap can be between the two remaining sticks, or between the remaining stick and the end of the number line gap, or between the two ends of the number line gap.
Input
The first line contains two integers N and W — the number of drawn sticks and the minimum required gap width, respectively. It is guaranteed that 0 <= N<= 1 000 000 and 0 <= W <= 1 000 000.
The second line contains two numbers L and R — coordinates of the left and right ends of the span of the numerical axis (L <=<R). The third line contains N numbers — coordinates of the drawn sticks. All coordinates (including L and R) — various integers, modulo not exceeding 1 000 000. It is guaranteed that all sticks are drawn between the left and right ends of the side.
Imprint
In the first line print the minimum number of sticks Vasily needs to erase. The numbers of these sticks should follow in the second line. The sticks are numbered in the order they are specified in the input, starting from 1.
If there are several solutions, then you can print any. If there is no solution, then print a single line containing the number - 1.
Examples
| # |
Input |
Output |
| 1 |
3 2
26
3 4 5
|
1
1
|
| 2 |
3 2
16
4 3 5
|
0
|
| 3 |
3 5
17
5 3 4
|
3
2
3
1
|
| |
![]()
|
|
Темы:
Binary search
Binary search by answer
In the multiplayer game Agar.io, players control bacteria. Each bacterium has size — a positive integer. If two bacteria of different sizes meet, the larger bacterium engulfs the smaller bacterium. In this case, the smaller bacterium disappears, and the size of the larger bacterium increases by the size of the smaller bacterium. If two bacteria of the same size meet, nothing happens. The winner is the player whose bacterium remains on the game
field one.
There are n players in the game, you are given the sizes of their bacteria. Determine which of the players have the opportunity to win in this game.
Input data format
The program receives an integer n, 1 ≤ n≤ 105 — number of players. The next n lines contain one number each ai — bacteria sizes, 1 ≤ ai ≤ 109. The numbers ai are in non-decreasing order.
Output data format
The program should output n numbers equal to "0" or "1", one number per line. If the i-th number is equal to 0, then this means that the i-th player (whose bacterium size was originally
ai) cannot under any circumstances win this game. If the i-th number is equal to 1, then this means that the i-th player has the opportunity to win in this game.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
1
1
3
4 |
0
0
1
1 |
In the example from condition 4, bacteria of size 1, 1, 3, 4. Bacteria of size 1 can't do anything
eat, so they can't win. A size 4 bacterium can eat everyone. Bacteria size 3
can eat two bacteria in turn of size 1. Then her size will become 5, after that she can
eat bacteria size 4 and win. Answer: 0, 0, 1, 1. |
| |
![]()
|
|
Темы:
Binary search by answer
There are parcels on the conveyor belt that need to be delivered from one port to another within d days. The ship goes to another port once a day. i-th package on the conveyor belt has a weight of wi. The vessel takes on board the cargoes in the order in which they are located on the tape. Moreover, the ship will not be able to accommodate more parcels than its maximum carrying capacity.
You know the order in which the packages are placed on the conveyor belt. Find the minimum capacity of vessel that will be able to deliver all your packages to another port in d days.
Input
The first line of the input contains a natural number N (N <= 5·104) - the number of parcels to be delivered. The second line contains N numbers wi. The ith number means the weight of the ith load on the conveyor belt (1 <= i <= N,1 <= wi <= 500). Cargo with weight w1 is loaded onto the vessel first. The third line contains the number d (1 <= d <= 5·104)
Imprint
Print the minimum carrying capacity of a ship that can deliver all packages in d days.
Explanation
In the first example, the ship's minimum carrying capacity is 15. Then the ship will be able to deliver our packages in 5 days as follows:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Please note that the cargo must be sent in the order indicated, so use a vessel with a capacity of 14 and separate the parcels into parts such as (2, 3, 4, 5), (1, 6, 7), (8), (9) , (10) is not allowed.
Examples
| # |
Input |
Output |
| 1 |
10
1 2 3 4 5 6 7 8 9 10
5 |
15 |
| 2 |
6
3 2 2 4 1 4
3 |
6 |
| 3 |
5
1 2 3 1 1
4 |
3 |
| |
![]()
|
|
Темы:
Binary search by answer
Silvertown has n retail stores. The City Logistics Center delivered m types of goods with different quantities to be distributed to all retail stores. The Logistics Center needs to distribute all goods to the stores , following the following rules:
- Each store is allocated no more than one type of product, but any quantity.
- After distribution, each store is given a certain amount of goods (possibly zero).
Let x be the maximum number of items provided to any store. For successful sale of goods, it is necessary to ensure that x is as small as possible. In other words, it is necessary to reduce to a minimum the maximum number of products that are provided to any store.
Write a program for the logistics center that would find the smallest possible x.
Input
The first line of the input contains two space-separated natural numbers: n and m (1 <= m <= n <= 10< sup>5) - the number of retail stores and the number of product types. The second line contains m integers qi - the quantity of the i-th product type (0 ;<= i < 105, 1 <= qi <= 105).
Imprint
Output the smallest possible x.
Note
In the first test case, the optimal distribution would be:
- 11 products of type 0 are distributed to the first four stores in the following quantities: 2, 3, 3, 3
- 6 products of type 1 are distributed to two other stores in the following quantities: 3, 3
The maximum number of items provided to any store is max(2, 3, 3, 3, 3, 3) = 3.
Examples
| # |
Input |
Output |
| 1 |
6 2
116 |
3 |
| 2 |
7 3
15 10 10
| 5 |
| 3 |
1 1
100000 |
100000 |
| |
![]()
|
|
Темы:
Binary search by answer
Cheburashka loves tangerines. Now he was at the New Year's fair among a large number of boxes of tangerines. The ith box contains bi bananas. The fair starts its work in h hours.
Cheburashka is very smart and can choose the speed of eating tangerines - k mandarins per hour. He then selects a box of tangerines every hour and gobbles up k pieces from that box. If there are less than k tangerines in the box, then Cheburashka will eat them all and will not touch any more tangerines during this hour.
Cheburashka likes to eat slowly, but wants to eat all the tangerines before the fair opens.
Help Cheburashka find the minimum speed of eating tangerines, but such that he can still eat all the tangerines.
Input
The first line contains the number n (1 <= n <= 104) - the number of boxes with tangerines. The second line contains n numbers bi - the number of tangerines in the i-th box (1 < ;= bi <= 109). The third line contains the number h (n <= h <= 109) - after how many hours the fair opens.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
4
3 6 7 11
8 |
4 |
| 2 |
5
30 11 23 4 20
5 |
30 |
| 3 |
5
30 11 23 4 20
6 |
23 |
| |
![]()
|
|
Темы:
Binary search by answer
Чтобы помешать появлению СЭС в лагере, администрация ЛКШ перекопала единственную дорогу, соединяющую «Берендеевы поляны» с Судиславлем, теперь проехать по ней невозможно. Однако, трудности не остановили инспекцию, хотя для СЭС остается только одна возможность — дойти до лагеря пешком. Как известно, Судиславль находится в поле, а «Берендеевы поляны» — в лесу.
- Судиславль находится в точке с координатами (0, 1).
- «Берендеевы поляны» находятся в точке с координатами (1, 0).
- Граница между лесом и полем — горизонтальная прямая y=a, где a — некоторое число (0  a 1). - Скорость передвижения СЭС по полю составляет Vp, скорость передвижения по лесу — Vf. Вдоль границы можно двигаться как по лесу, так и по полю.
Администрация ЛКШ хочет узнать, сколько времени у нее осталось для подготовки к визиту СЭС. Она попросила вас выяснить, в какой точке инспекция СЭС должна войти в лес, чтобы дойти до «Берендеевых полян» как можно быстрее.
Входные данные
В первой строке входного файла содержатся два положительных целых числа V p и V f (1 V p, V f 10 5) . Во второй строке содержится единственное вещественное число — координата по оси Oy границы между лесом и полем a (0 a 1) .
Выходные данные
В единственной строке выходного файла выведите вещественное число с точностью не менее 8 знаков после запятой — координата по оси Ox точки, в которой инспекция СЭС должна войти в лес.
| Ввод |
Вывод |
5 3
0.4 |
0.783310604 |
|
5 5
0.5
|
0.500000000 |
| |
![]()
|