Совсем недавно закончился межгалактический турнир по известной онлайн-игре «Defence of the Young». Во время турнира страсти разыгрались не на шутку, и судьи только и успевали, что планировать проведение матчей и следить за соблюдением правил. К несчастью, ни одна команда из галактики Млечный путь не смогла пройти отбор на соревнования, поэтому мы традиционно болели за наших друзей из скопления Андромеды.
Всего в соревнованиях участвовало n команд. Турнир проводился по олимпийской системе, то есть команда выбывала сразу после первого проигрыша. Поскольку на турнире присутствовали команды с самым разным уровнем мастерства, то сетка турнира могла быть совершенно произвольной. В частности, количество участвовавших команд совершенно не обязательно было равно какой-либо степени двойки. Также известно, что никакая команда не играла две игры в один день.
К сожалению, во время бурного чествования ставшей победителем команды «Kind Genius», были утеряны записи о самом турнире. Единственная информация, которую смогло найти жюри, это количество матчей, сыгранное в каждый из дней турнира. Жюри просит вас, пользуясь этими данными и информацией о структуре турнира из предыдущего абзаца, восстановить хотя бы значение n — количество команд, участвоваших в турнире.
В первой строке входных данных записано целое число k ( 1 ≤ k ≤ 100 000 ) –– количество дней, которое длился межгалактический турнир по DOTY. В следующей строке записаны k неотрицательных целых чисел, не превышающих 10 9 , i -е из них задаёт количество игр, сыгранных в i -й день турнира.
Выведите единственное целое число n — количество команд, участвовавших в турнире. Гарантируется, что n может быть однозначно восстановлено по входным данным и будет не больше 10 9 . Также гарантируется, что в турнире участвовала хотя бы одна команда.
Одной из возможных сеток турнира во втором примере является:
3 2 2 1
6
5 0 1 0 1 1
4
Ваш друг Вася учит машины. Точнее, он занимается машинным обучением, и недавно перед ним поставили задачу: кластеризовать по темам все письма из архива компании. Итогом плодотворной работы по изучению статей и алгоритмов стала программа, реализующая разработанный Васей алгоритм кластеризации.
На вход алгоритм принимает матрицу вхождений — такую таблицу, где строки соответствуют письмам, а столбцы словам. В j -й клетке i -й строки стоит 1 , если слово с номером j содержится в письме с номером i .
Проблема Васи состоит в том, что системные администраторы забыли дать Васе доступ к письмам и уже ушли домой, а результат надо представить начальству уже завтра утром! К счастью, предыдущим заданием Васи было построение поисковой системы по архиву, поэтому у него остался доступ к обратному индексу . В рамках данной задачи обратный индекс — это файл, в каждой строчке которого сначала записано слово, а потом названия писем, в которых это слово встречается.
Ваша задача — построить по данному обратному индексу матрицу вхождений для Васиной задачи, в которой i -я строка будет соответствовать i -му в лексикографическом порядке названию письма. Слова можно пронумеровать как вам удобно — Васин алгоритм классификации не зависит от порядка столбцов.
В первой строке ввода содержится число n ( 1 ≤ n ≤ 100 ) — количество строк в обратном индексе. Cледующие n строк ввода соответствуют строкам обратного индекса. Каждая из них содержит не менее двух и не более 100 слов. Первое слово в строке — это некоторое слово, встречающееся в письмах, следующие слова соответсвуют названиям писем, в которых данное слово встречается. Суммарное количество слов во всех строках не превосходит 1000 .
Все слова имеют длину, не превышающую 10 символов, и состоят из маленьких английских букв. Гарантируется, что первые слова во всех строках попарно различные.
Вам нужно вывести матрицу вхождений слов в письма, то есть матрицу из « 0 » и « 1 », где в i -й строке на j -м месте стоит « 1 », если слово с номером j встречается в письме с номером i . Письма нумеруются в порядке лексикографической сортировки, а нумерацию слов вы выбираете сами. Числа внутри одной строки нужно разделять пробелом, а строки между собой — переводом строки.
Лексикографическим порядком называется порядок следования строк, который можно встретить, например, в словаре. Формально: строка s 1 лексикографически меньше строки s 2 , если выполнено одно из двух условий: либо s 1 является префиксом s 2 , либо в первой позиции, где строки отличаются, в s 1 стоит меньший символ.
3 bob gamea gameb alice gamea mail spam
1 1 0 0 1 0 0 0 1
1 bob gamea gameb
1 1
Как вам, может быть, известно, на одном хлебобулочном заводе, который специализируется на производстве багетов, всем заправляет вовсе не гендиректор, а его жена, хотя официально она даже не является сотрудницей завода. Однажды об этом узнал и сам гендиректор. Он страшно разозлися и решил показать жене, кто на заводе хозяин. Для этого он предложил ей сыграть в управленческую игру.
Иерархия сотрудников завода описывается следующими простыми правилами:
Гендиректор и его жена ходят по очереди, начинает гендиректор. За один ход необходимо выбрать одного произвольного сотрудника, чьим непосредственным начальником ещё не является гендиректор, и исправить эту оплошность, то есть назначить гендиректора непосредственным начальником выбранного сотрудника. Тот, кто не может сделать ход, проигрывает.
Определите, кто из супругов выиграет при правильной игре и сможет называть себя настоящим хозяином завода.
В первой строке находится число n ( 1 ≤ n ≤ 200 000 ) — количество сотрудников на хлебобулочном заводе, не считая директора .
Во второй строке следуют числа d 1 , d 2 , ..., d n ( 0 ≤ d i < i ), где d i означает номер сотрудника, который является непосредственным начальником сотрудника под номером i . Сам гендиректор имеет номер 0 .
Если при правильной игре выигрывает гендиректор, то выведите « Husband » (без кавычек). Если, как бы ни старался гендиректор, победу в игре одержит его жена, то выведите « Wife » (без кавычек).
Во первом примере все сотрудники уже являются непосредственными подчинёнными гендиректора, поэтому в игре нельзя сделать ни одного хода.
2 0 0
Wife
6 0 1 2 1 4 5
Husband
Название одной маленькой, но очень гордой корпорации состоит из n строчных английских букв. Корпорация решила провести ребрендинг — активную маркетинговую стратегию, включающую комплекс мероприятий по изменению бренда (как компании, так и производимого ею товара), либо его составляющих: названия, логотипа, слогана. Начать решили именно с названия.
Для этого корпорация последовательно наняла \(m\) дизайнеров. Как только компания нанимает \(i\)-го дизайнера, тот сразу вносит свою лепту в создание нового имени корпорации следующим образом: он меняет в текущей версии названия все буквы \(x_i\) на \(y_i\) , а все буквы \(y_i\) на \(x_i\), после чего получается новая версия. Возможно, каких-то из этих букв в строке нет, а также возможно, что \(x_i\) совпадает с \(y_i\). Вариант имени, получившийся после работы последнего дизайнера, становится новым названием корпорации.
Менеджер Аркадий лишь недавно устроился на работу в эту фирму, но уже проникся корпоративным духом и очень переживает за успех ребрендинга. Естественно, ему не терпится узнать, какое имя в итоге получит корпорация.
Удовлетворите любопытство Аркадия — назовите ему окончательный вариант названия.
В первой строке входных данных находятся два числа \(n\) и \(m (1 ⩽ n, m ⩽ 200 000)\) — длина изначального названия и количество нанятых дизайнеров соответственно.
Вторая строка состоит из n строчных английских букв и представляет собой изначальное имя корпорации.
В следующих \(m\) строках содержатся описания действий дизайнеров: в \(i\)-й из последующих строк записаны две строчные английские буквы \(x_i\) и \(y_i\).
Выведите окончательный вариант названия корпорации.
Во втором примере название корпорации последовательно претерпевает следующие изменения:
abacabadaba → babcbabdbab
babcbabdbab → cacbcacdcac
cacbcacdcac → cdcbcdcacdc
cdcbcdcacdc → cdcbcdcacdc
cdcbcdcacdc → cdcbcdcfcdc
cdcbcdcfcdc → cdcbcdcfcdc
6 1 police p m
molice
11 6 abacabadaba a b b c a d e g f a b b
cdcbcdcfcdc
Лесничий Хогвартса Хагрид собирается заняться разведением драконов, для этого он намерен закупить партию драконьих яиц. С этой целью он отправился в волшебный зоомагазин в Косом переулке.
Хагриду известно, что магическая сила новорождённого дракона зависит от веса яйца дракона в фунтах, а именно, она равняется сумме квадратов цифр в десятичной записи веса. Заметим, что в волшебном мире вес яйца дракона всегда выражается целым положительным числом фунтов.
Естественно, Хагрид желает завести себе драконов как можно большей суммарной силы, но его мотоцикл не сможет поднять груз весом более l фунтов. Ассортимент в волшебном зоомагазине поистине волшебный, поэтому можно считать, что для любого целого положительного веса x , Хагрид может купить в магазине произвольное количество яиц драконов с таким весом.
Напишите программу, которая определит максимальную возможную суммарную волшебную силу драконов, родившихся из яиц, которые Хагрид сможет увезти на своём мотоцикле.
В единственной строке входных данных находится целое число l ( 1 ≤ l ≤ 10 12 ) — максимальный вес груза, который может поднять мотоцикл Хагрида.
Выведите единственное целое число — максимальную возможную суммарную волшебную силу драконов, которых Хагрид будет разводить рядом с Хогвартсом, при условии, что он съездит за яйцами только один раз и увезёт всю покупку на своём мотоцикле.
В первом примере выгоднее всего купить одно яйцо весом 6 фунтов.
Во втором примере выгоднее всего купить два яйца весом 9 фунтов каждое.
6
36
18
162