Информатика

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

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

Всего цепочка, которую собирается менять Локи, состоит из \(n\) кубиков. Среди них есть похожие, на чём и собирается сыграть Локи. Он берёт какой-то отрезок кубиков в этой цепочке, вырывает его, разворачивает и вставляет обратно. При этом, он выбирает отрезок таким образом, чтобы внешне цепочка не изменилась. Затем он повторяет то же самое с другим отрезком, который содержал в себе первый, но не совпадал с ним. Очевидно, после этих двух операций цепочка уже не будет совпадать с исходной, и артефакт будет испорчен.

Чтобы оценить вероятность быть уличённым в порче Тессеракта, Локи решил выяснить, сколькими способами он мог выбрать первый отрезок.

Рассмотрим, к примеру, цепочку \(aabaa\), в которой одинаковыми буквами обозначены похожие кубики. Тогда настоящий Тессеракт содержит цепочку \(a_1a_2ba_3a_4\). Локи может, например, проделать следующую последовательность действий: \(a_1a_2ba_3a_4 \to a_2a_1ba_3a_4 \to a_4a_3ba_1a_2\). Внешне ничего не изменилось, однако цепочка уже другая.

Формат входных данных
В первой и единственной строке задана цепочка, состоящая из маленьких латинских букв, длиной не более \(100{\,}000\).

Формат выходных данных
Единственное число — количество различных первых действий Локи.

 

 

Примеры

№	Входные данные	Выходные данные
1	3 3 3 3	3

 

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

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

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

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

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

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

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

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

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

Ввод	Вывод
abacaba	1 abacaba
abcabc	2 aab ccb
abc	3 a b c
cabacbac	2 bcb acaca

На уроке информатики учитель рассказал Васе про новый вид строк — минимально-символьные строки. Строка называется минимально-символьной, если символ, который встречается в ней минимальное количество раз, единственен. Например, строка "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 цифру.

Филипп устроился работать в службу регистрации автомобильных номеров. По своей неопытности в первый же день работы Филипп разлил на стопку номеров кофе. У некоторых номеров оказался залит первый блок цифр (цифры на позициях 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 в противном случае

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

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

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

Формат входного файла
В первой строке находятся два натуральных числа n, k (1 ≤ n ≤ 10⁵ , 1 ≤ k ≤ n) — количество наборов карандашей, имеющихся в магазине, и количество наборов, необходимое Колобку. В каждой из следующих n строк находится ci (1 ≤ ci ≤ 2·10⁵ ) — количество карандашей в наборе. Далее, в этой же строке, следуют ci натуральных чисел aij (1 ≤ a_ij ≤ 10⁹ ) — длины карандашей в i-м наборе. Гарантируется, что сумма всех c_i не превосходит 2 · 10⁵ .

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

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

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

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

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

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

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

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

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

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

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

• Суммарная прибыль от выполнения этих задач была равна X или более рублей.
• Суммарное время, затраченное на выполнение задач, включённых в план, было минимально.

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

 

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

В первой строке входного файла input.txt находятся натуральные числа X (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) — необходимая минимальная прибыль и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 ≤ t_i, p_i ≤ 100 000) — время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

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

Ввод	Вывод
10 3 6 20 2 7 3 4	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

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

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

• Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
• Суммарная прибыль от выполнения этих задач была максимальна.

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

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

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

В первой строке  находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа ti и pi (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

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

 

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

Мальчик Гриша прочитал в одном научном журнале, что не так давно астрономы открыли новую планету, на которой как и на Земле существует жизнь. Ученые уже установили связь с ее жителями и успели выяснить, что эта планета обращается вокруг своей оси за другое время, поэтому сутки здесь длятся не 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	0
4 2 3 1 1 1 0 0 0 0 0 0	14
50 50 24 0 0 3 0 0 18 15 0 7	11295