Типы данных

128 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Минимальная OR сумма#44571

Громозека записал на листочек n чисел ai. Затем он выполняет над массивом следующую операцию

  • выбирает два различных целых числа i, j (1 <= i < j <= n) и заменяет ai на x и aj на y. Чтобы не нарушать массив, Громозека следить чтобы выполнялось условия ai|aj=x|y, где | обозначает побитовое ИЛИ. Заметьте, что x и y это целые неотрицательные числа.

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


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

Первая строка  входных данных содержит целое число n (2 <= n <= 100) -  количество чисел, которые записал Громоезка на листочке. Вторая строка входных данных содержит n целых чисел a1,a2,…,an (0<=ai<=230).


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

Выведите минимальную возможную сумму массива.



Примеры
№ Входные данные Выходные данные
1 
3
1 3 2
 
3
2 
5
1 2 4 8 16
 
31
3 
2
6 6
 
6
4 
3
3 5 6
 
7
 
Битовые операции
✓ 39✗ 37800средняяВойти и решать
Волшебник ORZ#44389

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

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

  • Он выбирает целое число i, такое что 1<= i <= n. Затем он шепчет заклинание и после этого одновременно число  ai превращается в число равное (ai or z), а число z превращается в число, равное (ai and z). 


Здесь or и and обозначают операции побитового ИЛИ и побитового И соответственно.

Найдите максимально возможное значение максимального элемента в массиве a после некоторого (возможно, нулевого) количества превращений.


Входные данные
Первая строка набора входных данных содержит два целых числа: n и z (1 <= n <= 2000, 0 <= z < 230). Вторая строка набора входных данных содержит n целых чисел: a1, a2,...,an (0 <= ai < 230). Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 104.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 2 3
3 4		 7

Одной из оптимальных последовательностей действий является следующая:

  • Выполнить операцию для i = 1. Теперь a1 становится равным (3 or 3) = 3, а z становится равным (3 and 3) = 3.
  • Выполнить операцию для i = 2. Теперь a2 становится равным (4 or 3) = 7,, а z становится равным (3 and 3) = 0.
  • Выполнить операцию для i = 1. Теперь a1 становится равным (3 or 0) = 3, а z становится равным (3 and 0) = 0.

После этих операций последовательность a становится равной [3,7], и максимальное значение в ней равно 7. Можно доказать, что максимальное значение в a не может превосходить 7 ни при какой последовательности операций, так что ответ равен 7.
2 5 5
0 2 4 6 8		 13  
Битовые операции
✓ 19✗ 36800средняяВойти и решать
Подстрока#43798
В этой задаче Вам требуется найти максимальную по длине подстроку данной строки, такую что каждый символ встречается в ней не более k раз.

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

Выходные данные
В выходной файл выведите два числа – длину искомой подстроки и номер её первого символа. Если решений несколько, выведите любое.
Примеры
№ Входные данные Выходные данные
1 3 1
abb		 2 1
2 5 2
ababa		 4 1
"Два указателя"Бинарный поиск по ответуСтроки
✓ 23✗ 59900средняяВойти и решать
Середина отрезка#42262
Громозека и Алиса играют в следующую игру. Изначально, они ставят на числовую прямую три точки в целые координаты. Затем, один из них стирает любую крайнюю точку и ставит ее посередине между двумя оставшимися в координату с целым числом. Если между оставшимися точками четное количество целых чисел, то можно поставить точку в любую из них.

Например, если изначально стояли точки в координатах 3, 6, 8, то первым ходом можно стереть точку с координатой 3 и поставить ее в координату 7. Или стереть точку с координатой 8 и поставить ее в координату 4 или 5.

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

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

Входные данные
Программа получает на вход три целых числа A, B и C (1<=A < B < C <= 1000). Каждое число записано с новый строки.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные
1 3
6
8		 4
Целые числаЦиклы
✓ 16✗ 371 000средняяВойти и решать
Меню для школьника#42255
Питание школьника, при грамотной организации, должно обеспечивать содержание белков, жиров и углеводов в соотношении 10%:30%:60% (допускается погрешность +/- 1%). Детский лагерь составляет меню, состоящее из N различных продуктов. Для каждого продукта известна энергетическая ценность в белках (P), жирах (F) и углеводах (C), а также количество каждого вида продукта в меню (K).

