| Problem description | | Progress |
|
Темы:
Depth walk
Bor
A chain of words of length n is a sequence of words w1, w2, ..., wn such that for 1 ≤ i ≤ n the word wi is a proper prefix of the word wi + 1.
Recall that a word u of length k is called a proper prefix of word v of length l if l > k and the first k letters of v match the word u.
Set of words S = {s1, s2, ..., sm >}. Find the maximum length of a chain of words that can be constructed using (perhaps not all) the words of this set.
Input
The first line of the input file contains the integer m(1 ≤ m ≤ 255). Each of the next m lines contains one word from the set S.
All words are not empty, have a length not exceeding 255 characters, and consist only of lowercase Latin letters.
Output
Output the answer to the problem in the output file.
| Input |
Output |
|
3
a
ab
abc
|
3 |
|
5
a
ab
bc
bcd
add
|
2 |
| |
![]()
|
|
Темы:
Bor
Depth walk
You need to print N words on Movable Type Printer. Movable Type Printers — they are old printers that require small pieces of metal (each piece containing one letter) to be placed in a certain order to form words. Then they are all pressed into a sheet of paper. This prints one word. Your printer allows you to do the following:
- Add a letter to the end of the word currently on the printer.
- Remove the last letter from the word currently on the printer. This operation can be done only if the word contains at least one letter.
- Print the word currently on the printer.
Initially, the printer contains an empty word. You can leave a non-empty word at the end of printing on the printer. You can type the words you are given in any order.
Each of the three operations takes one unit of time. You need to find a sequence of operations that prints the given N words in the minimum amount of time. If there are several minimal sequences, print any one.
Input
Your program should take the following input:
On the first line is the number N (1<=N<=25000).
On the next N lines, words consisting of small letters of the Latin alphabet. The length of each word does not exceed 20. All words are different.
Output
Your program should output the following:
On the first line M — number of operations.
On the next M lines, one — description of operations. Each operation is described by a single character:
Adding a character is indicated by the character itself.
Deleting a character is indicated by the character "-" (minus, ASCII code 45).
The "print current word" operation denoted by the symbol «P» (capital Latin letter P).
| Input |
Output |
|
3
print
the
poem
|
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
|
| |
![]()
|
|
Темы:
Depth walk
Given a directed unweighted graph. It is necessary to sort it topologically.
Input: The first line contains two natural numbers n and m (1≤n≤105, 1≤m≤10< sup>5) — the number of vertices and edges in the graph, respectively. Next m lines list the edges of the graph. Each edge is given by a pair of numbers — the numbers of the start and end vertices, respectively.
Output: Print any topological sort of the graph as a sequence of vertex numbers. If the graph cannot be topologically sorted, print −1.
The first line contains the number of vertices N and edges M.
Examples
| # |
Input |
Output |
| 1 |
4 4
14
4 3
4 2
3 2 |
1 4 3 2 |
| |
![]()
|
|
Темы:
Depth walk
An undirected unweighted graph is given. For it, you need to find the number of vertices that lie in the same connected component with a given vertex (counting this vertex).
Input: The first line of the input contains two numbers: N and S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), where N– the number of graph vertices, and S – given top. The next N lines contain N numbers each – graph adjacency matrix, where 0 means no edge between vertices, and 1 – its presence. It is guaranteed that there are always zeros on the main diagonal of the matrix.
Output: Print a single integer – desired number of vertices.
Examples
| # |
Input |
Output |
| 1 |
3 1
0 1 1
1 0 0
1 0 0
| 3 |
| |
![]()
|
|
Темы:
Depth walk
Count the number of connected components in an undirected graph. There can be loops and multiple edges in a graph.
Input: First, the first line contains two numbers N and M, setting respectively the number of vertices and the number of edges (1<=N<= 100, 0<=M<=10000), and then the edges are listed. Each edge is defined by the two vertex numbers it connects
Output: Print a single number - the number of connected components
Examples
| # |
Input |
Output |
| 1 |
3 4
1 1
1 2
1 3
2 3
|
1 |
| 2 |
5 3
1 1
1 2
2 1
|
4 |
| 3 |
5 0 |
5 |
| |
![]()
|
|
Темы:
Depth walk
An undirected, unweighted graph is given. You need to determine if it is a tree.
Input: The first line contains one natural number N (N ≤ 100) - the number of vertices in the graph. Next, in N lines, N numbers each - the adjacency matrix of the graph: in the i-th line, the j-th position is 1 if vertices i and j are connected by an edge, and 0 if there is no edge between them. There are zeros on the main diagonal of the matrix. The matrix is symmetrical about the main diagonal.
Output: Print "YES" if the graph is a tree and "NO" otherwise.
Examples
| # |
Input |
Output |
| 1 |
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
|
NO |
| 2 |
3
0 1 0
1 0 1
0 1 0
|
YES |
| |
![]()
|
|
Темы:
Depth walk
N Very Important Persons (VVPs) were invited to the banquet. 2 tables were set up. The tables are large enough so that all banquet attendees can sit at any of them. The problem is that some OVPs don't get along with each other and can't sit at the same table. You have been asked to determine if it is possible for all OVPs to be seated at two tables.
Input: The first line of the input contains two numbers: N and M (1 <= N,M <= 100), where N – the number of ORP, and M – the number of OVP pairs that cannot sit at the same table. The next M lines contain 2 numbers – OVP couples who can't sit at the same table.
Output: If there is a way to seat OVP, then print YES on the first line and the numbers of the OVPs you need to seat at the first table on the second line. Otherwise, in the first and only line print NO.
Examples
| # |
Input |
Output |
| 1 |
3 2
1 2
1 3
|
YES
1 |
| |
![]()
|
|
Темы:
Depth walk
You are given a directed unweighted connected graph. You want to determine if it contains cycles.
Input: The first line contains one natural number n — number of vertices (0 ≤ n ≤ 1 111).
The next n lines contain the adjacency matrix of the graph. If the position (i, j) of the square matrix is 1, then the i-th and j-th edges are connected by edges, and if it is a zero, then they are not connected. In this case, the edge is directed from the i-th to the j-th edge of the graph, and the j-th and i-th edges are not connected by edges.
Output: The first line should contain YES if the graph contains a cycle and NO — otherwise.
Examples
| # |
Input |
Output |
| 1 |
8
0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
|
YES |
| |
![]()
|
|
Темы:
Depth walk
Given a matrix of N (1 <= N <= 100) by M (1 <= M <= 100). The matrix contains ‘.’ – empty cells and ‘#’ – cells that cannot be visited. You can only move up, down, left and right. Given q queries: row number and column number, if this cell – ‘#’, then it becomes ‘.’, otherwise – ‘#’. For each of q queries, determine whether cell tx;ty is reachable from cell Sx;Sy . Output on each line “Yes”, if reachable, and “No” - otherwise. It is guaranteed that the cell Sx; Sy and cell tx; ty are not ‘#’ cell in each request.
Input data.
On the first line enter the numbers Sx (1 <= Sx <= 100), Sy (1 < = Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), N (1 <= N <= 100), M(1 <= M <= 100) and q (1 <= q <= 100). The next N lines give a matrix where ‘.’ – empty cell and ‘#’ – a cell that cannot be visited. The next q lines give the row number and column number to be changed.
Output.
Print for each of the q queries “Yes”, if from cell Sx; Sy into cell tx; ty can be hit, “No” – otherwise.
| Input |
Output |
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2 |
No
Yes |
Explanation:
After the first request, the matrix will look like this:
. . #
# # .
###
There is no passage from point 1;1 to 2;3, therefore, we print “No”.
After the second request, the matrix will look like this:
. . #
# . .
###
There is a passage from point 1;1 to 2;3, so we output “Yes”. The path we can follow is highlighted.
(с) Vsevolod Shaldin
| |
![]()
|
|
Темы:
Depth walk
A rectangular garden plot N meters wide and M meters long is divided into squares with a side of 1 meter. Beds have been dug up in this area. A bed is a collection of squares that satisfies the following conditions:
* from any square of this bed you can get into any other square of the same bed, successively moving along the bed from square to square through their common side;
* no two beds intersect and do not touch each other either on the vertical or horizontal sides of the squares (touching the beds with the corners of the squares is allowed).
Count the number of beds in the garden.
Input
The first line contains the numbers N and M separated by a space, followed by N lines of M characters each. The symbol # denotes the territory of the beds, the dot corresponds to the unoccupied territory. There are no other characters in the original file. 1≤ N, M≤ 200.
Imprint
Print one number - the number of beds in the garden.
Examples
| # |
Input |
Output |
| 1 |
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
|
5 |
| |
![]()
|
|
Темы:
Depth walk
Enterprise "Auto-2010" produces engines for world-famous cars. The engine consists of exactly n parts, numbered from 1 to n, and the part with number i is made in pi seconds. The specifics of the enterprise "Auto-2010" is that only one engine part can be manufactured there at a time. Some parts require a prefabricated set of other parts to be produced.
General Director of "Auto-2010" set an ambitious task for the enterprise — to produce part number 1 in the shortest time to present it at the exhibition.
It is required to write a program that, given the dependencies of the order of production between parts, will find the shortest time in which it is possible to produce part number 1.
Input
The first line of the input file contains the number n (1≤ n ≤ 100000) — number of engine parts. The second line contains n positive integers p1, p2, pn, which define the manufacturing time of each part in seconds. The time to craft each part does not exceed 109 seconds.
Each of the next n lines of the input file describes the characteristics of the production of parts. Here the i-th line contains the number of parts ki required to produce part number i, as well as their numbers. There are no duplicate part numbers in the i-th line. The sum of all numbers ki does not exceed 200000.
It is known that there are no cyclic dependencies in the production of parts.
Imprint
The first line of the output file should contain two numbers: the minimum time (in seconds) required to produce part number 1 as soon as possible and the number k of parts that need to be produced for this. In the second line you need to print k space-separated numbers — part numbers in the order in which they should be produced in order to produce part number 1 as soon as possible.
| Input |
Output |
3
100 200 300
1 2
0
2 2 1
| 300 2
2 1
|
2
23
1 2
0 |
5 2
2 1
|
4
2 3 4 5
2 3 2
1 3
0
2 1 3
| 9 3
3 2 1
|
| |
![]()
|
|
Темы:
Depth walk
Floyd's algorithm
Given a directed graph. You want to determine if it contains a cycle.
Input
The first line contains the number of vertices N≤ 50. Next, N lines are followed by N numbers, each of which – 0 or 1. The j-th number in the i-th row is equal to 1 if and only if there is an edge going from the i-th vertex to the j-th one. It is guaranteed that there will be zeros on the diagonal of the matrix.
Output
Print 0 if there is no cycle in the given graph, and 1 if there is one.
Examples
| # |
Input |
Output |
| 1 |
3
0 1 0
0 0 1
0 0 0
|
0 |
| 2 |
3
0 1 0
0 0 1
1 0 0
|
1 |
| |
![]()
|
|
Темы:
Applying Depth Traversal
Depth walk
Error
| |
![]()
|
|
Темы:
Dynamic Graph Programming
Depth walk
Disjoint set system
Error
| |
![]()
|
|
Темы:
Depth walk
There were N cities in Far Far Away, some of which were connected by roads. Unfortunately, recently it has become very difficult to get from one city to another due to traffic jams. In order to combat traffic jams, it was decided to make all roads one-way, i. allow travel on each road in only one direction. At the same time, it is required that it is still possible to get from any city to any other.
Input
The input file contains first the number N — number of cities (1≤N≤1000). Then the number M — number of roads (1≤M≤100000). Then there are M pairs of numbers defining the roads (each road is described by the numbers of the cities it connects). There are no roads from some city to the same city. There can be several roads between two cities. It is guaranteed that before the introduction of one-way traffic it was possible to get from any city to any other.
Imprint
The output file should contain M pairs of numbers corresponding to the roads (the roads should be output in the same order as they are given in the input file). For each road, the number of the city from which it will be possible to leave after the introduction of one-way traffic must first be recorded, and then — the number of the city where this road leads.
If you enter one-way traffic so that you can get from any city to any other, it is impossible, the output file should contain a single number 0.
Examples
| # |
Input |
Output |
| 1 |
4
6
1 2
1 2
23
24
4 3
14 |
2 1
2 1
3 2
4 2
4 3
14 |
| |
![]()
|
|
Темы:
Depth walk
There are N stations on a certain railway line, which are sequentially numbered from 1 to N. The distances between some stations are known. It is required to accurately calculate the lengths of all hauls between neighboring stations or indicate that this is impossible (that is, the information provided is contradictory or insufficient).
Input
The input file contains the numbers N — number of stations (2 ≤ N ≤ 100) and E — the number of pairs of stations, the distances between which are given (0 ≤ E ≤ 10000). Next comes E triples of numbers, the first two numbers of each triple set the station numbers (these are numbers from the range from 1 to N), and the third — the distance between these stations (all these distances are specified exactly and are expressed as real non-negative numbers with no more than 3 digits after the decimal point).
Imprint
In the case when it is possible to restore the lengths of the stages unambiguously, first print the number 1, and then N–1 real number into the output file. The first of these numbers should correspond to the distance from the 1st station to the 2nd, the second — from 2nd to 3rd, and so on. All numbers must be displayed with an accuracy of 3 digits after the decimal point.
If the given information about distances between stations is inconsistent or does not allow you to unambiguously accurately restore the lengths of hauls, output a single number 2 to the output file.
Examples
| # |
Input |
Output |
| 1 |
2 3
1 1 0
2 2 0
2 1 2.5
| 1
2.500 |
| 2 |
15 13
1 2 1
1 3 2
1 4 3
1 5 4
1 6 5
1 7 6
1 8 7
1 9 8
1 10 9
1 11 10
1 12 11
1 13 12
15 14 13
| 2 |
| |
![]()
|
|
Темы:
Depth walk
Company "Castles and Castles" has recently developed a new type of combination lock to be placed on gate locks. The lock panel is a rectangle w cells wide and h cells high. Some of them have buttons.
The code on this lock is entered by simultaneously pressing k buttons. To make the code easier to remember, the buttons used in it should form a cohesive area. An area is called connected if it is possible to get from any cell of the area to any other by moving only between the cells of this area with a common side. An important criterion for the reliability of the lock is the number of different codes that can be dialed on it.
To assess the reliability of locks, you need to write a program to calculate the specified value.
Imprint
The first line of the input file contains three integers h, w and k (1 ≤ h, w ≤ 30; 1 ≤ k ≤ 10). Each of the following h lines contains w characters. The symbol "#" denotes a button, and "." — her absence.
Imprint
In the output file print a single number — the number of codes that meet the specified requirements.
Examples
| # |
Input |
Output |
| 1 |
2 2 2
.#
##
|
2 |
| 2 |
5 6 7
.#....
##.##.
..#.#.
.####.
.....#
|
3 |
| |
![]()
|
|
Темы:
Dynamic programming
Algorithms on graphs
Depth walk
Dynamic Graph Programming
There are N villages in the thirtieth state. Some pairs of villages are connected by roads. In order to save money, “superfluous” there are no roads, i.e. There is only one way to get from any village to any village by road.
The latest research has shown that the thirtieth state is located in a seismically dangerous zone. Therefore, the head of state wanted to know what kind of damage an earthquake could bring to his country. Namely, he wants to know what is the minimum number of roads that must be destroyed in order to form a group of exactly P villages, isolated from the rest, such that from any village from this group to any other village from this group it will still be possible to get by undestroyed roads (a group is isolated from the rest if no undamaged road connects a village in this group with a village not in this group).
You should write a program to help him with this.
Input data format
The first line of the input file contains two numbers: N and P (1 ≤ P ≤ N ≤ 150). All other lines contain road descriptions, one per line: the road description consists of two village numbers (from 1 to N) that this road connects. All numbers in the input file are separated by spaces and/or newlines.
Output data format
In the output file print a single number — desired number of roads.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3 2
1 2
3 2 |
1 |
|
| 2 |
11 6
1 2
1 3
14
15
26
27
28
49
4 10
4 11 |
2 |
A group of villages (1, 2, 3, 6, 7, 8) will be isolated from the rest if roads 1–4 and 1–5 are destroyed. |
| |
![]()
|
|
Темы:
Depth walk
Topological sort
A group of recruit soldiers arrived at the army unit N666. After meeting the ensign, it became obvious that only a miracle could save a soldier from working in the kitchen to peel potatoes.
The ensign, unable to remember the names, numbered the recruits from 1 to N. After that, he ordered them to line up in height (starting with the tallest). Even completely untrained recruits can cope with this simple task, but the trouble is, the ensign assured himself that he knows about some soldiers, which of them is higher than whom, and this is far from always true.
After three days of training, the recruits managed to find out what the ensign knows (or rather, thinks he knows). Help them, using this knowledge, to line up so that Comrade Ensign is satisfied.
Input
First, the numbers N and M are input to the program (1 < N <= 100, 1 <= M <= 5000) – the number of soldiers in the company and the number of pairs of soldiers, about which the ensign knows which of them is higher. Next come these pairs of numbers A and B, one per line (1 <= A,B <= N), which means that, in the opinion of the ensign, soldier A is higher than B. It is not guaranteed that all pairs of numbers in input data are different.
Imprint
In the first line print "Yes" (if you can line up so that the ensign is satisfied) or "No" (if not). After answering "Yes" on the next line print N numbers separated by spaces - one of the possible constructions.
Examples
| # |
Input |
Output |
| 1 |
4 5
1 2
23
34
14
4 1 |
No |
| |
![]()
|
|
Темы:
Depth walk
recursion
It is required to calculate the area of a room in a square maze.
Input
The first line of enters the number N – maze size (3 <= N <= 10). The following N lines contain a maze (‘.’ – empty cell, ‘*’ – wall). And finally, the last line contains two numbers – the number of the row and column of the cell located in the room whose area is to be calculated. It is guaranteed that this cell is empty and that the labyrinth is surrounded by walls on all sides.
Imprint
It is required to print a single number – the number of empty cells in this room.
Examples
| # |
Input |
Output |
| 1 |
5
*****
**..*
*.*.*
*..**
*****
24
|
3 |
| |
![]()
|
|
Темы:
Depth walk
The little boy is making beads. He has many numbered beads. Each bead has a unique number - an integer in the range from 1 to N. He lays out all the beads on the floor and connects the beads together in an arbitrary way so that no closed loops are formed. Each of the beads in this case is connected to some other bead. It is required to determine what is the maximum number of beads connected in series in the resulting figure.
Input
The first line contains the number N (1 ≤ N ≤ 2500) - the number of beads. In the next N - 1 lines, two integers each - the numbers of the connected beads.
Imprint
Output one number - the desired number of beads.
Examples
| # |
Input |
Output |
| 1 |
2
1 2
| 2 |
| 2 |
5
2 1
23
24
25 |
3 |
| |
![]()
|
|
Темы:
Depth walk
In a city built during the Middle Ages, the width of the streets began to impede the movement of traffic, which was originally two-way on each of the streets. To solve this problem, it was proposed to make traffic on each of the streets one-way. The mayor entrusted this task to his first deputy. After much thought, he reported that on some streets the traffic would have to be left two-way, otherwise it would be impossible to drive from anywhere in the city to any other. According to the given scheme of the city, it is required to find all such streets.
Input
The first line of the input file contains the numbers N - the number of squares in the city and M - the number of streets connecting them (1 <= N <= 20000, 1 <= M <= 200000). The squares are numbered from 1 to N. Each of the next M lines contains a pair of natural numbers describing between which two squares the corresponding street passes (two squares are connected by at most one street).
Imprint
On the first line print the number B - the number of streets on which it is impossible to organize one-way traffic. On the next line print B integers - the numbers of these streets in ascending order. Streets are numbered starting from one in the order in which they are given in the input file.
Examples
| # |
Input |
Output |
| 1 |
10 16
26
37
6 5
5 9
5 4
1 2
98
6 4
2 10
38
79
14
24
10 5
16
6 10
| 1
4 |
| |
![]()
|
|
Темы:
Depth walk
The new prime minister decided to travel across Russia from Moscow to Vladivostok by rail and then back. He instructed his assistants to develop a route so that he did not have to pass through the same city twice. However, the assistants said that this was not possible for the Russian Railways. Decide which cities the Prime Minister will be forced to visit twice.
Input
The first line of the input file contains the numbers N - the number of Russian cities connected by railways into a single network and M - the number of railway lines connecting pairs of cities (1 <= N <= 20000, 1 <= M <= 200000) . The cities are numbered from 1 to N. Each of the next M lines contains a pair of positive integers describing between which two cities the corresponding railway line passes. The last line contains two integers S and E (1 <= S != E <= N) - numbers of Moscow and Vladivostok according to Russian Railways.
Imprint
In the first line print number B - the number of cities that the prime minister will have to visit twice. In the next lines print B integers - the numbers of these cities in ascending order.
Examples
| # |
Input |
Output |
| 1 |
3 2
1 2
23
3 1
| 1
2 |
| |
![]()
|
|
Темы:
Depth walk
Simple puzzles
Petya drew n circles on paper and connected some pairs of circles with lines. After that, he colored each circle in one of the three colors – red, blue or green.
Now Petya wants to change their coloring. Namely – he wants to recolor each circle with some other color so that no two circles of the same color are connected by a line. At the same time, he wants to necessarily recolor each circle, and repainting the circle in the same color as it was originally painted is not allowed.
Help Petya decide what colors the mugs should be repainted in order to fulfill the specified condition.
Input
The first line contains two integers n and m – the number of circles and the number of lines drawn by Petya, respectively (1 ≤ n ≤ 1000, 0 ≤ m ≤ 20000).
The next line contains n characters from the set {'R', 'G', 'B'} – The i-th of these symbols means the color of the i-th circle ('R' – red, 'G' – green, 'B' &ndash ; blue).
Then m lines contain two integers – pairs of circles connected by segments.
Imprint
Print one line consisting of n characters from the set {'R', 'G', 'B'} – the colors of the circles after repainting. If there are several solutions, print any one.
If there is no solution, print the word "Impossible''.
Examples
| # |
Input |
Output |
| 1 |
4 5
RRRG
1 3
14
34
24
2 3
| BBGR |
| 2 |
4 5
RGRR
1 3
14
34
24
2 3
| Impossible |
| |
![]()
|
|
Темы:
Depth walk
Formula derivation
Farmer John's new barn consists of N rooms (2 ≤ N ≤ 2500), consecutively numbered 1 x hellip; N, and N x minus; 1 corridors. Each corridor connects a pair of rooms in such a way that it is possible to go from one room to any through a series of corridors.
Each room in the barn has a round clock on the wall with the standard 1…12 on the front. However, this clock has only one hand, which always points exactly to one of the integers (it never points between two of those numbers).
Cow Besi wants to synchronize all the clocks in the barn so that they all point to the number 12. But with her cow thinking, every time she enters the room, she moves the hand forward one position. For example, if the arrow was pointing at 5, Besie will move the hand to 6. If the clock was pointing to 12, she will move the hand to 1. If Besie enters the room multiple times, she will move the hand each time she enters.
Determine the numbers of rooms in which Besie can start the journey through the barn to set all arrows to 12. Note that Besie does not move the arrow in the starting room at the beginning of the path and moves each time she enters it. The arrows themselves do not move. Besi entering the corridor must reach the end and enter the room at the end of the corridor. She can't turn back inside the hallway to re-enter the room she left.
Input
The first line of input contains N. The next line contains N integers, each in the range 1*12, indicating the initial positions of the arrows in each room. Each of the following N−1 lines describes a corridor with two integers a and b, each in the range 1…N, and the numbers of the rooms connected by this corridor.
Imprint
Print the numbers of the rooms Besi can start in to set all clocks to 12.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
11 10 11 11
12
2 3
24
|
1 |
In this example, Besi can only set all arrows to 12 if she starts in room 2 (e.g. moving like this: 1, 2, 3, 2, 4. |
| |
![]()
|
|
Темы:
Depth walk
Bust
Implementation task
Farmer John is testing a new camera that can "grab the picture" and automatically calculate the position of the cows. Unfortunately, the camera does not have a very good algorithm for finding cows and the FD needs your help.
The picture taken by the camera can be described by a lattice of NxN characters, each in the range A…Z, representing one of 26 possible different colors. The FD considers the following cow recognition algorithm to be the best: PCL (possible placement of a cow) is a rectangle on a lattice (possibly the entire lattice) with sides parallel to the sides of the lattice, which does not contain other PCLs inside and has the following property: exactly two colors must be present inside this rectangle, one forms a continuous region and the other forms two or more continuous regions.
For example, this image
AAAAA
ABABA
AAABB
is PCL because the A characters form a contiguous region, the B characters form more than one contiguous region. The interpretation is a cow with color A and spots with color B.
A region is continuous if you can traverse the entire region by moving from one cell to another neighboring one in the directions up, down, left, right.
Based on the given image of the PD camera, determine the amount of PCL.
INPUT FORMAT:
The first line of input contains N, the size of the grid (1≤N≤20). The next N lines describe the image, each consisting of N characters.
OUTPUT FORMAT:
Amount of PCL in the image.
| Input |
Output |
|
4
ABBC
BBBC
AABB
ABBC
|
2 |
| |
![]()
|
|
Темы:
Depth walk
Permutations
Farmer John's cows are dancing.
First, all N cows (2≤N≤105) are in a row and cow i is in position i. The sequence of dance movements is given by K (1≤K≤2⋅105) pairs of positions (a1,b1),(a2,b2),…,(aK,bK). Every minute i=1…K of the dance, the cows in positions ai and bi change places. The same K exchanges are made on minutes K+1*2K, then again on minutes 2K+1*3K, and so on. In other words,
at minute 1 the cows at positions a1 and b1 are swapped.
at minute 2, the cows at positions a2 and b2 are swapped.
...
At minute K, the cows at positions aK and bK swap.
At minute K+1, the cows at positions a1 and b1 are swapped.
At minute K+1, the cows at positions a2 and b2 are swapped.
etc. ...
For each cow, determine the number of unique positions it will visit during the endless dance.
Input
The first line of input contains the integers N and K. Each of the subsequent K lines contains (a1,b1)…(aK, bK) (1≤ai<bi≤N).
Imprint
Print N lines, where the i-th line contains the number of unique positions that cow i will visit.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5 4
13
12
2 3
24
|
4
4
3
4
1
|
- Cow 1 will reach positions {1,2,3,4}.
- Cow 2 will reach positions {1,2,3,4}.
- Cow 3 will reach positions {1,2,3}.
- Cow 4 will reach positions {1,2,3,4}.
- Cow 5 will not move and will not leave position 5.
|
| |
![]()
|
|
Темы:
Depth walk
Bust
Bor
Blaze sends movement orders to his troops, gathered from the inhabitants of one of the shadows. Unfortunately, they don't understand Amber, so Blaze has to send them messages in their own language.
Therein lies the problem: the Amberian prince does not know the spelling of this language well, so he sometimes makes mistakes in words, but no more than one mistake in a word.
There are a lot of words in the language, so if at least one letter in a word changes, then its meaning can change dramatically. If the army does not correctly understand the order, then the entire military campaign may fail. Therefore, it is very important for Blaise to check the correct spelling of words. He decided to ask you to help him.
You must create a program that will output in lexicographic order all the possible words that Blaise could have tried to write, given that he could have made a mistake 1 time.
Input
The first line contains numbers n and m - the number of orders given by Blaze and the number of commands understood by his troops, respectively. (1 <= n, m <= 5000)
The next line takes m words as input - commands that Blaze's troops understand.
In the next n lines, words are given as input - orders given by Blaze.
All strings are less than 100.
Output
Print n lines: line number i contains the answer to the problem for Blaze's order number i. Lines that are the answer to this query are displayed on a single line separated by a space.
Example
Input
5 5
is in if on of
it
in
of
ij
op
Output
if in is
if in is on
if of on
if in is
of on
(c) Evgeny Grigoriev
| |
![]()
|
|
Темы:
recursion
Depth walk
Given an nxn chessboard. Let the knight stand on the cell (1,1). It is necessary to find such a sequence of moves of the knight, in which he visits each square of the board exactly once.
Input
The input to the program is a natural number n (n ≤ 8).
Output
If the bypass is impossible, then output 0 to the output file, if possible, then 1, and on the next lines print the matrix nn, illustrating the order of the bypass. It is not necessary to align numbers by columns.
Note. The speed of the recursive program in this problem essentially depends on the order in which the variants of the knight's move from the next cell will be considered. One good order is to place all eight options "in a circle".
| Input |
Output |
| 3 |
0 |
| 5 |
1
1 20 17 12 3
16 11 2 7 18
21 24 19 4 13
10 15 6 23 8
25 22 9 14 5
|
| |
![]()
|