1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Perfectionist Arkadiy
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 2700
Tags: *special, number theory

Arkadiy has lots square photos with size a × a. He wants to put some of them on a rectangular wall with size h × w.

The photos which Arkadiy will put on the wall must form a rectangular grid and the distances between neighboring vertically and horizontally photos and also the distances between outside rows and columns of photos to the nearest bound of the wall must be equal to x, where x is some non-negative real number. Look on the picture below for better understanding of the statement.

Arkadiy haven't chosen yet how many photos he would put on the wall, however, he want to put at least one photo. Your task is to determine the minimum value of x which can be obtained after putting photos, or report that there is no way to put positive number of photos and satisfy all the constraints. Suppose that Arkadiy has enough photos to make any valid arrangement according to the constraints.

Note that Arkadiy wants to put at least one photo on the wall. The photos should not overlap, should completely lie inside the wall bounds and should have sides parallel to the wall sides.

Input format:
The first line contains three integers a, h and w (1 ≤ a, h, w ≤ 109) — the size of photos and the height and the width of the wall.

Output format:
Print one non-negative real number — the minimum value of x which can be obtained after putting the photos on the wall. The absolute or the relative error of the answer must not exceed 10 - 6.

Print -1 if there is no way to put positive number of photos and satisfy the constraints.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example Arkadiy can put 7 rows of photos with 5 photos in each row, so the minimum value of x equals to 0.5.

In the second example Arkadiy can put only 1 photo which will take the whole wall, so the minimum value of x equals to 0.

In the third example there is no way to put positive number of photos and satisfy the constraints described in the statement, so the answer is -1.

Example input:
2 18 13

Example output:
0.5

Example input:
4 4 4

Example output:
0

Editorial:
Пусть n — число рядов фотографий, а m — число столбцов. Тогда нам интересно решение
Repairing Of String
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 2200
Tags: *special, constructive algorithms

Stepan had a favorite string s which consisted of the lowercase letters of the Latin alphabet.

After graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. But Stepan remembers some information about the string, namely the sequence of integers c1, c2, ..., cn, where n equals the length of the string s, and ci equals the number of substrings in the string s with the length i, consisting of the same letters. The substring is a sequence of consecutive characters in the string s.

For example, if the Stepan's favorite string is equal to "tttesst", the sequence c looks like: c = [7, 3, 1, 0, 0, 0, 0].

Stepan asks you to help to repair his favorite string s according to the given sequence c1, c2, ..., cn.

Input format:
The first line contains the integer n (1 ≤ n ≤ 2000) — the length of the Stepan's favorite string.

The second line contains the sequence of integers c1, c2, ..., cn (0 ≤ ci ≤ 2000), where ci equals the number of substrings of the string s with the length i, consisting of the same letters.

It is guaranteed that the input data is such that the answer always exists.

Output format:
Print the repaired Stepan's favorite string. If there are several answers, it is allowed to print any of them. The string should contain only lowercase letters of the English alphabet.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test Stepan's favorite string, for example, can be the string "kkrrrq", because it contains 6 substrings with the length 1, consisting of identical letters (they begin in positions 1, 2, 3, 4, 5 and 6), 3 substrings with the length 2, consisting of identical letters (they begin in positions 1, 3 and 4), and 1 substring with the length 3, consisting of identical letters (it begins in the position 3).

Example input:
6
6 3 1 0 0 0

Example output:
kkrrrq

Example input:
4
4 0 0 0

Example output:
abcd

Editorial:
Для получения ответа нам всегда достаточно двух букв, например, «a» и «b». Пусть переменная cur изначально равна «a». В ней мы будем хранить текущую выводимую букву.
Пойдем по заданному массиву переменной i справа налево. Изначально i равно длине строки. Если в итоговой строке есть подстрока из одинаковых букв длины len, то в ней точно есть две подстроки длины len - 1, три подстроки длины len - 2, четыре подстроки длины len - 3 и так далее. Пусть текущая позиция в заданном массиву равна i. Тогда проитерируемся переменной j от i - 1 до 1 и уменьшим cj на величину ci·(i - j + 1). Обратите внимание, что в условии гарантируется, что ответ всегда существует, поэтому cj никогда не станет меньше нуля.
Таким образом, мы корректно пересчитаем префикс количества подстрок для всех длин меньше i. После этого нужно добавить в ответ ci строк длины i, причем после добавления очередной строки из букв cur, нужно изменять значение cur. Если она была равна «a», то cur нужно присвоить «b», в противном случае, cur нужно присвоить «a».
Composing Of String
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 2300
Tags: *special, dp

