Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 4999. Сколько слов в предложении
Темы: Строки    Символы   

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

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 test 1
2 test test 2

ID 38612. Измени регистр
Темы: Символы    Строки   

Измените регистр символа. Если он был строчной английской буквой сделайте его заглавной буквой; если он был заглавной английской буквой  - строчной.


Входные данные
Задан единственный символ c.

Выходные данные
Необходимо вывести  получившийся символ.
 

Примеры
Входные данные Выходные данные
1 a A
2 B b

ID 4995. Замени символы
Темы: Символы    Строки   

В одной строке записаны символ и некторый текст. Напишите программу, которая заменяет все символы текста, стоящие на четных местах, заданным символом. Нумерация символов начинается с 1.

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 t slovo stoto
2 a test test tasa aeat

ID 4994. Замена одного на другой
Темы: Символы    Строки   

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

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 a b slovo slovo
2 r t rr rr tt tt

ID 4998. Символы на нужных местах
Темы: Символы    Строки   

В одной строке через пробел записаны число и некоторый текст. Напишите программу, которая выводит из текста те символы, номера которых кратны заданному числу (нумерация начинается с 1).

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 2 slovo lv
2 3 test test stt

ID 5000. Считаем цифры
Темы: Символы    Строки   

Дана строка. Напишите программу, которая определяет, есть ли в заданной строке цифры.

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 test NO
2 Ocenka-5 YES

ID 5002. Слово с нужной буквой на конце
Темы: Символы    Строки   

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

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 a b 0
2 t test slovo 1

ID 38237. Буквы по кругу
Темы: Строки    Перебор   

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

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

Во второй строке записано слово, которое хочет найти Петя. Оно также состоит из строчных латинских букв и имеет длину от 1 до 100.

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

Примеры
Входные данные Выходные данные
1 abcdefg
abd
NO
2 abcdg
bag
YES
3 a
aaa
YES

ID 38317. Благозвучное слово
Темы: Цикл for    Строки   

Все буквы латинского алфавита делятся на гласные и согласные. Гласными буквами являются: a, e, i, o, u, y. Остальные буквы являются согласными.

Слово называется благозвучным, если в этом слове не встречается больше двух согласных букв подряд и не встречается больше двух гласных букв подряд. Например, слова abba, mama, program — благозвучные, а слова aaa, school, search — неблагозвучные.

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

Входные данные
Вводится слово, состоящее только из маленьких латинских букв. Длина слова не превышает 30 символов.

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

Примеры
Входные данные Выходные данные Пояснение
1 program 0 Слово уже является благозвучным.
2 school 1 Достаточно добавить одну гласную букву, например, между буквами s  и с

ID 39378. Строковый сдвиг
Темы: Алгоритмы сортировки    Строки   

В непустой строке сдвиг влево перемещает первый символ в конец строки, а сдвиг вправо перемещает последний символ в начало строки. Например, сдвиг влево на строке abcde приводит к bcdea, а два сдвига вправо на abcde приводят к deabc.

Дана непустая строка S, состоящая из строчных латинских букв. Среди строк, которые можно получить, выполнив ноль или более сдвигов влево и ноль или более сдвигов вправо, найдите лексикографически наименьшую строку и лексикографически наибольшую строку.

Входные данные
На вход подается одна строка SS состоит из строчных английских букв. 1 <= |S| <= 1000, где |S| - длина строки S.

Выходные данные
Выведите в первой строке лексикографически наименьшу строку, во второй - лексикографически наибольшую строку.
 

Примеры
Входные данные Выходные данные
1 aaba aaab
baaa
2 z z
z
3 abracadabra aabracadabr
racadabraab

ID 38216. «У моего папы больше денег»
Темы: Строки   

Двое играют в такую игру. Первый называет число, затем второй называет число. Если число второго больше, то он выиграл, в противном случае (даже если числа равны), выиграл первый. Помогите второму игроку – напишите программу, которая будет за него успешно играть в эту игру.

Входные данные
Вводится натуральное число A, которое назвал первый игрок (в числе А  не больше 100 цифр).

Выходные данные
Выведите одно натуральное число – какой-нибудь (любой!) выигрышный ход второго игрока.

Примеры
Входные данные Выходные данные
1 1 2
2 1000000000000000 1000000000000009

ID 38240. Умножения
Темы: Строки   

Дано алгебраическое выражение, состоящее из натуральных чисел, переменных (a, b, c, ..., z) записанных строчной латинской буквой, знаков арифметических операций  + ,  - ,  *  (умножение) и  *  *  (возведение в степень). При этом если после числа идет переменная, то знак умножения может быть пропущен.

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

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

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

Примеры
Входные данные Выходные данные
1 2x+5 1 0
2 x**y**2z*3*5 3 2

ID 38257. Слишком много кофеина
Темы: Строки    Цикл while   

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

Однажды друзья познакомили Артура с девушкой по имени Нина (о, какое прекрасное имя!). Она была очаровательна и очень болтлива, поэтому Артуру почти не нужно было подбирать слова — она заполняла неловкую тишину за него. Разумеется, он пригласил ее в кафе выпить чашечку кофе. Артур даже продумал все свои реплики заранее: «Счастлив тебя видеть», «Ты сегодня восхитительна», «Да, конечно, я внимательно тебя слушаю», «И что дальше?», «Счет, пожалуйста» и, конечно, «Я позвоню тебе на днях, не скучай».

Но, как известно, не бывает идеальных планов. Все шло как по маслу, но вдруг, сидя за столиком в кафе, Нина сказала, что ужасно не выспалась и не отказалась бы от N чашек кофе. И тут Артур понял, что он не обдумал заранее, как он будет делать заказ. Понятно, что нужно сказать что-то вроде: «Сколько-то чашек кофе, пожалуйста», но вот сколько же чашек нужно, чтобы Нина так и не поняла, что Артур не выговаривает букву «р»? Явно нужно заказать не меньше, чем N + 1 чашку — чтобы и Нине досталось N чашек, и самому выпить, но вот сколько точно — Артур не знает. Денег у него не слишком много, поэтому заказывать больше, чем жизненно необходимо для того, чтобы избежать разоблачения, Артур не хочет.

Помогите Артуру — посчитайте, сколько чашек кофе он должен заказать.

Входные данные
Вводится одно целое число N (1 ≤ N ≤ 2999).

Выходные данные
Выведите одно число — количество чашек кофе, которое должен заказать Артур.

Примеры
Входные данные Выходные данные
1 1 2
2 12 15

ID 38271. Cлова не пройдут
Темы: Строки   

Дети, как известно, все раньше и раньше начинают пользоваться интернетом. Теперь, когда у них возникают вопросы, они не бегут к родителям, а заходят в свою любимую поисковую систему и узнают ответ в интернете. Но вдруг они случайно найдут что-нибудь, что им знать пока рановато? Или, может быть, лучше не знать вообще никогда?

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

Ваша задача — помочь правительству этой страны защитить детей от вредной информации. Напишите программу, которая будет проверять, нет ли в данной строке запрещенного слова, учитывая возможное коварство сайтовладельцев. Известно, что сайтовладельцы иногда делают следующие замены: e  3, o  0, i  1, t  7, a  4, s  5.

Входные данные
В первой строке входных данных дана строка — текст с сайта. Во второй строке входных данных дана другая строка — запрещенное слово. Первая строка состоит из маленьких латинских букв и цифр, вторая строка состоит только из маленьких латинских букв. Длина каждой строки не превышает 100.

Выходные данные
Выведите «YES», если запрещенное слово встречается как подстрока в строке с сайта, и «NO» иначе. Возможно, в строке с сайта некоторые буквы изначально были заменены на цифры в соответствии с приведенными выше правилами.
 

Примеры
Входные данные Выходные данные
1 inah0leinthegroundthereliv3dah0bb1t
hobbit
YES
2 whath4v3igotinmypocket
handses
NO
3 whath4veig0t1nmyp0ck37
knife
NO
4 wh4thav31go71nmyp0ck3t
stringofnothing
NO

ID 38311. Метод бутерброда
Темы: Строки   

