| Problem description | | Progress |
|
Темы:
Bypass in width
Vitya wants to come up with a new game with numbers. This game requires players to convert four-digit non-zero numbers using the following allowed set of actions:
1. You can increase the first digit of a number by 1 if it is not equal to 9.
2. You can decrease the last digit by 1 if it is not equal to 1.
3. You can cycle through all the numbers by one to the right.
4. You can cycle through all the numbers by one to the left.
For example, applying these rules to the number 1234 results in the numbers 2234, 1233, 4123, and 2341, respectively. Victor has not yet come up with the exact rules of the game, but for now he is interested in the question of how to get another from one number in the minimum number of operations.
Input: The input is given two different four-digit numbers, each of which does not contain zeros. Each number on a new line
Output: The program should output a sequence of four-digit numbers that do not contain zeros. The sequence must start with the first of the given numbers and end with the second of the given numbers, each subsequent number in the sequence must be obtained from the previous number by applying one of the rules. The number of numbers in the sequence should be as small as possible.
Examples
| # |
Input |
Output |
| 1 |
1234
4321 |
1234
2234
3234
4323
4322
4321 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
ID 22020.
Path
Темы:
Bypass in width
In an undirected graph, you need to find the minimum path between two vertices.
Input:
- the first line contains the number N - the number of vertices in the graph (\(1<=N<=100\));
- the next lines set the adjacency matrix (0 means no edge, 1 - edge);
- the last line contains numbers of two vertices - initial and final.
Output: print first L - the length of the path (number of edges to pass). Then print < code>L+1 number - vertices in order along this 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
3 2 1 5
|
| |
![]()
|
|
Темы:
Bypass in width
On the chessboard NxN in the cell (x1, y1) there is a hungry chess knight. He wants to get into the cell (x2, y2), where delicious chess grass grows. What is the least number of moves he has to make to do this?
Input: The program receives five numbers: N, x1< /code>, y1, x2, y2 (\(5 <= N <= 20\), \(1 <= x_1,\ y_1,\ x_2,\ y_2 <= N\)).
The top left cell of the board has coordinates (1, 1), the bottom right cell has coordinates (N, N).
Output: Print a single number K - the least necessary number of knight moves.
Examples
| # |
Input |
Output |
| 1 |
5
1 1
3 2 |
1 |
| |
![]()
|
|
Темы:
Bypass in width
One of the Top-Secret Organizations, whose name we are not allowed to reveal, is a network of N underground bunkers connected by tunnels of equal length, through which one can get from any bunker to any other (not necessarily directly). Communication with the outside world is carried out through special secret exits, which are located in some of the bunkers.
The organization needed to draw up a staff evacuation plan in case of an emergency. To do this, for each of the bunkers, you need to find out how long it will take to get to the nearest exit. You, as a specialist in such tasks, are instructed to calculate the required time for each of the bunkers according to a given description of the premises of the Top Secret Organization. For your convenience, the bunkers are numbered from 1 to N.
Input:
- the first two lines contain two natural numbers N, K (\(1 <= N <= 100000\) , \(1 <= K <= N\)) — the number of bunkers and the number of exits respectively;
- in the third line, space-separated K different numbers from 1 to N, indicating the numbers of the bunkers where the exits are located;
- the fourth line contains the number M (\(1 <= M <= 100000\)) — number of tunnels;
- in the following M lines enter pairs of numbers – numbers of bunkers connected by a tunnel.
Each of the tunnels can move in both directions. An organization does not have tunnels leading from a bunker to itself, but there can be more than one tunnel between a pair of bunkers.
Output: print N space-separated numbers — for each of the bunkers, the minimum time required to get to the exit. Assume that the time to travel through one tunnel is 1.
Examples
| # |
Input |
Output |
| 1 |
3
1
2
3
1 2
3 1
2 3
| 1 0 1 |
| 2 |
10
2
10 8
9
67
75
58
8 1
1 10
10 3
34
49
9 2 |
1 4 1 2 1 3 2 0 3 0 |
| |
![]()
|
|
Темы:
Bypass in width
Case Study
In the country from the previous task, there are many specialists not only in the protection of children, but also in the design of cities. Therefore, in order to solve the problem of traffic jams in the overcrowded capital once and for all, it was decided to build a new capital and move the entire government there. It is said — done.
The streets in the new capital form a regular rectangular grid in which all streets intersect at exactly one local length unit. Vertically running streets are called streets, and horizontally running — alleys. In total, the city got 2000 streets and 2000 alleys, therefore, in order not to come up with many new names, they were all simply numbered. The streets were numbered from west to east with numbers from −1000 to 999, and alleys — from south to north, also numbers from −1000 to 999. The city center is considered to be blocks at the intersection of streets and alleys with numbers from −100 to 100.
In order to increase the capacity of roads in the city, it was decided to make all streets and alleys one-way. On streets with even numbers it is allowed to drive only from north to south, and on streets with odd numbers — only from south to north. Similarly, even-numbered alleys can only be driven from east to west, and odd-numbered — only from west to east.
How many local units of length will the mayor of the new capital have to pass every evening, returning home from the mayor's office of the city? Both the city hall and the mayor's house are located in the city center. The mayor is driving home by the shortest route, observing, however, the rules of the road.
Input
The first line contains two numbers x1 and y1 — street number and alley number at the intersection of which the city hall is located. The second line contains two numbers x2 and y2 — street number and alley number at the intersection of which the mayor's house is located. All numbers are integers and do not exceed 100 in absolute value.
Imprint
Print one number: the length of the shortest path from the mayor's office to the mayor's house by car.-
Examples
| # |
Input |
Output |
| 1 |
0 0
1 1
| 4 |
| 2 |
3 5
24 |
4 |
| |
![]()
|
|
Темы:
Bypass in width
2D arrays
You are one of the developers of a new computer game. The game is played on a rectangular board consisting of W×H cells. Each cell can either contain or not contain a chip (see picture).
An important part of the game is to check if two pieces are connected in a way that satisfies the following properties:
1. The path must consist of segments of vertical and horizontal straight lines.
2. The path must not cross other tokens.
In this case, part of the path may be off the board. For example:
Chips with coordinates (1, 3) and (4, 4) can be connected. Chips with coordinates (2, 3) and (5, 3) can also be connected. But chips with coordinates (2, 3) and (3, 4) cannot be connected — any path connecting them intersects other tiles.
You need to write a program that checks whether two tiles can be connected by a path that has the above properties, and, in case of a positive answer, determines the minimum length of such a path (it is assumed that the path has breaks, the beginning and end only in the centers of cells (or “ cells”, located outside the board), and the segment connecting the centers of two adjacent cells has a length of 1).
Input data format
The first line of the input file contains two natural numbers: W — board width, H — board height (1 ≤ W, H ≤ 75). The next H lines contain a description of the board: each line consists of exactly W characters: the character “X” (capital English letter “ex”) denotes a chip, the symbol “.” (dot) denotes an empty space. All other lines contain descriptions of requests: each request consists of four natural numbers separated by spaces — X1, Y1, X2, Y2, where 1 ≤ X1, X2 ≤ W, 1 ≤ Y1, Y2 ≤ H. Here (X1, Y1) and (X2, Y2) — the coordinates of the chips to be connected (the upper left cell has the coordinates (1, 1)). It is guaranteed that these coordinates will not match (except for the last request). The last line contains a query consisting of four numbers 0; this request does not need to be processed. The number of requests does not exceed 20.
Output data format
For each query, print one integer on a separate line — the length of the shortest path, or 0 if no such path exists.
Examples
| # |
Input |
Output |
| 1 |
5 4
XXXXX
X...X
XXX.X
.XXX.
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
|
5
6
0 |
| 2 |
4 4
XXXX
.X..
..X.
X...
1 1 3 1
0 0 0 0
|
4 |
| |
![]()
|
|
Темы:
Bypass in width
Simulation tasks
There are N halls in the dungeon connected by tunnels. In some halls there are robots that have simultaneously received a command to gather in one place.
The robots are arranged in such a way that, having received a command, they all begin to move at such a speed that the tunnel between any two halls is overcome in 1 minute. Robots cannot stop (including in the halls) and also change direction while in the tunnels (however, once in the hall, the robot can go out of it through the same tunnel through which it came to this hall).
Write a program that calculates the minimum time it takes for all the robots to get together (in a hall or in a tunnel).
Input
First, the numbers N — number of halls (1≤N≤400) and K — number of tunnels (1≤K≤20000). Next, K pairs of numbers are introduced, each pair describes the numbers of halls connected by a tunnel (you can move along the tunnel in both directions). There may be several tunnels between two halls. The tunnel can connect the hall to itself. This is followed by the number M (1≤M≤400) — the number of robots. Then M numbers are entered, specifying the numbers of the halls where the robots are located at the beginning. There can be several robots in one room.
Imprint
Print the minimum time in minutes after which the robots can get together. If the robots can never get together, print a single number –1 (minus one).
Examples
| # |
Input |
Output |
| 1 |
4 5
1 2
23
34
14
1 3
3
1 2 4
| 1 |
| 2 |
3 2
1 2
23
2
1 3
| 1 |
| |
![]()
|
|
Темы:
Algorithms on graphs
Shortest paths in a graph
Bypass in width
You are given a tree with N vertices. Here a tree is a kind of graph, more precisely, a connected undirected graph with N−1 edges, where N is the number of its vertices. Ith edge (\(1<=i<=N-1\)) connects ai vertices and bi and is ci.
You are also given Q queries and an integer K. For each jth query (\(1<=j<=Q\)) find the length of the shortest path from the top xj to vertex yj via vertex K.
Input
The first line contains an integer N (\(3<=N<=10^5\)). The following N lines contain the vertices ai and bi (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\) ) and the length between them ci (\(1<=c_i<=10^9\ ), \(1<=i<=N-1\))
Next come two numbers Q and K (\(1<=Q<=10^5\), \(1<=K<=N\)). The last Q lines contain integers xj, yj (\(x_j \neq y_j\),\(x_j \neq K\), < span class="math-tex">\(y_j \neq K\) \(1<=j<=Q\), ) .
The given graph is a tree.
Imprint
Print responses to queries in Q lines. On the j-th line print the answer to the j-th query.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
24
23
4 5 |
3
2
4 |
The shortest paths for the three queries are as follows:
Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4: Length 1 + 1 + 1 = 3
Query 2: Vertex 2 → Vertex 1 → Vertex 3: Length 1 + 1 = 2
Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Pinnacle 3 → Vertex 5: Length 1 + 1 + 1 + 1 = 4 |
| 2 |
7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7
| 5
14
22 |
The path for each request must pass through node K = 2. |
| 3 |
10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10
| 17000000000 |
|
| |
![]()
|
|
Темы:
Bypass in width
Given a table consisting of N rows and M columns. Each cell of the table contains one of the numbers: 0 or 1. The distance between the cells (x1, y1) and (x2, y2) is the sum |x1-x2|+|y1-y2|. You need to build a table, in the cell (i, j) which will contain the minimum distance between the cell (i, j) of the initial table and the cell in which 1 is written. It is guaranteed that there is at least one 1 in the table.
Input
The first line contains two natural numbers N and M, not exceeding 500. Then there are N lines of M numbers each - elements of the table.
Imprint
It is required to display N lines by M numbers - the elements of the desired table.
Examples
| # |
Input |
Output |
| 1 |
2 3
0 0 1
1 0 0
| 1 1 0
0 1 1 |
| |
![]()
|
|
Темы:
Bypass in width
On a standard chessboard (8x8) there are 2 chess knights: Red and Green. Usually they carelessly jump across the expanses of the board, pinching the chess grass, but today is a special day: the Green Horse has a birthday. The green horse decided to celebrate this event with the red one. But for the implementation of this wonderful plan, they need to be on the same cell. Note that the Red and Green chess knights are very different from black and white: they do not move in turn, but at the same time, and if they end up on the same square, no one eats anyone. How many moves will they need to enjoy the holiday?
Input
The input of the program is the coordinates of the horses, written according to standard chess rules (i.e., two characters - a small Latin letter (from a to h) and a number (from 1 to 8), defining a column and a row, respectively).
Imprint
It is required to output the least required number of moves, or the number -1 if the knights cannot meet.
Examples
| |
![]()
|
Темы:
Bypass in width
Some villages are connected by roads, which can be represented as an undirected graph. The vertices of this graph are villages, and the edges are roads between villages (the graph may contain cycles). It is known that in the village S an artel Pedlars. Every morning, to sell their small haberdashery, peddlers go to villages that have not yet visited, and to which there there is a road from the current one. The artel of peddlers is always divided into groups so that they can go around all the villages that have roads from the current one in one day.
In how many days will the peddlers visit all the villages? Write a \(bfs()\) function that will return the answer to the problem.
Input
The first line contains 3 integers n, m, s ( \(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - the number of villages, the number of roads between them, and the number of the village in which the peddler's gang is based. In the following m< /code> lines contain 2 numbers each u, v(\(1 <= u, v <= n\ )) - numbers of two villages between which there is a road. Villages are indexed with 1.
Imprint
Print a single number - how many days it will take the pedlars to visit all the villages.
Examples
| # |
Input |
Output |
| 1 |
6 7 1
1 2
15
23
5 4
34
36
4 6 |
4 |
| |
![]()
|
|
Темы:
Bypass in width
Some cells have been removed from a rectangular sheet of checkered paper (M rows, N columns). How many pieces will the rest of the sheet break up into? Two cells do not fall apart if they have a common side.
Input
The first line contains the numbers M and N, the following M lines contain N characters. If the cell has not been cut out, this corresponds to the # sign, if it is cut out - a dot. 1 <= M, N <= 100.
Output
Output one number.
Examples
| # |
Input |
Output |
| 1 |
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
|
5
|
| |
![]()
|
|
Темы:
Bypass in width
Unemployed Dave out of boredom built a labyrinth out of cardboard boxes in his own living room. Maze contains K inputs. When his girlfriend Annie returned, the labyrinth grew incredibly from the inside, and the unfortunate inventor himself got lost there and can't get out.
The only thing Annie found in the room was a map of the labyrinth, which has dimensions of NxM cells. The map showed the place where Dave is located (no one knows how it happened). The cells of the labyrinth are either empty, which you can walk through, or there is a wall in them and you cannot walk through them. A cell can have up to 4 adjacent cells, which can be accessed from the current one.
Annie has invited you to help her figure out where to start on her way to get to Dave as quickly as possible. If there are multiple such entrances, Annie will go from the entrance with the smallest number.
Input
The program takes several lines as input. The first line contains 2 numbers N and M (1<= N, M <= 100, NxM <= 100), dimensions labyrinth. This is followed by N lines of M characters each - a description of the labyrinth. 0 means that the cell is free; 1 that there is a wall in the cage. The symbol * denotes a cage with Dave.
The (N+2)th line contains the number K (1<=K<=NxM) -- the number of entrances to the labyrinth. The K lines then contain the coordinates of the inputs. The ith line contains the numbers xi and yi meaning that i- The th entry is located in the xith row and in the yith column (1<=xi<=N,1<=yi<=M).
The coordinates of the entrances are pairwise different, all the entrances are located in empty cells. None of the entrances are in the cage with Dave.
Output
Print one number - the input number (numbering starts from 1). If Dave can't be reached, print -1.
Examples
| # |
Input |
Output |
| 1 |
5 5
00000
00000
10*00
01111
00000
4
eleven
15
4 1
5 5
|
1
|
| 2 |
3 3
010
1*1
010
4
eleven
13
3 1
3 3
|
-1
|
| |
![]()
|
|
Темы:
Bypass in width
Aborigines from the planet Sheshiner are very fond of terrestrial pineapples. After visiting them, Alice decided to send a few of them as a gift. There are only 24 hours to deliver fresh pineapples.
Alice wants to send as many pineapples as possible. Captain Poloskov decided to help her and happily agreed to fly on his spaceship. But there is one caveat: on some space routes, you can refuel a ship that does not exceed the maximum weight. And you always need to refuel the ship on the way, otherwise it simply will not fly. Therefore, if the ship is filled with pineapples to the maximum, then it will not be possible to refuel it on the way and therefore it will not be possible to use the shortest routes, and you will have to fly through other planets. It may even happen that the ship does not have time to reach Sheshinyera in time, and the pineapples will go bad.
So, how many pineapples can be loaded into a spaceship to deliver the cargo on time?
Input
The program receives several lines as input. The first line contains the numbers n (1 <= n <= 500) and m - the number of planets and the number of space routes between planets, respectively. The following m lines contain information about the routes. Each route is described on a separate line as follows. First, the numbers of the planets that are connected by a space route are indicated, then the time spent on a flight along this route, and, finally, the maximum spacecraft that can be refueled along this route. It is known that all space routes connect different planets, and for each pair of planets there is at most one route directly connecting them. All numbers are separated by one or more spaces.
Planets are numbered from 1 to n. Planet Earth has number 1, and Sheshiner's planet has number n. The flight time along the route is specified 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 pineapple weighs 100 grams, and an empty ship weighs 3 tons.
Imprint
Print a single number - the maximum number of pineapples that can be delivered within 24 hours.
Examples
| # |
Input |
Output |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2
|
| |
![]()
|