| Problem description | | Progress |
|
Темы:
Using sort
Besi is studying for a PhD in Computer Science. She published N articles (1≤N≤105) and her i-th article was cited ci times (0≤ci≤ 105).
Besi heard that academic achievement is measured by the h-index. h-index is the largest number h such that the scientist has at least h articles, each of which is cited at least h times. For example, a scientist with four papers with citation counts (1,100,2,3) has an h-index of 2, and a scientist with citation counts of (1,100,3,3) has an h-index of 3.
To improve her h-index, Besi plans to write a review article citing some of her past articles. Due to a page limit, she can include no more than L citations in her review (0≤L≤105), so of course she can cite each of her articles no more than once.
Help Besi determine the maximum h-index she can achieve by writing her review article.
Note that the supervisor should have warned Besi that writing an article solely for the purpose of increasing his h-index is ethically dubious.
INPUT FORMAT
The first input line contains N and L.
The second input line contains N space-separated integers c1,…,cN.
OUTPUT FORMAT
The maximum h-index that Besi can get by writing a review article.
| # |
Input |
Output |
Explanation |
| 1 |
4 0
1 100 2 3 |
2 |
Besi cannot cite his articles. As stated earlier, its h-index for (1,100,2,3) is 2. |
| 2 |
4 1
1 100 2 3
| 3 |
If Besi cites the third article, her citation counts will become (1,100,3,3). As noted earlier, h in this case is 3.
|
| |
![]()
|
|
Темы:
Using sort
Masha got a set of nesting dolls for her birthday!
Now Masha sits and puts them one into the other. She noticed that nesting dolls differ in size, and one fits inside the other only if its dimensions are strictly smaller. So, if there are two nested dolls i and j , and their sizes are ai and aj respectively, then nested doll i is nested inside nested doll j if and only if ai < aj . Of course, only one other nesting doll can be put directly inside the nesting doll, otherwise it will turn out sloppy, and Masha — very neat girl.
Masha especially likes it if she can put nesting dolls into each other so that they all end up inside one largest nesting doll. But, unfortunately, this is not always possible. Therefore, Masha decided to put some of the nesting dolls in the closet, leaving such a set so that they could all be put into each other. Help Masha understand the maximum number of nesting dolls in such a set.
Input
The first line contains the number n — the number of dolls given to Masha ( 1 ≤ n ≤ 1000 ). The next line contains n space-separated numbers — matryoshka sizes. The number ai , standing in place of i , specifies the size of the doll with number i ( 1 ≤ ai ≤ 10 000 ).
Imprint
Print one number — the maximum number of dolls that can be nested inside each other.
Examples
| # |
Input |
Output |
| 1 |
3
2 10 2
| 2 |
| 2 |
6
2 1 2 1 3 4
| 4 |
| 3 |
4
3 1 4 2
| 4 |
| |
![]()
|
|
Темы:
One-Dimensional Arrays
Using sort
Carlson has a set of n candy jars at home. The jars are numbered from 1 to n , the i -th of them contains a i candies. Carlson considers a set of jars to be cute if this set does not contain three jars with different numbers of sweets.
Carlson has an unlimited supply of sweets in his pockets, so he can add any number of candies to any jar. Help him determine the minimum total number of candies he needs to add to make the set of candy jars cute.
Input
The first line of the input contains a natural number n ( 1 ≤ n ≤ 105 ) — number of cans in Carlson's set.
The second line of the input contains n integers a i ( 0 ≤ ai ≤ 109 ) — number of candies in jars. Neighboring numbers are separated from each other by one space.
Imprint
Print one number — the minimum total amount of candy that Carlson needs to add in order for the jar set to be cute.
Note
In the first test from the example, Carlson can add two candies to the first jar, and — one candy. Then in the first and fourth jars there will be 7 candies each, and in the second and third — 2 sweets each.
In the second test from the example, the set of jars is initially cute, no candy is required.
Examples
| # |
Input |
Output |
| 1 |
4
5 1 2 7
| 3 |
| 2 |
3
1 1 1
| 0 |
| |
![]()
|
|
Темы:
Using sort
Given a natural four-digit number. Find the smallest natural four-digit number that contains the same digits as the given one. Note that four-digit numbers cannot start with a zero.
Input
A natural four-digit number is entered.
Imprint
Print the minimum natural four-digit number consisting of the same digits.
Examples
| # |
Input |
Output |
| 1 |
1513 |
1135 |
| |
![]()
|
|
Темы:
structures
Using sort
Elementary geometry
Print all initial points in ascending order of their distances from the origin.
Create a Point structure and store the original data in an array of Point structures.
Input
The program receives a set of points on the plane as input. First, the number of points n is given, then there is a sequence of n lines, each of which contains two numbers: the coordinates of the point. The value of n does not exceed 100, all initial coordinates – integers not exceeding 103.
Imprint
It is necessary to display all initial points in ascending order of their distances from the origin. The program displays only the coordinates of the points, there is no need to display their number.
Examples
| # |
Input |
Output |
| 1 |
2
1 2
2 3
| 1 2
2 3
|
| |
![]()
|
|
Темы:
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 |
|
| |
![]()
|
|
Темы:
Using sort
Algorithms on strings
Vasya wrote a large number on a long strip of paper and decided to show off this achievement to his older brother Petya. But as soon as he left the room to call his brother, his sister Katya ran into the room and cut a strip of paper into several pieces. As a result, one or more consecutive numbers appeared on each part.
Now Vasya cannot remember exactly what number he wrote. Just remember that it was very big. To console his younger brother, Petya decided to find out what the maximum number could be written on a strip of paper before cutting. Help him!
Input
The input consists of one or more lines, each containing a sequence of digits. The number of lines does not exceed 100, each line contains from 1 to 100 digits. It is guaranteed that the first digit in at least one line is different from zero.
The last line of the input stream contains the number -1 - a sign of the end of the data.
Imprint
Output a single line – the maximum number that could be written on the strip before cutting.
Examples
| # |
Input |
Output |
| 1 |
2
20
004
66
-1 |
66220004 |
| 2 |
3
-1 |
3 |
| |
![]()
|
|
Темы:
USE
Using sort
The file contains positive integers. The first line of the file contains the number N - the number of numbers, and the natural number S. The following N lines contain the actual numbers.
In your answer, indicate two numbers separated by a space: first, the maximum number of numbers that must be added so that the sum does not exceed the number S, then the value of the resulting sum.
| |
![]()
|
|
Темы:
Using sort
USE
In the set of numbers N, replace one number with a number from the set of numbers M so that the sum of the numbers in the set N is as close as possible to the number < code>S. Print three numbers, each on a separate line:
1 line - the number that was replaced from the set N;
2nd line - the number from the set M, which was replaced;
Line 3 - the resulting sum of numbers from the set N.
It is guaranteed that such a substitution can be made. If possible substitutions several, then choose the one in which the number from the N set is less.
Input
In the first line, enter 3 numbers separated by a space: n (10<=N<=105) - the number of numbers in the set N, < code>m (10<=M<=105) - number of numbers in set M, S ( 10<=S<=109) S>sum(N), where sum(N) is the sum of all numbers in the set < code>N.
The second line contains a set of numbers N: n numbers separated by one space (each number modulo does not exceed 105).
The third line contains a set of numbers M: m numbers separated by one space (each number modulo does not exceed 105).
Imprint
Display the answer to the problem as specified in the condition.
Examples
| # |
Input |
Output |
| 1 |
2 2 10
24
1 3
| 2
3
7 |
| |
![]()
|
|
Темы:
USE
Using sort
The system administrator creates an archive of user files once a week. However, the size of the disk where it places the archive may be less than the total size of the archived files. It is known how much space each user's file occupies. Given information about the size of user files and the free space on the archive disk, determine the maximum number of users whose files can be archived, as well as the maximum size of an existing file that can be stored in the archive, provided that the files of the maximum possible number of users are saved. Write a program that calculates the maximum number of users whose files can be archived, as well as the maximum size of an existing file that can be archived, provided that the files of the maximum possible number of users are stored.
Input:
The first line contains two numbers: S – free disk space (a natural number not exceeding 100,000) and N – number of users (a natural number not exceeding 10000). The next N lines contain the values of each user's file sizes (all natural numbers, not exceeding 100), each on a separate line.
Output:
Print two space-separated numbers on one line: first, the largest number of users whose files can be archived, then the maximum size of an existing file that can be archived, provided that the files of the maximum possible number of users are stored.
Example
| # |
Input |
Output |
| 1 |
100 4
80
30
50
40 |
2 50 |
With this initial data, you can save the files of a maximum of two users. The possible sizes of these two files are 30 and 40, 30 and 50 or 40 and 50. The largest file size of the listed – 50, so the answer for this example is: 2 50
| |
![]()
|
|
Темы:
Using sort
USE
In quizzz "Pass the exam for 100 points" You can score up to 10,000 points. At the end of the game, the first K participants who scored the most points receive a bonus to their points in the form of +30% of the scores. You know the information about how many points each participant in the game scored. Determine the maximum number of points that the bonus did not apply to, as well as the integer part of the total bonus amount received by the players.
Input and output data
The first line input file contains two numbers separated by spaces: N – total number of players (a natural number not exceeding 10,000) and K – the number of players who receive the bonus. The following N lines contain the results of each participant (the number of points scored - all natural numbers not exceeding 10,000), each in a separate line.
Write down two numbers in your answer: first, the maximum number of points to which the bonus did not apply, and then the whole part of the sum of all bonuses.
Example input file:
12 4
370
580
3000
1310
1700
2810
1660
1250
1870
1340
1400
1260
With such initial data, the answer should contain two numbers – 1660 2814.
| |
![]()
|
|
Темы:
Using sort
USE
Ded Moroz's factory produces light bulbs of various weights and brightness. The weight of the bulb does not exceed 100 grams, the brightness of the bulb does not exceed 10,000 lumens.
K of the brightest light bulbs are selected to make a New Year's garland. If the brightness of two bulbs is the same and they all do not fit in a garland, then place a bulb with a smaller weight.
Information is known about the weight and brightness of each light bulb brought to the workshop to form a New Year's garland.
Determine the total weight of the bulbs in the garland and the average brightness of the entire garland.
Input and output data
In file in the first line space-separated numbers N are written - the number of light bulbs brought to the workshop (natural number, not exceeding 1000) and K – the number of light bulbs in the garland (a natural number not exceeding 100). Each of the following N lines contains two numbers – the weight and brightness of each bulb.
Write in the answer two numbers – first, the total weight of the bulbs in the garland, then the average brightness of the entire garland (only the whole part).
An example of the organization of source data in the input file:
9 4
50 600
60 480
45 540
30 300
15 180
70 560
30 360
91 910
40 320
Response: 256 652
| |
![]()
|
|
Темы:
USE
Using sort
The planet Bluk is home to the largest super stadium in the galaxy. In the super stadium 10,000 rows, numbered starting from 1. In each row 10 000 places numbered starting from 1. To date, the Superstar concert has sold N tickets. The file contains information about sold tickets: row number and seat number in this row. Determine which row has the most vacant seats adjacent to each other. If there are the same number of such seats in several rows, then indicate the minimum number of the row. And also indicate the minimum number of the place from which such free places begin.
Input
The first line of the input file contains an integer N – the total number of tickets sold. Each of the following N lines contains 2 integers: the row number and the position number in this row.
In your answer, write down two integers: the number of the row that has the most empty seats next to it, then – the minimum number of the place from which such free places begin.
An example of the organization of the initial data in the input file (with 5 rows and 5 places in a row):
17
1 2
23
24
3 1
3 2
4 1
4 2
4 3
5 1
5 5
5 4
5 2
5 3
34
3 5
4 5
15
Response: 1 3
Assignment file
| |
![]()
|
|
Темы:
USE
Using sort
Math lover Gosha came up with his own sequence. The rules in its sequence are:
1) all numbers in the sequence have their own number;
2) the first element of the sequence has number 1;
3) each number in the sequence must be divisible by its number;
4) the number with a larger number must be no less than the number with a smaller number.
An example of Gosha's sequence: 1 4 6 8 10 18 21.
Given a set of numbers, determine what is the maximum number of numbers that can be chosen to compose the Goshin sequence, as well as what is the maximum number that can be in it.
Input
The first line of the input file contains the number N - the number of numbers in the file. Next comes N natural numbers (N <= 105), each on a separate line.
Write down in your answer: first, the maximum number of numbers that can be chosen to make the Goshin sequence, then the maximum number that can be in this sequence.
Example input file:
12
25
17
20
15
6
9
10
12
5
3
4
1
Response: 5 25
Assignment file
| |
![]()
|
|
Темы:
USE
Using sort
The store purchases bolts (bolt), nuts (nut), nails (pin), washers (shim) and screws (screw), for which a certain amount of money has been allocated. The hardware plant has various modifications of these products at a retail price. When buying, the manager is guided by the following rules:
- You need to buy as many items as possible, regardless of their type and modification.
- If you can buy the maximum number of two different items in different ways, you need to choose the method that will buy the most bolts.
- If it is possible to buy the maximum number of products in different ways with the same number of other products, you need to choose the method in which the entire purchase will be cheaper.
Determine how many bolts will be purchased in total and how much will remain unused.
Input
The program receives several lines as input. The first line contains two numbers separated by a space: N - the total number of bolts, nuts, nails, washers and screws from the hardware plant and M - the amount of money allocated for the purchase (in rubles). Each of the next N lines contains an integer (price of the product in rubles) and the type of the product. All data in the lines is separated by a single space.
Imprint
In your answer, write down two whole numbers: first, the number of bolts purchased, then the remaining unused amount of money. (in one line with one space)
Examples
| # |
Input |
Output |
| 1 |
6 1650
600 screw
750 bolt
750 shim
450 pin
300 nut
150 bolt
2 0 |
|
| |
![]()
|
|
Темы:
USE
Using sort
The store purchases bolts (bolt) and nuts (nut), for which a certain amount of money is allocated. The hardware plant has various modifications of these products at a retail price. When buying, the manager is guided by the following rules:
- You need to buy as many items as possible, regardless of their type and modification.
- If you can buy the maximum number of products in different ways, you need to choose the method that will buy the most nuts.
- If you can buy the maximum number of products with the same number of nuts in different ways, you need to choose the method in which the entire purchase will be cheaper.
Determine how many nuts will be bought in total and how much will remain unused.
Input
The program receives several lines as input. The first line contains two numbers separated by a space: N - the total number of bolts and nuts at the hardware plant and M - the amount of money allocated for the purchase (in rubles). Each of the next N lines contains an integer (price of the product in rubles) and the type of product (bolt - bolt, nut - nut). All data in the lines is separated by a single space.
Imprint
In your answer, write down two whole numbers: first, the number of nuts purchased, then the remaining unused amount of money.
Examples
| # |
Input |
Output |
| 1 |
6 6500
1500 bolt
500 bolt
3500 nut
3000 nut
2500 bolt
1000 nut
2 500 |
|
| |
![]()
|
|
Темы:
USE
Using sort
The store purchases bolts (bolt), nuts (nut), nails (pin), washers (shim) and screws (screw), for which a certain amount of money has been allocated. The hardware plant has various modifications of these products at a retail price. When buying, the manager is guided by the following rules:
- You need to buy as many items as possible, regardless of their type and modification.
- If you can buy the maximum number of two different products in different ways, you need to choose the method that will buy the most nuts.
- If you can buy the maximum number of products with the same number of nuts in different ways, you need to choose the method in which the entire purchase will be cheaper.
Determine how many nuts will be bought in total and how much will remain unused.
Input
The program receives several lines as input. The first line contains two numbers separated by a space: N - the total number of bolts and nuts at the hardware plant and M - the amount of money allocated for the purchase (in rubles). Each of the next N lines contains an integer (price of the product in rubles) and the type of the product. All data in the lines is separated by a single space.
Imprint
In your answer, write down two whole numbers: first, the number of bolts purchased, then the remaining unused amount of money. (in one line with one space)
Examples
| # |
Input |
Output |
| 1 |
6 1650
600 screw
750 bolt
750 nut
450 pin
300 nut
150 bolt
2 0 |
|
| |
![]()
|
|
Темы:
USE
Using sort
The store purchases bolts (bolt) and nuts (nut), for which a certain amount of money is allocated. The hardware plant has various modifications of these products at a retail price. When buying, the manager is guided by the following rules:
- You need to buy as many items as possible, regardless of their type and modification.
- If you can buy the maximum number of items in different ways, you need to choose the method that will buy the most bolts.
- If you can buy the maximum number of products with the same number of bolts in different ways, you need to choose the method in which the entire purchase will be cheaper.
Determine how many bolts will be purchased in total and how much will remain unused.
Input
The program receives several lines as input. The first line contains two numbers separated by a space: N - the total number of bolts and nuts at the hardware plant and M - the amount of money allocated for the purchase (in rubles). Each of the next N lines contains an integer (price of the product in rubles) and the type of product (bolt - bolt, nut - nut). All data in the lines is separated by a single space.
Imprint
In your answer, write down two whole numbers: first, the number of bolts purchased, then the remaining unused amount of money. (in one line with one space)
Examples
| # |
Input |
Output |
| 1 |
6 6500
1500 nuts
500 nut
3500 bolt
3000 bolt
2500 nut
1000 bolt
2 500 |
|
| |
![]()
|
|
Темы:
Using sort
USE
Math lover Gosha came up with his own sequence. The rules in its sequence are:
1) all numbers in the sequence have their own number;
2) the first element of the sequence has number 1;
3) each number in the sequence must be divisible by its number;
4) the number with the larger number must be greater than the number with the smaller number.
An example of Gosha's sequence: 1 4 6 8 10 18 21.
Given a set of numbers, determine what is the maximum number of numbers that can be chosen to make the Goshin sequence, and also what is the maximum number that can be in it.
Input
The first line contains the number N - the number of numbers in the file (N <= 105). Next comes N natural numbers (no more than 106), each on a separate line.
Input
Print two space-separated numbers: first, the maximum number of numbers that can be chosen to make the Goshin sequence, then the maximum number that can be in this sequence.
Examples
| # |
Input |
Output |
| 1 |
12
25
17
20
15
6
9
10
12
5
3
4
1 |
5 25 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
Dynamic programming
Using sort
Binary search in an array
The restaurant received n orders for a banquet. Each order is characterized by two values: the start time of the banquet li and the end time ri (li ≤ r i).
The restaurant management can either accept the order or reject it. What is the maximum number of orders that can be accepted?
No two accepted orders can intersect, that is, there should not be a point in time that belongs to two accepted orders at once. If one of the orders starts at the same time as the other ends, then they cannot be accepted together.
Input:
The first line contains an integer n (1 ≤ n ≤ 200000) — the number of orders. Each of the next n lines contains a pair of integers li, ri (0 ≤ li &le ; ri ≤ 109).
Output:
Print the maximum number of orders that can be accepted.
Examples:
| Input |
Output |
2
7 11
4 7 |
1 |
5
1 2
23
34
4 5
5 6 |
3 |
6
48
15
47
25
1 3
68 |
2 |
| |
![]()
|
|
Темы:
Using sort
Greedy Algorithm
Little Misha loves to play with counting sticks. He takes counting sticks from his sister, a first grader. Since he rarely gives them back, Mom often has to buy new sticks. Therefore, not all Misha's sticks are the same, but all sticks have an integer length.
Today Misha is building the next figure out of sticks. He started from the corner of the room. We will denote, conditionally, this angle by the coordinate (0, 0). Then Misha lays out the stick parallel to one of the two walls coming from the given corner. We will assume that the walls are even and form an angle of 90 degrees with each other at the point (0, 0). At the same time, Misha never lays out two sticks in a row at the same time parallel to the same wall (in other words, he always alternates the direction of the sticks).
Misha, although he is small and does not know geometry, is always happy if the end of his figure is as far as possible from the starting angle. Help Misha lay out a figure that will make him happy. Any two sticks that Misha places always have at least one point of contact or intersection.
Input
The program receives several lines as input. The first line contains the integer n (1<= n <= 100000) — the number of sticks Misha has. The second line contains n integers a1,...,a n (1 <= ai <= 10000) - lengths of Misha sticks.
Imprint
Print a single integer — square of the maximum distance from the corner with coordinate (0,0) to the end point of the shape that Misha built.
Examples
| # |
Input |
Output |
| 1 |
3
1 2 3
| 26 |
| 2 |
4
1 1 2 2
| 20 |
| |
![]()
|
|
Темы:
Using sort
Greedy Algorithm
Implementation task
Simple puzzles
"Two Pointers"
Little Misha has cubes, each of which has one English lowercase letter written on it. Yesterday he laid out the cubes in two rows. In the first row Misha has n cubes with letters, in the second - m cubes with letters. It so happened that in these two rows there are no matching letters. In other words, no letter is contained in both rows at the same time.
Today little Misha decided to continue playing with blocks. But now he takes any one cube from any row and makes a third row of them, always adding a cube to the end. Little Misha never takes more than k dice in a row from the same row. Misha stopped playing when he ran out of cubes in one row (in the first or in the second).
Dad, who was watching the game, noticed that playing in this way, Misha got the lexicographically smallest line. Using the known two strings, which are formed by reading the letters of the first and second rows and the number k determine the string that little Misha received.
The string x is lexicographically less than the string y only and only if one of the following conditions is true:
- x is a prefix of y, but x != y;
- in the first position, where x and y differ, in the string x there is a letter that is in the alphabet earlier than the corresponding letter y.
Input
The program receives several lines as input. The first line contains three numbers: n - the number of cubes in the first row, m - the number of cubes in the second row, k > is an integer(1 <= n, m, k <= 100). The second line contains a string a of length n - a string formed by reading the letters written on the cubes of the first row. In the third line - string b of length m - a string formed by reading the letters written on the cubes of the second row.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
6 4 2
aaaaaa
bbbb |
aabaabaa |
| |
![]()
|