| Problem description | | Progress |
|
Темы:
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. |
| |
![]()
|
|
Темы:
Sorting algorithms
Simulation tasks
N participants came to the Olympiad in Informatics. It is known in which schools the participants of the Olympiad study. There are N computers in the computer class, lined up along the wall. You need to seat the participants of the Olympiad so that no two participants from the same school sit next to each other.
Input
The program receives as input a positive integer number of participants in the Olympiad N1000. Next, N lines contain the numbers of schools where the participants of the Olympiad study. School numbers — integers from 1 to 3000.
Imprint
The program should output N numbers — the numbers of the schools of the participants of the Olympiad in the order in which they need to be seated in the computer class. The output sequence of school numbers must be a permutation of the given school numbers. The displayed answer should not contain two identical school numbers in a row.
If the problem has no solution, you need to print a single number 0.
Numbers can be displayed both in separate lines and in one line separated by a space. If there are several seating options, then you need to display any of them (but only one).
Examples
| # |
Input |
Output |
| 1 |
4
1005
1005
5
2005
| 1005 5 1005 2005 |
| 2 |
4
1005
1005
2005
1005
| 0 |
| |
![]()
|
|
Темы:
Sorting algorithms
Segment tree, RSQ, RMQ
Greedy Algorithm
Jack found N stones and arranged them in order of increasing mass. The masses of all stones are different. The lightest stone was number 1, the next ≤ 2 and so on, the heaviest one was numbered N.
Jack has a scale and decided to put all the stones on it in some order. The order in which he will place the stones is known, and which stone will land on which bowl.
Your task — determine the state of the scales after adding each stone. The exact weights of the stones are not known — only their numbers are given.
Input
The first line contains the integer N (1 N ≤ 100000).
Each of the next N lines contains two integers: R (1 ≤ R ≤ N) and S (1 ≤ S ≤ 2). R is the number of the stone that will be placed on the bowl S. All Rs will be different.
Imprint
Output N lines - one for each stone. If bowl 1 is heavier after adding the corresponding stone, print “<”. If side 2 is heavier, print “>”. If it is impossible to determine what state the scales will be in, print “?”.
Examples
| # |
Input |
Output |
| 1 |
5
1 2
3 1
2 1
4 2
5 1 |
<
>
>
?
>
|
| |
![]()
|
|
Темы:
Strings
Sorting algorithms
Iroha has a sequence of N strings s1, s2, .. , sN. Each line is L long. Iroha wants to concatenate all strings to get a very long string. Among all the strings it can get in this way, find the lexicographically smallest one.
We will assume that the string s = s1s2...sn is lexicographically less than the string < code>t = t1t2...tm if one of the following conditions is true:
- there is an index i (\(1<=i<=min(n,m)\)) such that \(s_j =t_j \), for all indices j (\(1<=j<= i\)), and \(s_i <t_i \);
- \(s_i=t_j\) for all i (\(1<=i<=min( n,m)\)), and \(n<m\).
Input
The first line contains numbers N and L. Next are the lines s1, s2, .., sN< /sub>, each on a separate line.
Imprint
Print the lexicographically smallest string that Iroha can create.
Examples
| # |
Input |
Output |
| 1 |
3 3
dxx
ax
cxx |
axxcxxdxx |
| |
![]()
|
|
Темы:
One-Dimensional Arrays
Using sort
Sorting algorithms
Gromozek has a sequence of integers A of length N. It freely chooses the integer b. Here he will become sad if Ai and b+i are far apart. More precisely, Gromozeka's sadness is calculated as follows:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\) .
Here \(abs(x) \) is a function that returns the absolute value of x. Find Gromozeka's minimum possible sadness.
Input
The first line contains an integer N (\(1<=N<=2 \cdot 10^5\)). The second line contains N integers Ai (\(1<=A_i<=10 ^9\)).
Imprint
Display Gromozeka's minimum possible sadness.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5
2 2 3 5 5
| 2 |
If we choose b = 0, Gromozeka's sadness will be \(\)
abs (2- (0 + 1)) + abs (2-(0 + 2))+ abs (3-(0 + 3)) + abs (5- (0 + 4)) + abs(5-(0 + 5)) = 2.
Any other choice of b does not make Gromozeka's sadness less than 2, so the answer is 2. |
| 2 |
9
1 2 3 4 5 6 7 8 9
| 0 |
|
| 3 |
6
6 5 4 3 2 1
| 18 |
|
| 4 |
7
1 1 1 1 2 3 4
| 6 |
|
| |
![]()
|
|
Темы:
Sorting algorithms
In some other world today is December 30th. N trees have been planted in grandfather Kokovani's garden. The height of the ith tree (1 <= i <= N) is hi meters. He decides to choose from these K trees and decorate them with a garland. To make the scenery more beautiful, the height of the decorated trees should be as close to each other as possible. More specifically, let the height of the tallest decorated tree be hmax meters and the height of the lowest decorated tree be hmin< /code> meters. The smaller the hmax-hmin value, the better. Determine the minimum possible value hmax-hmin?
Input
The first line contains two space-separated numbers N and K (2 <= N, K <= 105). The following N lines contain integers hi (1 <= hi <= 109), one per line.
Imprint
Display the answer to the problem.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5 3
10
15
11
14
12 |
2 |
If decorating the first, third and fifth trees, hmax=12, hmin=10, hmax-hmin=2. |
| 2 |
5 3
5
7
5
7
7 |
0 |
|
| |
![]()
|
|
Темы:
USE
Sorting algorithms
The file contains positive integers. The first line of the file contains the number N - the number of numbers. The following N lines contain the numbers themselves. In your answer, write in the column the 10 largest three-digit numbers.
Assignment file
| |
![]()
|
|
Темы:
Sorting algorithms
Gromozeka plays a single player game using a number line and N tiles. Each of the chips is located in some integer coordinate. Note that multiple tiles can be placed at the same coordinate.
Goal of the game: to visit with chips all M coordinates X1, X2, ..., XM by repeating the next move.
Move: select a token with coordinate X. Place this token at X+1 or X-1.
Please note that the coordinates where we originally placed the chips are already considered visited.
Find the minimum number of moves required to reach the goal.
Input
In the first line, the program receives two integers as input: N and M (1 <= N, M <= 105). The second line contains M integers X1, X2, . .., XM (-105 <= Xi <= 105). All numbers Xi are distinct.
Imprint
Display the answer to the problem.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
2 5
10 12 1 2 14
| 5 |
The goal can be reached in five moves as follows, and this is the minimum required number of moves.
First place two chips at coordinates 1 and 10.
Move the chip with coordinate 1 to 2.
Move the chip with coordinate 10 to 11.
Move the chip with coordinates 11 to 12.
Move the chip with coordinates 12 to 13.
Move the chip at coordinates 13 to 14. |
| 2 |
3 7
-10 -3 0 9 -100 2 17 |
19 |
|
| 3 |
100 1
-100000 |
0 |
|
| |
![]()
|
|
Темы:
Sorting algorithms
USE
Hearing that chocolate is good for the brain and nervous system, student Vasily decides to buy chocolate for the entire academic year. Vasily decided to buy chocolate for R rubles. He walked around in the city all N shops that sell various chocolates. Vasily saved to a file the information that in ith shop he can buy no more Bi bars of chocolate by < code>Ai rubles each.
A thrifty student wants to spend as much of his money as possible (preferably all at once) and buy as much chocolate as possible with it. Help Vasily figure out how many chocolate bars he can buy with his own money and how much the most expensive bar he can buy will cost.
Input
The first line in the file contains two numbers: N and R. The following N lines contain a pair of numbers: Ai and Bi.< br />
In your answer, write two numbers separated by a space on one line: first, the number of chocolate bars that Vasily can buy with his own money, then the cost of the most expensive chocolate bar that Vasily will have after the purchase.
Assignment file
| |
![]()
|
|
Темы:
Sorting algorithms
Using sort
Hearing that chocolate is good for the brain and nervous system, student Vasily decides to buy M chocolate bars. There are N shops in the city that sell a variety of chocolates. In the i store, Vasily can buy no more than Bi chocolate bars by Ai< /sub> rubles each. Help Vasily determine the minimum amount of money he needs to save up to buy M chocolate bars?
It is guaranteed that Vasily will always be able to buy M chocolate bars with the required amount.
Input
The first line contains two numbers: N and M (1 <= N, M <= 105). The following N lines contain 2 numbers each: Ai (1 <= Ai <= 109) and Bi (1 <= Bi <= 105 ). \(B_1 + B_2 +... + B_N >= M\).
Imprint
Print the minimum amount of money Vasily needs to buy M chocolate bars.
Examples
| # |
Input |
Output |
| 1 |
2 5
49
24 |
12 |
| 2 |
4 30
6 18
25
3 10
7 9
| 130 |
| 3 |
1 100000
1000000000 100000
| 100000000000000 |
| |
![]()
|
|
Темы:
Sorting algorithms
Formula derivation
Farmer John wants to create a triangular pasture for his cows.
There are N fence posts (3 ≤ N ≤ 105) as different (X1,Y1)…(X< sub>N,YN) points on the farm map. He can choose three of them to form the vertices of a triangular pasture, but so that one of the sides is parallel to the x-axis and the other is parallel to the y-axis.
What is the sum of the areas of all possible pastures that a FD can form?
Input
The first line contains N.
Each of the following N lines contains two integers Xi and Yi, each in the interval −104…104 inclusive, describing the position of the post.
Imprint
Since the sum of areas may not be an integer and very large, print the remainder after dividing twice the sum of areas by 109+7.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
0 0
0 1
10
1 2
|
3 |
Points (0,0), (1,0), (1,2) form a triangle with area 1.
Points (0,0), (1,0), (0,1) form a triangle with area 0.5.
So the answer is 2⋅(1+0.5)=3. |
| |
![]()
|
|
Темы:
Sorting algorithms
The concert venue stores data about sold tickets and available seats. Information about which places are free is known. It is necessary to purchase 5 tickets for the event, and so that all the seats are in the same row and go in a row. Find the lowest numbered row that has five adjacent free spaces. It is guaranteed that there is at least one series that satisfies this condition. In your answer, write down two integers, on one line separated by a space: the minimum number of the row and the largest number of the place from the suitable free places found in this row.
Input
The first line of the input file 26.txt contains the number N – the number of vacancies (a natural number not exceeding 10,000). Each of the following N lines contains two natural numbers not exceeding 100,000: the number of the row and the number of the free space.
Imprint
Two non-negative integers: The minimum number of the row where the places indicated in the problem were found and the maximum number of a suitable empty place in this row.
Example input file
6
1 1
1 2
1 3
14
15
16
Assignment file
| |
![]()
|
|
Темы:
Sorting algorithms
Trees are being planted in the forest belt. Moreover, seedlings are planted in rows at the same distance.
After some time, aerial photography is carried out, as a result of which it is determined which seedlings have taken root. It is necessary to determine the row with the maximum number, in which there are at least 11 non-rooted seedlings in a row, provided that the seedlings have taken root to the right and left of them.
In your answer, first write down the largest number of the row, then the smallest number of the unattached places.
Input
The first line of the input file contains the number N - the number of established seedlings (a natural number not exceeding 10,000). Each of the following N lines contains two natural numbers not exceeding 100,000: the number of the row and the number of the place where the seedlings have taken root.
Imprint
Two non-negative integers: the largest number of the row, then the smallest number of the unattached places.
Example input file
7
40 30
40 34
50 125
50 129
50 64
50 68
50 70
An example answer (when searching for 3 non-rooted seedlings in a row):
50 65
File for the task
| |
![]()
|
|
Темы:
2D arrays
Sorting algorithms
Write a program that rearranges the rows of a matrix so that the values in the K column are in descending order. Rows whose values in the K column are equal must be output in the same order in which they were in the original matrix.
Input
The first line contains space-separated dimensions of the matrix: the number of rows N and the number of columns M ( 1 <= N ;, M <= 100 ). The following N lines contain matrix rows, each – by M natural numbers separated by spaces. The last line is the column number K .
Output
The program should output the resulting matrix, in which the rows are rearranged so that the values in the K column are in descending order.
Examples
| # |
Input |
Output |
| 1 |
4 5
21 22 23 24 25
26 12 18 29 33
11 37 31 14 39
16 17 18 5 20
1
|
26 12 18 29 33
21 22 23 24 25
16 17 18 5 20
11 37 31 14 39
|
| |
![]()
|
|
Темы:
2D arrays
Sorting algorithms
Write a program that rearranges the elements of a square matrix located on the main diagonal in ascending order. The remaining elements of the matrix should remain in place.
Input
The first line contains a single number N the size of a square matrix ( 1 <= N <= 100 ). The following N lines contain matrix rows, each – by N natural numbers separated by spaces.
Output
The program should output the resulting matrix, in which the elements of the main diagonal are arranged in ascending order.
Examples
| # |
Input |
Output |
| 1 |
5
1 11 11 5 10
2 9 2 10 2
12 9 10 9 15
6 15 14 1 11
11 12 4 9 3
|
1 11 11 5 10
2 1 2 10 2
12 9 3 9 15
6 15 14 9 11
11 12 4 9 10
|
| |
![]()
|