| Problem description | | Progress |
|
Темы:
Queue
In a children's card game, a deck of cards is dealt equally to two players. Next, they reveal one top card at a time, and the one whose card is higher takes both of the revealed cards for himself, which are placed under the bottom of his deck. The one who remains without cards – loses.
For simplicity, we will assume that all cards are different in face value, and also that the lowest card defeats the highest card ("six takes ace").
The player who takes the cards for himself first places the card of the first player under the bottom of his deck, then the card of the second player (that is, the card of the second player is at the bottom of the deck).
Write a program that simulates the given game and determines who wins. The game involves 10 cards with values from 0 to 9, the big card beats the smaller one, the card with a value of 0 beats the card 9.
Input: The program receives two lines as input: the first line contains 5 numbers separated by spaces — card numbers of the first player, the second – similarly 5 cards of the second player. Cards are listed from top to bottom, meaning each line starts with the card that will be revealed first.
Output: The program should determine who wins in this hand, and output the word first or second, then output the number of moves made before winning. If the game does not end within 106 moves, the program should output the word botva.
Examples
| # |
Input |
Output |
| 1 |
1 3 5 7 9
2 4 6 8 0
| second 5 |
| |
![]()
|
|
Темы:
Queue
The drawing is specified as a A matrix, in which the A[y][x] element defines the color of the pixel at the intersection of the y row and the column x. Recolor to 2 a one-color area starting at pixel (x0,y0).
Input
The first line specifies the size of the n square matrix (\(0<n<10\)). The second line contains the coordinates of the point (x0, y0) - two numbers separated by a space. Followed by n lines of n numbers in each line space (each number is not greater than 10).
Imprint
Output the resulting matrix after recoloring.
Examples
| # |
Input |
Output |
| 1 |
5
1 2
0 1 0 1 1
1 1 1 2 2
0 1 0 2 2
3 3 1 2 2
0 1 1 0 0
| 0 2 0 1 1
2 2 2 2 2
0 2 0 2 2
3 3 1 2 2
0 1 1 0 0
|
| |
![]()
|
|
Темы:
Queue
Everyone knows the exciting game "Battleship". Now you can play Sea Battle not only with a neighbor on your desk, but also with a computer. The game with the computer is played on a rectangular field of arbitrary sizes N×M, where N is the number of rows, M is the number of columns. The Sea Battle World Championship is approaching. It is planned to broadcast it in real time: show a map with ships and display statistics: the number of intact, damaged and destroyed ships on the field. It is required to write a program to calculate statistics.
Ship on the field — this is a connected figure, standing from one or more adjacent cells that have a common side. Ships can be absolutely any shape and size!
Input
The first line contains two integers N and M (\(1<= N,M <= 10^3\) ), separated by spaces. These are the dimensions of the playing field. Next come N lines of M characters - a description of the playing field. The English letter 'X' denotes a padded ship cell, 'S' - unlined ship cell, '-' – free water space.
Output
In your answer, output three numbers separated by a space:
- number of whole ships;
- number of wrecked ships;
- number of destroyed ships.
Examples
| # |
Input |
Output |
| 1 |
3 8
---SSS--
XX--S-X-
X-S---S-
|
2 1 1 |
| |
![]()
|
Темы:
Queue
Chief Wiggum must ensure the correct order of the floats in the city parade. Platforms can arrive in any order, but must enter the central square strictly in ascending order of numbers. Wiggum can direct the platform either directly to the square, or first to a side street, and then from it to the square. The length of the side street is sufficient to accommodate all platforms, but the width of the streets does not allow one platform to overtake another.
Write a program to determine if Wiggum can ensure the floats move in the correct order on parade.
Input
The first line of input contains a single integer N ( \(1 <= N <= 100\)) – number of platforms.
The second line contains N different integers from 1 to N – platform numbers in order of arrival.
Imprint
Print "YES" if the correct platform order can be ensured, or "NO" if not.
Examples
| # |
Input |
Output |
| 1 |
4
1 3 4 2
|
YES |
| 2 |
4
4 3 2 1
|
NO |
| 3 |
4
2 1 3 4
| YES |
| |
![]()
|
|
Темы:
Bypass in width
Queue
In an undirected graph, you want to find the length of the shortest path between two vertices.
Input:
- the first line of the input contains the number N - the number of vertices in the graph (\(1<=N<=100\));< br />
- next, the adjacency matrix is written from a new line (0 indicates the absence of an edge, 1 - the presence of an edge);
- the last line contains the numbers of two vertices - start and end.
Output: Print the length of the shortest path. If the path does not exist, print a single number -1.
Examples
| # |
Input |
Output |
| 1 |
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
|
3 |
| |
![]()
|
|
Темы:
Queue
Case Study
Farmer Eureka's pasture can be viewed as a huge 2D grid of cells (a chessboard). Initially, the pasture is empty.
Farmer Yurik adds N (\(1<=N<=10^5\)) cows to pasture one by one. ith cow will occupy the cell (xi,yi ) which is different from the cells occupied by all other cows (\(0<=x_i,y_i<=1000\)).
A cow is called "comfortable" if it has exactly three horizontal and vertical neighbors. Comfortable cows produce less milk, so Farmer Yurik wants to add cows until there are comfortable cows (including the one he will add). Note that the cows you add do not have to have x and y coordinates in the range \(0… 1000\).
For each i in the range \(1…N\), print the minimum number of cows it needs to add so that there are no comfortable cows left, assuming that only cows are in the pasture \(1…i\).
Input
The first line contains the integer N. Each of the following N lines contains 2 space-separated integers (x, y) indicating cell coordinates with a cow.
Imprint
The minimum number of cows Farmer Yurik must add, for each i in the \(1…N\) range, on a separate line.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
9
0 1
10
1 1
1 2
2 1
2 2
3 1
3 2
4 1 |
0
0
0
1
0
0
1
2
4 |
For i=4, Farmer Yurik must add a cow to position (2,1),
to make the cow in position (1,1) uncomfortable.
For i=9, the best Farmer can do is add cows at positions (2,0), (3,0), (2,−1), (2, 3).
|
| |
![]()
|
|
Темы:
Queue
Simulation tasks
In the game of drunkard, the deck of cards is dealt equally to two players. Next, they reveal one top card at a time, and the one whose card is higher takes both of the revealed cards for himself, which are placed under the bottom of his deck. The one who remains without cards – loses.
For simplicity, we will assume that all cards are different in face value, and also that the lowest card defeats the highest card (“six takes ace”).
The player who takes the cards for himself first places the card of the first player under the bottom of his deck, then the card of the second player (that is, the card of the second player is at the bottom of the deck).
Write a program that simulates a game of drunkard and determines who wins. The game involves 10 cards with values from 0 to 9, the big card beats the smaller one, the card with a value of 0 beats the card 9.
Input
The program receives two lines as input: the first line contains 5 numbers separated by spaces — card numbers of the first player, the second – similarly 5 cards of the second player. Cards are listed from top to bottom, meaning each line starts with the card that will be revealed first.
Imprint
The program should determine who wins the given hand, and output the word first or second, and then print the number of moves made before winning. If the game does not end within 106 moves, the program should output the word botva.
Examples
| # |
Input |
Output |
| 1 |
1 3 5 7 9
2 4 6 8 0
| second 5 |
| |
![]()
|
|
Темы:
Queue
Implement the "queue" data structure. Write a program that describes the queue and simulates the operation of the queue by implementing all the methods listed here. The program reads a sequence of commands and, depending on the command, performs one or another operation. After executing each command, the program should print one line. Possible commands for the program:
push n
Add the number n to the queue (the value of n is given after the command). The program should print ok.
pop
Remove the first element from the queue. The program should output its value.
front
The program should output the value of the first element without removing it from the queue.
size
The program should print the number of elements in the queue.
clear
The program should clear the queue and print ok.
exit
The program should print bye and exit.
It is guaranteed that the set of input commands satisfies the following requirements: the maximum number of elements in the queue at any time does not exceed 100, all pop and front commands are correct, that is, when they are executed, the queue contains at least one element.
Input
Queue management commands are entered, one per line
Imprint
It is required to display the log of work with the queue, one message per line
Examples
| # |
Input |
Output |
| 1 |
size
push 1
push 2
push 3
exit |
0
ok
1
ok
2
ok
3
bye |
| |
![]()
|
|
Темы:
Queue
Implement the "queue" data structure. Write a program that describes the queue and simulates the operation of the queue by implementing all the methods listed here. The program reads a sequence of commands and, depending on the command, performs one or another operation. After executing each command, the program should print one line. Possible commands for the program:
push n
Add the number n to the queue (the value of n is given after the command). The program should print ok.
pop
Remove the first element from the queue. The program should output its value.
front
The program should output the value of the first element without removing it from the queue.
size
The program should print the number of elements in the queue.
clear
The program should clear the queue and print ok.
exit
The program should print bye and exit.
Before executing the front and pop operations, the program must check whether the queue contains at least one element. If there is a front or pop operation in the input data, and the queue is empty, then the program should output the string error instead of a numeric value.
Input
Queue management commands are entered, one per line
Imprint
It is required to display the log of the queue operation, one message per line
Examples
| # |
Input |
Output |
| 1 |
push 1
exit |
ok
1
bye |
| 2 |
size
push 1
push 2
push 3
exit |
0
ok
1
ok
2
ok
3
bye |
| |
![]()
|
|
Темы:
Queue
Gromozeka handed out N to earthly children standing in a circle, brought gifts. In order not to offend anyone, Gromozeka decided that every time he would give a gift to the K-th child. The child who received the gift happily ran out of the circle, and everyone else closed the circle.
Decide in what order the children received the gifts.
Input
The input string contains numbers N ( 1 <= N <= 10000 ) and K ( 1 <= K <= 10000 ), separated by spaces.
Imprint
The program should display in one line, separated by a space, the numbers of the guys in the order in which they receive the gift.
Examples
| # |
Input |
Output |
| 1 |
5 3 |
3 1 5 2 4 |
| |
![]()
|