Определите, является ли составленное меню сбалансированным или нет.


Входные данные
Программа получает на вход несколько строк. В первой строке записано число натуральное число N (N <= 100) количество различных продуктов. В каждой из следующих N строк записаны по 4 числа: Pi, Fi, Ci и Ki. Все числа вещественные, не превосходят 103.

Выходные данные
Выведите YES, если меню сбалансированное, и NO в противном случае. 
 
 
Примеры
№ Входные данные Выходные данные
1 3
0 1 1 2
1 2 7 1
3 7 13 1		 YES
Вещественные числаЦиклы
✓ 51✗ 262800средняяВойти и решать
Коровий алфавит#39561
Малоизвестен тот факт, что у коров свой алфавит "cowphabet". Он состоит из тех же 26 букв от 'a' до 'z', но в другом порядке.
Чтобы скоротать время, Беси бормочет cowphabet опять и опять. Фермеру Джону интересно, сколько раз она его пробормотала.

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

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

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

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

abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz
ПереборСтроки
✓ 9✗ 7800средняяВойти и решать
Мир XOR#39385
Пусть \(F(A, B) = A \oplus (A+1) \oplus (A+2) \oplus ... \oplus B\), где \(\oplus\) - операция исключающее ИЛИ (XOR).
По известным числам A и B посчитайте F(A, B).

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

Выходные данные
Выведите F(A, B). 
 
Примеры
№ Входные данные Выходные данные
1 2 4 5
2 123 456 435
3 123456789012 123456789012 123456789012
Битовые операции
✓ 8✗ 941 100средняяВойти и решать
Строковый сдвиг#39378
В непустой строке сдвиг влево перемещает первый символ в конец строки, а сдвиг вправо перемещает последний символ в начало строки. Например, сдвиг влево на строке abcde приводит к bcdea, а два сдвига вправо на abcde приводят к deabc.

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

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

Выходные данные
Выведите в первой строке лексикографически наименьшу строку, во второй - лексикографически наибольшую строку.
 
Примеры
№ Входные данные Выходные данные
1 aaba aaab
baaa
2 z z
z
3 abracadabra aabracadabr
racadabraab
Строки
✓ 22✗ 47900средняяВойти и решать
3 коровы#38835
Склиссы — "сумчатые парнокопытные" в виде коровы с перепончатыми крыльями с планеты Шешинеру. Несмотря на способность летать, склисс, как и любая земная корова, достаточно ленива и тугодумна (почитайте побольше про склиссов ). 
Профессор Игорь Селезнев взял на борт трех склиссов для изучения: Бесси (Bessie), Элси (Elsie) и Милдред (Mildred), каждая из которых изначально дает 7 галлонов молока в день. Поскольку известно, что надой склисса со временем может измениться, профессор Селезнев проводит периодические измерения в течение следующих 100 дней и записывает их в журнал. Записи в его журнале выглядят так:

35 Bessie -2
14 Mildred +3

Первая запись указывает на то, что на 35-й день надой Бесси был на 2 галлона ниже, чем при последнем измерении. Следующая запись указывает, что на 14-й день надой молока у Милдред увеличился на 3 галлона по сравнению с тем, когда он был измерен в последний раз.
Профессор Селезнев занят во многих исследованиях, поэтому он может сделать не более одного измерения в день. К сожалению, он не всегда успевает сразу записать все в журнал и, поэтому его измерения могут идти не в хронологическом порядке.

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

Входные данные
Первая строка ввода содержит N, количество измерений, которые сделал профессор. Каждая из последуюших N строк описывает одно измерение, в формате, описанном выше: день (целое число от 1 до 100), имя склисса, и изменение производительности (ненулевое целое число). Количество молока, которое даёт любой склисс, всегда будет в интервале 0..1000.

Выходные данные
Выведите е количество дней, в течение которых профессору Игорю Селезневу нужно было бы менять фотографию.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 
4
7 Mildred +3
4 Elsie -1
9 Mildred -1
1 Bessie +2
 