Stepan has a set of n strings. Also, he has a favorite string s.

Stepan wants to do the following. He will take some strings of his set and write them down one after another. It is possible that he will take some strings more than once, and will not take some of them at all.

Your task is to determine the minimum number of strings in the set which Stepan needs to take and write so that the string s appears as a subsequence in the resulting written down string.

For example, in the string "abcd" strings "ad", "acd", "abcd" appear as subsequences, and strings "ba", "abdc" don't appear as subsequences.

Input format:
The first line contains the integer n (1 ≤ n ≤ 50) — the number of strings in Stepan's set.

The next n lines contain n non-empty strings consisting of lowercase letters of the English alphabet. The length of each of these strings does not exceed 50 symbols. It is possible that some strings from Stepan's set are the same.

The next line contains the non-empty string s, consisting of lowercase letters of the English alphabet — Stepan's favorite string. The length of this string doesn't exceed 2500 symbols.

Output format:
Print the minimum number of strings which Stepan should take from the set and write them down one after another so that the string s appears as a subsequence in the resulting written down string. Each string from the set should be counted as many times as Stepan takes it from the set.

If the answer doesn't exsist, print -1.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test, Stepan can take, for example, the third and the second strings from the set, write them down, and get exactly his favorite string.

In the second example Stepan can take, for example, the second, the third and again the second strings from the set and write them down. Then he will get a string "aabaaaab", in which his favorite string "baaab" is a subsequence.

In the third test Stepan can not get his favorite string, because it contains the letter "c", which is not presented in any of the strings in the set.

Example input:
3
a
aa
a
aaa

Example output:
2

Example input:
4
ab
aab
aa
bb
baaab

Example output:
3

Editorial:
Для решения данной задачи будем пользоваться жадными соображениями. Пусть pos это позиция в строке s, начиная с которой мы еще не набрали букв. Изначально pos равна нулю.
Будем пытаться приложить каждую из строк набора, начиная с позиции pos. Будем поддерживать переменную maxPos — это максимальная позиция до которой мы наберем буквы в строке s, если приложим какую-то одну строку из набора. После прикладывания всех строк, если pos = maxPos, то это означает, что буквы spos нет ни в одной из строк набора, поэтому набрать стоку s не получится. В противном случае, увеличим ответ на единицу, присвоим переменной pos значение maxPos и начнем алгоритм заново, если еще не набрали все строку s целиком.
Stepan's Series
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 2000
Tags: *special, dp

Well, the series which Stepan watched for a very long time, ended. In total, the series had n episodes. For each of them, Stepan remembers either that he definitely has watched it, or that he definitely hasn't watched it, or he is unsure, has he watched this episode or not.

Stepan's dissatisfaction is the maximum number of consecutive series that Stepan did not watch.

Your task is to determine according to Stepan's memories if his dissatisfaction could be exactly equal to k.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ n) — the number of episodes in the series and the dissatisfaction which should be checked.

The second line contains the sequence which consists of n symbols "Y", "N" and "?". If the i-th symbol equals "Y", Stepan remembers that he has watched the episode number i. If the i-th symbol equals "N", Stepan remembers that he hasn't watched the epizode number i. If the i-th symbol equals "?", Stepan doesn't exactly remember if he has watched the episode number i or not.

Output format:
If Stepan's dissatisfaction can be exactly equal to k, then print "YES" (without qoutes). Otherwise print "NO" (without qoutes).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test Stepan remembers about all the episodes whether he has watched them or not. His dissatisfaction is 2, because he hasn't watch two episodes in a row — the episode number 3 and the episode number 4. The answer is "YES", because k = 2.

In the second test k = 1, Stepan's dissatisfaction is greater than or equal to 2 (because he remembers that he hasn't watch at least two episodes in a row — number 5 and number 6), even if he has watched the episodes from the first to the fourth, inclusive.