Секретное агентство «Super-Secret-no» решило для шифрования переписки своих сотрудников использовать «метод бутерброда». Сначала буквы слова нумеруются в таком порядке: первая буква получает номер 1, последняя буква - номер 2, вторая – номер 3, предпоследняя – номер 4, потом третья … и так для всех букв (см. рисунок). Затем все буквы записываются в шифр в порядке своих номеров. В конец зашифрованного слова добавляется знак «диез» (#), который  нельзя использовать в сообщениях.

Например, слово «sandwich» зашифруется в «shacnidw#».



К сожалению, программист «Super-Secret-no», написал только программу шифрования и уволился. И теперь агенты не могут понять, что же они написали друг другу. Помогите им.

Входные данные
Вводится слово, зашифрованное методом бутерброда. Длина слова не превышает 20 букв.

Выходные данные
Выведите расшифрованное слово.

Примеры
Входные данные Выходные данные
1 Aabrrbaacda# Abracadabra

ID 38333. Телефонные номера
Темы: Строки    Обработка текста   

Телефонные номера в адресной книге мобильного телефона имеют один из следующих форматов:

+7<код><номер>

8<код><номер>

<номер>

где <номер> — это семь цифр, а <код> — это три цифры или три цифры в круглых скобках. Если код не указан, то считается, что он равен 495. Кроме того, в записи телефонного номера может стоять знак “-” между любыми двумя цифрами (см. пример).

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

Два телефонных номера совпадают, если у них равны коды и равны номера. Например, +7(916)0123456 и 89160123456 — это один и тот же номер.

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

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

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

Примеры
Входные данные Выходные данные
1 8(495)430-23-97
+7-4-9-5-43-023-97
4-3-0-2-3-9-7
8-495-430
YES
YES
NO

ID 38338. Строки
Темы: Строки    Конструктив   

Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.

Необходимо при помощи этих операций сделать все три строки равными какой-то другой общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать общее количество операций.

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

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

Примеры
Входные данные Выходные данные
1 aaaza
aazzaa
azzza
aazza
2 xy
xxyy
yx
IMPOSSIBLE

ID 38446. Вопль
Темы: Строки   

Вожди известного племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из N букв (всего в алфавите племени M букв). Также, после долгих исследований было выяснено, что если в вопле встречается слово si  (слово – это последовательность букв алфавита, не длиннее трех символов), то этот вопль вселяет во врага fi единиц страха. Если в вопль входит несколько слов, то их “страшность” суммируется. Например, если вопль содержит слова si и sj, то вопль вселяет fi+fj единиц страха. 
Требуется по заданным N, M, алфавиту и списку слов si составить максимально страшный вопль. 

Входные данные:
В первой строке записано три числа – N, M и К (0<N≤100, 0<M<25, 0 ≤ K ≤ 100), где K – количество страшных слов. В следующей строке записан алфавит – строка из M строчных латинских букв. Далее в K строках записана информация о словах – само слово и через пробел одно число, обозначающее страшность этого слова (0 < fi ≤ 10000).

Выходные данные:
В выходной файл необходимо вывести страшность полученного вопля и на следующей строке – сам вопль.

Примеры
Входные данные Выходные данные
1 3 5 4
abcde
abc 10
ab 5
be 7
e 4
16
abe

ID 39535. Голодная пешка
Темы: Строки    Условный оператор    Вывод формулы   

Громозека уважает игры на шахматной доске. На обычной доске размером 8х8 у Громозеки стоит голодная пешка. Голодная пешка каждым ходом съедает какую-либо фигуру соперника (т.е. она может пойти по диагонали вперед на 1 клетку вправо или влево, назад пойти она не может). Громозека, не глядя на доску, научился определять, может ли голодная пешка попасть с одной клетки доски на другую. Превращаться в ферзя голодной пешке нельзя.
Напишите программу, с помощью которой вы могли бы также легко проверить Громозеку.

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

Выходные данные
Выведите слово YES (заглавными буквами), если голодная пешка может попасть из первой клетки во вторую, и NO в противном случае.
Доска имеет размер 8x8, вертикали нумеруются маленькими латинскими буквами от a до h, горизонтали - числами от 1 до 8. Исходная и конечная клетки не совпадают.
 

Примеры
Входные данные Выходные данные
1 a1 b2 YES
2 b2 a1 NO
3 a1 h7 NO

ID 21889. Чемпионат по поиску в сети Меганет
Темы: Структуры данных    Строки    Динамическое программирование    Конструктив    Задача на реализацию   

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

Имя сервера представляет собой строку, содержащую от одной до пяти частей включительно. Каждая часть представляет собой непустую строку, состоящую из строчных букв латинского алфавита. Части разделены точкой. Примеры корректных имен сервера: «a», «ab.cd», «abacaba», «a.b.c.d.e».

Имя раздела представляет собой строку, которая может быть либо пустой, либо содержать от одной до пяти частей включительно. Каждая часть начинается с символа «/», после которого следует одна или несколько строчных латинских букв. Примеры корректных имен разделов: «», «/a», «/aba», «/a/b/c/d/e». Адрес формируется приписыванием имени раздела в конец имени сервера. Например, корректными адресами являются строки: «a», «aba/d/f/g/h», «a.b», «aba.caba/def/g», «c.d.e.f.g/a/b/c/d/e».

Для ограничения доступа к некоторым адресам сети Меганет организаторы чемпионата подготовили несколько фильтров. Фильтр, как и адрес, состоит из двух частей: фильтра сервера и фильтра раздела.

Фильтр сервера состоит из имени сервера, перед которым может также идти строка «*.». Если фильтр сервера представляет собой только имя сервера, то этому фильтру соответствует только сервер, имеющий точно такое же имя. Если фильтр сервера представляет собой строку «*.S », где S — имя сервера, то ему соответствуют сервера, удалением нуля или более начальных частей от имени которых можно получить строку S.

Аналогично, фильтр раздела представляет собой имя раздела, после которого может идти строка «/*». Фильтру раздела, который представляет собой просто имя раздела R, соответствуют только разделы, в точности совпадающие с R. Если фильтр раздела представляет собой строку «R/*», то ему соответствуют все разделы, удалением от имен которых нуля или более конечных частей можно получить строку R. Адрес соответствует фильтру, если его имя сервера соответствует фильтру сервера, а его имя раздела соответствует фильтру раздела.

Примеры фильтров и соответствующих им адресов приведены в таблице ниже.

ab.c/d/e ab.c/d/e
*.a a             ax.a         efg.a
*.a/b/c a/b/c       x.a/b/c      e.fg.a/b/c
x.yz/a/* x.yz/a      x.yz/a/b/c    x.yz/a/xyz
*.a/* a             x.a                   e.fg.a
a/b/c    x.a/ddd/c           e.fg.a/b/c/g/haha/i
*.a/b/c/* a/b/c                           x.a/b/c                           e.fg.a/b/c
a/b/c/xxx                   e.fg.a/b/c/d/e/f
   

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

Пример:
Ввод:
2 0
a.bb/c
bb/c/d
4
a.bb
bb/c/d
a.bb/c/d
bb/c

Вывод:
0
1
0
0


Вывод:
4 0
*.bb/c
*.bb/c/*
bb/c/*
bb/c/*
6
bb
bb/c
bb/c/d
a.bb
a.bb/c
a.bb/c/d

Вывод:
0
4
3
0
2
1

ID 27114. СКОБКИ
Темы: Строки    Задача на реализацию   

Дано корректное математическое выражение, состоящее из переменных, обозначаемых строчными латинскими буквами, инфиксных бинарных операций и круглых скобок для группировки подвыражений. Все операции имеют ассоциативность слева направо и приоритеты, указанные в таблице:
 

Приоритет Операции
1 (наибольший) *, /
2  +, -
3  &
4  ^
5 (наименьший)  |

Требуется удалить из выражения все лишние пары скобок, не влияющие на порядок операций в нём (операции трактовать абстрактно, без какого-либо математического смысла, опираясь только на формальный порядок операций). Приоритет определяет, в каком порядке выполняются операции в цепочке, а ассоциативность определяет направление вычислений в цепочке операций одного приоритета.
 
Ввод Вывод Замечания
a+(b*c) a+b*c (у ‘*’ приоритет выше, чем у ‘+’, поэтому она и так выполняется первой,- скобки лишние);
((a+b)+(c+d)) a+b+(c+d) (Скобки вокруг всего выражения допустимы, но никогда не влияют на порядок вычисления внутри. Поскольку ассоциативность всех операций слева направо, первые внутренние скобки лишние, а вторые – нет, без них выражение было бы эквивалентно (((a+b)+c)+d));
((a)+b)&c^d  a+b&c^d (скобки вокруг переменной всегда лишние).
(((a)&b^c|((d)))) a&b^c|d  
a a  


Формат входного файла:
Одна строка, содержащая исходное математическое выражение не длиннее 100 символов.
Формат выходного файла:
Одна строка с математическим выражением без лишних скобок.

ID 23370. Опять двойка (В, В')
Темы: Строки    Задача на реализацию   

Пете нравится цифра 2. Он считает число красивым, если в его десятичной записи ровно две цифры 2. Петя хочет получить большой список красивых чисел и повесить его на стенку.
ПомогитеПете и выведите все красивые числа, не превосходищие n.
 
Формат входных данных
В первой и единственной строке записано одно целое число n (1 <= n <= 106).
 
Формат выходных данных
Выведите все целые положительные числа, не превосходящие n, в десятичной записи которых ровно две цифры 2.  Числа следует выводить в порядке возрастания, по одному на строке.
 
Ввод Вывод
179 22
122
1  
 
Замечание
Обратите внимание, что список может быть пустым, в этом случае ничего выводить не нужно.

ID 48933. Палиндромные числа
Темы: Строки    Задача на реализацию   

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Однажды во время прогулки Алина увидела длинное число, которое кто-то написал на асфальте. Алина захотела найти положительное число такой же длины без ведущих нулей, чтобы сумма этих двух чисел была палиндромом.

Число называется палиндромом, если оно читается одинаково справа налево и слева направо. Например, числа \(121, 66, 98989\) являются палиндромами, а \(103, 239, 1241\) — нет.

После некоторых размышлений Алина поняла, что такое число всегда можно найти. Помогите Алине найти подходящее число!

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(2 \leq n \leq 100\,000\)) — длина числа, которое увидела Алина.

Во второй строке вводится одно положительное целое число длины \(n\). Гарантируется, что оно не содержит ведущих нулей.

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

Если таких чисел несколько, вы можете вывести любое из них.

 

В первом примере из условия \(99 + 32 = 131\) — палиндром. Число \(12\) также будет являться ответом, так как \(99 + 12 = 111\).

Во втором примере из условия \(1023 + 8646 = 9669\).

В третьем примере из условия \(385 + 604 = 989\).

ID 30714. Телефонные номера
Темы: Разбор случаев    Задача на реализацию    Строки   

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

Будем считать, что любой телефонный номер состоит из 11 цифр и делится на три части, каждая из которых является числом без ведущих нулей. Первая часть состоит из одной, двух или трех цифр и является кодом страны, в которой этот телефон зарегистрирован. Вторая часть может состоять из трех, четырех или пяти цифр, и может являться или кодом региона, в котором зарегистрирован номер, или кодом мобильного оператора, которому этот номер принадлежит. Третья часть состоит из всех оставшихся цифр номера и является номером конкретного абонента.

При отображении телефонного номера на экране телефона, части этого номера принято отделять друг от друга различными символами так, чтобы номер было проще прочитать и запомнить. Так, перед кодом страны обычно ставится символ «+», код региона или оператора берется в скобки, номер абонента разделяется символами «-» на несколько частей. При этом, то, на сколько частей он разбивается, напрямую зависит от количества цифр в нем:
• если номер абонента состоит из трех цифр, то он представляет собой одну часть, состоящую из трех цифр;
• если номер абонента состоит из четырех цифр, то он разбивается на две части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из пяти цифр, то он разбивается на две части, первая из которых состоит из трех цифр, а вторая — из двух;
• если номер абонента состоит из шести цифр, то он разбивается на три части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из семи цифр, то он разбивается на три части, первая из которых состоит из трех цифр, а все остальные — из двух.

Естественно, что человек, заносящий новый номер в записную книжку своего телефона, не станет задумываться об этих правилах, а просто введет его как последовательность из 11 цифр. Однако, перед отображением номера на экране, программное обеспечение телефона должно выяснить, какая часть этого номера является кодом страны, какая — кодом региона или оператора, а какая — номером абонента, и отформатировать номер по правилам, описанным выше. Чтобы сделать эту задачу разрешимой, в память телефона записывается информация о том, какие в данный момент существуют коды государств и какие в этих государствах существуют коды операторов или регионов. Вам необходимо реализовать программу, которая, имея эту информацию, будет правильно форматировать номера, сохраненные в записной книжке телефона.

Формат входных данных
Первая строка файла содержит одно целое число n (1 ≤ n ≤ 100) — количество государств, информация про телефонные коды которых записана в память телефона. Далее следуют n описаний этих государств, разделенных переводами строк. Первая строка описания каждого государства содержит два целых числа c и k (1 ≤ c ≤ 999, 1 ≤ k ≤ 100) — телефонный код этого государства и количество операторов или регионов, существующих в этом государстве. Следующие k строк описания этого государства содержат целые числа, каждое из которых не меньше 100 и не больше 99999 — коды операторов или регионов, зарегистрированных в этом государстве.
Следующая строка входного файла содержит одно целое число m (1 ≤ m ≤ 10 000) — количество телефонных номеров, которые необходимо отформатировать. Следующие m строк содержат сами номера — строки, состоящие ровно из 11 цифр.
Гарантируется, что ни один данный вам номер невозможно разбить на код государства, код оператора или региона и номер абонента более, чем одним способом.

Формат выходных данных
Выведите номера, данные вам во входном файле, отформатированными по правилам, описанным в условии. Каждый номер необходимо вывести в отдельной строке. Номера необходимо выводить в том же порядке, в котором они были перечислены во входном файле. Вместо номеров, корректного разбиения которых на код государства, код оператора или региона и номер абонента не существует, необходимо вывести слово «Incorrect».
 

Ввод Вывод
2
7 3
981
3517
812
351 3
34712
1234
963
8
79818266456
35196328463
78122472557
01234567890
73517960326
35134712239
35112342013
78120203040
+7(981)826-64-56
+351(963)284-63
+7(812)247-25-57
Incorrect
+7(3517)96-03-26
+351(34712)239
+351(1234)20-13
Incorrect

ID 34772. Римские числа
Темы: Задача на реализацию    Разбор случаев    Строки   

Один древнеримский торговец брал несколько раз ссуду в древнеримском банке. Каждый раз банкир записывал размер выданной ссуды на листе пергамента, используя римские числа. Но ввиду дороговизны пергамента запись производилась плотно и все числа оказались записанными подряд, без разделителей. Когда торговец пришёл возвращать ссуду, оказалось, что невозможно установить разбиение записи на числа.

Например, если на пергаменте записана строка «XIIV», её можно разбить на римскиечисла разными способами, например, XI + IV = 11 + 4 = 15 или XII + V = 12 + 5 = 17, возможны и другие варианты разбиения.

Торговец хочет вернуть как можно меньше денег, поэтому он хочет так разбить строку цифр на римские числа, чтобы сумма всех чисел была как можно меньше.

Программа получает на вход строку, длина которой не превосходит 250 символов. Строка состоит только из заглавных латинских букв I, V, X, L, С, D, M.

Программа должна вывести единственное число – минимально возможную сумму, которую можно получить при разбиении данной строки на последовательность корректных римских чисел. Ответ нужно вывести арабскими цифрами в десятичной системе счисления.

Правила записи римских чисел
Римскими цифрами можно записать целые числа от 1 до 3999. Число представляется в виде суммы тысяч, сотен, десятков и единиц. Далее из следующей таблицы берётся по одному элементу, соответствующему тысячам, сотням, десяткам, единицам ровно в таком порядке.



Если число тысяч, сотен, десятков, единиц равно 0, то из соответствующего столбца ничего не берётся. Например, число 1990 записывается, как 1000 + 900 + 90 = MCMXС.

Ввод Вывод
XIIV 15

 

ID 27294. Palindromic Paths
Темы: Динамическое программирование    Динамическое программирование: два параметра    Комбинаторика    Строки   

<div>Ферма Джона представлена решёткой <strong>N&times;N</strong> полей (1&le;N&le;500). Каждое поле представлено символом латинского алфавита. Например:</div> <div>ABCD</div> <div>BXZX</div> <div>CDXB</div> <div>WCBA</div> <div>Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.</div> <div>&nbsp;</div> <div>Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.</div> <div>&nbsp;</div> <div><strong>ФОРМАТ ВВОДА</strong>:</div> <div>Первая строка ввода содержит N, и последующие N строк содержат N строк решётки, описывающей поля. Каждая строка содержит N символов в интервале A..Z.<br /> &nbsp; <div><strong>ФОРМАТ ВЫВОДА</strong>:</div> <div>Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.</div> &nbsp; <table border="1" cellpadding="1" cellspacing="1" style="width: 500px"> <tbody> <tr> <td>Ввод</td> <td>Вывод</td> </tr> <tr> <td> <div>4</div> <div>ABCD</div> <div>BXZX</div> <div>CDXB</div> <div>WCBA</div> </td> <td>12</td> </tr> </tbody> </table> </div> Примечание: <div>Беси может сделать следующие палиндромы:</div> <div>&nbsp;</div> <div>1 x &quot;ABCDCBA&quot;</div> <div>1 x &quot;ABCWCBA&quot;</div> <div>6 x &quot;ABXZXBA&quot;</div> <div>4 x &quot;ABXDXBA&quot;</div>

ID 33219. Шифровка - 2
Темы: Строки   

Для кодирования сообщения используют следующие действия: сообщение записывают, опуская пробелы, в прямоугольник заданной высоты по столбцам, а затем прочитывают строки в заданном порядке.
 
1 P R I 
2 R A N 
3 O M G 
4 G M 
 
а затем, если выбрать порядок строк 3, 1, 2, 4, получают закодированное сообщение OMGPRIRANGM.
 
Требуется написать программу, которая по заданным высоте прямоугольника и порядке прочтения строк при кодировке декодирует заданное сообщение.
 
Входные данные
Входные данные содержат: в первой строке высоту прямоугольника H (2 ≤ H ≤ 10), во второй – порядок прочтения строк (числа записаны через пробел), в третьей – закодированное сообщение, длина которого составляет от 1 до 200 символов. Закодированное сообщение состоит из заглавных и строчных латинских букв  и цифр.
 
Выходные данные
В выходные данные записывается декодированное сообщение.

Ввод Вывод
4
3 1 2 4
OMGPRIRANGM
PROGRAMMING


 

ID 34888. Шифр Юлия
Темы: Строки   

Юлий Цезарь использовал свой способ шифрования текста. Каждая буква заменялась на следующую по алфавиту через K позиций по кругу. Необходимо по заданной шифровке определить исходный текст.

Входные данные:  в первой строке дана шифровка, состоящая из заглавных латинских букв. Во второй строке число K (\(1 <= K <= 10\)).

Выходные данные: требуется вывести результат расшифровки.
 

Примеры
Входные данные Выходные данные
1 XPSE
1
WORD
2 ZABC
3
WXYZ

ID 38190. Количество слов
Темы: Строки   

На вход программы поступает строка текста, в которой могут встречаться:
— прописные и строчные (т.е. большие и маленькие) латинские буквы;
— пробелы;
— знаки препинания: точка, запятая, восклицательный и вопросительный знак;
— символ –, обозначающий в некоторых случаях тире, а в некоторых — дефис.
Слово — это последовательность подряд идущих латинских букв и знаков дефис, ограниченная с обоих концов. В качестве ограничителей могут выступать начало строки, конец строки, пробел, знак препинания, тире. Тире отличается от дефиса тем, что слева и справа от знака дефис пишутся буквы, а хотя бы с одной стороны от тире идет либо начало строки, либо конец строки, либо пробел, либо какой-либо знак препинания, либо еще одно тире.
Напишите программу, определяющую, сколько слов в данной строке текста.

Входные данные
Вводится строка длиной не более 200 символов.

Выходные данные
Выведите одно число — количество слов, которые содержатся в исходной строке.
 
Примеры

Входные данные Выходные данные
1 Hello , world! 2
2 www.olympiads.ru 3
3 Gyro-compass - this is a ... 4

ID 38203. Негласный палиндром
Темы: Строки   

Возьмем произвольное слово и проделаем с ним следующую операцию: поменяем местами его первую согласную букву с последней согласной буквой, вторую согласную букву с предпоследней согласной буквой и т.д. Если после этой операции мы вновь получим исходное слово, то будем называть такое слово негласным палиндромом. Например, слова sos, rare, rotor, gong, karaoke являются негласными палиндромами.

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

Входные данные
Вводится одно слово.

Выходные данные
Программа должна вывести YES, если введенное слово является негласным палиндромом, и NO в противном случае.

Примеры
Входные данные Выходные данные
1 tennete YES

ID 38218. Считалочка
Темы: Строки   

Дети решили поиграть в догонялки, и, чтобы выбрать водящего, встали в круг и стали считаться. Для этого они использовали считалочку. Показывая пальцем по очереди на каждого стоящего в кругу, считающий произносит одно слово, и тот, на кого придется последнее слово, и будет водить. Требуется по данной считалочке определить, кто же будет водить.

Входные данные
В первой строке вводится считалочка. Она состоит из слов, записанных латинскими буквами. Слова разделены одним пробелом. Знаков препинания нет, строка начинается и заканчивается буквой. В считалочке не менее двух слов, а длина строки не превосходит 100.

Во второй строке в том же формате вводится список имен школьников в том порядке, в котором они стоят по кругу. Считать начинают с первого школьника. Детей не менее двух, а длина строки не превосходит 100.

Выходные данные
Выведите имя школьника, которому предстоит водить.
 

Входные данные Выходные данные
1 To be or not to be
John Mary Ann Kate
Mary
2 Na zolotom kryltse sideli
Vasya Vasya Vasya
Vasya

ID 38220. Хорошие стихи
Темы: Строки   

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

Нет? А вот редактор литературного журнала занимается этим каждый день, получая тонны корреспонденции от молодых авторов, желающих стать известными поэтами. Благо, в последнее время большая часть стихов присылается по электронной почте, поэтому у редактора возникла мысль автоматизировать процесс. Он твердо уверен, что стихи тем лучше, чем точнее в них рифма. Он считает две строки зарифмованными, если у них совпадает несколько последних букв. И чем больше букв совпадает, тем лучше зарифмованы строки. Например, у строк “палка” и “веревка” совпадают только пары последних букв “ка”, а у строк “олимпиада” и “рая и ада” совпадают четыре буквы (пробелы мы пропускаем). Поэтому вторая рифма лучше. Редактор считает, что в четверостишии (четыре строки) первая строка должна рифмоваться с третьей, а вторая – с четвертой. Для каждой из этих двух пар строк он считает количество совпадающих последних символов и из этих двух чисел выбирает наибольшее. Полученное число он называет коэффициентом качества стихотворения – чем он выше, тем больше шансов у стихотворения быть опубликованным. Помогите редактору – напишите программу, которая определяет качество стихотворения. И кто знает, может быть, благодаря вашим усилиям, мир познакомится с гениальными стихами (см. первый пример).

Входные данные
На вход подается 4 непустые строки, каждая из которых состоит из не более чем 100 строчных латинских букв (стихотворение уже подверглось предварительной обработке: из него удалили все пробелы и знаки препинания, а заглавные буквы сделали строчными).

Выходные данные
Выведите одно число – коэффициент качества стихотворения.
 

Входные данные Выходные данные
1 yapomnyuchudnoemgnovenje
peredomnojyavilasty
kakmimoletnoevidenje
kakgenijchistoykrasoty
4
2 eto
vovse
ne
stihi
0
3 etootlichnyestihi
etootlichnyestihi
etootlichnyestihi
etootlichnyestihi
17

ID 27298. Censoring
Темы: Строки    Хеш    Структуры данных   

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров. К сожалению, последний номер содержит неподходящую статью - как приготовить бифштекс. ФД не хочет, чтобы его коровы её читали.
 
ФД взял текст журнала, создал строку S длиной не более чем 10^5 символов. У него есть список слов t_1, t_2, ..., t_N, которые он хочет удалить из S. Поэтому ФД находит ближайшее вхождение слова из списка T (то есь с наименьшим индексом) и удаляет его из S. Затем он продолжает это процесс опять, пока в S не останется слов из T. Заметим, что удаление слова может создавать новое вхождение свлоа из T, которое не существовало ранее.
 
ФД заметил, что слова из списка T обладают таким свойством, что никакое из них не является подстрокой другого слова из T. В частности, это означает, что ранее вхождение слова из T в S всегда определено однозначно. Пожалуйста, помогите ФД определить финальное содержание строки S.
 
INPUT FORMAT: 
Первая строка содержит S. Вторая строка содержит N - количество удаляемых слов. Последующие N строк содержат строки t_1, t_2, ..., t_N. Каждая строка содержит только маленькие латинские буквы (a..z) и суммарная длина всех строк не превысит 10^5.
 
OUTPUT FORMAT: 
Строка S после всех удалений. Гарантируется, что S не станет пустой.
 
Ввод Вывод
begintheescapexecutionatthebreakofdawn
2
escape
execution
beginthatthebreakofdawn


 

ID 48046. Телефонный справочник
Темы: Линейный поиск    Задача на реализацию    Строки   

Саша недавно начала регистровать компанию по разработке чат ботов и уже подала необходимые документы. Но добрые люди рассказали Саше, что в телефонном справочнике компании располагаются в лексикографически возрастающем порядке их названий. Что такое телефонный справочник, Саша не знает, но решила учесть рекомендации и поменять название своей компании, чтобы оно было как можно раньше в телефонном справочнике. Поскольку Саша уже подала документы, она не может полностью поменять название компании, но может сказать, что допустила опечатку, и поменять любые две буквы в названии местами. Помогите Саше выбрать новое название компании или оставить текущее.

Формат входных данных
В единственной строке содержится одно слово, состоящее из строчных латинских букв от "a" до "z" (2 ≤ n ≤ 106

Формат выходных данных
Выведите одно слово - новое название компании. Если название не~изменилось, выведите изначальное название.
 

ID 38264. Телеграммы Матроскина
Темы: Строки   

Когда Дядя Фёдор уехал домой в город, следить за хозяйством остались Матроскин и Шарик. Но поскольку Дядю Фёдора очень волновали дела в Простоквашино, они договорились, что каждую неделю Матроскин будет писать письмо с отчетом о делах. Довольно скоро Матроскин понял, что письма идут слишком долго, поэтому решил отправлять телеграммы. Обычно отчеты очень длинные, поэтому Матроскину пришлось отправлять несколько телеграмм. Чтобы Дяде Фёдору было удобнее разобраться в пришедших телеграммах, Матроскин следует следущим правилам:

В каждой телеграмме должно быть не более 140 символов, включая пробелы и знаки препинания.
Исходный текст должен быть разбит на телеграммы по пробелам, при этом пробел, по которому разбивается телеграмма, уничтожается.
Если телеграмма не является последней, в её конец нужно дописать три точки.
Если телеграмма не является первой, в её начало нужно дописать три точки.
Чтобы сэкономить деньги на отправке телеграмм, Матроскин хочет разбить текст на как можно меньшее количество.

Помогите Матроскину разбить исходный текст на как можно меньшее количество телеграмм по приведенным выше правилам.

Входные данные
На вход подается строка из маленьких латинских букв и пробелов. Она не начинается и не заканчивается пробелами и никакие два пробела в ней не идут подряд. Длина строки не превышает 10000.

Выходные данные
В первой строке выведите число N – количество телеграмм, на которое надо разбить исходную строку. В следующих N строках выведите сами телеграммы. Если текст передать заданным способом невозможно, выведите −1.

 

Примеры
Входные данные Выходные данные
1 deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl bwuoio 2
deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl...
...bwuoio

ID 38293. Подстрока-палиндром
Темы: Строки   

Марина очень любит палиндромы. Палиндром — это строка, которая одинаково читается слева направо и справа налево, например « noon », « rotator » или « radar ».

Марина написала на доске строку s , состоящую из n строчных латинских букв s1 s2 ... sn . Подстрокой строки s называется строка s ls l + 1 ... sr для некоторых 1 ≤ l ≤ r ≤ n . Марина ищет в строке s как можно более длинную подстроку, которая является палиндромом. Например, в строке « rotateradars » такой подстрокой будет « radar ».

Вова хочет изменить написанную Мариной строку, чтобы подстрока-палиндром была как можно длиннее. Он может либо оставить строку нетронутой, либо изменить в ней ровно одну букву на другую. Например, если в строке « rotateradars » изменить шестую букву на « o », получится строка « rotatoradars », в которой максимальная подстрока-палиндром « rotator » имеет длину 7 . Подстроку-палиндром большей длины получить нельзя.

Помогите Вове определить, какую максимальную длину подстроки-палиндрома он сможет получить.

Входные данные
Первая строка входных данных содержит натуральное число n — длину строки, которую написала Марина ( 1 ≤ n ≤ 100 ).

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

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

Примеры
Входные данные Выходные данные
1 12
rotateradars
7

ID 33648. Неправильный палиндром
Темы: Строки   

Палиндромом называется слово, которое одинаково читается как слева направо, так и справа налево, например, в английском языке такими словами являются «radar» и «racecar».
Света изучает английский язык и решила принять участие в дистанционном конкурсе знатоков английского языка. Но, когда она писала ответ на задание «найдите самое длинное слово, которое является палиндромом», ошиблась и нажала на клавиатуре одну лишнюю клавишу.
Определите, какую букву нужно удалить в набранном Светой слове, чтобы это слово стало палиндромом.

Входные данные
Программа получает на вход строку из строчных английских букв, содержащую не менее 2 и не более 100 000 символов.

Выходные данные
Программа должна вывести единственное число – номер буквы в строке, при удалении которой слово становится палиндромом. Если при удалении любой буквы слово не станет палиндромом, программа должна вывести число 0.

Примеры
Входные данные Выходные данные
1 raceczar 6
2 car 0

ID 38954. Скучная лекция
Темы: Строки   

Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далеким и незаметным...

Чтобы окончательно не уснуть, он взял листок и написал на нём свое любимое слово. Чуть ниже он повторил своё любимое слово, без первой буквы. Ещё ниже он снова написал своё любимое слово, но в этот раз без двух первых и последней буквы.

Тут ему пришла в голову мысль — времени до конца лекции все равно ещё очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?

После лекции Лёша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Лёши в листочке. Но к сожалению, сам листочек куда-то запропастился.

Макс хорошо знает любимое слово Лёши, а ещё у него не так много свободного времени, как у его друга, так что помогите ему быстро восстановить, сколько раз Лёше пришлось выписать каждую букву.

Входные данные
На вход подаётся строка, состоящая из строчных латинских букв — любимое слово Лёши.

Длина строки лежит в пределах от 5 до 100 000 символов.

Выходные данные
Для каждой буквы на листочке Лёши, выведите её, а затем через двоеточие и пробел сколько раз она встретилась в выписанных Лёшей словах (см. формат вывода в примерах). Буквы должны следовать в алфавитном порядке. Буквы, не встречающиеся на листочке, выводить не нужно.

Примеры
Входные данные Выходные данные
1 hello e: 8
h: 5
l: 17
o: 5
2 abacaba a: 44
b: 24
c: 16


Примечание
Пояснение к первому примеру. Если любимое Лёшино слово — "hello", то на листочке у Лёши будут выписаны следующие слова:

"hello"
"hell"
"ello"
"hel"
"ell"
"llo"
"he"
"el"
"ll"
"lo"
"h"
"e"
"l"
"l"
"o"
Среди этих слов 8 раз встречается буква "e", 5 раз — буква "h", 17 раз — буква "l" и 5 раз буква "o".

ID 21951. Британские учёные и Василий
Темы: Z-функция. Префикс-функция    Строки   

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

Вдохновившись исследованием британских учёных о восприятии человеком текста, Вася решил, что современная письменность нуждается в серьёзном упрощении. В частности, в лексиконе Васи все слова состоят только из букв a, b и c. Кроме того, память у Васи плохая, поэтому Вася помнит лишь слова, которые содержат не более L букв.

Более того, с тех пор как наш юный друг пролил кофе на свой любимый ноутбук, он не утруждает себя нажатием клавиши пробел (объясняя это тем, что и отсутствие пробелов в тексте совершенно не мешает его пониманию). Однако остальные клавиши клавиатуры работают исправно, что позволяет Васе набирать все известные ему слова без единой орфографической ошибки.

Британские учёные очень заинтересовались исследованиями Васи. Они вступили с молодым учё- ным в активную переписку, однако, получив очередное Васино сообщение были несколько озадачены тем, что же он имел ввиду. Так как разобраться они так и не смогли, а очередное революционное открытие уже было проанонсировано в СМИ, они решили как-то оценить уровень гениальности автора. Для этого они решили понять, а из какого минимального количества слов может состоять словарный запас Василия?

Формат входных данных
В первой строке входных данных содержится целое число L — максимальная длина слова, кото- рое может содержаться в лексиконе Васи (1 <= L <= 10 000). В следующей строке содержится непустое сообщение, полученное учеными. Длина сообщения не превосходит 20 000 символов.

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

Пример
Ввод:
3
ababaabab

Вывод:
2
aba
ab

Замечание
В первом примере из условия одним из возможных способов проинтерпретировать Васино сооб- щение является: ab aba ab ab.

ID 27218. Bovine Genomics
Темы: Строки    Хеш    Множества   

У Фермера Джона NN коров с пятнами и NN коров без пятен. Пройдя курс генетики, ФД убеждён, что пятна у коров вызваны мутацией генов.
За большие деньги ФД зафиксировал геномы своих коров. Каждый геном это строка длиной MM, состоящая из символов A, C, G, T. Когда он выписал все геномы у него получилась такая таблица, N=3 и M=8:
 
Позиция  :                   1 2 3 4 5 6 7 8
 
Пятнистая корова 1:  A A T C C C A T
Пятнистая корова 2:  A C T T G C A A
Пятнистая корова 3:  G G T C G C A A
 
Корова без пятен 1:  A C T C C C A G
Корова без пятен 2:  A C T C G C A T
Корова без пятен 3:  A C T T C C A T

Посмотрев внимательно на эту таблицу, он заметил, что последовательность от позиции 2 до позиции 5 успешна, чтобы объяснять пятнистость. То есть, рассматривая символы в этих позициях (2…5), ФД может предсказать какие из его коров пятнистые, а какие нет. Например, если он видит символы GTCG в этих позициях, он знает, что корова будет пятнистая.
 
Помогите ФД определить длину кратчайшей последовательности позиций, которая может объяснить пятнистость.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N (1≤N≤500) и M (3≤M≤500). Каждая из N следующих строк содержит по M символов. Эти символы описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен. Никакая пятнистая корова на имеет точно такой же геном, как корова без пятен.
 
ФОРМАТ ВЫВОДА:
 
Пожалуйста, выведите длину кратчайшей последовательности позиций, достаточной для объяснения пятнистости. Последовательность позиций объясняет пятнистость, если по ней можно предсказывать абсолютно точно пятнистая или нет любая из коров ФД.
 
Ввод Вывод
3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
4


 

ID 27117. Consonant Fencity
Темы: Конструктив    Строки   

There are two kinds of sounds in spoken languages: vowels and consonants. Vowel is a sound, produced with an open vocal tract; and consonant is pronounced in such a way that the breath is at least partly obstructed. For example, letters a and o are used to express vowel sounds, while letters b and p are the consonants (e.g. bad, pot).

Some letters can be used to express both vowel and consonant sounds: for example, y may be used as a vowel (e.g. silly) or as a consonant (e.g. yellow). The letter w, usually used as a consonant (e.g. wet) could produce a vowel after another vowel (e.g. growth) in English, and in some languages (e.g. Welsh) it could be even the only vowel in a word.
In this task, we consider y and w as vowels, so there are seven vowels in English alphabet: a, e, i, o, u, w and y, all other letters are consonants.

Let’s define the consonant fencity of a string as the number of pairs of consecutive letters in the string which both are consonants and have different cases (lowercase letter followed by uppercase or vice versa). For example, the consonant fencity of a string CoNsoNaNts is 2, the consonant fencity of a string dEsTrUcTiOn is 3 and the consonant fencity of string StRenGtH is 5.

You will be given a string consisting of lowercase English letters. Your task is to change the case of some letters in such a way that all equal letters will be of the same case (that means, no letter can occur in resulting string as both lowercase and uppercase), and the consonant fencity of resulting string is maximal.

Input
The only line of the input contains non-empty original string consisting of no more than 106 lowercase English letters.

Output
Output the only line: the input string changed to have maximum consonant fencity.
 

Input Output
consonants CoNsoNaNts
destruction dEsTrUcTiOn
strength StRenGtH

ID 33533. Клад
Темы: Циклы    Строки   

Путь к кладу задан в виде указаний, какое количество шагов нужно пройти в одном из четырёх направлений: север (N), юг (S), запад (W), восток (E). Весь маршрут записан в виде строки, содержащей последовательность из чисел и следующих за числами букв, указывающих направление перемещения. Например, строка «7N5E2S3E» означает "пройти 7 шагов на север, 5 шагов на восток, 2 шага на юг, 3 шага на восток». В маршруте может быть много команд перемещения, поэтому каждый такой маршрут можно сократить.
Например, ранее приведённый маршрут можно сократить до «5N8E". По данному маршруту до клада сократите его до строки минимальной длины.

Программа получает на вход строку, состоящую из целых неотрицательных чисел, не превосходящих 107 каждое, и одной буквы (N, S, W, E ) следующей за каждым
числом. Других символов (в том числе пробелов), кроме цифр и букв направлений, в строке нет. Длина строки не превосходит 250 символов. Гарантируется, что начальная
и конечная точки маршрута различаются.
Программа должна вывести маршрут, ведущий в ту же точку, записанный в таком же виде, как во входных данных, используя минимальное число символов. Если ответов
несколько, программа должна вывести один (любой) из них.
 

Ввод Вывод Примечание
7N5E2S3E 5N8E Правильным ответом будет также «8E5N»
10N30W20N 30N30W Правильным ответом будет также «30W30N»

ID 38246. Шпионские штучки
Темы: Строки   

Алиса и Боб — очень опытные шпионы. Лучше всего им удается находить пароли для доступа к различным секретным данным. Вот и в этот раз Алиса получила от Боба сообщение, в котором говорилось, что ключом является число и далее шло само это число. Также Боб писал, что число-ключ должно делиться на 9. Когда Алиса попробовала ввести полученный пароль, то оказалось, что он не подходит. Алиса очень доверяет Бобу, и поэтому она решила, что Боб мог ошибиться только в одной цифре пароля. Поскольку у Алисы не так много времени, она решила не выяснять у Боба правильный ответ, а перебрать все числа, которые могли бы быть паролем, т.е. все такие числа, которые могут быть получены из того числа, которое прислал Боб, заменой ровно одной из его цифр и делятся на 9. За помощью Алиса обратилась к вам. Напишите программу, которая предложит Алисе все возможные варианты пароля.

Входные данные
Во входных данных содержится единственное число P (1 ≤ P ≤ 109) — то число, которая Алиса получила в сообщении от Боба. Гарантируется, что оно не начинается с нуля.

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

Примеры
Входные данные Выходные данные
1 256 756
216
252

ID 47741. Артефакты Максимуса
Темы: Строки   

У Магистра Максимуса в руках три артефакта с последовательностями символов. Чтобы раскрыть их тайны, нужно открыть все три артефакта одновременно с помощью одинаковых последовательностей символов. Для этого Максимус может удалять только самый правый символ из каждой последовательности сколько угодно раз. Обратите внимание, что для того, чтобы Максимус мог удалить символ из последовательности, ее длина должна быть не менее двух символов. 
Определите минимальное количество операций, которые необходимо выполнить Максимусу, чтобы привести три последовательности к одинаковому виду. Если такое невозможно, ответ должен быть -1.

Входные данные
Программа получает на вход три строки s1, s2, s3 - последовательности символов, записанные на каждом из артефактов. 
 

Constraints:

  • 1 <= |s1|, |s2|, |s3| <= 100
  • s1s2 и s3 состоят только из строчных английских букв
|s|  означает длину последовательности s

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

ID 38616. Две одинаковые буквы
Темы: Строки    Символы   

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

Входные данные
На вход подается 1 строка.

Выходные данные
Необходимо вывести  букву, которая встречается в строке дважды.
 

Примеры
Входные данные Выходные данные
1 fif f

ID 46982. Судьба Королевства
Темы: Символы    Строки    Условный оператор   

В далеком царстве жил могущественный маг по имени Эльдрик, который был помешан на шахматах. В башне Эльдрика была волшебная шахматная доска, о которой говорили, что она предсказывает будущее королевства. Но был казус. Шахматные фигуры двигались только по белым клеткам, а черные клетки хранили секреты прошлого.

Однажды молодой оруженосец по имени Леон решил узнать все секреты прошлого  и пошел к башне.  Маг Эльдриг дал оруженосцу пергамент, на котором были написаны координаты одной клетки шахматной доски. Эльдриг сказал, что если он сумеет не глядя на доску определить какой цвет у данной клетки шахматной доски, то ему откроются все секреты прошлого!

Леон не был так помешан на шахматах, но все же смог определить цвет клетки правильно! Сможете ли это сделать и вы? 

Шахматная доска выглядит таким образом


Формат входных данных
Программа получает на вход одну строку, в которой записана координата шахматной клетки.
 

Ограничения

  • длина строки == 2
  • 'a' <= первый символ строки <= 'h'
  • '1' <= второй символ строки <= '8'

Формат выходных данных
Выведите слово white, если клетка белого цвета и black - если черного.

ID 23086. Символы перед запятой
Темы: Строки    Символы   

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

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается исходное предложение.

Выходные данные: необходимо вывести все символы предложения, которые предшествуют первой запятой, если запятых нет - вывести все предложение

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1
fore, s t.
fore
2 fore s t. fore s t.

ID 23087. Первая "e"
Темы: Строки    Символы   

Дано предложение, в котором имеется несколько букв 'e' (англ.). Найти порядковый номер первой из них.

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается исходное предложение.

Выходные данные: необходимо вывести номе первой буквы "е" (англ) в предложении

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 foresete 4

ID 23088. Найди "a"
Темы: Символы    Строки   

Дано предложение. Определить, есть ли в нем буква "a" (англ.). В случае положительного ответа вывести порядковый номер первой из них. В случае отрицательного - вывести слово NO.

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается исходное предложение.

Выходные данные: выведите ответ на задачу.

Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 foresete NO
2 forast 4

ID 23089. Перевертыш
Темы: Строки    Символы   

Дано слово. Проверить, является ли оно "перевертышем", (то есть читается одинаково как сначала, так и с конца).

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается слово.

Выходные данные: необходимо вывести слово "YES", если слово является перевертышем, и слово "NO" - в противном случае

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 foresete NO
2 halah YES

ID 23090. Сколько "i"
Темы: Строки    Символы   

Дана строка, разбитая на предложения. Все предложения заканчиваются знаком точка. Определить количество букв 'i' в первом предложении. 

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: программа получает на вход строку.

Выходные данные: необходимо вывести количество букв 'i' в первом предложении.

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 foresete. forest. 0
2 firist. forist 2

ID 23093. Сколько "o"
Темы: Строки    Символы   

Дано предложение, в котором нет символа "-". Определить количество букв "o" (англ.) в первом слове. В начале предложения могут быть пробелы.

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в единственной строке задается исходное предложение.

Выходные данные: необходимо вывести количество букв "о" (англ.) в первом слове.

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1    fore  sete. 1
2 hal ah. 0

ID 23092. Префикс
Темы: Символы    Строки   

Дано два слово. Определить, сколько начальных букв первого слова совпадает с начальными буквами второго слова

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается два слова через пробел
Выходные данные: необходимо вывести количество совпадающих с начала букв

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 fore forest 4
2 forest torest 0

ID 23094. Сколько "n" перед запятой
Темы: Символы    Строки   

Дано предложение. Определить количество букв "n", предшествующих первой запятой предложения. 

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается исходное предложение.

Выходные данные: необходимо вывести количество букв "n", предшествующих первой запятой предложения.

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 fore, sete. 0
2 hanah. 1

ID 23095. Первые одинаковые
Темы: Строки    Символы   

Дано предложение. Определить порядковые номера первой пары одинаковых соседних символов. Если таких символов нет, то вывести на экран слово NO.

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.


Входные данные
В первой строке задается  предложение длиной не более 255 символов (в начале и конце предложения нет пробелов).

Выходные данные 
Необходимо вывести через пробел порядковые номера первой пары одинаковых соседних символов, или слово "NO" - если такой пары соседних символов нет (первый символ в предложении имеет порядковый номер 1).

 

Примеры
Входные данные Выходные данные
1 foresete NO
2 haah 2 3

ID 23091. Одинаковые в начале
Темы: Символы    Строки   

Дана последовательность символов, в начале которой имеется некоторое количество одинаковых символов. Определить это количество.

Решите задачу, не используя встроенные функции работы со строками, за исключением функции, возвращающей длину строки.

Входные данные: в первой строке задается последовательность символов.

Выходные данные: необходимо вывести количество одинаковых симвлов в начале строки.

Пример входных и выходных данных

№ теста Входные данные Выходные данные
1 foresete 0
2 ааав 3

ID 23385. Увеличение чисел - 1
Темы: Строки   

В первой строке входных данных записано число N (от 1 до 100).

В каждой из последующих N строк записано сначала некоторое целое число (из диапазона от 0 до 10000), затем пробел, и затем некоторый текст (не более 20 символов).

Требуется вывести информацию в том же формате, увеличив число в каждой строке (кроме первой, где записано число N) на 1.

 
Примеры
Входные данные Выходные данные
1
2
14 Start
42 Stop
2
15 Start
43 Stop
 

ID 23402. Арифметическое выражение
Темы: Строки   

В первой строке входных данных записано арифметическое выражение в виде:

<число> <операция> <число> =

<Число> - это натуральное число, не превышающее 10000.

<Операция> - один из знаков +, -, *.

В начале строки, в конце строки, а также между числами и знаком операции, числом и символом =, может быть любое число пробелов (а может пробелов и не быть).

Гарантируется, что длина строки не превышает 200 символов.

 Выведите результат вычисления выражения.

 

Примеры
Входные данные Выходные данные
1 154    +3   = 157
 

ID 39561. Коровий алфавит
Темы: Перебор    Строки   

Малоизвестен тот факт, что у коров свой алфавит "cowphabet". Он состоит из тех же 26 букв от 'a' до 'z', но в другом порядке.
Чтобы скоротать время, Беси бормочет cowphabet опять и опять. Фермеру Джону интересно, сколько раз она его пробормотала.

По заданной строке букв, которые ФД расслышал из бормотания Беси, определите минимальное количество раз, которое Беси должна пробормотать cowphabet, чтобы ФД услышал заданную строку. ФД не всегда обращает внимание на бормотание Беси, поэтому он может не расслышать некоторые буквы из бормотания Беси. Данная Вам строка содержит только те буквы, которые он услышал.

Входные данные
Первая строка ввода содержит 26 маленьких латинских букв от 'a' до 'z' в порядке их появления в cowphabet. Следующая строка содержит строку из маленьких латинских букв, которые услышал ФД. Эта строка имеет длину от 1 до 1000.
Выходные данные
Выведите минимальное количество раз, которое Беси пробормотала алфавит.

Примеры
Входные данные Выходные данные Пояснение
1
abcdefghijklmnopqrstuvwxyz
mood
3

В этом примере cowphabet упорядочен как нормальный алфавит.

Бесси пробормотала cowphabet как минимум 3 раза. Ниже показано, как Беси бормотала, и большими буквами - какие буквы услышал ФД.

abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz

ID 23405. Таймер
Темы: Дата и время    Условный оператор    Строки   

Таймер - это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени. Напишите программу, которая определяет, когда должен быть подан звуковой сигнал.
 
Входные данные:
В первой строке записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60. 
Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0. 
А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.
 
Выходные данные:
В ответе выведите в формате ЧЧ:ММ:СС время, когда прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол-во> days. Например, если сигнал прозвучит на следующий день - то +1 days

Примеры
Входные данные Выходные данные
1
01:01:01 
48:0:0
01:01:01+2 days
2
01:01:01
58:119
02:01:00
3
23:59:59
1  
00:00:00+1 days

ID 24659. И.О. Фамилия
Темы: Строки   

Ввести имя, отчество и фамилию. Преобразовать их к формату «инициалы-фамилия».

Входные данные: в первой строке задается предложение. Слова разделены одном пробелом, вначале и в конце текста лишних пробелов нет.

Выходные данные: необходимо вывести модифицированную строку.
 

Примеры
Входные данные Выходные данные
1 Inav Ivanovich Ivanov I. I. Ivanov

ID 24675. Арифметическое выражение-1
Темы: Строки   

Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). На вход подается символьная строка, представляющая собой арифметическое выражение. Все числа целые.
 

Примеры
Входные данные Выходные данные
1 12+3+45 60
2 12-45+3 -30

ID 24676. Арифметическое выражение-3
Темы: Строки   

Напишите программу, которая вычисляет выражение, состоящее из трех чисел, трех знаков арифметических операций (допускаются знаки «+», «–», «*» и «/») и круглых скобок. На вход подается символьная строка, представляющая собой арифметическое выражение. Все числа - целые. Операция «/» выполняется как целочисленное деление. 
 

Примеры
Входные данные Выходные данные
1 2*(3+45)+4 100
2 2*3/(5-2) 2

ID 38155. Финальная стоимость - 1
Темы: Строки   

Представьте, что вас наняли в IT отдел сетевого продуктового магазина. Со следующего месяца планируется ввести скидку в 20% на некоторые товары. От вас требуется написать программу расчета финальной стоимости покупки с учетом всех скидок.

Покупка задается в виде списка товаров, где каждый товар описывается в формате <НазваниеТовара> <цена> x<количество>. Если название товара заканчивается на подстроку «sale», то цена на товар при финальном расчете покупки уменьшается на 20% с округлением до целого числа в меньшую сторону. Так, например, если цена товара была 12 рублей, с учетом скидки она составит 9 рублей. На остальные товары скидка не распространяется.

Суммарная стоимость каждого товара вычисляется по формуле finalPrice⋅x, где finalPrice - финальная цена, возможно, с учетом скидки и округлением, а x - количество товара в списке покупок. 
Ваша задача - вычислить итоговую стоимость покупки.

Входные данные
В первой строке дано число n - число наименований товаров в покупке (1≤n≤1000).
В следующих n строках заданы описания товаров в покупке в формате: <НазваниеТовара> <цена> x<количество>.
Название товара состоит из не более чем 20 строчных латинских букв. Цена - натуральное число, которое строго больше 1, но не больше 1000. Количество - натуральное число не больше 100.

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

Примеры
Входные данные Выходные данные Пояснение
1 5
bananassale 10 x2
breadfixed 5 x5
colafixed 20 x2
gumsale 9 x10
tea 2 x15
181 В тесте из примера итоговые стоимости товаров составят: 8, 5, 20, 7 и 2 соответственно. Итоговая стоимость покупки: 8⋅2+5⋅5+20⋅2+7⋅10+2⋅15=181.

 

ID 38156. Финальная стоимость - 2
Темы: Строки   

Представьте, что вас наняли в IT отдел сетевого продуктового магазина. Со следующего месяца планируется ввести скидку в 20% на некоторые товары. От вас требуется написать программу расчета финальной стоимости покупки с учетом всех скидок.

Покупка задается в виде списка товаров, где каждый товар описывается в формате <НазваниеТовара> <цена> x<количество>. Если название товара не заканчивается на подстроку «fixed», то цена на товар при финальном расчете покупки уменьшается на 20% с округлением до целого числа в меньшую сторону. Так, например, если цена товара была 12 рублей, с учетом скидки она составит 9 рублей. На товары, название которых заканчивается на подстроку «fixed», скидка не распространяется. 

Суммарная стоимость каждого товара вычисляется по формуле finalPrice⋅x, где finalPrice - финальная цена, возможно, с учетом скидки и округлением, а x - количество товара в списке покупок. 
Ваша задача - вычислить итоговую стоимость покупки.

Входные данные
В первой строке дано число n - число наименований товаров в покупке (1≤n≤1000).
В следующих n строках заданы описания товаров в покупке в формате: <НазваниеТовара> <цена> x<количество>.
Название товара состоит из не более чем 20 строчных латинских букв. Цена - натуральное число, которое строго больше 1, но не больше 1000. Количество - натуральное число не больше 100.

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

Примеры
Входные данные Выходные данные Пояснение
1 5
bananassale 10 x2
breadfixed 5 x5
colafixed 20 x2
gumsale 9 x10
tea 2 x15
166 В тесте из примера итоговые стоимости товаров составят: 8, 5, 20, 7 и 1 соответственно.
Итоговая стоимость покупки: 8⋅2+5⋅5+20⋅2+7⋅10+1⋅15=166$.

 

ID 33237. Средний балл по предметам - 2
Темы: Структуры    Строки   

Определите средний балл всех учащихся по каждому предмету.
 
Входные данные
В первой строке задается количество учащихся n (\(0 < n <=100\)). Далее идет n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.
 
Выходные данные
Выведите три действительных числа, разделяя их одним пробелом: средний балл всех учащихся по математике, по физике, по информатике.
 
Примеры
Входные данные Выходные данные
1
2
Markov Valeriy 4 5 2
Kozlov Georgiy 5 1 2
4.5 3 2

ID 38717. Учащиеся без троек
Темы: Строки    Структуры   

Выведите фамилии и имена учащихся, не имеющих троек (а также двоек и колов).

Входные данные
Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.

Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Порядок вывода должен быть таким же, как в исходных данных.
 

Примеры
Входные данные Выходные данные
1 3
Babat Anna 5 4 3
Belova Galina 4 3 5
Moroz Yaroslav 3 5 4
 

ID 38718. Трое лучших
Темы: Строки    Структуры   

Определите трех учащихся с наилучшим средним баллом по трем предметам. Выведите фамилии и имена этих учащихся. Если при этом у нескольких учащихся средний балл совпадает со средним баллом учащегося, "занявшего 3-е место", то необходимо вывести их всех.

Входные данные
Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.

Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Порядок вывода должен быть таким же, как в исходных данных.
 
 

Примеры
Входные данные Выходные данные
1 3
Yakovlev Ivan 5 5 5
Yapryntsev Aleksey 5 5 5
Kozlov Georgiy 5 5 5
Yakovlev Ivan
Yapryntsev Aleksey
Kozlov Georgiy

ID 38720. Отсортировать по среднему баллу
Темы: Строки    Структуры   

Выведите фамилии и имена учащихся в порядке убывания их среднего балла.

Входные данные
Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.

Общее число учащихся не превосходит 100001.
Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Если несколько учащихся имеют одинаковые средние баллы, то их нужно выводить в порядке, заданном во входных данных.
 


Примеры
Входные данные Выходные данные
1 2
Markov Valeriy 1 1 1
Ivanov Ivan 2 2 2
Ivanov Ivan
Markov Valeriy
2 3
Markov Valeriy 5 5 5
Sergey Petrov 1 1 1
Petrov Petr 3 3 3
Markov Valeriy
Petrov Petr
Sergey Petrov

ID 30704. Замена подстроки
Темы: Строки   

Найти в строке указанную подстроку и заменить ее на новую. Строка s, ее подстрока s1 для замены и новая подстрока s2 вводятся.

P.S. Искомые подстроки в исходной строке не пересекаются.
P.P.S. В строках не содержатся пробелы.
P.P.P.S. Искомая подстрока может встречаться неоднократно.
P.P.P.P.S. Все буквы строчные.
P.P.P.P.P.S. Нет символов помимо строчных латинских букв.

На вход подаются 3 строки: s, s1, s2. Длина всех строк не превосходит 100.
 

Примеры
Входные данные Выходные данные
1 abcde
ab
fg
fgcde
2
ababc
ab
c
ccc

 

ID 30705. Редактор скобочной последовательности
Темы: Строки   

Задана строка, состоящая только из:
• прописных и строчных букв английского алфавита;
• символов подчёркивания (они используются в качестве разделителей);
• круглых скобок (как открывающих, так и закрывающих).

Гарантируется, что каждая открывающая скобка имеет парную закрывающую, идущую следом. Аналогично, каждая закрывающая скобка имеет парную открывающую, которая расположена до неё. Для каждой пары соответствующих скобок верно, что между ними нет каких-либо других скобок. Иными словами, каждая скобка в строке входит в пару «открывающая-закрывающая», и такие пары не вкладываются друг в друга.
Например, допустимой строкой является: _Hello_Vasya(and_Petya)__bye_(and_OK)
Словом называется нерасширяемая последовательность подряд идущих букв, то есть последовательность букв, где слева и справа от неё находится скобка или символ подчёркивания, или соответствующий символ отсутствует.
Приведенный пример содержит семь слов: «Hello», «Vasya», «and», «Petya», «bye», «and» и «OK».

Напишите программу, которая найдет:
• длину самого длинного слова вне скобок (выведите 0, если слов вне скобок нет),
• количество слов внутри скобок (выведите 0, если слов внутри скобок нет).
 
Входные данные: в первой строке записано целое число n (\(1 <= n <= 255\)) — длина заданной строки. Во второй строке записана строка, состоящая только из строчных и прописных английских букв, открывающих и закрывающих скобок, а также символов подчёркивания.
 
Выходные данные: выведите два числа:
• длину самого длинного слова вне скобок (выведите 0, если слов вне скобок нет);
• количество слов внутри скобок (выведите 0, если слов внутри скобок нет).
 
Примеры
Входные данные Выходные данные
1 37
_Hello_Vasya(and_Petya)__bye_(and_OK)
5 4
2
37
_a_(_b___c)__de_f(g_)__h__i(j_k_l)m__
2 6
3
27
(LoooonG)__shOrt__(LoooonG)
5 2
4
5
(___)
0 0

Примечание
В первом примере слова «Hello», «Vasya» и «bye» записаны вне скобок, а слова «and», «Petya», «and» и «OK» — внутри. Обратите внимание, что слово «and» встречается дважды, и учитывать в ответе его тоже следует два раза.

ID 48935. Вордл наоборот
Темы: Строки    Задача на реализацию    Перебор   

Камила и Динара играют в <<Wordle>>. Камила загадала слово длины \(n\), состоящее из различных латинских букв. Динара сделала одну попытку угадать и назвала слово длины \(n\), также состоящее из различных латинских букв. Камила раскрасила буквы в догадке Динары в соответствии со следующими правилами:

  • Буква, совпадающая с буквой в загаданном слове, красится в зеленый цвет и обозначается G.

  • Буква, которая присутствует в загаданном слове, но стоит не своей позиции, красится в жёлтый цвет и обозначается Y.

  • Буква, отсутствующая в загаданном слове, красится в белый цвет и обозначается W.

Например, если было загадано слово ALERT, а догадка была ALONE, то буквы будут раскрашены в цвета GGWWY. Первые две буквы в словах совпадают, поэтому они зеленые. Буква E есть в загаданном слове, но находится на другой позиции, поэтому она жёлтая. Остальные буквы белые, так как их нет в загаданном слове.

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

В первой строке вводится одно целое число \(n\) \((1 \le n \le 10)\) — длина загаданного слова.

Во второй строке вводится строка длины \(n\), состоящая из заглавных латинских букв — загаданное слово. Гарантируется, что все буквы в нем различны.

В третьей строке вводится строка длины \(n\), состоящая из букв G, Y, W — цвета, в которые были раскрашены буквы в слове Динары.

Если подходящих слов не существует, выведите No.

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

 

Разберем первый пример из условия.

Буквы H и G не встречаются в загаданном слове, поэтому они белые.

Буквы E и B встречаются, но на других позициях, поэтому они жёлтые

Буквы C и D совпадают с буквами на соответствующих позициях в загаданном слове, поэтому они зелёные.

Есть и другие ответы, любой правильный ответ будет зачтен.

Обратите внимание, что строка HECDBH не является ответом, так как в ней есть совпадающие буквы.

 

ID 39618. Анализ файла
Темы: ЕГЭ    Строки   

Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Текст разбит на строки различной длины. Назовем подпоследовательность оригинальной, если она ограничена слева подстрокой , а справа подстрокой BA (данные подстроки также входят в подпоследовательность) и при этом в этой подпоследовательности нет других букв А и B. Оригинальная подпоследовательность не может начинаться в одной строке, а заканчиваться в другой.
Определите, сколько  всего  оригинальных подпоследовательностей во всем файле, а также длину максимальной из них.

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

Пример
Исходный файл:
AAABCAABCBAA
ZZABZZZBABCBA
QRABUTUUBA

В этом примере всего 4 оригинальных подпоследовательности (AВСВА, ABZZZBA, ABCBA, ABUTUTBA)
Самая длинная подпоследовательность (ABUTUTBA) имеет длину 8.
Ответ: 48


Файл к заданию

ID 38944. Новый вопрос
Темы: Строки   

ID 21533. Строка - 4
Темы: Строки   

Напишите программу, которая выводит строчку.
[:|/||\|:]

ID 21532. Строка - 3
Темы: Строки   

Напишите программу, которая выводит строчку.
\\||//\\||//||\\||//

ID 21530. Строка - 2
Темы: Строки   

Напишите программу, которая выводит строчку.
(:)]-/\-\/

ID 21531. Строка - 5
Темы: Строки   

Напишите программу, которая выводит строчку.
(-["|-|-|"]-)

ID 21529. Рыбка
Темы: Строки   

Напишите программу, которая выводит рыбку в виде рисука ASCII-арт (рисунок в виде строки 1х10 символов).
<@(/\/\)>< 

ID 21537. Стрела
Темы: Строки   

Напишите программу, которая рисует картинку размером 11х7 символов.
(
   \
     )
##-------->
     )
   /
(

ID 21535. Гномик
Темы: Строки   

Напишите программу, которая рисует картинку размером 7х5 символов.
  /_\
{~._.~}
 ( Y )
()~*~()
(/)-(\)

ID 21536. Собачка
Темы: Строки   

Напишите программу, которая рисует картинку размером 13х4 символов.
_ _        ;;
.~.~~;;;;;;;
\_/-\|----\\
 '    ""  ""

ID 21538. Цветочек
Темы: Строки   

Напишите программу, которая рисует картинку размером 7х5 символов.
 0 0
0 " 0
 0 0
    \/\
     \/

ID 46033. Первый уникальный
Темы: Строки    Сортировка подсчетом   

Символ называется уникальным, если он встречается в строке один раз. Первый уникальный символ - это уникальный символ с наименьшим индексом.
Дана строка s. Найдите первый уникальный символ в данной строке. Выведите его индекс. Если в строке нет уникальных символов, выведите -1.

Входные данные
Программа получает на вход последовательность непробельных символов s

Ограничения
'a' <= s[i] <= 'z'
0 <= i <= 255

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

Примеры
Входные данные Выходные данные
1
silvertests
1
2
sstt
-1

ID 46034. Сортировка строки по частоте букв
Темы: Строки    Сортировка подсчетом   

Дана строка s. Отсортируйте символы данной строки в порядке убывания частоты встречаемости. Частота встречаемости символа - это количество раз, которое данный символ встречается в строке.

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

Входные данные
Программа получает на вход

Ограничения
1 <= s.length <= 5 * 10(s.length - длина строки s)
s содержит большие и маленькие английские буквы и цифры.


Выходные данные
Выведите отсортированную строку.
 
 

Примеры
Входные данные Выходные данные
1
tree
eert
2
cccaaa
aaaccc
3
Aabb
bbAa

ID 34870. Криптостойкий пароль. Встроенные методы
Темы: Строки   

Пароль называется криптостойким, если он включает в себя и строчные латинские буквы, и заглавные латинские буквы, и цифры, при этом его длина должна быть не менее 8 символов.
Требуется по данному паролю определить, является ли он криптостойким.

Входные данные
Вводится одна строка, состоящая только из латинских букв и цифр. Количество символов в строке не превышает 100.

Выходные данные
Выведите слово YES, если указанный пароль является криптостойким, и NO – в противном случае.
 
Примеры
Входные данные Выходные данные
1 e NO
2 AAAbbb123 YES

ID 22025. Украшение елки
Темы: Строки   

В преддверии Нового Года Вася купил ёлку и решил её украсить. Для этого он должен достать с верхней полки шкафа самые красивые украшения. К сожалению, ставить стул на стул было плохой идеей… Теперь у него вместо коробки украшений – куча, состоящая из украшений, осколков и вещей из других коробок. Конечно же, её нужно разобрать. Но Вася так хочет смотреть новогодние фильмы! Помогите ему написать программу, которая разберёт кучу мусора за него. 
 
Входные данные
На вход подаётся две строки. Первая – примеры украшений. Вторая – собственно куча. 
 
Выходные данные
Нужно вывести количество украшений каждого вида, а также количество разбитых (обозначены точкой) украшений. 
 
Примеры
Входные данные Выходные данные
1
60oQ 
484QQQQ.Qhu.6.oodnh...ddh76762..300ojha.
6: 3 
0: 2 
o: 3 
Q: 5 
Broken: 9
2
80 
..7.8.7.8.9.8 
8: 3 
0: 0 
Broken: 7 
 

ID 34959. Шифр Цезаря
Темы: Строки   

Гай Юлий Цезарь (13 июля, или из других источников, 12 июля 100 или 102 гг. до н. э. — 15 марта 44 г. до н. э.) — древнеримский государственный и политический деятель, диктатор, полководец, писатель. Своим завоеванием Галлии Цезарь расширил Римскую державу. Деятельность Цезаря коренным образом изменила культурный и политический облик Западной Европы и оставила неизгладимый след в жизни следующих поколений европейцев. Гай Юлий Цезарь, обладая блестящими способностями военного стратега и тактика, одержал победу в сражениях гражданской войны и стал единовластным повелителем Pax Romana.

Цезарь часто брал бумагу и писал письма во время гладиаторских боёв. Его спросили, мол, как вы и на гладиаторов можете смотреть и письма писать. На что Цезарь ответил: «Цезарь может делать три дела одновременно: и писать, и смотреть, и слушать».

Юлий Цезарь, чтобы скрыть информацию от врагов, использовал свой способ шифрования текста. Каждая буква заменялась на следующую по алфавиту через K позиций по кругу.

Используя современные компьютерные технологии, определите по заданной шифровке исходный текст.

Входные данные
В первой строке дана шифровка, состоящая из заглавных латинских букв. Во второй строке число K (\(1 <= K <= 10\)).

Выходные данные 
Требуется вывести результат расшифровки.
 
Примеры
Входные данные Выходные данные
1 XPSE
1
WORD

ID 34963. Сочинения Гай Юлия Цезаря
Темы: Строки   

Избрав путь политика и полководца, Цезарь имел немного времени для творческой работы, однако написал сочинения разных жанров: эпическую поэму "Геркулес", трагедию "Царь Эдип", поэму "Путешествие", "Записки о галльской войне" и "Записки о гражданской войне". Были изданы сборники его сентенций, речей, писем. Кроме того, великий полководец интересовался филологией.

Отвлекшись от написания поэмы, Цезарь записал одну под другой две строчки и задумался. Затем он посмотрел на написанные строчки и понял, что первая строка (S) может содержать в себе несколько раз вторую строку (T). Гай Юлий Цезарь решил подсчитать все вхождения строки T в строку S. Помогите ему, напишите соответствующую программу.


Входные данные
Первые две строки входных данных содержат строки S  и T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.

Выходные данные
Выведите номера символов, начиная с которых строка T входит в строку S, в порядке возрастания (по одному значению в строке).
 
Примеры
Входные данные Выходные данные
1 ababbababa
aba
0
5
7

ID 34964. Задача
Темы: Строки   

Ученики, посещавшие школы в Древнем Риме решали на занятиях различные задачи. Вот одна из задач:

101=1

8181515=4

1111112=0

8888888=14

1010101=3

7000007=?

Пусть первое число x, а соответствующее ему n.
Напишите программу, которая по числу x определяет n.


Входные данные 
Единственное неотрицательное число x, не превышающее 101001.

Выходные данные
Выведите n.


Примеры
Входные данные Выходные данные
1 689 4

ID 34965. Распаковка строчки
Темы: Строки   

Всем известно, что Цезарь пользовался иногда тайнописью, т. е. неким шифром, изобретенным им самим.
Иногда, чтобы сократить время написания, Цезарь использовал упаковку, принцип которой заключается в удалении повторяющихся букв и замены их на числа, определяющих количество повторений.
Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Данная строка может быть представлена как 4AB5C4D.
Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.
 

Входные данные
Входные данные содержат одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

Выходные данные
Выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).
 
Примеры
Входные данные Выходные данные
1 ABC ABC
2 O2A3O2AO OAAOOOAAO
3 A2B3C4D5E6F7G ABBCCCDDDDEEEEEFFFFFFGGGGGGG

ID 38481. Ироха любит строки
Темы: Строки    Алгоритмы сортировки   

У Ирохи есть последовательность из N строк s1, s2, .., sN. Каждая строка длиной L. Ироха хочет объединить все строки, чтобы получить очень длинную строку. Среди всех строк, которые она может получить таким образом, найдите лексикографически наименьшую. 

Будем считать, что строка s = s1s2...sлексикографически меньше строки t = t1t2...tm, если выполняется одно из следующих условий:
- существует индекс i (\(1<=i<=min(n,m)\)), такой что \(s_j =t_j \), для всех индексов j (\(1<=j<=i\)), и \(s_i <t_i \);
-  \(s_i=t_j\) для всех i (\(1<=i<=min(n,m)\)), и \(n<m\).


Входные данные
В первой строке задаются числа N и L. Далее идут строки s1, s2, .., sN, каждая в отдельной строке.

Выходные данные
Выведите лексикографически наименьшую строку, которую может создать Ироха.
 

 

Примеры
Входные данные Выходные данные
1 3 3
dxx
axx
cxx
axxcxxdxx

 

ID 38484. Клавиатура Громозеки
Темы: Строки   

Громозека построил собственную клавиатуру. Эта клавиатура разработана для максимальной простоты, на ней всего 3 клавиши: клавиша 0, клавиша 1 и клавиша backspace.

Тестировать собственную клавиатуру Громозека решил в текстовом редакторе. Этот редактор всегда отображает одну строку (возможно, пустую). При запуске редактора эта строка пуста. При нажатии каждой клавиши на клавиатуре в строке происходят следующие изменения:
- клавиша 0: символ 0 будет вставлен справа от строки;
- клавиша 1: символ 1 будет вставлен справа от строки;
- клавиша backspace: если строка пуста, ничего не происходит. В противном случае удаляется крайняя правая буква строки.

Громозека запустил редактор и несколько раз нажал эти клавиши. Вам дана строке s, которая является записью нажатий клавиш по порядку. В этой строке символ 0 обозначает клавишу 0, символ 1 обозначает клавишу 1, а символ B обозначает клавишу backspace. Определите какая строка теперь отображается в редакторе?

Входные данные
На вход подается строка (\(1 <= len(s) <=10\)). Строка состоит из символов 01 или B.

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

 

Примеры
Входные данные Выходные данные
1
01B0
00
2
0BB1
1

 

ID 38488. Красивая строка
Темы: Строки   

Пусть s - строка, состоящая из строчных букв. Мы будем называть строку s красивой, если каждая строчная буква английского алфавита встречается в ней четное количество раз. По заданной строке s, определите, красива ли она.

Входные данные
На вход подается строка. Длина строки не нулевая и не более 100 символов. Строка состоит только из строчных английских букв (a-z).

Выходные данные
Выведите Yes если s красива, в противном случае, выведите No.
 

 

Примеры
Входные данные Выходные данные
1 abaccaba Yes
2 hthth No

 

ID 38510. Мечта
Темы: Строки   

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

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

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

 

ID 38519. Хайку
Темы: Строки   

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

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

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

 

Примеры
Входные данные Выходные данные
1
happy,newyear,enjoy
happy newyear enjoy

 

ID 38522. Уменьшим-увеличим
Темы: Строки    Циклы   

У вас есть целочисленная переменная x. Первоначально \(x = 0\). Кто-то дал вам строку S длины N, и, используя эту строку, вы выполнили следующую операцию N раз. В i-й операции вы увеличили значение x на 1, если Si = I, и уменьшили значение x на 1, если Si = D. Найдите максимальное значение, которое принимает x во время операций (в том числе до первой операции и после последней операции).

Формат входных данных
В первой строке задается число (\(1<=N<=100\)), во второй - строка S. Длина строки N. Строка содержит только символы и D.

Формат выходных данных
Выведите максимальное значение x, полученное во время операций.

ID 38526. A-Z строка
Темы: Строки   

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

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

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

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

ID 38626. Арифметические печеньки. Очень легкая задача
Темы: Условный оператор    Строки    Символы   

В уме Громозеки всегда есть целое число. Первоначально в уме Громозеки целое число равно 0. Теперь Громозека собирается съесть четыре печеньки, на каждой из которых написан символи либо + либо -. Когда он ест печеньку с символом +, целое число в его уме увеличивается на 1; когда он ест печеньку с символом -, целое число в его уме уменьшается на 1. Печеньки, которые Громозека собирается съесть, даются вам в виде строки S, i-й символ в S - это i-я печенька, которую он ест. Найдите целое число в уме Громозеки после того, как он съест все печеньки.

Входные данные
На вход подается строка из 4-х символов, каждый из которых равен или -.

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

 

Примеры
Входные данные Выходные данные
1
+-++
2
2
-+--
-2
3
----
-4

 

ID 38653. Множество формул
Темы: Простые задачи на перебор    Строки   

Вам дана строка S, состоящая из цифр от 1 до 9 включительно. Вы можете вставить символ + в некоторые позиции (возможно, ни в одну) между двумя цифрами в этой строке. Здесь знак + не должен появляться последовательно после вставки (т.е. не должно быть два и больше знака подряд). Все строки, которые можно получить таким образом, можно оценить как формулы. Оцените все возможные формулы и распечатайте сумму результатов, полученных при вычислении всех возможных формул.

Входные данные
На вход подается непустая строка S, состоящая из цифр от 1 до 9 включительно. Длина строки не более 10 символов.

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

 

Примеры
Входные данные Выходные данные Пояснение
1 125 176 Всего можно получить 4 формулы: 125, 1 + 25, 12 + 5 и 1 + 2 + 5.
Результат после вычисления каждой формулы:
125
1 + 25 = 26
12 + 5 = 17
1 + 2 + 5 = 8
Таким образом, сумма 125 + 26 + 17 + 8 = 176.
2 9999999999 12656242944  

 

ID 44032. Когда же Новый год?
Темы: Строки    Условный оператор   

Томми очень любит Новый год! 31 декабря в этом году приходится на субботу. Томми захотел узнать, сколько дней осталось до 31 декабря. Мы знаем, что сегодня будний день S (по-английски) и 31 декабря уже на этой неделе в субботу. Помогите Томми определить сколько дней оставалось до 31 декабря после сегодня (считая день 31 декабря, но не считая сегодняшний день S)?

Входные данные
На вход подается строка S (S может быть  Monday(понедельник), Tuesday(вторник), Wednesday(среда), Thursday(четверг) или Friday(пятница)).

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

Используйте вложенные условия (конструкцию elif для языка Python и else if для других языков).
 

Примеры
Входные данные Выходные данные
1
Wednesday
3

ID 47717. Головасты
Темы: Целые числа    Строки    Арифметические алгоритмы (Теория чисел)   

Находясь на планете Малого Арктура, Алиса и Громозека отправились в зоопарк. Этот зоопарк известен тем, что в нем можно увидеть головастов - рептилий, которые обитают только на этой планете. Чтобы получить доступ к рептилиям, им необходимо ввести код на входе в зоопарк. Однако, код постоянно меняется и всегда равен минимальному числу, не меньшему, чем записанное на экране перед входом и состоящему только из цифр 3, 6 и 9.
Помогите Алисе и Громозеке определить код доступа к рептилиям.


Входные данные

Ввод содержит одно число n (1 <= n <= 1018).


Выходные данные

Выведите одно число - код доступа к рептилиям.



 
 
Примеры
Входные данные Выходные данные
1
2007
3333
2
97
99

ID 23404. Статистика
Темы: Строки   

Дан текст. Напишите программу, которая посчитает статистику - сколько раз встречается буква A, сколько - B и т.д. При этом большие и маленькие латинские буквы считать одинаковыми. В тексте могут быть сколь угодно длинные строки. Длина текста не превышает 100 Кб.
 
Входные данные
На вход подается текст, состоящий из английских букв (больших и маленьких), знаков препинания, цифр и т.д.
 
Выходные данные
Выведите 26 строк. Каждая строка должна соответствовать латинской букве, буквы должны идти в алфавитном порядке.Каждая строка должна содержать сначала большую латинскую букву, которой она соответствует, пробел, символ - (тире), пробел и число: сколько раз буква встречается во входном файле.
 
Примеры
Входные данные Выходные данные
1 Ab - a
A - 2
B - 1
C - 0
D - 0
<...здесь в выходном файле перечисляются все буквы...>
Z - 0
 

ID 39356. Получите OK
Темы: Строки    Префиксные суммы(минимумы, ...)   

Дана строка S длины N, состоящая из символов S, T, O и K. Дайте ответ на запросов следующего вида.
Запрос i(1 <= i <= Q): для заданных целых чисел li и r(1 <= li< ri <= N),  рассматривается подстрока S, начинающаяся с индекса li и заканчивающася индексом r(оба включительно). Необходимо определить, сколько раз в этой строке втречается OK как подстрока?
 

Пояснение
Подстрока строки - это строка, полученная удалением нуля или более символов из начала и конца строки исходной строки. Например, для строки KOTS подстроками будут строки KO, KOT, OT, OTS, (пустая строка) и другие, но не OK.


Входные данные
В первой строке записаны два числа N (2<=N<=105) и Q (1<=Q<=105). Во второй строке записана строка S длины N. Каждый символ строки это S, T, O или K. Далее идут Q строк по 2 числа в каждой: li и r(1 <= li< ri <= N).

Выходные данные
Выведите Q строк. I-я строка должна содержать ответ на i-й запрос.
 
Примеры
Входные данные Выходные данные
1 8 3
OKOKTOKS
3 7
2 3
1 8
2
0
3

ID 39830. Индексы и срезы
Темы: Символы    Строки   

На вход программы поступает строка s.  Используя обращения к символам по индексу и срезы строк выведите следующие подстроки:

  1. все символы, начиная с индекса 3, до середины строки включительно (при нечетной длине строки, средний символ не брать);
  2. последний символ;
  3. все символа с четными индексами (0, 2, ...);
  4. все символы с нечетнымы индексами (1, 3, ...);
  5. все символы, кроме последнего;
  6. все символы, кроме первого;
  7. все символы в обратном порядке;
  8. все символы в обратном порядке, начиная с 3 с конца, и кроме первых двух;
  9. все символы первой половины в обратном порядке, кроме первого (при нечетной длине строки, средний символ не брать);
  10. скопировать срезом всю строку s в строку s2.
Допишите строчки в программе.
 
Примеры
Входные данные Выходные данные
1 Hallo, World! lo,
!
Hlo ol!
al,Wrd
Hallo, World
allo, World!
!dlroW ,ollaH
lroW ,oll
,olla
Hallo, World!

ID 39832. Строки с гласными и согласными
Темы: Задачи на процедуры и функции    Строки    Символы   

Напишите функцию vowels_count, которая принимает строку и подсчитывает количество английских гласных в ней.
Английские гласные буквы: a, e, i, o, u, y.

Используя данную функцию, определите две строки:
s1 - строку с самым большим числом гласных букв (если таких строк несколько, взять ту, которая встретится раньше).
s2 - строку с самым маленьким числом согласных букв (если таких строк несколько, взять ту, которая встретится раньше).


Входные данные
В первой строке подается натуральное число n (1 < n <= 10) - количество строк. Далее идут n строк. Каждая строка состоит из английских маленьких букв и пробелов.

Выходные данные
Выведите на экран две строки: сначала строку s1, затем, с новой строки - s2. Наименьшую из данных строк выровняйте по длине с наибольшей, добавив слева строки символы '*'.
 

Примеры
Входные данные Выходные данные
1 4
mama papa
doughter son
brother sister
grandmama grandpa
grandmama grandpa
********mama papa
 

ID 38207. Число
Темы: Цикл for    Условный оператор    Строки   

Вводится натуральное число. Требуется разделить запятыми тройки его цифр (считая справа).

Входные данные
Вводится одно натуральное число, не превышающее 10100.

Выходные данные
Вывести то же число, разделяя тройки цифр запятыми.

Примеры

Входные данные Выходные данные
1 1000 1,000
2 12345678 12,345,678
3 999 999

ID 40062. Чего не хватает?
Темы: Строки    Символы   

Вам дается строка S длиной ровно 9 символов. Каждый символ в строке - это любая из цифр от 0 до 9. Все символы в строке различны. Выведите цифру, которой не хватает в строке.

Входные данные
На вход подается строка, состоящая из цифр. 

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

Примеры
Входные данные Выходные данные
1
023456789
1
2
459230781
6

ID 40082. Шаг вправо
Темы: Строки   

Есть 4 квадрата, нарисованных горизонтально в ряд.

Вам дана строка S длиной 4, состоящие из 0 и 1.
Если i-й символ S равен 1, в i-м квадрате слева есть человек;
если i-й символ S равен 0, в i-м квадрате слева нет человека.

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

Выведите результат в виде строки в том же формате, что и S. (Для наглядности см. пример ввода / вывода).

Входные данные
На вход подается строка S длиной 4, состоящие из 0 и 1.

Выходные данные
Выведите строку длиной 4. i-й символ должен быть равен 1, если в i-м квадрате слева после перемещения будет человек, и 0 в противном случае.
 

Примеры
Входные данные Выходные данные
1
1011
0101
2
1111
0111

ID 42698. Копирование n-ok
Темы: Типы данных    Строки   

Пусть  \(N(n,k) = n+\overline{nn}+\overline{nnn} + ... +\underbrace{\overline{n..n}}_{k}\). По заданному значению n и k посчитайте значение N(n, k).

Входные данные
Программа получает на вход две строки. В первой строке записано натуральное число n (1<=n<=9), во второй строке - натуральное число k (1 <= k <= 10).

Выходные данные
Выведите на экран N(n, k) в виде выражения и ответа.
 

Примеры
Входные данные Выходные данные
1
1
3
1+11+111=123

ID 48050. Строка Громозеки
Темы: Строки   

У Громозеки есть его любимая строка S и другая строка T.  Он внимательно посмотрел на свои строки и понял, что первая строка (S) может содержать в себе несколько раз вторую строку (T). Громозека подсчитал все вхождения строки T в строку S и написал себе в порядке возрастания список индексов, начиная с которых строка T входит в строку S. Однако, путешествуя по Галактике, Громозека потерял этот список и пришел в уныние. Помогите Громозеке восстановить потерянный список. 


Формат входных данных
Первые две строки входных данных содержат строки S  и T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.

Формат выходных данных
Выведите в порядке возрастания индексы символов, начиная с которых строка T входит в строку S (в одной строке должно быть записано одно число).

ID 52184. Искусство ASCII
Темы: Строки    Символы   

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

Формат входных данных
Программа получает на вход строку с кодом.  Части кода разделены пробелом.
Каждый фрагмент кода это либо: 
nl означает NewLine (переход на новую строку)
либо 
Количество символа и какой символ
В качестве символов может быть любой печатаемый символ ASCII кода (до символа с кодом 127) либо специальные символы, закодированные следующим образом:
sp - пробел
bS - бэкслеш \
sQ - апостроф '
Количество символа - натуральное число, не превышающее 100.

Формат выходных данных 
Выведите получившуюся картинку.

ID 42452. Когда же суббота
Темы: Строки    Условный оператор   

Однажды, устав от похода в школу, Томми захотел узнать, сколько дней осталось до субботы. Мы знаем, что этот день был будним, и название дня недели было S (по-английски).Сколько дней оставалось до первой субботы после этого дня (считая саму субботу, но не считая день S)?

Входные данные
На вход подается строка S (S может быть  MondayTuesdayWednesdayThursday или Friday).

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

Используйте вложенные условия (конструкцию elif для языка Python и else if для других языков).
 

Примеры
Входные данные Выходные данные
1
Wednesday
3

ID 42693. БОльшие цифры
Темы: Строки    Типы данных   

Пусть S(n) - сумма цифр в десятичной системе счисления целого числа n. Например, S(123)=1+2+3=6.

Для двух трехзначных целых чисел A и B, найдите большее из S(A) и S(B).

Входные данные
На вход подается одна строка, содержащая два целых числа A и B (100 <= A, B <= 999).

Выходные данные
Выведите значение большего из значений S(A) и S(B). Если они равны, выведите S(A).

Обратите внимание, что при решении задачи нельзя пользоваться операциями деления.

Примеры
Входные данные Выходные данные
1 123 234 9

ID 43798. Подстрока
Темы: Бинарный поиск по ответу    Строки    "Два указателя"   

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

Входные данные
В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , где n – количество символов в строке. Во второй строке n символов – данная строка, состоящая только из строчных латинских букв.

Выходные данные
В выходной файл выведите два числа – длину искомой подстроки и номер её первого символа. Если решений несколько, выведите любое.

Примеры
Входные данные Выходные данные
1 3 1
abb
2 1
2 5 2
ababa
4 1

ID 46575. (C++) Обращение к символам строки
Темы: Строки   

На вход программе подаются две строки:
- в первой строке задается слово s;
- во второй - три целых числа a, b, c (каждое число находится в диапазоне [0; len(s)-1])

Выведите на экран новое слово, образованное символами с индексами a, bc (в указанном порядке)
 

Примеры
Входные данные Выходные данные
1 информатика
2 3 4
фор

ID 48025. Самая длинная подстрока
Темы: Поиск подстроки в строке    Строки    ЕГЭ   

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

Формат входных данных
Программа получает на вход строку (10 <= s <= 106). Строка состоит из символов английского алфавита, записанных в верхнем регистре (от A до Z).

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

ID 48030. Гласная подстрока
Темы: Строки    Поиск подстроки в строке   

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

Формат входных данных
Программа получает на вход строку (10 <= s <= 106). Строка состоит из символов английского алфавита, записанных в верхнем регистре (от A до Z). Гласные буквы английского алфавита: AEIOUY.

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

ID 55086. Найди и замени
Темы: Строки   

В текстовом редакторе Microsoft Word имеется достаточно мощный механизм поиска и замены, который доступен после установки флажка Подстановочные знаки (Use wildcards). При этом некоторые символы в строке поиска получают особый смысл.

Так, знаком вопроса в шаблоне поиска можно задать ровно один любой символ. Кроме того, в шаблоне поиска на месте одного из символов в квадратных скобках можно перечислить сразу несколько символов, никак их при этом не разделяя (поиск будет считаться успешным, если на этом месте стоит один из символов, указанных в [ ]). В квадратных скобках можно вместо любого символа указывать и диапазоны символов. Мы будем использовать только три следующих диапазона: 0–9, a–z и A–Z (других диапазонов не будет). В этом случае будет искаться один любой символ из указанного диапазона (диапазонов). Если же первый символ в квадратных скобках – “!”, то, наоборот, искаться будет любой символ, из не перечисленных после восклицательного знака в квадратных скобках (например, [!.a-z,] означает один любой символ кроме точки, запятой, и строчных латинских букв). Если же искать надо один из специальных символов !, ?, [, ], (, ), –, \ то, как в квадратных скобках, так и без скобок перед таким символом ставится \.

Еще одно замечательное свойство строки поиска – выражения. Выражением считается часть строки поиска, взятая в круглые скобки. Пар скобок может быть до 9, но вложенность не допускается. В строке замены выражения представляются в виде \n, где n – порядковый номер выражения в шаблоне поиска (от 1 до 9). Например, по шаблону поиска (k)(?)t и шаблону замены t\2\1 произойдут например, следующие замены:
kot -> tok
kit -> tik

Таким образом, в строке замены существует только один специальный символ – \ , после которого обязательно должна идти цифра. Причем, например, цифра 5 может идти только если в строке поиска было не менее пяти выражений в скобках. При этом символы !, ?, [, ], (, ), – в строке замены указываются без предшествующего символа , а символ \ используется только перед цифрой и обозначает номер выражения. В качестве символа, который должен попасть в конечный текст, символ \ в строке замены не может быть использован.

Поиск начинается с первого символа текста. Находится первый фрагмент, который соответствует шаблону поиска, и производится его замена в соответствии с шаблоном замены. После этого поиск продолжается с символа, следующего за замененным фрагментом. Если снова находится фрагмент, соответствующий шаблону поиска, то он снова заменяется, и так далее до тех пор, пока поиск не достигнет конца текста.

Требуется по данному образцу поиска и образцу замены, произвести все замены в заданном тексте.

Входные данные
В первой строке входных данных расположен текст, в котором требуется произвести все необходимые замены. Длина текста не превышает 100 символов. Во второй строке записан шаблон для поиска. Шаблон является корректным: каждой открывающей скобке соответствует закрывающая, восклицательный знак как спецсимвол употребляется только сразу за символом [ и т.д. В третьей строке расположен шаблон для замены. Выражения в шаблоне для замены также корректны. Длины шаблонов не превышают 100 символов. Коды всех символов, встречающихся как в тексте, так и в шаблонах находятся в диапазоне от 32 до 126. Символы перевода строки в сами шаблоны и в текст не входят.

Выходные данные
Выведите одну строку – текст после всех произведенных замен.

ID 50096. 50096
Темы: Строки   

Требуется разделить заданный текст на английском языке на 3 группы слов по их первой букве так, чтобы количество слов в группах отличалось на минимальную величину. Группы могут формироваться только на основе алфавитного порядка латинских букв и задаются в виде диапазонов, например a-i, j-o, p-z.

Входные данные
В первой строке записано число N, не превышающее 106 - количество строк в тексте. Далее записано N строк текста, в каждой из которых не более 1000 символов. Текст состоит из латинских букв разного регистра, пробелов и знаков препинания ".", ",", "!", "?", ":".
После каждого знака препинания обязательно ставится пробел либо строка заканчивается.
Переносы слов с одной строки на другую отсутствуют.

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

Примеры
Входные данные Выходные данные Примечание
1 3
Above all zoo the blue bird
soars. Hippopotamus hopes high
honey
hotel?
2 Слова можно разбить на 3
группы:
1-я - 4 слова на буквы a и b;
2-я - 5 слов на букву h;
3-я - 3 слова на буквы s-z.
2 2
A a a a, o.
O o o! A?
5 Слова можно разбить на 2
группы:
1-я - все слова на букву a;
2-я - все слова на букву o;
3-я - пустая.

ID 50410. Древний английский
Темы: Строки    Символы   

Онуфрий изучает древний английский язык. Поскольку он делает это в рамках домашнего задания на завтра, он не успевает детально изучить его грамматику, поэтому он решил для простоты применить следующие правила для перевода современных английских слов в свой вариант древнего английского.

  • Все буквы <<s>>, после которых не идет <<h>> и которые не являются первыми в слове, заменяются на комбинацию <<th>>.

  • Если первая буква в слове <<e>>, то она заменяется на <<ae>>.

  • Комбинация <<oo>> заменяется на <<ou>>, причем если в слове идет подряд более двух букв <<o>>, то из них заменяются только первые две.

Помогите Онуфрию перевести несколько слов на свою версию древнего английского языка.

Формат входных данных
Первая строка ввода содержит \(n\) — количество слов, которые требуется перевести (\(1 \le n \le 100\)). Далее следует \(n\) строк, каждая из которых состоит только из букв латинского алфавита. Все буквы каждого слова строчные, кроме, возможно первой, которая может быть заглавной. Длина каждого слова не превышает 30.

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

ID 55400. Контрольная по ударениям
Темы: Строки    Бинарный поиск в массиве   

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

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

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

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤20000).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

ID 56051. Контрольная по ударениям
Темы: Строки    Бинарный поиск в массиве   

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

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

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

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤100).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 30000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

ID 50973. Новое --- это хорошо забытое старое
Темы: Строки    Задача на реализацию   

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

Получив желаемое издание, он стал его изучать, открывая в произвольных местах. На одной из открытых страниц было всего две статьи, название первой из них можно было легко прочитать, так как оно было записано английскими буквами, а буквы в названии второй из них оказались практически затертыми. Легко определить было только что остались следы от \(k\) букв. Очевидно также, что второе название стоит в алфавитном порядке позже, чем первое. Это означает, что либо первая не совпадающая в написании двух слов буква в первом слове стоит в алфавите раньше, чем соответствующая буква второго слова, либо начало второго слова полностью совпадает с первым словом, но при этом второе слово длиннее первого (содержит еще какие то буквы).

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

Помогите Андрею найти первое следующее в алфавитном порядке слово, состоящее из тех же букв, что и заданное слово, и состоящее ровно из \(k\) букв. Гарантируется, что такое слово существует.

Формат входных данных
В первой строке задано целое число \(n\) (\(1 \leq n \leq 100\,000\)) — количество букв в первом слове.

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

В третьей строке задано целое число \(k\) (\(1 \leq k \leq 100\,000\)) — количество букв в искомом слове.

Формат выходных данных
Выведите искомое слово, состоящее из \(k\) букв, входящих в первое слово.


Примечание

В первом тестовом примере требуемое слово должно состоять из букв a, b и c. Следующим после abc в алфавитном порядке будет слово abca, но оно состоит из 4 букв, а не из 3. Следующим после abc в алфавитном порядке состоящим из букв a, b и c и имеющим длину 3 будет слово aca.

В данной задаче \(50\) тестов, помимо тестов из условия. 

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

Решения, работающие при \(1 \leq n, k \leq 3\) будут набирать не менее \(10\) баллов.

Решения, работающие при \(1 \leq n, k \leq 10\) будут набирать не менее \(30\) баллов.

Решения, работающие при \(1 \leq n, k \leq 5\,000\) будут набирать не менее \(60\) баллов.

ID 53964. Изображение таблицы
Темы: Строки    Задачи на моделирование   

При разработке программ для просмотра веб-страниц одной из наиболее сложных задач является корректное отображение таблиц. Компания <<Kozilla>>, в которой вы работаете, планирует разработать новую версию браузера <<Waterrat>> для работы в терминальном режиме, и просит вас написать фрагмент ядра отображения веб-страниц, ответственный за формирование структуры таблиц.

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

Таблица состоит из строк, каждая строка состоит из одной или нескольких ячеек, \(j\)-я ячейка \(i\)-й строки имеет ширину \(a_{i,j}\).

По заданным параметрам таблицы постройте символическое изображение ее структуры.

Формат входных данных
Первая строка содержит \(n\) — количество строк в таблице (\(1 \le n \le 100\)). Следующие \(n\) строк входного файла содержат описание строк таблицы.

Описание каждой строки включает число \(m_i\) — количество ячеек этой строки, и \(m_i\) целых чисел \(a_{i,1}, a_{i,2}, \dots, a_{i,m_i}\) — ширину каждой из ячеек строки (\(1 \le m_i \le 10\), \(1 \le a_{i,j} \le 20\)).

Формат выходных данных
Выведите символическое изображение структуры таблицы.

Изображение \(i\)-й строки таблицы должно начинаться изображением горизонтальной линии, составленным из символов <<+>> (плюс) и <<->> (минус). Затем должна следовать строка, содержащая пробелы и символы <<|>> (вертикальная черта). Первым символом строки должна быть вертикальная черта, затем \(a_{i,1}\) пробелов, затем вертикальная черта, затем \(a_{i,2}\) пробелов, и так далее, всего \(m_i\) блоков пробелов. После последнего блока должна следовать вертикальная черта. После последней строки таблицы также должно следовать изображение горизонтальной линии.

В изображении горизонтальной линии используйте символ <<+>>, если сверху или снизу от этой позиции находится вертикальная черта, и <<->> в противном случае. Горизонтальная линия должна иметь минимальную возможную длину, чтобы над каждым символом вертикальной черты следующей строки и под каждым символом вертикальной черты предыдущей строки были символы <<+>>.

ID 53979. Календарь
Темы: Дата и время    Строки   

Неудовлетворенный стандартным календарем своей операционной системы, Витя решил написать программу, которая будет выводить красиво отформатированный календарь. Он разработал формальные требования к календарю, но понял, что сам не способен написать соответствующую программу. Помогите ему.

Календарь состоит из блоков, каждый из которых соответствует одному месяцу. Блоки расположены в виде таблицы из \(k\) столбцов и \(12/k\) строк (\(k\) выбирается делителем числа 12). Месяцы выводятся в следующем порядке: первая строка содержит блоки, соответствующие месяцам с первого по \(k\)-ый, следующая — с \((k + 1)\)-го по \(2k\)-ый, и т. д.

Ширина всех блоков в столбце должна быть одинакова, высота всех блоков равна семи (числу дней в неделе). Между блоками различных строк таблицы выводится пустая строка, в каждой строке между соседними блоками из разных столбцов выводится три пробела.

Блок, соответствующий месяцу, устроен следующим образом. Каждой (в том числе неполной) неделе данного месяца в блоке соответствует столбец, имеющий ширину равную двум. Между двумя соседними столбцами в каждой строке выводится один пробел. Если несколько блоков располагаются в одном столбце в календаре, то для выравнивания ширины в те блоки, которые содержат меньше недель, в конец добавляется необходимое число пустых столбцов-недель. При этом разные столбцы календаря могут иметь разную ширину.

Все числа месяца заносятся в блок, соответствующий этому месяцу. Число заносится в ту строку блока, которая соответствует дню недели, на который приходится число в этом месяце. Число заносится в столбец блока, соответствующий неделе, в которой находится данное число. Однозначные числа дополняются слева одним пробелом. Таким образом, числа в столбце оказываются выравнены по правому краю.

image

Формат входных данных
Входной файл содержит описание года, календарь для которого следует вывести — три числа: \(d\) — день недели, на который приходится первое января (\(1 \le d \le 7\)), \(l\) — является ли год високосным (\(l = 1\) означает, что год является високосными, \(l = 0\) — что не является) и \(k\) — количество столбцов в календаре (\(k\) — одно из чисел \(1, 2, 3, 4, 6, 12\)).

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

Формат выходных данных
Выведите календарь, отформатированный как описано в условии задачи. Проверяющая программа в этой задаче игнорирует пробелы в конце строк. В остальном календарь должен быть отформатирован в точности в соответствии с условием.

Для наглядности в примере вместо пробелов выведены точки. Ваша программа должна выводить пробелы.

ID 53728. Лучшие учащиеся
Темы: Строки    Структуры   

Определите учащихся с наилучшей успеваемостью, то есть с максимальным средним баллом по трем предметам. Выведите всех учащихся, имеющих максимальный средний балл.


Входные данные

Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.


Выходные данные

Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Порядок вывода должен быть таким же, как в исходных данных.

ID 53874. Вполоборота
Темы: Строки   

Словом считается непустая последовательность больших и маленьких латинских букв. Вам необходимо развернуть все слова во входном файле задом наперед.

Входные данные
Во входном файле записано все что угодно. Его размер не превышает 1 Мб.

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

ID 53900. Слишком вложенные скобки
Темы: Строки   

Дана правильная последовательность из круглых скобок. Требуется удалить из неё все скобки, находящиеся на глубине вложенности N и более. Например, в последовательности (()((()(())())))(((()))) выделены скобки, вложенные на 3 и более уровней.

Входные данные
Первая строка входного файла содержит число N (1 <= N <= 5000). Вторая строка содержит правильную скобочную последовательность длиной от 2 до 10000 символов.

Выходные данные
Выходной файл должен содержать укороченную скобочную последовательность.

ID 55369. Шифровка
Темы: Строки   

Шпион Коля зашифровал и послал в центр радиограмму. Он использовал такой способ шифровки: сначала выписал все символы своего сообщения (включая знаки препинания и т.п.), стоявшие на четных местах, в том же порядке, а затем – все символы, стоящие на нечетных местах. Напишите программу, которая расшифровывает сообщение.

Входные данные
Вводится одна непустая строка длиной не более 250 символов – зашифрованное сообщение. Строка может состоять из любых символов, кроме пробельных.

Выходные данные
Выведите одну строку – расшифрованное сообщение.

ID 55384. ЕГЭ
Темы: Строки   

В ЕГЭ по математике было решено не давать задач, в которых используются числа, большие 5, например, 6, 10 и т.п. (они теперь считаются трудными и не обязательными для изучения). Вводится уравнение. Требуется определить, можно ли его давать в ЕГЭ (в уравнении могут присутствовать любые символы-нецифры, а также натуральные числа).

Входные данные
Вводится одна строка без пробелов, состоящая из не более чем 100 символов.

В строке могут встречаться натуральные числа, а также нецифровые символы.

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

ID 55699. Многочлен
Темы: Строки    Условный оператор   

Васе задали несколько однотипных задач по математике: «найти значение многочлена». Он хочет написать программу, которая по заданному многочлену и значению x находила бы ответ. Напишите такую программу!

Входные данные
В первой строке входного файла записан многочлен в виде суммы одночленов. Между одночленами находится знак + или –. Перед первым одночленом может быть знак –. Одночлен записывается как

[<Коэффициент>*]x[^<Степень>]

или

<Коэффициент>

где <Коэффициент> — натуральное число, не превосходящее 100, x — символ переменной (всегда маленькая латинская буква x), <Степень> — натуральное число, не превосходящее 4. Параметры, взятые в квадратные скобки, могут быть опущены. Во второй строке записано одно целое число — значение x.

Выходные данные
В выходной файл нужно записать одно число — значение данного многочлена при данном значении x.

Ограничения

Все числа в исходном файле по модулю не превосходят 100. Количество одночленов не более 10 (могут быть одночлены одинаковой степени).

Hallowen