Язык программирования

На уроке информатики учитель рассказал Васе про новый вид строк — минимально-символьные строки. Строка называется минимально-символьной, если символ, который встречается в ней минимальное количество раз, единственен. Например, строка "abacaba" — минимально-символьная, потому что единственный символ, который встречается минимальное количество раз в ней — 'c'. В то же время строка "cababac" — не минимально-символьная, потому что символы 'b' и 'c' встречаются в ней минимальное количество раз, то есть не являются единственными.

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

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

В единственной строке входного файла input.txt записана строка s, характеризующая набор символов. Ее длина не превосходит 100.

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

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

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

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

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

 

Ввод	Вывод
abacaba	1 abacaba
abcabc	2 abb acc
abc	3 a b c
cababac	2 bcb acaa

В Берляндии каждый автомобиль имеет регистрационный номер. Автомобильные номера в Берляндии имеют следующий вид: LDDLDDL, где символ L обозначает строчную латинскую букву, а D цифру.

Филипп устроился работать в службу регистрации автомобильных номеров. По своей неопытности в первый же день работы Филипп разлил на стопку номеров кофе. У некоторых номеров оказался залит второй блок цифр (цифры на позициях 5 и 6).

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

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

В первой строке записано натуральное число n, не превосходящее 1000 — количество номеров в стопке.

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

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

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

Первая строка должна содержать NO, если в стопке были одинаковые номера. Иначе первая строка должна содержать YES, а далее n строк должны содержать номера из стопки — по одному в каждой строке, причем i+1-я строка должна содержать i-й номер. Номера должны удовлетворять принятому в Берляндии формату в том же порядке, что и во входном файле.

Если ответов несколько — разрешается вывести любой.

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

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

 

Ввод	Вывод
4 a10a10c a30b??c a30b??c x70r??r	YES a10a10c a30b10c a30b22c x70r37r
3 a00b10c a00b10c c02y03x	NO
2 a99a??b a99a??b	YES a99a11b a99a22b

В Берляндии каждый автомобиль имеет регистрационный номер. Автомобильные номера в Берляндии имеют следующий вид: LDDLDDL, где символ L обозначает строчную латинскую букву, а D цифру.

Филипп устроился работать в службу регистрации автомобильных номеров. По своей неопытности в первый же день работы Филипп разлил на стопку номеров кофе. У некоторых номеров оказался залит первый блок цифр (цифры на позициях 2 и 3).

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

Формат входных данных

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

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

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

Формат выходных данных

Первая строка выходного данных должна содержать NO, если в стопке были одинаковые номера. Иначе первая строка должна содержать YES, а далее n строк должны содержать номера из стопки — по одному в каждой строке, причем i+1-я строка должна содержать i-й номер. Номера должны удовлетворять принятому в Берляндии формату в том же порядке, что и во входных данных.

Если ответов несколько — разрешается вывести любой.

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

Ввод	Вывод
4 a10a10c a??b30c a??b30c x??r70r	YES a10a10c a10b30c a22b30c x37r70r
3 a10b00c a10b00c c03y02x	NO
2 a??a99b a??a99b	YES a11a99b a22a99b

 

Составьте программу, которая печатает 1, если указанное высказывание является истинным, и 0 в противном случае

Составьте программу, которая печатает 1, если указанное высказывание является истинным, и 0 в противном случае

Составьте программу, которая печатает 1, если указанное высказывание является истинным, и 0 в противном случае

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

Лиса считает, что смех — это последовательность чередующихся букв «a» и «h». Так например, «ahahaha», «hah» и «a» являются смехом, а «abacaba» и «hh» — нет.

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

Лиса просит вас помочь ей с этой задачей.

Формат входного файла
В первой строке входного файла находится одно натуральное число n (1 ≤ n ≤ 105 ) — длина строки с разговором колобка. Во второй строке находится строка из строчных латинских букв длины n — запись разговора колобка.

Формат выходного файла
В выходной файл выведите одно число — наибольшую длину смеха в разговоре Колобка
 

Ввод	Вывод
5 ahaha	5
24 ahahrunawayahahsofasthah	4
10 ahahaahaha	5

