Sorting arrays - examples
1. Landscaping
Marko had a garden with N flowers of flowers arranged in the order of the lowest plant to the maximum. Some time has passed and since the plants grow at different speeds, Marko has noticed that the garden is no longer regulated. Marko wants to rebuild his garden, and it works by comparing two adjacent plants, and if the first is higher than the other, replace them. Write a program that prints the height of the plants in the re-arranged Mark's garden.
Input
Number of plants N.
N rows with one number representing the height of the plant.
Output
N rows with one number representing the height of the plant.
Limitations
0 ≤ N ≤ 1000, N is the integer. Plant height is the whole number.
0 ≤ N ≤ 1000, N is the integer. Plant height is the whole number.
Example
Input
5 4 3 7 8 1
Output
1 2 3 4 5 6 7 8
Number of plants N.
N rows with one number representing the height of the plant.
Output
N rows with one number representing the height of the plant.
Limitations
0 ≤ N ≤ 1000, N is the integer. Plant height is the whole number.
0 ≤ N ≤ 1000, N is the integer. Plant height is the whole number.
Example
Input
5 4 3 7 8 1
Output
1 2 3 4 5 6 7 8
2. The shortest fence
There are n trees in the forest. For each of the m trees, its type and geographical coordinates are given. The forester wants to enclose all the trees of one type of wire rectangular shape (viewed from above) whose edges have north-south and east-west directions. What kind of fence should it make to spend the least wires?
Input
In the first place, the number of types n and the number of trees m, separated by a space. In each of the following lines, the description of a single tree is: x-coordinate, then y-coordinate, and finally index of the species, separated by spaces.
Output
First of all the index of fenced species. In the second row, the four integers are separated by spaces representing the coordinates of the fringe of the smallest circumference that includes all the trees of this type: first x and y coordinates of the lower left corner, then the x and y coordinates of the upper right-hand corner (I quadrant). If there are several species that can be enclosed with a fence of the same length, the solution is the one with the smallest index.
Limitations
1 ≤ n ≤ 500, 1 ≤ m ≤ 5000. Coordinates are integers in a closed interval between 0 and 1000. Two trees can have the same coordinates. Each species must be represented at least by one tree, that is, m ≥ n.
Example
Input
2 5
3 1 0
5 2 0
4 2 1
0 4 0
6 0 1
Output
1
4 0 6 2
In the first place, the number of types n and the number of trees m, separated by a space. In each of the following lines, the description of a single tree is: x-coordinate, then y-coordinate, and finally index of the species, separated by spaces.
Output
First of all the index of fenced species. In the second row, the four integers are separated by spaces representing the coordinates of the fringe of the smallest circumference that includes all the trees of this type: first x and y coordinates of the lower left corner, then the x and y coordinates of the upper right-hand corner (I quadrant). If there are several species that can be enclosed with a fence of the same length, the solution is the one with the smallest index.
Limitations
1 ≤ n ≤ 500, 1 ≤ m ≤ 5000. Coordinates are integers in a closed interval between 0 and 1000. Two trees can have the same coordinates. Each species must be represented at least by one tree, that is, m ≥ n.
Example
Input
2 5
3 1 0
5 2 0
4 2 1
0 4 0
6 0 1
Output
1
4 0 6 2
3. Sort numbers
Write a program that arranges (sort) a series of numbers decreasing (each subsequent must be greater than or equal to the previous one).
Input
From the standard input, enter the number n (1≤n≤5⋅10^4) and then n the natural numbers smaller than 2*n, each in a special order.
Output
On the standard output, print the loaded numbers in the sorted order.
Example
Input
5 3 1 6 8 1
Output
1 2 3 4 5 6 7 8
From the standard input, enter the number n (1≤n≤5⋅10^4) and then n the natural numbers smaller than 2*n, each in a special order.
Output
On the standard output, print the loaded numbers in the sorted order.
Example
Input
5 3 1 6 8 1
Output
1 2 3 4 5 6 7 8
4.The most valuable items
For each item that is sold, the code and price are given. The buyer has at his disposal a certain amount of dinar and wants to buy as expensive items as possible. It takes items from the most expensive, with money, in a row. If there is no money for the most expensive, it takes the most expensive money for it. Display the item codes the buyer buys and, if left, the remaining amount of money. Note: this strategy does not guarantee that the items it buys will be in total the highest possible value (for example, if it has 5 $ and if the price of the case is 4, 3 and 2 $, it will buy the object only the object of 4 $, and could buy objects of 3 and 2 $).
Input
In the first line of the standard input there is the amount of money (real number) that the buyer has, in another case number, N
Output
In each line of the standard output, the codes and prices of purchased items (separated by a space) are printed, if any. The last line shows the remaining amount of money, if any.
-
Example 1
Input
1250.75
5
object1
1010.30
object2
357.35
object3
725.45
object4
1125.5
object5
115.75
Output
object4 1125.5
object5 115.75
9.50
Example 2
Input
10000
6
object1
3010
object2
3005
object3
5725
predmet4
1265
object5
2075
predmet6
385
Output
object3 5725.00
object1 3010.00
object4 1265.00
Example 3
Input
1000
6
object1
3010
object2
3005
object3
5725
object4
1265
object5
2075
predmet6
3850
Output
1000.00
In the first line of the standard input there is the amount of money (real number) that the buyer has, in another case number, N
Output
In each line of the standard output, the codes and prices of purchased items (separated by a space) are printed, if any. The last line shows the remaining amount of money, if any.
-
Example 1
Input
1250.75
5
object1
1010.30
object2
357.35
object3
725.45
object4
1125.5
object5
115.75
Output
object4 1125.5
object5 115.75
9.50
Example 2
Input
10000
6
object1
3010
object2
3005
object3
5725
predmet4
1265
object5
2075
predmet6
385
Output
object3 5725.00
object1 3010.00
object4 1265.00
Example 3
Input
1000
6
object1
3010
object2
3005
object3
5725
object4
1265
object5
2075
predmet6
3850
Output
1000.00
5.Merging
In the school of small yellow ants, the teacher examined the control task. The first was to examine the pupils who worked for group A, and then those who worked group B, scored the results for each group and ants based on the number of points they won. Write a program that helps him to get a unique list of all pupils from a list of pupils who did Group A tasks and a list of pupils who did Group B tasks.
Input
From the standard input, the number of pupils mm, who worked group A (5≤m≤25000), is entered, and then the number of points of these pupils, each in a separate line, is then untapped. Thereafter, the number of n students who worked group B (5≤n≤25000) is entered, and then the number of points of these pupils, each in a separate line, is then untapped.
Output
On the standard output, print out the unnumbered sorted set of points of all the students together, each in a separate line.
Example
Input
4 1 3 5 7 3 2 4 5
Output
1 2 3 4 5 6 7
From the standard input, the number of pupils mm, who worked group A (5≤m≤25000), is entered, and then the number of points of these pupils, each in a separate line, is then untapped. Thereafter, the number of n students who worked group B (5≤n≤25000) is entered, and then the number of points of these pupils, each in a separate line, is then untapped.
Output
On the standard output, print out the unnumbered sorted set of points of all the students together, each in a separate line.
Example
Input
4 1 3 5 7 3 2 4 5
Output
1 2 3 4 5 6 7
6.Circular zones
The quality of the signal depends on the distance of the point from the transmitter. The space is divided into zones of circular ring shapes, where the widths of the rings are different from one another. Write a program that determines for the given point the zone to which it belongs.
Input
From the standard input, the number n (1≤n≤50000) is entered, and then n are real numbers rounded to two decimal places, each in a special order, representing the widths of all circular rings. After that enter the number m (1≤m≤50000) and then m pairs of coordinates of the points (in each row there are two real numbers rounded to two decimals, separated by one space).
Output
Print the m line on the standard output. In each line, print either the zone index (counts from zero) which point belongs to or the text outside if the point is outside of the last zone. If a point is at the border of two zones, consider it to belong to the inside.
Example
Input
3
2.0
3.0
7.0
5
1.0 1.0
2.0 3.0
8.0 7.0
13.2 14.5
0.0 12.0
Output
0
1
2
outside
2
From the standard input, the number n (1≤n≤50000) is entered, and then n are real numbers rounded to two decimal places, each in a special order, representing the widths of all circular rings. After that enter the number m (1≤m≤50000) and then m pairs of coordinates of the points (in each row there are two real numbers rounded to two decimals, separated by one space).
Output
Print the m line on the standard output. In each line, print either the zone index (counts from zero) which point belongs to or the text outside if the point is outside of the last zone. If a point is at the border of two zones, consider it to belong to the inside.
Example
Input
3
2.0
3.0
7.0
5
1.0 1.0
2.0 3.0
8.0 7.0
13.2 14.5
0.0 12.0
Output
0
1
2
outside
2
7.Binary search example
There are many types of products in the store and their bar codes are known. The manufacturer wants to find out how many of his products are sold in that store. If the list of all product codes in the store is given in a sorted form, and the list of all product codes of the manufacturer is delivered unsorted, write a program that determines the required number.
Input
From the standard input, the number n (1≤n≤50000) is loaded, and then in the next n lines one natural number (maximum six-digit) is loaded. These numbers represent the bar codes of the product in the store and are sorted by the growing ones. After that, the bar codes of the products delivered by the manufacturer (up to six-digit natural numbers, each in a special order) are loaded to the end of the input.
Output
To the standard output, print the number of products of the manufacturer that are already sold in the store.
Example
Input
5
1
3
5
6
7
2
3
4
5
8
Output
2
From the standard input, the number n (1≤n≤50000) is loaded, and then in the next n lines one natural number (maximum six-digit) is loaded. These numbers represent the bar codes of the product in the store and are sorted by the growing ones. After that, the bar codes of the products delivered by the manufacturer (up to six-digit natural numbers, each in a special order) are loaded to the end of the input.
Output
To the standard output, print the number of products of the manufacturer that are already sold in the store.
Example
Input
5
1
3
5
6
7
2
3
4
5
8
Output
2
© 2019 by Slobodan izprogramiranja.weebly.com
All rights reserved