#113347

Источники: [ Командные олимпиады, ВКОШП, 2015, Задача J ]

На перемене перед уроком математики Рома решил поупражняться в определении простоты числа. Напомним, что простым называется натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Сначала он написал на доске первое простое число, после чего справа приписал к нему второе, затем третье и так далее. Всего Рома выписал на доску первые \(n\) простых чисел. В результате действий Ромы на доске появилось одно длинное число, которое начинается так: «23571113171923... ».

Когда в кабинет вошла Елена Евгеньевна, учительница Ромы, она предложила классу решить следующую задачку: вычеркнуть из написанного на доске числа \(k\) цифр так, чтобы оставшееся на доске число было максимальным.

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

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

Входной файл к этой задаче содержит несколько наборов тестовых данных. В первой строке входного файла задано число \(T\) — количество наборов в файле.

В следующих \(T\) строках идут описания наборов, каждое из которых состоит из двух целых положительных чисел \(n\) и \(k\). Гарантируется, что первые n простых чисел содержат в себе хотя бы \(k + 1\) цифру суммарно.

Сумма всех \(n\) во входном файле не превосходит 400 000.

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

Для каждого из тестовых наборов в отдельной строке выведите искомое максимальное число для соответствующих \(n\) и \(k\).

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

В первом тесте Рома выписал число 2357. Максимальное число, которое может получиться после вычеркивания из него двух цифр: 57.

Во втором тесте Рома выписал число 235711. Максимальное число, которое может получиться после вычеркивания из него трех цифр: 711.

Примеры

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

2
4 2
5 3

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

57
711

#113348

Робот

Источники: [ Командные олимпиады, ВКОШП, 2015, Задача K ]

Компания «Филипп индастриз» разрабатывает программу для нового робота-марсохода. Участок Марса, на котором будет работать робот, представляет собой квадратное поле размером \(n \times n\), разбитое на квадратные участки размером \(1 \times 1\), некоторые из которых могут содержать скалу \((1 \le n \le 1000\), не более 300 участков содержат скалу).

Введем на поле систему координат таким образом, что участки имеют координаты \((1, 1),(1, 2), \dots ,(1, n),(2, 1), . . . ,(n, n)\). Программа для робота представляет собой последовательность инструкций, каждая из которых кодируется одной латинской буквой:

• «U» — переместиться с участка (x, y) на участок (x, y + 1).

• «D» — переместиться с участка (x, y) на участок (x, y − 1).

• «R» — переместиться с участка (x, y) на участок (x + 1, y).

• «L» — переместиться с участка (x, y) на участок (x − 1, y).

Для экономии инженеры записывают в память последовательность инструкций \(s\), пронумерованных от 1 до \(t\). Затем можно заставить робота выполнить подпрограмму — одну или несколько следующих подряд инструкций. Каждая подпрограмма, таким образом, характеризуется двумя целыми числами \((l, r)\) — номером первой и последней инструкции в подпрограмме.

В процессе лабораторного эксперимента робот был размещен на некотором участке тестового поля. Будем называть подпрограмму \((l, r)\) корректной, если при последовательном выполнении инструкций \(s[l], s[l + 1], \dots , s[r]\) робот не покидает поле и не перемещается на участок со скалой.

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

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

В первой строке входного файла находятся два числа \(n\) и \(t\) (\(1 \le n \le 1000, 1 \le t \le 10^5\) ) — размер поля и количество инструкций в программе робота.

Во второй строке входного файла находится строка \(s\) длины \(t\) — программа робота. Гарантируется, что строка \(s\) состоит только из символов «U», «D», «R» и «L». Следующие \(n\) строк содержат по \(n\) символов в каждой и задают поле. Символ «.» означает, что участок пустой и по нему может перемещаться робот. Символ «#» означает, что на участке находится скала. Символ «@» означает, что в этой клетке находится стартовая позиция робота. Ось X направлена слева направо, ось Y — снизу вверх. Гарантируется, что символ «@» встречается ровно один раз, а символ «#» встречается не более 300 раз.

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

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

Пояснение к примеру

В примере следующие подпрограммы являются корректными: (1, 1)=«U», (1, 2)=«UL», (1, 3)=«ULU», (3, 3)=«U», (3, 4)=«UR», (4, 4)=«R».