3
 Иначально все склиссы дают по 7. В день 1 производительность Бесси вырастет до 9, делая её единственной победительницей и вынуждающей профессора сменить фотографию. В день 4 производительность Элси уменьшится до 6, но это не изменит того факта, что лидером останется Бэсси. В день 7 Милдред выйдет в лидеры, в день 8 Милдред сравняется с Бесси, что опять приведёт к смене карточек.
Словари
✓ 70✗ 151800средняяВойти и решать
Свойства объектов - 2#38788
В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 109.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит. Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество удаленных свойств у объекта r
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Входные данные
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 105). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= ki <= 100, 1 <= pi,j <= 109).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 105. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 105).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 109);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

Выходные данные
Для всех запросов на нахождение количества оставшихся свойств у объекта, в отдельных строках, в порядке их поступления для каждого запроса выведите это количество.
 
Примеры
№ Входные данные Выходные данные
1 2
3 1 2 4
3 2 3 5
12
- 1
? 1
? 2
- 2
? 1
? 2
- 5
? 1
? 2
- 6
? 1
? 2		 1
0
2
1
2
2
2
2


Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта 1 удаленное свойство, а у второго все еще 0.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта теперь 2 удаленных свойства, а у второго 1.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов становится 2 удаленных свойства.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество удаленных свойств у объектов.
 
Словари
✓ 2✗ 21 000средняяВойти и решать
Свойства объектов - 1#38787
В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 109.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит.
Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество оставшихся свойств у объекта с номером r.
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Входные данные
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 105). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= ki <= 100, 1 <= pi,j <= 109).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 105. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 105).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 109);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

Выходные данные
Для всех запросов на нахождение количества оставшихся свойств у объекта, в отдельных строках, в порядке их поступления для каждого запроса выведите это количество.
 
Примеры
№ Входные данные Выходные данные
1 2
3 1 2 4
3 2 3 5
12
- 1
? 1
? 2
- 2
? 1
? 2
- 5
? 1
? 2
- 6
? 1
? 2		 2
3
1
2
1
1
1
1

Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта остается 2 свойства, а у второго все еще 3.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта остается 1 свойство, а у второго - 2.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов остается 1 свойство.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество свойств у объектов.
 
Словари
✓ 18✗ 42800средняяВойти и решать
Генеалогическое древо - 2. Потомки#38786

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


Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

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

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента, необходимо вывести число его потомков.
 

Пример
№ Входные данные Выходные данные
1 
9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
 
Alexander_I 0
Alexei 1
Anna 4
Elizabeth 0
Nicholaus_I 0
Paul_I 2
Peter_I 8
Peter_II 0
Peter_III 3
Деревьяпоиск в глубину и подобноеСловари
✓ 38✗ 65900средняяВойти и решать
Генеалогическое древо - 1. Высота#38785

Генеалогическое древо — это графическая схема, описывающая родственные связи в пределах одной семьи. Начало такого дерева — это один предок (родоначальник) или супруги и далее цепочка строится вниз. Сопоставим с каждым элементов дерева целое неотрицательное число, называемое высотой.  У самого верхнего предка высота 0, у каждого следующего потомка высота на 1 больше, чем у его родителя. 

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


Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

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

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

Пример
№ Входные данные Выходные данные
1 
9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
 
Alexander_I 4
Alexei 1
Anna 1
Elizabeth 1
Nicholaus_I 4
Paul_I 3
Peter_I 0
Peter_II 2
Peter_III 2
Линейные алгоритмыСловари
✓ 68✗ 86800средняяВойти и решать
Сортировка точек#38689
Выведите все исходные точки в порядке возрастания их расстояний от начала координат.

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 103.

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

 Примеры
№ Входные данные Выходные данные
1 2
1 2
2 3		 1 2
2 3
Использование сортировкиСтруктурыЭлементарная геометрия
✓ 5✗ 121 000средняяВойти и решать
Множество формул#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  

 

Простые задачи на переборСтроки
✓ 8✗ 7800средняяВойти и решать
Сумма цифр числа#38646
Для целых чисел b ( b >= 2 ) и n ( n >= 1 ) пусть функция f(b, n) определяется следующим образом:
\(f (b, n) = n, когда\ n < b \\ f (b, n) = f (b, floor (n / b)) + (n \ mod \ b), когда \ n >= b\)

Здесь
floor(n / b) обозначает наибольшее целое число, не превышающее n / b;
n mod b обозначает остаток от n, деленный на b.

Менее формально f(b, n) равно сумме цифр n, записанных в базе b. Например, справедливо следующее:
\(f (10,87654) = 8 + 7 + 6 + 5 + 4 = 30\\ f (100,87654) = 8 + 76 + 54 = 138\)

Вам даны целые числа n и s. Определите, существует ли целое число b (b >= 2) такое, что f(b, n) = s. Если ответ положительный, найдите наименьшее из таких b.


Входные данные
В первой строке вводится целое число n (1 <= n <= 1011). Во второй строке - целое число s (1 <= s <= 1011).

Выходные данные
Выведите ответ на задачу. Если ответа нет, то выведите -1.
 

 

Примеры
№ Входные данные Выходные данные
1 87654
30		 10
2 87654
138		 100
3 87654
45678		 -1
4 31415926535
1		 31415926535
5 1
31415926535		 -1

 

Целые числаЦиклы
✓ 6✗ 471 100средняяВойти и решать
Любимое число Громозеки#38621
Сегодня проходит памятный конкурс STCoder Contest 100. В этом случае Алиса хотела бы передать Громозеке целое число. Поскольку название конкурса - STCoder Contest 100, Громозека был бы счастлив, если бы ему дали положительное целое число, которое можно разделить на 100 ровно D раз. Найдите N-е наименьшее целое число, которое сделает Громозеку счастливым.

Входные данные
Во входной строке содержится два целых числа: D (равно 0, 1 или 2) и N (1<=N<=100).

Выходные данные
Выведите N-е наименьшее целое число, которое можно разделить на 100 ровно D раз.
 

 

Примеры
№ Входные данные Выходные данные
1 0 5 5
2 1 11 1100
3 2 85 850000

 

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

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

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

 

Строки
✓ 13✗ 901 000средняяВойти и решать
Вопль#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
Строки
✓ 5✗ 191 000средняяВойти и решать
Чунга-Чанга#38378
Наше счастье постоянно — жуй кокосы, ешь бананы, Жуй кокосы, ешь бананы, Чунга-чанга!
м/ф «Катерок»
После открытия острова «Чунга-Чанга» туда постепенно начала пробираться цивилизация и даже стала развиваться рыночная экономика. Появилась и новая валюта — чижик. Теперь для того, чтобы счастливо жевать кокосы, их нужно сначала купить под пальмой.

Саша и Маша проходили мимо пальмы, под которой продаются кокосы по цене z чижиков за штуку. У Саши есть x чижиков, а у Маши y. Каждая из девочек собирается купить максимальное число кокосов, на которое у неё хватит денег. Обсудив планы о покупке кокосов, девочки заметили, что если одна из них передаст какое-то количество чижиков другой, то суммарное количество кокосов, которое они купят, может от этого увеличиться (а может и уменьшиться). Кокосы не продаются по частям, то есть каждая из девочек может купить только целое неотрицательное число кокосов. Чижики тоже не могут быть разделены на части, то есть одна из девочек может передать другой только целое неотрицательное число чижиков.

Например, предположим, что у Саши было 5 чижиков, у Маши 4, а один кокос стоит 3 чижика. Тогда, если девочки не будут обмениваться чижиками, то они купят 1+1=2 кокоса. Если же Маша передаст Саше один чижик, то у Саши их будет 6, а у Маши 3, и девочки купят 2+1=3 кокоса.

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

Входные данные
Первая строка содержит три целых числа x, y и z (0 ≤ x, y ≤ 1018 , 1 ≤ z ≤ 1018) — количество чижиков у Саши, количество чижиков у Маши и цена одного кокоса.

Выходные данные
Выведите два целых числа — максимальное суммарное количество кокосов, которое можно купить, и минимальное количество чижиков, которым для этого придётся поделиться одной из девочек.
Примечание
Первый пример разобран в условии задачи. Во втором примере оптимально не обмениваться чижиками, в таком случае будет куплено 3+4=7 кокосов.
Примеры
№ Входные данные Выходные данные
1 5 4 3 3 1
2 6 8 2 7 0
Условный операторЦелые числа
✓ 11✗ 55900средняяВойти и решать
Поделиться
Класснуть