Вы занимаетесь разработкой системы по продаже билетов на поезда. Несмотря на то, что поезда ходят по множеству различных маршрутов, вы будете работать только с одним из них. Маршрут рассматриваемого поезда состоит из n остановок: маршрут начинается в первой из них, а заканчивается в n-й, соответственно. Всего в поезде имеется m мест для пассажиров.

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

• f, где f  число свободных мест мест между L-й и R-й станциями, если хотя бы одно такое место есть. В этом случае пассажир покупает один билет с L-й по R-ю станцию.
• 0 если подходящих свободных мест нет. В этом случае пассажир билет не покупает.

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

В первой  находятся натуральные числа n (2 ≤ n ≤ 100), m (1 ≤ m ≤ 100) и k (1 ≤ k ≤ 100) — число станций в маршруте поезда, максимальное число пассажиров в поезде и число обращений обращений пассажиров к системе покупки билетов.

Следующие k строк содержат по два натуральных числа L_i и R_i (1 ≤ L_i < R_i ≤ n)  — начальная и конечная станции в i-м обращении к системе.

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

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

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

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

Вы занимаетесь разработкой системы по продаже билетов на поезда. Несмотря на то, что поезда ходят по множеству различных маршрутов, вы будете работать только с одним из них. Маршрут рассматриваемого поезда состоит из n остановок: маршрут начинается в первой из них, а заканчивается в n-й, соответственно. Всего в поезде имеется m мест для пассажиров.

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

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

 

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

В первой строке находятся натуральные числа n (2 ≤ n ≤ 100), m (1 ≤ m ≤ 100) и k (1 ≤ k ≤ 100) — число станций в маршруте поезда, максимальное число пассажиров в поезде и число обращений обращений пассажиров к системе покупки билетов.

Следующие k строк содержат по два натуральных числа L_i и R_i (1 ≤ L_i < R_i ≤ n)  — начальная и конечная станции в i-м обращении к системе.

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

Для каждого обращения к системе в своей строке выведите её ответ: YES или NO.

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

Ввод	Вывод
5 2 4 1 4 1 3 2 5 3 5	YES YES NO YES

 

Мальчик Филя прочитал в одном научном журнале, что не так давно астрономы открыли новую планету, на которой как и на Земле существует жизнь. Ученые уже установили связь с ее жителями и успели выяснить, что эта планета обращается вокруг своей оси за другое время, поэтому сутки здесь длятся не 24 часа. На ней, так же как и на Земле, время измеряется часами, минутами и секундами. Но количество минут в часе, и секунд в минуте не совпадает с привычными земными.

А именно: в одном часе A минут, в одной минуте B секунд. Также, в одних сутках на этой планете X часов, Y минут Z секунд. То есть когда часы должны показать момент времени X:Y:Z, они показывают 0:0:0, и с этого момента начинается отсчет новых суток

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

Филя увлекается нумерологией, поэтому его интересует вопрос: сколько хороших моментов времени на часах этой планеты будет показано с момента времени H1:M1:S1 до момента времени H2:M2:S2 включительно. Филя называет момент времени хорошим, если в нем не содержится цифры c, то есть ни один из дисплеев не содержит (с учетом вышеописанных правил) цифру c.

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

В первой строке находятся два натуральных числа A, B (1 ≤ A, B ≤ 50) — количество минут в часе и секунд в минуте.
В следующей строке находятся три целых числа X, Y, Z (0 ≤ X ≤ 50, 0 ≤ Y < A, 0 ≤ Z < B) — количество часов, минут и секунд в сутках. Гарантируется, что X, Y, Z одновременно не равны нулю.
В следующей строке находятся три целых числа H1, M1, S1— стартовое время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
В следующей строке находятся три целых числа H2, M2, S2— конечное время время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
Обратите внимание, что моменты времени могут находиться в разных сутках. Также обратите внимание, что моменты времени могут совпадать. В этом случае в интервале находится единственный момент времени.
В следующей строке находится цифра c (0 ≤ c < 10).

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

Требуется вывести одно число — количество хороших моментов времени с H1:M1:S1 до H2:M2:S2 включительно.

 

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

Ввод	Вывод
3 2 5 0 0 0 0 0 1 0 0 3	7
4 2 3 1 1 1 0 0 0 0 0 0	6
50 50 24 0 0 3 0 0 18 15 0 7	26956

 

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

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

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

