Темы
Информатика(2656 задач)
--->
228 задач
<---
Мальчик Вартáн настолько любит языки программирования, что выучил уже целых девять и обзавёлся самоучителем по ещё одному языку! Впрочем, просто учить языки ему уже немного надоело, и он решил придумать свой. Название для языка было придумано всего за пару минут — PJ (аббревиатура от любимых команд Вартана), казалось бы, полдела сделано.
После пяти лет упорной работы Вартан реализовал две команды, работающие с целыми неотрицательными числами:
Изначально исполнитель находится на первой строке, работа программы начинается с выполнения записанной в ней команды. Выполнение программы заканчивается после того, как исполнитель попытается перейти дальше последней строки. Нетрудно догадаться, что на данном языке невозможно написать программу, не завершающуюся за конечное число итераций.
По имеющейся программе на языке PJ определите сумму всех чисел, которые будут выведены в результате её исполнения.
На ввод подаётся корректная программа на языке PJ, состоящая как минимум из одной, но не более чем из 10 5 команд. Количество строк в файле совпадает с количеством команд, каждая команда занимает отдельную строку. Команда, записанная в строке с номером i (при нумерации от единицы), удовлетворяет одному из двух форматов:
Выведите сумму всех чисел, которые будут выведены в процессе выполнения данной программы.
print 1 print 2 jump 2 2
7
print 3 jump 1 1 print 1 print 1 jump 1 2
18
1. Заменить в текущем выражении любой знак ‘+’ на ‘-’
2. Добавить в выражение пару из открывающейся и закрывающейся скобок. Открывающаяся скобка обязательно ставится сразу после знака ‘+’ или ‘-’, а закрывающаяся обязательно ставится сразу после переменной (и, разумеется, после соответствующей ей открывающейся).
Требуется получить выражение, эквивалентное \(⋄_1\) \(x_1\) \(⋄_2\) \(x_2\) \(⋄_3\) ... \(⋄_n\) \(x_n\);
где каждое \(⋄_i\) — это знак ‘+’ или ‘-’.
Выражения f(\(x_1\); \(x_2\); ... ; \(x_n\)) и g(\(x_1\); \(x_2\); ... ; \(x_n\)) называются эквивалентными, если f(\(x_1\); \(x_2\); ... ; \(x_n\)) = g(\(x_1\); \(x_2\); ... ; \(x_n\)) для любых(\(x_1\); \(x_2\); ... ; \(x_n\)), то есть они равны для любых возможных значений используемых переменных. С точки зрения предлагаемой задачи данное определение означает, что после раскрытия всех скобок каждая переменная встречается в обоих выражениях с одним и тем же знаком.
Эмма использует \(A\) единиц магии на выполнение каждой операции первого типа и \(B\) единиц магии на выполнение каждой операции второго типа. Помогите Эмме определить, какое минимальное количество единиц магии ей придётся использовать, чтобы преобразовать исходное выражение в эквивалентное требуемому.
В первой строке входных данных записано единственное целое число \(N\) (1 <= N <= \(10^6\)) — количество переменных в выражениях. Во второй строке записана строка длины \(N\), состоящая только из символов ‘+’ и ‘-’, \(i\)-й символ строки соответствует знаку \(⋄_i\). В третьей строке записаны два целых числа \(A\) и \(B\) (0 <= \(A\); \(B\) <= \(10^9\)), задающие стоимости операций
Выведите одно число — искомое минимальное количество единиц магии, необходимое для получения эквивалентного выражения из исходного
В первом примере Эмме выгодно сначала заменить первый ‘+’ на ‘-’, затратив одну единицу магии, а потом бесплатно поставить скобки. В результате у нее получится
-(\(x_1\) + \(x_2\) + \(x_3\)) = -\(x_1\) -\(x_2\) -\(x_3\)3 --- 1 0
1
7 --+++-- 2 1
6
Совсем недавно закончился межгалактический турнир по известной онлайн-игре «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