Информатика

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

Пете подарили 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

На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.

Перед отправкой ящики упаковывают и сортируют. Упаковка и сортировка ящиков неэффективна и происходит следующим образом:

• Ящик под номером i поступает на склад.
• Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
• Поступающий ящик помещается наверх найденной или сформированной стопки.
• Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

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

 

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

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

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

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

Требуется вывести одно число — сколько ящиков останутся на складе, после выполнения отправки.

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

Ввод	Вывод
5 2 1 1 1 2 1 1 1 2 1 1 1	1
5 1 2 1 1 1 2 1 1 1 2 1 1	5

                   ЭПИЗОД X: ФИРИОН НАНОСИТ ОТВЕТНЫЙ УДАР
Берляндия наконец-то окрепла после крупного поражения в войне против Стерляндии, и император Берляндии Фирион готовит атаку на противника. 
Стерляндия представляет собой определенное количество городов, соединенных двусторонними дорогами. От любого города Стерляндии можно добраться до любого другого. Никакая дорога не соединяет город с самим собой. 
Планируется следующее:
Выбирается город, на который будет производиться атака. Город уничтожают, а дороги, исходящие из него, баррикадируются. При этом Стерляндия должна потерять свою целостность. Далее одна из образованных областей подвергается атаке. При этом эта область должна составлять не менее 1/8 и не более 1/4  от оставшейся площади страны ( площадь измеряется в количестве городов в данной области).  Если при разрушении города Стерляндия сохраняет целостность, или подходящих областей не образуется, то данный город не подходит для атаки.
Фирион хочет знать сколько городов удовлетворяют выше описанным условиям, а также номера этих городов в порядке возрастания.
Входные данные
В первой строке даны два числа: n – кол-во городов в Стерляндии ( 2 <= n <= 10^3), m – количество дорог в Стерляндии ( 1 <= m <= 10^4).
Далее идут m строк, в которых задается описание дорог, а именно: в каждой строке заданы два числа: X и Y. Это означает, что город X и город Y соединены дорогой.
Выходные данные
В первой строке выведите число s  – кол-во городов, подходящих для атаки. Во второй строке выведите s чисел  - номера таких городов в порядке возрастания.
Пример

5 5 1 2 1 3 2 3 3 4 4 5

1 4

                                           ГОЛБЕЗ В БЕРЛЯНДИИ
Турист Голбез очень любит путешествовать. На этот раз он решил посетить Берляндию.
 Берляндия представляет собой определенное количество городов, соединенных двусторонними дорогами. От любого города Берляндии можно добраться до любого другого. Никакая дорога не соединяет город с самим собой.  
Будем называть дорогу дорогой федерального значения, если существует любая пара городов v и u ( v != u), такая, что любой путь от v до u лежит через эту дорогу. Будем называть город городом федерального значения, если все дороги, исходящие  из этого города являются дорогами федерального значения.
 Голбез решил посетить все города федерального значения Берляндии. Помогите ему определить какие именно города ему необходимо посетить.
Входные данные
В первой строке даны два числа: n – кол-во городов в Берляндии ( 2 <= n <= 10^5), m – количество дорог в Берляндии ( 1 <= m <= 10^6).
Далее идут m строк, в которых задается описание дорог, а именно: в каждой строке заданы два числа: X и Y. Это означает, что город X и город Y соединены дорогой.
Выходные данные
В первой строке выведите число s  – кол-во городов федерального значения. Во второй строке выведите s чисел  - номера городов федерального значения в порядке возрастания.
Пример

5 5 1 2 1 3 2 3 3 4 4 5

2 4 5

Вам дан массив целочисленных чисел размера n.Необходимо реализовать структуру данных,которая могла бы исполнять следующие операции:
1)Прибавлять всем числам на отрезке [l;r] величину d.
2)Получить сумму чисел на отрезке [l;r].
3)Получить минимум из чисел на отрезке [l;r].
INPUT
На ввод приходит число n – размер массива.В следующей строке,через пробел, даны n чисел - a_i.
Далее задается число m - количество запросов.В следующих m строках запросы трех видов:
1)add l r d - прибавление на отрезке [l;r] числа d.
3)rsq l r - запрос суммы на отрезке [l;r].
3)rmq l r - запрос минимума на отрезке [l;r].
OUTPUT
Ответы для запросов второго и третьего типов через пробел.
P.S. 0 < n, m < 100001 a_i < 1000000001.
P.S.S. Гарантируется,что ответ вмещается в 64-битный тип данных.
INPUT
5
1 2 3 4 5
3
rsq 1 5
add 2 3 1
rmq 2 4
OUTPUT
15 3


(с) Никита Максимов, 2017г.

В первой строке вводится натуральное чило 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