A. Камрон и строки

Xotira: 32 MB, Vaqt: 1000 ms

Masala

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

На последней паре преподаватель продиктовал Виталию две строки \(s\) и \(t\) одинаковой длины, состоящие из строчных букв латинского алфавита, причем строка \(s\) лексикографически меньше строки \(t\). Виталию стало интересно — существует ли такая строка, которая лексикографически больше строки \(s\) и одновременно лексикографически меньше строки \(t\). Искомая строка Виталия также должна состоять из строчных букв латинского алфавита и иметь длину, равную длинам строк \(s\) и \(t\).

Давайте поможем Виталию решить эту несложную задачу!

Kiruvchi ma'lumotlar:

В первой строке задана строка \(s (1 ≤ |s| ≤ 100)\), состоящая из строчных букв латинского алфавита, где \(|s|\) — длина строки.

Во второй строке задана строка \(t (|t| = |s|)\), состоящая из строчных букв латинского алфавита, где \(|t|\) — длина строки.

Гарантируется, что длины строк \(s\) и \(t\) одинаковы, и строка \(s\) лексикографически меньше строки \(t\).

Chiquvchi ma'lumotlar:

Если не существует строки, удовлетворяющей заданным требованиям, выведите единственную строку «No such string» (без кавычек).

Если же такая строка существует, выведите ее в первую строку выходных данных. Если подходящих строк несколько, разрешается вывести любую из них.

Izoh:

По определению, строка \(s = s_1s_2... s_n\) лексикографически меньше строки \(t = t_1t_2... t_n\), если существует такое \(i\), что \(s_1 = t_1, s_2 = t_2, ... s_{i - 1} = t_{i - 1}, s_i < t_i.\)

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	a c	b
2	aaa zzz	kkk
3	abcdefg abcdefh	No such string

B. Сардор и поздравление

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Маленькая Сардор решила поздравить папу с Днем рождения и подарить ему открытку. Она уже составила текст для поздравления — строку \(s\) длины \(n\), состоящую из прописных и строчных букв латинского алфавита. Сардор пока не умеет писать, поэтому она нашла газету и решила вырезать оттуда буквы и наклеить их в открытку, чтобы получилась строка \(s\). В газете записана строка \(t\), состоящая из прописных и строчных букв латинского алфавита. Известно, что длина строки \(t\) не меньше длины строки \(s\).

Возможно, что в газете не хватает каких-то букв для составления поздравления, а какие-то буквы могут оказаться лишними. Поэтому Сардор хочет вырезать из газеты некоторые \(n\) букв и составить из них поздравление длины ровно \(n\), чтобы оно было максимально похоже на \(s\). Если буква в заданной позиции совпадает и по значению, и по регистру (в строке \(s\) и в той строке, что наклеит Сардор ), то она радостно кричит \(«УРА!»\), а если буква в заданной позиции совпадает только по значению, но не по регистру, то она произносит \(«ОПА»\).

Сардор хочет наклеить такую надпись, чтобы максимальное количество раз прокричать \(«УРА!»\), а если это можно сделать несколькими способами, то во вторую очередь она хочет максимизировать количество раз, которое она скажет \(«ОПА»\). Вам предстоит помочь Сардоре в составлении поздравления.

Kiruvchi ma'lumotlar:

В первой строке задана строка \(s (1 ≤ |s| ≤ 2·10^5)\), состоящая из прописных и строчных букв латинского алфавита — текст для поздравления, который составила Таня.

Во второй строке задана строка \(t (|s| ≤ |t| ≤ 2·10^5)\), состоящая из прописных и строчных букв латинского алфавита — текст, записанный в газете.

Запись \(|a|\) обозначает длину строки \(a\).

Chiquvchi ma'lumotlar:

Выведите два целых числа, разделенных пробелом, где:

первое число — сколько раз Таня прокричит «УРА!» при составлении поздравления,
второе число — сколько раз Таня произнесет «ОПА» при составлении поздравле

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	AbC DCbA	3 0
2	ABC abc	0 3
3	abacaba AbaCaBA	3 4

C. Аня и смартфон

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Аня купила новый смартфон с операционной системой Berdroid. В меню смартфона ровно \(n\) приложений, у каждого своя иконка. Иконки расположены на различных экранах, на одном экране помещается \(k\) иконок. Иконки с первой по \(k-ю\) расположены на первом экране, \(с (k + 1)\)-й по \(2k-ю\) на втором и так далее (последний экран может быть заполнен не полностью).

Изначально меню смартфона установлено на экран номер \(1\). Чтобы запустить приложение, чья иконка расположена на экране \(t\), Ане надо сделать следующие движения пальцем: сначала домотать до нужного экрана номер \(t\), сделав \(t - 1\) движение (если иконка на экране \(t\)), а затем сделать еще одно движение — нажать ровно \(1\) раз на иконку нужного приложения для его запуска.