В первой строке находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирек.
В каждой из следующих n строк находятся два натуральных числа a_i, b_i (1 ≤ a_i ≤ 1000, 1 ≤ b_i ≤ 2) — масса гири и номер чаши весов, на которой она находится.

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

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

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

Ввод	Вывод
5 4 2 1 1 8 1 5 2 2 1	0
6 20 2 3 2 2 1 5 1 1 1 3 2	6
4 3 2 10 2 8 2 9 2	4

В школьную столовую пришли n учеников разных классов и выпили суммарно k стаканов компота. Кассирша тетя Таня хорошо знает всех учеников, поэтому про i-го пришедшего школьника она знает число a_i — максимальное количество стаканов компота, которое мог выпить этот школьник. Также она знает, i-й школьник выпьет явно не меньше a_i-x стаканов компота. Теперь ей стало интересно: а какое максимальное количество стаканов компота гарантированно выпил один из школьников? То есть она хочет найти такое максимальное число m, что при любом корректном распределении количества выпитых стаканов компота между школьниками, школьник, выпивший максимальное количество стаканов компота, выпил их не менее чем m штук. Помогите ей с этой задачей.

Формат входного файла

В первой строке находятся три натуральных числа n, k, x (1 ≤ n ≤ 100; 1 ≤ k ≤ 2 · 10⁴; 1 ≤ x ≤ 100) — количество школьников, пришедших в столовую, количество стаканов компота, выпитого ими, и максимальное количество стаканов, на которое каждый школьник мог выпить менее своего максимального количества, соответственно.
В следующей строке находятся n целых чисел a_i (x+1 ≤ a_i ≤ 200), разделенных пробелами, — максимальное количество стаканов компота, которое выпил i-й школьник.
Гарантируется, что входные данные корректны.

Формат выходного файла

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

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

 

Ввод	Вывод	Комментарий
3 4 1 2 2 3	2	Так как всего было выпито 4 стакана компота, а школьники выпили хотя бы 2-1=1, 2-1=1 и 3-1=2 стакана соответственно, первый школьник выпил ровно 1 стакан, второй — ровно 1 стакан, третий — ровно 2 стакана. Следовательно, ответ равен 2.
3 6 1 2 2 3	2	Каждый из школьников мог выпить по 2 стакана компота. Значит, ответ 3 гарантировать нельзя. Следовательно, ответ равен 2.
3 7 1 2 2 3	3	Так как всего выпито 7 стаканов компота, хотя бы один школьник выпил 3 стакана. Ответ 4, очевидно, недостижим. Следовательно, ответ равен 3.
3 12 2 3 4 6	5	Первый школьник выпил хотя бы 1 стакан и не более 3, второй — хотя бы 2 и не более 4, третий — хотя бы 4 и не более 6. Невозможно выпить 12 стаканов компота, если третий школьник выпьет ≤ 4 стакана, следовательно, ответ равен 5.

В первой строке вводится натуральное чило n 
Во второй строке вводится число B
Вывести на экран
-  слово YES, если сумма его цифр больше числа В, а само число четное
-  в противном случае вывести слово NO

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

№ теста	Входные данные	Выходные данные
1	45545  15	NO
2	554 5	YES

Дано натуральное число N (N<=10⁹). Определить порядковый номер его минимальной цифры, считая от конца числа (если таких цифр несколько, то вывести номер первой из них)

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

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

.

Дано натуральное число N (N<=10⁹). Определить порядковый номер его минимальной цифры, считая от начала числа (если таких цифр несколько, то вывести номер первой из них)

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

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

Дано натуральное число N (N<=10⁹). Определить порядковый номер его максимальной цифры, считая от начала числа (если таких цифр несколько, то вывести номер первой из них)

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

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

Дано натуральное число N (N<=10⁹). Определить порядковый номер его максимальной цифры, считая от конца числа (если таких цифр несколько, то вывести номер первой из них)

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

№ теста	Входные данные	Выходные данные
1	45545	1
2	100	3

Дано натуральное число N (N<=10⁹). Найти сумму его максимальной и минимальной цифр

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

№ теста	Входные данные	Выходные данные
1	45545	9
2	111	2