Example input:
5 2
NYNNY

Example output:
YES

Example input:
6 1
????NN

Example output:
NO

Editorial:
В данных ограничениях задачу можно было решать следующим образом. Переберем все отрезки длины k в заданной последовательности.
Пусть текущий отрезок начинается в позиции i. Заменим все вопросы с позиции i до позиции i + k - 1, включительно, на буквы «N», а все остальные вопросы на буквы «Y». После этого найдем неудовлетворенность Степана от просмотра в получившейся последовательности. Если она в точности равна k, то нужно вывести «YES» и закончить работу программы.
Если ни для одного отрезка неудовлетворенность не равна в точности k, то ответ «NO».
Stepan and Vowels
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 1600
Tags: *special, implementation, strings

Stepan likes to repeat vowel letters when he writes words. For example, instead of the word "pobeda" he can write "pobeeeedaaaaa".

Sergey does not like such behavior, so he wants to write a program to format the words written by Stepan. This program must combine all consecutive equal vowels to a single vowel. The vowel letters are "a", "e", "i", "o", "u" and "y".

There are exceptions: if letters "e" or "o" repeat in a row exactly 2 times, like in words "feet" and "foot", the program must skip them and do not transform in one vowel. For example, the word "iiiimpleeemeentatiioon" must be converted to the word "implemeentatioon".

Sergey is very busy and asks you to help him and write the required program.

Input format:
The first line contains the integer n (1 ≤ n ≤ 100 000) — the number of letters in the word written by Stepan.

The second line contains the string s which has length that equals to n and contains only lowercase English letters — the word written by Stepan.

Output format:
Print the single string — the word written by Stepan converted according to the rules described in the statement.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
13
pobeeeedaaaaa

Example output:
pobeda

Example input:
22
iiiimpleeemeentatiioon

Example output:
implemeentatioon

Editorial:
Для решения данной задачи нужно было сделать то, что описано в условии. Пойдем слева направо по заданному слову. Пусть текущая буква равна cur. Если cur согласная, выведем её и перейдем к следующей букве. В противном случае, пройдем по строке вправо до тех пор, пока буквы совпадают с cur. Пусть len это длина текущего отрезка из одинаковых букв. Тогда если cur не равно «e» и не равно «o», либо если значение len не равно двум, выведем cur, в противном случае, это исключение и нужно вывести cur два раза. После этого сразу перейдем к букве, которая находится после текущего отрезка длины len. Если таковой нет, значит мы рассмотрели всю строку и вывели ответ.
Determine Line
Contest: Mail.Ru Cup 2018 Round 3
Difficulty rating: 800
Tags: implementation

Arkady's morning seemed to be straight of his nightmare. He overslept through the whole morning and, still half-asleep, got into the tram that arrived the first. Some time after, leaving the tram, he realized that he was not sure about the line number of the tram he was in.

During his ride, Arkady woke up several times and each time he saw the tram stopping at some stop. For each stop he knows which lines of tram stop there. Given this information, can you help Arkady determine what are the possible lines of the tram he was in?

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of stops Arkady saw.

The next $$$n$$$ lines describe the stops. Each of them starts with a single integer $$$r$$$ ($$$1 \le r \le 100$$$) — the number of tram lines that stop there. $$$r$$$ distinct integers follow, each one between $$$1$$$ and $$$100$$$, inclusive, — the line numbers. They can be in arbitrary order.

It is guaranteed that Arkady's information is consistent, i.e. there is at least one tram line that Arkady could take.

Output format:
Print all tram lines that Arkady could be in, in arbitrary order.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Consider the first example. Arkady woke up three times. The first time he saw a stop with lines $$$1$$$, $$$4$$$, $$$6$$$. The second time he saw a stop with lines $$$1$$$, $$$4$$$. The third time he saw a stop with lines $$$10$$$, $$$5$$$, $$$6$$$, $$$4$$$ and $$$1$$$. He can be in a tram of one of two lines: $$$1$$$ or $$$4$$$.

Example input:
3
3 1 4 6
2 1 4
5 10 5 6 4 1

Example output:
1 4

