Информатика

Вновь открытое казино предложило оригинальную игру.

В начале игры крупье выставляет в ряд несколько фишек разных цветов. Кроме того, он объявляет, какие последовательности фишек игрок может забирать себе в процессе игры. Далее игрок забирает себе одну из заранее объявленных последовательностей фишек, расположенных подряд. После этого крупье сдвигает оставшиеся фишки, убирая разрыв. Затем игрок снова забирает себе одну из объявленных последовательностей и так далее. Игра продолжается до тех пор, пока игрок может забирать фишки.

Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому — на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.

После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.

Требуется написать программу, определяющую максимальную сумму, которую сможет получить игрок.

Входные данные
В первой строке входных данных содержится число K (1 ≤ K ≤ 26) — количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число X_i (1 ≤ X_i ≤ 150, i = 1..K) — цена фишки соответствующего цвета.

В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задаетсяL строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.

В следующей строке содержится число N(1 ≤ N ≤ 150) — количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.

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

Примеры

№	Входные данные	Выходные данные
1	3 v 3 l 1 u 2 luvu 3 luv vul uuu	6

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

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

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

Помогите школьникам по данному описанию притоков определить минимальное количество переправ, которое им придется совершить во время похода.

Входные данные
Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит 10⁵ символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R - приток впадает в реку с правого берега и B - притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

Выходные данные
Выведите одно целое число - минимальное количество переправ.

Примечания
Рисунок к приведенному ниже примеру.

Примеры

№	Входные данные	Выходные данные
1	LLBLRRBRL	5

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

Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10) - количество заданных Петей вопросов. Каждая из N последующих строк содержит описание четырех точек - четыре пары целых чисел X и Y (−100 ≤ X ≤ 100, −100 ≤ Y ≤ 100), обозначающих координаты точки.

Выходные данные
Для каждого из вопросов определите, образуют ли данные точки параллелограмм. Если они образуют параллелограмм, то выведите номера этих точек в одной строке через пробел в порядке обхода параллелограмма. Начинать обход можно с любой из вершин. Если они не образуют параллелограмм, выведите в этой строке одно число 0. Ответ на каждый из запросов должен быть в отдельной строке.
 

Примеры

№	Входные данные	Выходные данные
1	3 1 1 4 2 3 0 2 3 1 1 5 2 2 3 3 0 0 0 5 1 6 3 1 2	1 3 2 4 0 1 2 3 4

Алиса и капитан Буран играют в покер с одной картой. Однокарточный покер - это игра для двух игроков с игральными картами. Каждая карта в этой игре показывает целое число от 1 до 13 включительно. Сила карты определяется числом, написанным на ней, следующим образом:
Слабая 2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1 Сильная
В покер с одной картой играют следующим образом:
- Каждый игрок берет одну карту из колоды.
- Выбранная карта становится рукой игрока.
- Игроки раскрывают друг другу руки.
- Игрок с более сильной картой побеждает в игре.
- Если их карты одинаково сильны, игра заканчивается вничью.
Вы смотрите, как Алиса и капитан Буран играют в игру, и можете видеть их руки. Число, написанное на карточке Алисы, - A, а число, написанное на карточке капитана Бурана, - B.

Напишите программу для определения исхода игры.
 

Ушан решил сыграть шестигранным кубиком. На каждой из шести сторон изображено целое число от 1 до 6, а два числа на противоположных сторонах всегда в сумме дают 7. Ушан сначала кладет кубик на стол произвольной стороной вверх, а затем повторно выполняет следующую операцию. Поверните кубик на 90 ° в одном из следующих направлений: влево, вправо, вперед (кубик приблизится) и назад (кубик уйдет дальше), затем получите y очков, где y - это число, написанное на стороне, обращенной вверх.