Примеры

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

4 4
ULUR
..#.
....
.#@.
#.#.

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

#113349

Турнир по DOTY

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2015, Лига Б, Задача A ]

Совсем недавно закончился межгалактический турнир по известной онлайн-игре «Defence of the Young». Во время турнира страсти разыгрались не на шутку, и судьи только и успевали, что планировать проведение матчей и следить за соблюдением правил. К несчастью, ни одна команда из галактики Млечный путь не смогла пройти отбор на соревнования, поэтому мы традиционно болели за наших друзей из скопления Андромеды.

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

К сожалению, во время бурного чествования ставшей победителем команды «Kind Genius», были утеряны записи о самом турнире. Единственная информация, которую смогло найти жюри, это количество матчей, сыгранное в каждый из дней турнира. Жюри просит вас, пользуясь этими данными и информацией о структуре турнира из предыдущего абзаца, восстановить хотя бы значение n — количество команд, участвоваших в турнире.

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

В первой строке входных данных записано целое число k ( 1 ≤ k ≤ 100 000 ) –– количество дней, которое длился межгалактический турнир по DOTY. В следующей строке записаны k неотрицательных целых чисел, не превышающих 10 ⁹ , i -е из них задаёт количество игр, сыгранных в i -й день турнира.

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

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

Примечание

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

Первая и вторая команда играют матч в первый день.
Победитель первого матча играет с третьей командой во второй день.
Победитель второго матча играет в финале с четвёртой командой в третий день соревнований.

Примеры

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

3
2 2 1

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

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

5
0 1 0 1 1

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

#113350

Машинное обучение

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2015, Лига Б, Задача B ]

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

На вход алгоритм принимает матрицу вхождений — такую таблицу, где строки соответствуют письмам, а столбцы словам. В j -й клетке i -й строки стоит 1 , если слово с номером j содержится в письме с номером i .

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

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

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

В первой строке ввода содержится число n ( 1 ≤ n ≤ 100 ) — количество строк в обратном индексе. Cледующие n строк ввода соответствуют строкам обратного индекса. Каждая из них содержит не менее двух и не более 100 слов. Первое слово в строке — это некоторое слово, встречающееся в письмах, следующие слова соответсвуют названиям писем, в которых данное слово встречается. Суммарное количество слов во всех строках не превосходит 1000 .

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

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

Вам нужно вывести матрицу вхождений слов в письма, то есть матрицу из « 0 » и « 1 », где в i -й строке на j -м месте стоит « 1 », если слово с номером j встречается в письме с номером i . Письма нумеруются в порядке лексикографической сортировки, а нумерацию слов вы выбираете сами. Числа внутри одной строки нужно разделять пробелом, а строки между собой — переводом строки.

Примечание

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

Примеры

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

3
bob gamea gameb
alice gamea
mail spam

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

1 1 0 
0 1 0 
0 0 1

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

1
bob gamea gameb

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

1 
1

#113351

Кто на заводе хозяин

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2015, Лига Б, Задача C ]

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

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

Всего на заводе n + 1 сотрудник. У каждого из них, кроме гендиректора, есть непосредственный начальник — один из других сотрудников. У гендиректора начальника нет.
Все сотрудники завода так или иначе подчинены гендиректору, то есть любой сотрудник является либо гендиректором, либо непосредственным подчинённым гендиректора, либо непосредственным подчинённым непосредственного подчинённого гендиректора и так далее.

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

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

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

В первой строке находится число n ( 1 ≤ n ≤ 200 000 ) — количество сотрудников на хлебобулочном заводе, не считая директора .

Во второй строке следуют числа d ₁ , d ₂ , ..., d _n ( 0 ≤ d _i < i ), где d _i означает номер сотрудника, который является непосредственным начальником сотрудника под номером i . Сам гендиректор имеет номер 0 .

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

Если при правильной игре выигрывает гендиректор, то выведите « Husband » (без кавычек). Если, как бы ни старался гендиректор, победу в игре одержит его жена, то выведите « Wife » (без кавычек).

Примечание

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

Примеры

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

2
0 0

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

Wife

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

6
0 1 2 1 4 5

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

Husband