A. Scrambled Scrabble

Xotira: 32 MB, Vaqt: 1000 ms

Masala

You are playing a word game using a standard set of $26$ uppercase English letters: A — Z. In this game, you can form vowels and consonants as follows.

The letters $A, E, I, O, and U$ can only form a vowel.
The letter Y can form either a vowel or a consonant.
Each of the remaining letters other than A, E, I, O, U, and Y can only form a consonant.
The string NG can form a single consonant when concatenated together.

Denote a syllable as a concatenation of a consonant, a vowel, and a consonant in that order. A word is a concatenation of one or more syllables.

You are given a string $S$ and you want to create a word from it. You are allowed to delete zero or more letters from $S$ and rearrange the remaining letters to form the word. Find the length of the longest word that can be created, or determine if no words can be created.

Kiruvchi ma'lumotlar:

A single line consisting of a string $S (1≤|S|≤5000)$ . The string $S$ consists of only uppercase English letters.

Chiquvchi ma'lumotlar:

If a word cannot be created, output 0. Otherwise, output a single integer representing the length of longest word that can be created.

Izoh:

Explanation for the sample input/output #1

A possible longest word is JAKCARTAP, consisting of the syllables JAK, CAR, and TAP.

Explanation for the sample input/output #2

The whole string $S$ is a word consisting of one syllable which is the concatenation of the consonant NG, the vowel E, and the consonant NG.

Explanation for the sample input/output #3

The whole string $S$ is a word consisting of one syllable which is the concatenation of the consonant Y, the vowel Y, and the consonant Y.

Explanation for the sample input/output #4

The whole string $S$ is a word consisting of two syllables: DAN and GAN.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	ICPCJAKARTA	9
2	NGENG	5
3	YYY	3
4	DANGAN	6
5	AEIOUY	0

B. ICPC Square

Xotira: 32 MB, Vaqt: 1000 ms

Masala

ICPC Square is a hotel provided by the ICPC Committee for the accommodation of the participants. It consists of $N$ floors (numbered from 11 to $N$ ). This hotel has a very unique elevator. If a person is currently at floor $x$ , by riding the elevator once, they can go to floor $y$ if and only if $y$ is a multiple of $x$ and $y−x≤D$ .

You are currently at floor $S$ . You want to go to the highest possible floor by riding the elevator zero or more times. Determine the highest floor you can reach.

Kiruvchi ma'lumotlar:

A single line consisting of three integers $N D S (2≤N≤1012;1≤D≤N−1;1≤S≤N).$

Chiquvchi ma'lumotlar:

Output a single integer representing the highest floor you can reach by riding the elevator zero or more times.

Izoh:

Explanation for the sample input/output #1

First, ride the elevator from floor 3 to floor 15. This is possible because 15 is a multiple of 3 and 15−3≤35. Then, ride the elevator from floor 15 to floor 30. This is possible because 30 is a multiple of 15 and 30−15≤35 Finally, ride the elevator from floor 30 to floor 60. This is possible because 60 is a multiple of 30 and 60−30≤35.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	64 35 3	60
2	2024 2023 1273	1273

C. Saraga

Xotira: 32 MB, Vaqt: 1000 ms

Masala

The word saraga is an abbreviation of sarana olahraga, an Indonesian term for a sports facility. It is created by taking the prefix sara of the word sarana and the suffix ga of the word olahraga. Interestingly, it can also be created by the prefix sa of the word sarana and the suffix raga of the word olahraga.

An abbreviation of two strings $S$ and $T$ is interesting if there are at least two different ways to split the abbreviation into two non-empty substrings such that the first substring is a prefix of $S$ and the second substring is a suffix of $T$ .

You are given two strings $S$ and $T$ . You want to create an interesting abbreviation of strings $S$ and $T$ with minimum length, or determine if it is impossible to create an interesting abbreviation.

Kiruvchi ma'lumotlar:

The first line consists of a string $S (1≤|S|≤200000).$

The second line consists of a string $T (1≤|T|≤200000).$

Both strings $S$ and $T$ only consist of lowercase English letters.

Chiquvchi ma'lumotlar:

If it is impossible to create an interesting abbreviation, output -1.

Otherwise, output a string in a single line representing an interesting abbreviation of strings $S$ and \(T\0 with minimum length. If there are multiple solutions, output any of them.

Izoh:

Explanation for the sample input/output #1

You can split saga into s and aga, or sa and ga. The abbreviation saraga is interesting, but saga has a smaller length.

Explanation for the sample input/output #2

The abbreviation belhijau is also interesting with minimum length, so it is another valid solution.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	sarana olahraga	saga
2	berhiber wortelhijau	berhijau
3	icpc icpc	icpc
4	icpc jakarta	-1

D. Outlining Borders

Xotira: 60 MB, Vaqt: 6000 ms

Masala

You are given an undirected graph consisting of $n$ ertices and $m$ edges. The vertices are numbered with integers from 1 to $n$ , the edges are numbered with integers from 1 to $m$ . Each edge can be unpainted or be painted in one of the $k$ colors, which are numbered with integers from 1 to $k$ . Initially, none of the edges is painted in any of the colors.

You get queries of the form "Repaint edge $e_i$ to color $c_i$ ". At any time the graph formed by the edges of the same color must be bipartite. If after the repaint this condition is violated, then the query is considered to be invalid and edge $e_i$ keeps its color. Otherwise, edge $e_i$ is repainted in color $c_i$ , and the query is considered to valid.

Recall that the graph is called bipartite if the set of its vertices can be divided into two parts so that no edge connected vertices of the same parts.

For example, suppose you are given a triangle graph, that is a graph with three vertices and edges (1, 2), (2, 3) and (3, 1). Suppose that the first two edges are painted color 1, and the third one is painted color 2. Then the query of "repaint the third edge in color 1" will be incorrect because after its execution the graph formed by the edges of color 1 will not be bipartite. On the other hand, it is possible to repaint the second edge in color 2.

You receive $q$ queries. For each query, you should either apply it, and report that the query is valid, or report that the query is invalid.

Kiruvchi ma'lumotlar:

The first line contains integers $n, m, k, q (2 ≤ n ≤ 5·10^5, 1 ≤ m, q ≤ 5·10^5, 1 ≤ k ≤ 50)$ — the number of vertices, the number of edges, the number of colors and the number of queries.

Then follow $m$ edges of the graph in the form $a_i, b_i (1 ≤ a_i, b_i ≤ n).$

Then follow $q$ queries of the form $e_i, c_i (1 ≤ e_i ≤ m, 1 ≤ c_i ≤ k).$

It is guaranteed that the graph doesn't contain multiple edges and loops.

Chiquvchi ma'lumotlar:

For each query print "YES" (without the quotes), if it is valid, or "NO" (without the quotes), if this query destroys the bipartivity of the graph formed by the edges of some color.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 3 2 5 1 2 2 3 1 3 1 1 2 1 3 2 3 1 2 2	YES YES YES NO YES

E. Kamron and Binary String (Easy Version)

Xotira: 256 MB, Vaqt: 2000 ms

Masala

This is the easy version of the problem. The difference between the versions is that in this version, string tt consists of only '0' and '1'. You can hack only if you solved all versions of this problem.

Kamron has a binary string $s$ of length $n$ . Kamron can perform the following operation:

Choose two adjacent blocks of $s$ and swap them.

A block is a maximal $substring∗$ of identical characters. Formally, denote $s[l,r]$ as the substring $s_ls_{l+1}…s_r.$ A block is $s[l,r]$ satisfying:

$l=1 or s_l≠s_{l-1}.$
$s_l=s_{l+1}=…=s_r.$
$r=n or s_r≠s_{r+1}.$

Adjacent blocks are two blocks $s[l_1,r_1]$ and $s[l_2,r_2]$ satisfying $r_1+1=l_2$ .

For example, if $s=0001100111$ , Kamron can choose the two blocks $s[4,5]$ and $s[6,7]$ and swap them, transforming $s$ into $0000011111$ .

Given a string t of length n consisting of '0', '1' and '?', Kamron wants to determine the minimum number of operations required to perform such that for any index $i (1≤i≤n)$ , if $t_i≠ '?'$ then $s_i=t_i$ . If it is impossible, output $−1$ .

∗∗A string a is a substring of a string b if a can be obtained from b by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Kiruvchi ma'lumotlar:

Each test contains multiple test cases. The first line contains the number of test cases $t (1≤t≤10^4)$ . The description of the test cases follows.

The first line of each test case contains a string s consisting of '0' and '1'.

The second line of each test case contains a string t consisting of '0' and '1'.

It is guaranteed that the lengths of s and tt are the same.

It is guaranteed that the sum of the length of ss over all test cases will not exceed $4⋅10^5$ .

Chiquvchi ma'lumotlar:

For each test case, output one integer — the minimum number of operations required. If it is impossible, output −1.

Izoh:

In the first test case, the possible way is shown in the statement.

In the second test case, one possible way could be:

Swap blocks $[2,2],[3,3]$ , s will become $001101$ .
Swap blocks $[3,4],[5,5]$ , s will become $000111$ .
Swap blocks $[1,3],[4,6]$ , s will become $111000$ .

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 0001100111 0000011111 010101 111000 0101 0110 0101 1010 011001 001110 0 1	1 3 1 -1 -1 -1

F. Kamron and Binary String (Hard Version)

Xotira: 32 MB, Vaqt: 1000 ms

Masala

This is the hard version of the problem. The difference between the versions is that in this version, string tt consists of '0', '1' and '?'. You can hack only if you solved all versions of this problem.

Kamron has a binary string $s$ of length $n$ . Kamron can perform the following operation:

Choose two adjacent blocks of $s$ and swap them.

A block is a maximal $substring∗$ of identical characters. Formally, denote $s[l,r]$ as the substring $s_ls_{l+1}…s_r.$ A block is $s[l,r]$ satisfying:

$l=1 or s_l≠s_{l-1}.$
$s_l=s_{l+1}=…=s_r.$
$r=n or s_r≠s_{r+1}.$

Adjacent blocks are two blocks $s[l_1,r_1]$ and $s[l_2,r_2]$ satisfying $r_1+1=l_2$ .

For example, if $s=0001100111$ , Kamron can choose the two blocks $s[4,5]$ and $s[6,7]$ and swap them, transforming $s$ into $0000011111$ .

Given a string t of length n consisting of '0', '1' and '?', Kamron wants to determine the minimum number of operations required to perform such that for any index $i (1≤i≤n)$ , if $t_i≠ '?'$ then $s_i=t_i$ . If it is impossible, output $−1$ .

∗∗A string a is a substring of a string b if a can be obtained from b by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Kiruvchi ma'lumotlar:

Each test contains multiple test cases. The first line contains the number of test cases $t (1≤t≤10^4)$ . The description of the test cases follows.

The first line of each test case contains a string s consisting of '0' and '1'.

The second line of each test case contains a string t consisting of '0' and '1'.

It is guaranteed that the lengths of s and tt are the same.

It is guaranteed that the sum of the length of ss over all test cases will not exceed $4⋅10^5$ .

Chiquvchi ma'lumotlar:

For each test case, output one integer — the minimum number of operations required. If it is impossible, output −1.

Izoh:

In the first test case, the possible way is shown in the statement.

In the second test case, one possible way could be:

Swap blocks $[2,2],[3,3]$ , s will become $001101$ .
Swap blocks $[3,4],[5,5]$ , s will become $000111$ .
Swap blocks $[1,3],[4,6]$ , s will become $111000$ .

In the first test case of the second example, one possible way could be:

Swap blocks $[1,1],[2,2]$ , $s$ will become $100101$ .
Swap blocks $[4,4],[5,5]$ , $s$ will become $100011$ .

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 0001100111 0000011111 010101 111000 0101 0110 0101 1010 011001 001110 0 1	1 3 1 -1 -1 -1
2	6 010101 ?0?0?? 0101 ?0?0 11100101 ???????? 11100101 ???11?1? 1000100011 ?11?000?0? 10101 ?1011	2 -1 0 2 2 -1

G. Артур и вопросы

Xotira: 32 MB, Vaqt: 1000 ms

Masala

После скобочных последовательностей Артур увлекся теорией чисел. И у него появилась новая любимая последовательность длины $n (a_1, a_2, ..., a_n)$ , состоящая из целых чисел, и целое число $k$ , не превышающее $n$ .

Эта последовательность обладала следующим свойством. Если выписать суммы всех ее подотрезков, состоящих из $k$ подряд идущих элементов $(a_1 + a_2 ... + a_k, a_2 + a_3 + ... + a_{k + 1}, ..., a_{n - k + 1} + a_{n - k + 2} + ... + a_n)$ , то элементы выписанной последовательности будут строго возрастать.

Например, для следующего примера: $n = 5, k = 3, a = (1, 2, 4, 5, 6)$ последовательность сумм будет иметь вид: $(1 + 2 + 4, 2 + 4 + 5, 4 + 5 + 6) = (7, 11, 15)$ , а значит последовательность a удовлетворяет описанному свойству.

Очевидно, в последовательности сумм будет $n - k + 1$ элемент.

Кто-то (не будем говорить кто) заменил в последовательности Артура некоторые числа на знаки вопроса (если число заменяется, то ровно на один знак вопроса). Нужно восстановить последовательность, чтобы она удовлетворяла нужному свойству, и при этом минимизировать сумму $|a_i|$ , где $|a_i|$ — абсолютная величина $a_i$ .

Kiruvchi ma'lumotlar:

В первой строке следуют два целых числа $n$ и $k (1 ≤ k ≤ n ≤ 10^5)$ , обозначающих соответственно количество чисел в последовательности Артура и длины подотрезков.

В следующей строке следуют через пробел $n$ элементов $a_i (1 ≤ i ≤ n)$ .

Если $a_i = ?$ , значит $i-й$ элемент последовательности Артура был заменен на знак вопроса.

В противном случае, $a_i ( - 10^9 ≤ a_i ≤ 10^9) — i-й$ элемент последовательности Артура.

Chiquvchi ma'lumotlar:

Если Артур что-то напутал, и последовательности, соответствующей данной информации нет, выведите единственную строку «Incorrect sequence» (без кавычек).

В противном случае, выведите в первую строку выходных данных $n$ целых чисел — любимую последовательность Артура. Если таких последовательностей несколько, выведите последовательность с минимальной суммой $|a_i|$ , где $|a_i|$ — абсолютная величина $a_i$ . Если и таких последовательностей несколько, разрешается вывести любую из них. Элементы последовательности следует выводить без лидирующих нулей.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 2 ? 1 2	0 1 2
2	5 1 -10 -9 ? -7 -6	-10 -9 -8 -7 -6
3	5 3 4 6 7 2 9	Incorrect sequence

H. Паша и труба

Xotira: 512 MB, Vaqt: 4000 ms

Masala

На очередном заседании правящей партии «A» министр Павел предложил усовершенствовать систему водопровода и проложить в городе новую трубу.

Город на карте представляет собой прямоугольное клетчатое поле размера $n × m$ . Каждая клетка поля либо свободна (тогда труба может проходить по ней), либо занята (по такой клетке труба проходить не может). На карте свободные клетки обозначены символом '.', а занятые — '#'.

Труба должна удовлетворят следующим свойствам:

труба имеет вид ломанной ширины 1,
труба проходит по свободным клеткам,
труба начинается с края поля, но не с угловой клетки,
труба заканчивается на краю поля, но не в угловой клетке,
труба имеет не более 2-х поворотов (на 90 градусов),
на краях поля должно существовать ровно две клетки, по которым проходит труба,
если труба представляет собой один отрезок, то концевые точки трубы должны лежать на разных краях поля,
для каждой неконцевой клетки трубы существует ровно две соседние по стороне клетки, которые тоже принадлежат трубе,
для каждой из концевых клеток трубы существует ровно одна соседняя по стороне клетка, которая тоже принадлежит трубе.

Примеры разрешенных маршрутов для прокладывания труб:

....# ....# .*..#
***** ****. .***.
..#.. ..#*. ..#*.
#...# #..*# #..*#
..... ...*. ...*.

Примеры запрещенных маршрутов для прокладывания труб:

.**.# *...# .*.*#
..... ****. .*.*.
..#.. ..#*. .*#*.
#...# #..*# #*.*#
..... ...*. .***.

В примерах трубы обозначены символами ' * '.

Вам поручили написать программу, которая вычисляет количество различных способов проложить ровно одну трубу на территории города.

Два способа прокладывания труб считаются различными, если они отличаются хотя бы в одной клетке.

Kiruvchi ma'lumotlar:

В первой строке входных данных следуют два целых числа $n, m (2 ≤ n, m ≤ 2000)$ — размеры карты Берляндии.

В следующих n строках задано по m символов — карта города.

Если клетка карты обозначена символом '.', значит она свободна, и по ней может проходить труба.

Если клетка карты обозначена символом '#', значит она занята, и труба по ней проходить не может.

Chiquvchi ma'lumotlar:

Выведите в первую строку выходных данных одно целое число — количество различных способов проложить ровно одну трубу.

Izoh:

В первом примере существует 3 способа проложить трубу (клетки трубы обозначены символами ' * '):

.*. .*. ...
.*# **# **#
.*. ... .*.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 3 ... ..# ...	3
2	4 2 .. .. .. ..	2
3	4 5 #...# #...# ###.# ###.#	4