Например, давайте рассмотрим ситуацию, когда сторона, показывающая 1, обращена вверх, ближняя сторона показывает 5, а правая сторона показывает 4, как показано на рисунке (исходное положение для нашего примера).
Если кубик повернуть вправо, как показано на рисунке, сторона, показывающая 3, будет обращена вверх. Если из исходного положения кубик повернуть влево, сторона, показывающая 4, будет смотреть вверх. Вверху будет сторона, показывающая 2, если кубик из исходного положения повернуть вперед, а сторона, показывающая 5, будет обращена вверх, если кубик повернуть назад из исходного положения.

Найдите минимальное количество операций, которое Ушан должен выполнить, чтобы набрать в сумме не менее x баллов.

Входные данные
На вход подается целое число x (\(1<=x<=10^{15}\)).

Выходные данные
Выведите на экран ответ.
 

 

Примеры

№	Входные данные	Выходные данные
1	7	2
2	149696127901	27217477801

 

Громозека решил построить строку, которая начинается с A и заканчивается Z, извлекая подстроку строки s (то есть последовательную часть s). Найдите наибольшую длину строки, которую может построить Громозека. Гарантируется, что всегда существует подстрока s, которая начинается с A и заканчивается Z.

Формат входных данных
На вход подается строка s (1 <= длина строки s <= 2·10⁵ ), состоящая из больших английских букв (A-Z).

Формат выходных данных
Выведите на экран ответ на задачу.
 

Пояснение к примерам
1. В первом примере, убрав символы с седьмого по одиннадцатый, можно построить строку ASDFZ, которая начинается с A и заканчивается Z.

Громозека решает задачи по шахматам из сборника для начинающих (ABC), если его текущий рейтинг меньше 1200, и задачи из сборника для клубных игроков (ARC) в противном случае. Вам дается текущий рейтинг Громозеки, x. Выведите ABC, если Громозека будет решать задачи для начинающих, и выведите ARC в противном случае.

Входные данные
На вход подается целое положительно число x.

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные
1	1000	ABC
2	2000	ARC

 

На линии, идущей с востока на запад, есть N городов. Города пронумерованы от 1 до N в порядке с запада на восток. Каждая точка на линии имеет одномерные координаты, а точка, которая находится дальше на восток, имеет большее значение координаты. Координата города i - Xi. Вы находитесь в городе 1 и хотите посетить все остальные города. У вас есть два способа путешествовать:
- Ходить по линии. Ваш уровень усталости увеличивается на A каждый раз, когда вы путешествуете на расстояние 1, независимо от направления.
- Телепортируйтесь в любое место по вашему выбору. Ваш уровень усталости увеличивается на B независимо от пройденного расстояния.
Найдите минимально возможное общее повышение уровня вашей усталости, когда вы посетите все города этими двумя способами.

