| 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
|
| |
![]()
|
|
Темы:
Bor
The string s is called a superfix for string t if t starts with s and ends with s. For example, "abra" is a prefix for the string "abracadabra". In particular, the string t itself is its own superfix. Suprefixes play an important role in various algorithms on strings.
In this problem, it is required to solve the inverse problem of finding a suprefix, which is as follows. Given a dictionary containing n words t1, t2, …, tn and a set of m sample strings s1 , s2, …, sm. It is necessary for each sample string from the given set to find the number of words in the dictionary for which this sample string is a superfix.
It is required to write a program that, given the number n, n dictionary words t1, t2, …, tn, the given number m and m pattern strings s1, s2, …, sm will calculate for each pattern string the number of words in the dictionary for which this the pattern string is a superfix.
Input
The first line of the input file contains an integer n (1 ≤ n ≤ 200 000).
The next n lines contain the words t1, t2, …, tn, one word per line. Each word consists of lowercase letters of the Latin alphabet. The length of each word does not exceed 50. The total length of all words does not exceed 106. The dictionary does not contain empty words.
This is followed by a line containing the integer m (1 ≤ m ≤ 200,000).
The next m lines contain sample strings s1, s2, …, sm, one per line. Each sample string consists of lowercase Latin letters: The length of each sample string does not exceed 50. The total length of all sample strings does not exceed 106. No pattern string is an empty string.
Output
The output file should contain m numbers, one per line.
For each pattern string, in the order in which they are given in the input file, print the number of dictionary words for which it is a superfix.
|
Enter |
Output |
|
4
abacaba
abracadabra
aa
abra
3
a
abra
abac
|
4
2
0 |
| |
![]()
|
|
Темы:
hash
Bor
Trees
Trees
Once Konstantin, having participated in the next, already the 13th international Olympiad, was returning home by train. He, as always, sat and thought about the meaning of life, simultaneously solving programming problems. After some time, Konstantin dozed off, but the trouble is, in order to wake up, he must solve the problem that has popped up in his head, which haunts him!
This time, Konstantin dreamed of a tree that initially consisted of only one vertex with number 1. In the problem he set, new vertices were gradually added to the tree. In the i-th second, a vertex with the number i+1 was added to the tree, which was suspended as a son from the vertex pi, and on the edge between the vertices i+1 and pi the letter ci was written.
Each path from the root of the tree to the vertex v corresponds to a certain string obtained by writing out the symbols written on the edges of the current path in the order from the root to the vertex v. Konstantin faced a difficult task at first glance - after each addition of a new vertex, count the number of unique strings starting at the root of the tree (vertex number 1) and ending at some other vertex.
In his dream, Konstantin is not a genius at all, so he himself cannot solve this problem. Help Konstantin solve the problem and wake up.
Input:
The first line contains the number n - the number of requests to add a new node to the tree (1 <= n <= 300000).
The next n lines describe requests for adding vertices. The i-th query is described by the parameters pi (1 <= pi <= i) and ci, which mean that the added the vertex with number i+1 is suspended from the vertex with number pi as a child, and the symbol ci is written on the resulting edge - a lowercase letter of the Latin alphabet.
Output:
Print n lines. On the i-th line print the answer to Konstantin's problem after adding the i+1-th vertex.
Examples:
| Input |
Output |
2
1 b
2p |
1
2 |
3
1 o
1 o
2 j |
1
1
2 |
| |
![]()
|
|
Темы:
Dynamic Graph Programming
Bor
On one of the TV channels, the next lottery is held every week. During the week, participants make their bets. Each bet consists of naming some M-digit number in the base K number system (that is, in fact, each participant names M digits, each of which lies in the range from 0 to K & minus; 1). Leading zeros are allowed in numbers.
At some point, betting on the current draw ends, and after that, the presenter announces the winning number on television (this is also an M-digit number in the K-ary number system). After that, those TV viewers, whose first digit of their number coincided with the first digit of the number named by the host, receive a win in the amount of A1 rubles. Those who matched the first two digits of — receive A2 rubles (at the same time, if the player has the second digit matched, but the first digit did not match, he does not receive anything). Similarly, those who guessed the first three digits receive A3 rubles. And so on. Those who guessed the whole number fully receive Am rubles. Moreover, if the player guessed the first t digits, then he receives At rubles, but does not receive prizes for guessing t−1, t−2, etc. digits. If the player didn't guess the first number, he gets nothing.
Write a program that, given the known bets made by viewers, finds the number that the TV presenter must name in order for the organizing company to pay out the minimum amount as winnings. For your convenience, bets made by players are already sorted in non-descending order.
Input
The first line contains the numbers N (the number of TV viewers who made their bets, 1N100000), M (the length of the numbers 1M10) K (the base of the number system 2 ≤ K ≤ 10). The next line contains M integers A1, A2, ..., AM, specifying payoffs if only the first, first two ,... , all digits (1 ≤ A1 ≤ A2 ≤ ... ≤ AM ≤ 100000 ). Each of the next N lines contains one M-digit K-ary number. The numbers are in non-decreasing order.
Imprint
On the first line print the desired number (if there are several solutions — print any of them), and on the second line — the amount that, when naming the TV presenter on the first day, will have to be paid as a win.
Examples
| # |
Input |
Output |
| 1 |
10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111 |
011
6 |
| 2 |
1 1 10
100
0 |
1
0 |
| |
![]()
|
|
Темы:
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
| |
![]()
|