Example input:
5
1 1
10 10 9 8 7 100 5 4 3 99 1
5 1 2 3 4 5
5 4 1 3 2 5
4 10 1 5 3

Example output:
1

Editorial:
This is a simple implementation problem. A tram line is suitable if it appears at all stops, i.e. exactly $$$n$$$ times. Make an array of $$$100$$$ integers and count how many times each integer appears. Then just output each index where the array hits $$$n$$$.
Divide Candies
Contest: Mail.Ru Cup 2018 Round 3
Difficulty rating: 1600
Tags: math, number theory

Arkady and his friends love playing checkers on an $$$n \times n$$$ field. The rows and the columns of the field are enumerated from $$$1$$$ to $$$n$$$.

The friends have recently won a championship, so Arkady wants to please them with some candies. Remembering an old parable (but not its moral), Arkady wants to give to his friends one set of candies per each cell of the field: the set of candies for cell $$$(i, j)$$$ will have exactly $$$(i^2 + j^2)$$$ candies of unique type.

There are $$$m$$$ friends who deserve the present. How many of these $$$n \times n$$$ sets of candies can be split equally into $$$m$$$ parts without cutting a candy into pieces? Note that each set has to be split independently since the types of candies in different sets are different.

Input format:
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 1000$$$) — the size of the field and the number of parts to split the sets into.

Output format:
Print a single integer — the number of sets that can be split equally.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, only the set for cell $$$(3, 3)$$$ can be split equally ($$$3^2 + 3^2 = 18$$$, which is divisible by $$$m=3$$$).

In the second example, the sets for the following cells can be divided equally:

- $$$(1, 2)$$$ and $$$(2, 1)$$$, since $$$1^2 + 2^2 = 5$$$, which is divisible by $$$5$$$;
- $$$(1, 3)$$$ and $$$(3, 1)$$$;
- $$$(2, 4)$$$ and $$$(4, 2)$$$;
- $$$(2, 6)$$$ and $$$(6, 2)$$$;
- $$$(3, 4)$$$ and $$$(4, 3)$$$;
- $$$(3, 6)$$$ and $$$(6, 3)$$$;
- $$$(5, 5)$$$.

In the third example, sets in all cells can be divided equally, since $$$m = 1$$$.

Example input:
3 3

Example output:
1

Example input:
6 5

Example output:
13

Editorial:
We are asked to count the number of pairs $$$(i, j)$$$ so that $$$(i^2 + j^2) \bmod m = 0$$$. Note that $$$(i^2 + j^2) \bmod m = ((i \bmod m)^2 + (j \bmod m)^2) \bmod m$$$. Thus the answer is equal for all pairs $$$(i, j)$$$ that have equal values $$$(i \bmod m, j \bmod m) = (x, y)$$$. Let's loop through all possible pairs of $$$(x, y)$$$ (there are $$$m^2$$$ of them), check if $$$(x^2 + y^2) \bmod m = 0$$$ and if yes, add to the answer the number of suitable pairs $$$(i, j)$$$, that is easy to compute in $$$O(1)$$$.
The complexity of the solution is $$$O(m^2)$$$.
Is your horseshoe on the other hoof?
Contest: Codeforces Round 141 (Div. 2)
Difficulty rating: 800
Tags: implementation

Valera the Horse is going to the party with friends. He has been following the fashion trends for a while, and he knows that it is very popular to wear all horseshoes of different color. Valera has got four horseshoes left from the last year, but maybe some of them have the same color. In this case he needs to go to the store and buy some few more horseshoes, not to lose face in front of his stylish comrades.

Fortunately, the store sells horseshoes of all colors under the sun and Valera has enough money to buy any four of them. However, in order to save the money, he would like to spend as little money as possible, so you need to help Valera and determine what is the minimum number of horseshoes he needs to buy to wear four horseshoes of different colors to a party.

Input format:
The first line contains four space-separated integers s1, s2, s3, s4 (1 ≤ s1, s2, s3, s4 ≤ 109) — the colors of horseshoes Valera has.

Consider all possible colors indexed with integers.

Output format:
Print a single integer — the minimum number of horseshoes Valera needs to buy.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
1 7 3 3

Example output:
1

Example input:
7 7 7 7

Example output:
3