После запуска приложения меню откатывается на первый экран, то есть, чтобы запустить следующее приложение необходимо вновь листать меню с экрана номер \(1\).

Все приложения пронумерованы от \(1\) до \(n\). Известен исходный порядок, в котором иконки приложений расположены в меню, но он изменяется по ходу использования операционной системы. Berdroid интеллектуально меняет порядок иконок, передвигая более часто используемые ближе к началу. Формально, сразу после запуска приложения его иконка меняется местами с впереди стоящей (т. е. имеющей на единицу меньший номер в порядке следования иконок), причем впереди стоящая иконка приложения может быть и на соседнем экране. Единственное исключение — если иконка запускаемого приложения уже стоит на первом месте, в этом случае расположение иконок не меняется.

Аня запланировала в каком порядке она будет запускать приложения. Сколько движений пальцем надо произвести Ане, чтобы запустить приложения в запланированном порядке?

Обратите внимание, что одно приложение может быть запущено многократно.

Kiruvchi ma'lumotlar:

В первой строке входных данных следуют три целых числа \(n, m, k (1 ≤ n, m, k ≤ 10^5)\) — количество приложений, имеющихся на смартфоне Ани, количество приложений, которые будут запущены, и количество иконок, которые помещаются на одном экране соответственно.

Следующая строка содержит n целых чисел, перестановку \(a_1, a_2, ..., a_n\) — изначальный порядок иконок слева направо в меню (от первой до последней), \(a_i\) — это номер приложения, иконка которого \(i-я\) в меню. Каждое целое число от \(1\) до \(n\) встречается ровно один раз среди ai.

Третья строка содержит m целых чисел \(b_1, b_2, ..., b_m(1 ≤ b_i ≤ n)\) — номера запускаемых приложений в запланированном порядке. Одно приложение может быть запущено несколько раз.

Chiquvchi ma'lumotlar:

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

Izoh:

В первом тесте исходная конфигурация выглядит как \((123)(456)(78)\), то есть на первом экране расположены иконки приложений \(1, 2, 3\), на втором экране — \(4, 5, 6\), а на третьем экране — \(7, 8\).

После запуска приложения номер \(7\) получим новое расположение иконок — \((123)(457)(68)\). При этом для его запуска необходимо сделать \(3\) движения пальцем.

После запуска приложения номер \(8\) получим конфигурацию — \((123)(457)(86)\). При этом для его запуска необходимо сделать \(3\) движения пальцем.

После запуска приложения номер \(1\) расположение иконок на экранах не меняется. При этом для его запуска необходимо сделать \(1\) движение пальцем.

Итого, Аня сделает \(7\) движений пальцем.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	8 3 3 1 2 3 4 5 6 7 8 7 8 1	7
2	5 4 2 3 1 5 2 4 4 4 4 4	8

D. Илья и эскалатор

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Илья устал от олимпиадного программирования, ушел из университета и устроился на работу в метрополитен. Перед ним поставили задачу определения нагрузки на эскалатор.

Пусть n человек стоят в очереди на эскалатор. В каждую секунду происходит одно из двух: либо первый человек в очереди с вероятностью p заходит на эскалатор, либо первый человек в очереди с вероятностью \((1 - p)\) остается стоять на месте, не в силах совладать с боязнью эскалаторов, задерживая при этом всю очередь за ним.

Формально говоря, \(i-й\) в очереди не сможет зайти на эскалатор, пока на него не зайдут люди с номерами от \(1\) до \(i - 1\) включительно. За одну секунду может зайти только один человек. Так как эскалатор бесконечный, то единожды зайдя на него, человек никогда с него не сойдёт, т. е. будет ехать на нем в эту и любую последующую секунды. Илье нужно посчитать математическое ожидание количества людей, которые будут находиться на эскалаторе после t секунд.

Вам необходимо помочь ему в решении этой непростой задачи.

Kiruvchi ma'lumotlar:

В первой строке входных данных следуют три числа \(n, p, t (1 ≤ n, t ≤ 2000, 0 ≤ p ≤ 1)\). Числа \(n\) и \(t\) — целые, чиcло \(p\) — вещественное, заданное ровно с двумя знаками после запятой.

Chiquvchi ma'lumotlar:

Выведите одно вещественное число — математическое ожидание количества людей, которые будут на эскалаторе через \(t\) секунд. Абсолютная или относительная погрешность не должна превышать \(10^{- 6}\).

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 0.50 1	0.5
2	1 0.50 4	0.9375
3	4 0.20 2	0.4

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

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

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

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