Входные данные
В первой строке заданы три целых числа N (\(2<=N<=10^5\)), A (\(1<=A<=10^9\)), B (\(1<=B<=10^9\)). Во второй строке заданы координаты городов Xi (\(1<=X_i<=10^9\)), для всех i \(X_i <X_{i+1}\)(\(1<=i<=N-1\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 2 5 1 2 5 7	11	Из города 1 пройдите расстояние 1 до города 2, затем телепортируйтесь в город 3, затем пройдите расстояние 2 до города 4. Общее увеличение вашего уровня усталости в этом случае составляет 2 × 1 + 5 + 2 × 2 = 11, что является минимально возможным значением.
2	7 1 100 40 43 45 105 108 115 124	84	Из города 1 пройдите пешком до города 7. Общее увеличение вашего уровня усталости в этом случае составляет 84, что является минимально возможным значением.
3	7 1 2 24 35 40 68 72 99 103	12	Посетите все города в любом порядке, телепортировавшись шесть раз. Суммарное повышение уровня утомляемости в этом случае составляет 12, что является минимально возможным значением.

 

Дано целое число N. Найдите количество положительных делителей числа N!, по модулю \(10 ^ 9 + 7\).

Входные данные
На вход подается целое число N (\(1<=N<=10^3\)).

Выходные данные
Выведите на экран количество положительных делителей числа N!, по модулю \(10 ^ 9 + 7\).
 

 

Примеры

№	Входные данные	Выходные данные
1	3	4
2	6	30
3	1000	972926972

 

В качестве новогоднего подарка Громозека получил строку s длиной 19 следующего формата:
[пять строчных английских букв], [семь строчных английских букв], [пять строчных английских букв].
Громозека хочет преобразовать строку s, разделенную запятыми, в строку, разделенную пробелами. Напишите программу для выполнения преобразования за него.

Входные данные
На вход подается одна строка s, длина строки ровно 19 символов. Шестой и четырнадцатый символы в s - это ,. Остальные символы - строчные буквы английского алфавита (a-z).

Выходные данные
Выведите строку после преобразования
 

 

Примеры

№	Входные данные	Выходные данные
1	happy,newyear,enjoy	happy newyear enjoy

 

Громозека собирается принять участие в финальном раунде STCoder Contest. В этом соревновании N задач, пронумерованных от 1 до N. Громозека знает, что на  решение задачи i (\(1<=i<=N\)) требуется Ti секунд. Кроме того, участникам предлагается M видов напитков, пронумерованных от 1 до M. Если Громозека выпьет напиток i (\(1 <= i <= M\)), его мозг будет стимулироваться и время, необходимое ему для решения задачи Pi станет Xi секунд. Это не влияет на время решения других задач.
Участнику разрешается выпить ровно один из напитков до начала конкурса. Для каждого напитка Громозека хочет знать, сколько секунд ему понадобится, чтобы решить все задачи, если он выпьет этот напиток. Предположим, что время, необходимое ему для решения всех задач, равно сумме времени, необходимого для решения отдельных задач. Ваша задача - написать вместо Громозеки программу для расчета времени.

Входные данные
На вход подаются целые числа. В первой строке число N (\(1<=N<=100\)), во второй строке N чисел Ti (\(1<=T_i<=10^5\)). В третьей строке задано число M (\(1<=M<=100\)). Далее идет M строк, в каждой из которых задана пара Pi,Xi (\(1<=P_i<=N\), \(1<=X_i<=10^5\)).


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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 2 1 4 2 1 1 2 3	6 9	Если Громозека выпьет напиток под номером 1, время, необходимое ему для решения каждой задачи, составит 1, 1 и 4 секунды, соответственно, всего 6 секунд. Если Громозека выпьет напиток 2, время, необходимое ему для решения каждой задачи, составит 2, 3 и 4 секунды, соответственно, всего 9 секунд.
2	5 7 2 3 8 5 3 4 2 1 7 4 13	19 25 30

 

Есть N городов. Есть также шоссе K и железные дороги L, проходящие между городами. Каждое i-я шоссе двунаправленно соединяет рi и qi города, а каждая i-я железная дорога двунаправленно соединяет ri и si города. Нет двух шоссе, соединяющих одну и ту же пару городов. Точно так же, никакие две железные дороги не соединяют одну и ту же пару городов. Будем считать, что города A и B соединены шоссе, если до города B можно добраться из города A по некоторому количеству шоссе. Здесь любой город считается соединенным с собой шоссе. Аналогичным образом, мы также определим возможность сообщения железными дорогами. Для каждого города найдите количество городов, соединенных с этим городом как шоссе, так и железными дорогами.

Входные данные
Входные данные поступают в следующем формате:

N K L 
p1 q1 
...
pK qK 
r1 s1 
... 
rl sL

Ограничения:
\(2<=N<=2\cdot10^5 \\ 1<=K,L<=10^5 \\ 1<=p_i,q_i,r_i,s_i<=N\\ p_i <q_i \\ r_i<s_i \\ Когда\ i \neq j, (p_i,q_i)\neq(p_j,q_j) \\ ?Когда\ i \neq j, (r_i,s_i)\neq(r_j,s_j)\)


Выходные данные
Выведите N целых чисел в одной строке, разделяя каждое число одним пробелом. Каждое i число должно обозначать количество городов, соединенных с i-м городом как шоссе, так и железными дорогами.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	4 3 1 1 2 2 3 3 4 2 3	1 2 2 1	Все четыре города связаны между собой дорогами. Железной дорогой соединены только второй и третий города. Таким образом, ответы для городов 1,2,2 и 1 соответственно.
2	4 2 2 1 2 2 3 1 4 2 3	1 2 2 1
3	7 4 4 1 2 2 3 2 5 6 7 3 5 4 5 3 4 6 7	1 1 2 1 2 2 2

 

У Громозеки есть любимая строка S, состоящая из строчных английских букв и пустая строка T. В конец строки T он хочет добавить произвольное количество раз одно из следующих слов: dream, dreamer, erase и eraser. Помогите Громозеке определить, сможет ли он получить S = T.

Формат входных данных
На вход подается строка S (1<= длина строки S <=10⁵), состоящая из строчных английских букв (a-z).

Формат выходных данных
Если возможно получить S = T, выведите YES. В противном случае выведите NO.

 

Есть изображение высотой H пикселей и шириной W пикселей. Каждый пиксель представлен либо символом . или *. Символ, представляющий пиксель в i-й строке сверху и j-м столбце слева, обозначается Ci,j. Растяните это изображение по вертикали так, чтобы его высота увеличилась вдвое. То есть напечатайте изображение  высотой 2H пикселей и шириной W пикселей, где пиксель в i-й строке и j-м столбце равен C(i+1)/2,j (результат деления округляется в меньшую сторону).

Входные данные
В первой строке записаны два целых числа H и W (\(1 <= H, W <=100\)). Затем идут H строк по W символов в строке, где каждый символ либо . либо *.

Выходные данные
Выведите на экран растянутое изображение.
 

 

Примеры

№	Входные данные	Выходные данные
1	2 2 *. .*	*. *. .* .*
2	1 4 ***.	***. ***.
3	9 20 .....***....***..... ....*...*..*...*.... ...*.....**.....*... ...*.....*......*... ....*.....*....*.... .....**..*...**..... .......*..*.*....... ........**.*........ .........**.........	.....***....***..... .....***....***..... ....*...*..*...*.... ....*...*..*...*.... ...*.....**.....*... ...*.....**.....*... ...*.....*......*... ...*.....*......*... ....*.....*....*.... ....*.....*....*.... .....**..*...**..... .....**..*...**..... .......*..*.*....... .......*..*.*....... ........**.*........ ........**.*........ .........**......... .........**.........

 

Два игрока, Петя и Ваня, играют в следующую игру. Имеется строка s длиной 3 или больше символов. Никакие два соседних символа в s не равны. Игроки ходят по очереди. Петя ходит первым. За один ход нужно удалить один из символов из строки s, за исключением крайних (первого и последнего). Символ не может быть удален, если удаление символа приведет к появлению двух соседних одинаковых символов в строке. Игрок, который не может выполнить операцию, проигрывает игру. Определите, какой игрок выиграет, если они будут играть оптимально.

Входные данные
На вход подается строка s (\(3 <= len(s) <= 10^5\)). Строка состоит только из строчных английских букв (a-z). Никакие два соседних символа в s не равны.

Выходные данные
Если Петя выиграет, выведите First. Если выиграет Ваня, выведите Second.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	aba	Second	Петя не может выполнить операцию, так как удаление символа b, который является единственным символом, который можно удалить, приведет к тому, что s станет равной aa, два одинаковых символа будут соседними.
2	abc	First	Когда Петя удаляет b из s, строка становится равной ac и Ваня не сможет выполнить операцию, поскольку в s нет других символов, за исключением крайних.
3	abcab	First

 

Назовём палиндромом непустую строку, которая читается одинаково справа налево и слева направо. Например, « abcba », « a » и « abba » являются палиндромами, а « abab » и « xy » не являются.

Назовём подстрокой строки строку, полученную отбрасыванием некоторого (возможно, нулевого) количества символов с начала и с конца строки. Например, « abc », « ab » и « c » являются подстроками строки « abc », а « ac » и « d » не являются.

Назовем палиндромностью строки количество её подстрок, которые являются палиндромами. Например, палиндромность строки « aaa » равна 6, так как все её подстроки являются палиндромами, а палиндромность строки « abc » равна 3, так как только подстроки длины 1 являются палиндромами.

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

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 100000) — длина строки s.

Во второй строке задана строка s, состоящая из n строчных букв латинского алфавита.

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

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

Примечание
В первом примере у строки « ololo » есть 9 подстрок-палиндромов: « o », « l », « o », « l », « o », « olo », « lol », « olo », « ololo ». Обратите внимание, что некоторые подстроки совпадают, но учитываются несколько раз.

Во втором примере палиндромность строки « abccbaghghghgdfd » равна 29.
 

Примеры

№	Входные данные	Выходные данные
1	5 oolol	ololo
2	16 gagadbcgghhchbdf	abccbaghghghgdfd

Вам даны неотрицательные целые числа a и b (a<=b) и положительное целое число x. Сколько целых чисел от a до b включительно делятся на x?

Входные данные
В одной строке задаются три числа a, b и x (\(0<=a<=b<=10^{18}\), \(1<=x<=10^{18}\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 8 2	3	Есть три целых числа от 4 до 8 включительно, которые делятся на 2: 4, 6 и 8.
2	0 5 1	6	Есть шесть целых чисел от 0 до 5 включительно, которые делятся на 1: 0, 1, 2, 3, 4 и 5.
3	9 9 2	0	Нет целого числа от 9 до 9 включительно, которое делится на 2.
4	1 1000000000000000000 3	333333333333333333	Остерегайтесь целочисленных переполнений!

 

Есть три упаковки конфет, каждая из которых содержит конфеты в количестве a, b и c штук соответственно. Двое воспитанников детского сада Сластена дерутся из-за этих конфет. Воспитательница Анна Николаевна пытается распределить пачки между двумя воспитанниками таким образом, чтобы каждый получил одинаковое количество конфет. Определите, возможно ли это.
Обратите внимание, что Анна Николаевна не может вынимать конфеты из упаковки, и все содержимое каждой упаковки должно быть отдано одному из учеников.

Входные данные
Во входной строке содержится три числа a, b и c (\(1<=a,b,c<=100\)).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10 30 20	Yes	Раздайте пачку с 30 конфетами одному, а две пачки по 10 и 20 конфет - другому. Каждый получает по 30 конфет.
2	30 30 100	No	В этом случае у воспитанника, который получает упаковку со 100 конфетами, всегда больше конфет, чем у другого. Обратите внимание, что каждую упаковку нужно отдать одному из них.
3	56 25 31	Yes

 

В ряд ставятся N кеглей. Громозека красит каждую из них в один из K цветов из своих банок с краской. Из эстетических соображений любые две соседних кегли должны быть окрашены в разные цвета. Найдите количество возможных способов раскрасить кегли.

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).
 

 

Примеры

№	Входные данные	Выходные данные
1	2 2	2
1	1 10	10

 

Громозека недавно купил три баллончика с краской. Цвет того, который он купил два дня назад, - a, цвет того, который он купил вчера, - b, и цвет того, что он купил сегодня, - c. Цвет каждого баллончика с краской условно представлен целым числом от 1 до 100 включительно. Поскольку Громозека забывчивый, он мог купить несколько баллончиков с краской одного цвета. Подсчитайте количество разных цветов этих баллончиков с краской и скажите ему.

Входные данные
В одной строке записаны три целых числа a, b и c (\(1 <= a,b,c<=100\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные
1	3 1 4	3
2	3 3 33	2