Editorial:
Two Tables
Contest: Codeforces Round 141 (Div. 2)
Difficulty rating: 1400
Tags: brute force, implementation

You've got two rectangular tables with sizes na × ma and nb × mb cells. The tables consist of zeroes and ones. We will consider the rows and columns of both tables indexed starting from 1. Then we will define the element of the first table, located at the intersection of the i-th row and the j-th column, as ai, j; we will define the element of the second table, located at the intersection of the i-th row and the j-th column, as bi, j.

We will call the pair of integers (x, y) a shift of the second table relative to the first one. We'll call the overlap factor of the shift (x, y) value:

$$\sum_{i,j}a_{i,j}\cdot b_{i+x,j+y}$$

where the variables i, j take only such values, in which the expression ai, j·bi + x, j + y makes sense. More formally, inequalities 1 ≤ i ≤ na, 1 ≤ j ≤ ma, 1 ≤ i + x ≤ nb, 1 ≤ j + y ≤ mb must hold. If there are no values of variables i, j, that satisfy the given inequalities, the value of the sum is considered equal to 0.

Your task is to find the shift with the maximum overlap factor among all possible shifts.

Input format:
The first line contains two space-separated integers na, ma (1 ≤ na, ma ≤ 50) — the number of rows and columns in the first table. Then na lines contain ma characters each — the elements of the first table. Each character is either a "0", or a "1".

The next line contains two space-separated integers nb, mb (1 ≤ nb, mb ≤ 50) — the number of rows and columns in the second table. Then follow the elements of the second table in the format, similar to the first table.

It is guaranteed that the first table has at least one number "1". It is guaranteed that the second table has at least one number "1".

Output format:
Print two space-separated integers x, y (|x|, |y| ≤ 109) — a shift with maximum overlap factor. If there are multiple solutions, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 2
01
10
00
2 3
001
111

Example output:
0 1

Example input:
3 3
000
010
000
1 1
1

Example output:
-1 -1

Editorial:
Fractal Detector
Contest: Codeforces Round 141 (Div. 2)
Difficulty rating: 2000
Tags: dp, hashing

Little Vasya likes painting fractals very much.

He does it like this. First the boy cuts out a 2 × 2-cell square out of squared paper. Then he paints some cells black. The boy calls the cut out square a fractal pattern. Then he takes a clean square sheet of paper and paints a fractal by the following algorithm:

1. He divides the sheet into four identical squares. A part of them is painted black according to the fractal pattern.
2. Each square that remained white, is split into 4 lesser white squares, some of them are painted according to the fractal pattern. Each square that remained black, is split into 4 lesser black squares.

In each of the following steps step 2 repeats. To draw a fractal, the boy can make an arbitrary positive number of steps of the algorithm. But he need to make at least two steps. In other words step 2 of the algorithm must be done at least once. The resulting picture (the square with painted cells) will be a fractal. The figure below shows drawing a fractal (here boy made three steps of the algorithm).

One evening Vasya got very tired, so he didn't paint the fractal, he just took a sheet of paper, painted a n × m-cell field. Then Vasya paint some cells black.

Now he wonders, how many squares are on the field, such that there is a fractal, which can be obtained as described above, and which is equal to that square. Square is considered equal to some fractal if they consist of the same amount of elementary not divided cells and for each elementary cell of the square corresponding elementary cell of the fractal have the same color.

Input format:
The first line contains two space-separated integers n, m (2 ≤ n, m ≤ 500) — the number of rows and columns of the field, correspondingly.

Next n lines contain m characters each — the description of the field, painted by Vasya. Character "." represents a white cell, character "*" represents a black cell.

It is guaranteed that the field description doesn't contain other characters than "." and "*".

Output format:
On a single line print a single integer — the number of squares on the field, such that these squares contain a drawn fractal, which can be obtained as described above.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
The answer for the first sample is shown on the picture below. Fractals are outlined by red, blue and green squares.

The answer for the second sample is 0. There is no fractal, equal to the given picture.

Example input:
6 11
......*.***
*.*.*....**
.***....*.*
..***.*....
.*.*.....**
......*.*..

Example output:
3

Example input:
4 4
..**
..**
....
....

Example output:
0

Editorial: