Страница: << 103 104 105 106 107 108 109 >> Отображать по:
#112691
Турбулентность
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Миша решил развлечься в свободное от решения задач время и сейчас проходит квест «Турбулентность». Задание квеста заключается в том, что Мише нужно добыть статуэтку золотого кота. Миша уже добрался до сейфа, в котором предположительно находится статуэтка, и ему осталось лишь подобрать код от замка.

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

Также Миша решил, что перебирать все такие слова будет слишком долго, поэтому в качестве кода от сейфа он хочет попробовать лексикографически минимальное среди всех подходящих слов. Помогите Мише определить, какое слово ему нужно ввести.

Формат входного файла

В первой строке содержатся два целых числа: \(N\) — длина переданного сообщником слова (\(1 \leq N \leq 10^6\)) и \(K\) (\(1 \leq K \leq 26\)).

Во второй строке содержится переданное сообщником слово.

Формат выходного файла

Выведите строку, которую Миша хочет попробовать в качестве кода от сейфа

Примеры
Входные данные
3 2
aab
Выходные данные
ba
Входные данные
6 3
aaabbc
Выходные данные
ac
#112692
Язык PJ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Мальчик Вартáн настолько любит языки программирования, что выучил уже целых девять и обзавёлся самоучителем по ещё одному языку! Впрочем, просто учить языки ему уже немного надоело, и он решил придумать свой. Название для языка было придумано всего за пару минут — PJ (аббревиатура от любимых команд Вартана), казалось бы, полдела сделано.

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

  1. print value "— число value выводится на экран, после чего исполнитель переходит к следующей строке.

  2. jump num count "— если выполнено условие count > 0 , то управление передаётся в строку с номером num , а count уменьшается на 1 . В текущей реализации PJ не предусмотрено использование в качестве num числа большего, чем номер строки, в которой записана данная команда. Если же count = 0 , то исполнитель просто переходит к следующей строке. Обратите внимание, что в следующий раз, когда интерпретатору встретится данная строка, он будет работать уже с новым значением count , то есть можно считать, что каждой команде jump соответствует своя глобальная переменная.

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

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

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

На ввод подаётся корректная программа на языке PJ, состоящая как минимум из одной, но не более чем из 10 5 команд. Количество строк в файле совпадает с количеством команд, каждая команда занимает отдельную строку. Команда, записанная в строке с номером i (при нумерации от единицы), удовлетворяет одному из двух форматов:

  1. print value , где 0 ≤ value ≤ 10 4 .
  2. jump num count , где 1 ≤ num ≤ i , 0 ≤ count ≤ 10 4 .

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

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

Примеры
Входные данные
print 1
print 2
jump 2 2
Выходные данные
7
Входные данные
print 3
jump 1 1
print 1
print 1
jump 1 2
Выходные данные
18
#112693
У любой магии есть своя цена
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Городок Сторибрук проклят Злой Королевой, и Эмме просто необходимо разрушить её чары. Для того чтобы спасти жителей маленького городка штата Мэн, ей необходимо преобразовать имеющееся заклинание, которое по странному стечению обстоятельств является математическим выражением, в эквивалент более сильного заклинания. Изначально у Эммы имеется выражение +\(x_1\)+\(x_2\)+...+\(x_n\). Для его преобразования доступны две операции:

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\)), задающие стоимости операций

Формат выходного файла

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

Note

В первом примере Эмме выгодно сначала заменить первый ‘+’ на ‘-’, затратив одну единицу магии, а потом бесплатно поставить скобки. В результате у нее получится

-(\(x_1\) + \(x_2\) + \(x_3\)) = -\(x_1\) -\(x_2\) -\(x_3\)

Примеры
Входные данные
3
---
1 0
Выходные данные
1
Входные данные
7
--+++--
2 1
Выходные данные
6
#112694
Дружелюбный интерфейс
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

После получения разноцветного диплома об окончании факультета Высокой Магии и Колдовства Марсианского Галактического Университета, Пафнутий готовится поступать в аспирантуру. На лето он устроился системным администратором в контору по заготовке чистых стёкол и прямых досок, рассчитывая, что работа почти не будет отвлекать его от подготовки к вступительным экзаменам. Но вместо ожидаемого погружения в мир прикладной магии (и сапёра) Пафнутию каждый день приходится сталкиваться со сложными задачами!

В компании работает N сотрудников, каждый из которых использует ровно один персональный компьютер. Машины объединены в сеть с помощью N - 1 соединений, разрешающих парам компьютеров обмениваться данными в любом направлении. Сеть спроектирована таким образом, что между любой парой компьютеров существует ровно один кратчайший (по числу соединений) путь.

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

Сообщения передаются при помощи интерфейса, который ещё помнит, как весело жужжала старушка БЭСМ-6. Его работа происходит строго по следующим правилам:

  1. На каждой машине имеется ячейка памяти, в которой в любой момент времени может находиться не более одного сообщения.
  2. Пока сеть выключена, любой сотрудник может создать сообщение для отправки коллегам. Для этого он помещает сообщение в ячейку памяти своего компьютера и задаёт список адресатов. Как только сеть активируется, возможность создания сообщений отключается и начинается их пересылка.
  3. Пересылка состоит из последовательного выполнения операций передачи сообщения от одного компьютера, на котором создано сообщение, к другому, который находится в списке адресатов. Определение порядка передачи всех сообщений и есть основная функция системного администратора в данном учреждении.
  4. В процессе передачи сообщения между компьютерами v и u оно обязательно будет записано в ячейки памяти всех компьютеров, расположенных на кратчайшем пути между v и u .
  5. Если после выполнения очередной операции пересылки все исходные сообщения находятся в ячейках памяти всех своих адресатов, то работа интерфейса передачи сообщений считается успешно выполненной и сеть снова выключается. Что находится в этот момент в ячейках памяти компьютеров, которым не было адресовано ни одного сообщения, не имеет значения.

Гарантируется, что каждый компьютер в сети является получателем не более чем одного сообщения, причем никогда не является и отправителем, и получателем одновременно. Как этого добивается администрация "— остается загадкой.

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

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

В первой строке входного файла находится единственное целое число N — количество компьютеров. Следующие N - 1 строк содержат пары чисел v i и u i , каждая из которых означает наличие соединения между парой компьютеров с данными номерами. 1 ≤ N ≤ 4 000 , 1 ≤ v i , u i ≤ N , v i ≠ u i . Гарантируется, что между любой парой вершин существует путь, состоящий из данных соединений.

Следующая строка содержит единственное целое число S — количество отправляемых сообщений. Следующие S строк содержат по два целых числа s i и sid i — номер машины, отправляющей сообщение, и уникальный идентификатор сообщения. 1 ≤ S ≤ N , 1 ≤ s i , sid i ≤ N . Гарантируется, что все s i и sid i уникальны.

Далее следует строка, содержащая единственное целое число K — количество компьютеров, принимающих сообщения. Следующие K строк содержат по два целых числа t i и tid i — номер компьютера и идентификатор принимаемого сообщения. 1 ≤ S + K ≤ N , 1 ≤ t i , tid i ≤ N . Гарантируется, что все t i уникальны и что t i ≠ s j для любых i и j . Гарантируется, что для любого i найдётся j такое, что tid i = sid j .

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

В выходной файл выведите « YES », если решение для данного случая существует, и « NO » в противном случае.

Примечание

В первом примере требуется передать сообщение от компьютера 3 к компьютеру 1, а также от компьютера 4 к компьютерам 2 и 5. Передача сообщения от 4 к 2 затрёт сообщение, находящееся в ячейке памяти машины 3, поэтому необходимо сначала выполнить передачу от 3 к 1, а затем от 4 к 2. Передачу сообщения от компьютера 4 к компьютеру 5 можно выполнить когда угодно.

Во втором примере передача сообщения от компьютера 4 к компьютеру 1 затрёт содержимое ячеек памяти машин 2 и 3, поэтому успешная пересылка невозможна. Компьютер 5 не может быть использован ни в одной передаче сообщения.

Примеры
Входные данные
5
1 2
2 3
3 4
4 5
2
3 1
4 2
3
5 2
1 1
2 2
Выходные данные
YES
Входные данные
5
1 2
2 3
3 4
2 5
2
2 1
4 2
2
1 2
3 1
Выходные данные
NO
#112695
Файловое дерево
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
У студента Альберта завтра очень ответственный экзамен. Посмотрев на часы, он понял, что не успевает выучить \(N\) билетов. И тогда он решился пойти на крайние меры — сделать шпаргалку. Опасаясь за целостность своих карманов (посмотрите на ограничения для \(N\) и угадайте, в каком вузе учится Альберт!), он отказался от идеи написать ответы на бумаге. Вместо этого он решил разместить ответы на своём телефоне, который работает под управлением операционной системы CheatOS. Он уже подготовил \(N\) файлов: FILE_1, FILE_2, . . . , FILE_N, и теперь ему необходимо разместить их в каталоге, который он в целях конспирации назвал tmp.

Задача состоит в том, чтобы создать некоторое дерево подкаталогов в каталоге tmp и разместить в нём файлы так, чтобы доступ к самому далёкому файлу осуществлялся бы за минимально возможное количество действий: Альберт не хочет быть пойманным на списывании из-за промедления в поиске нужного файла

Более формально, при работе с файловой системой операционной системы CheatOS на экране телефона в каждый момент отображается содержимое текущего каталога в виде списка элементов, расположенных в следующем порядке: сперва символ «..» перехода в родительскую папку, затем список всех размещённых непосредственно в этом каталоге подкаталогов и файлов. Файлы и каталоги, содержащиеся в подкаталогах текущего каталога, не отображаются.

В каждый момент на один из элементов отображаемого списка (файл или папку) указывает курсор.

Нас будут интересовать два вида действий, которые потребуются Альберту на экзамене:

1. Войти в дочерний каталог, на который указывает курсор. При этом этот каталог становится текущим и всё его содержимое отображается на экране телефона так, как описано выше. Сразу после этого действия курсор указывает на символ «..».

2. Сдвинуть курсор на следующий по списку элемент (см. рисунок).

Изначально текущий каталог — tmp, курсор указывает на символ «..»

Расстоянием до файла будем называть минимальное суммарное число действий обоих видов, необходимое для того, чтобы курсор на экране стал указывать на этот файл.

Альберт просит вас помочь ему построить дерево каталогов и разместить в них все \(N\) файлов так, чтобы расстояние до самого далёкого файла было минимально возможным.

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

В файловой системе допускаются каталоги, не содержащие файлов, каталоги, не содержащие дочерних каталогов, а также пустые каталоги. Каталоги должны иметь названия FOLDER_1, FOLDER_2, ... , FOLDER_M.

Каждый из файлов, подготовленных Альбертом, должен быть размещён в построенном дереве каталогов ровно один раз.

В случае, если удовлетворяющих условию деревьев несколько, выведите любое.

Формат входного файла

На вход программе подаётся одно целое число \(N\) (1 <= \(N\) <= \(10^5\)).

Формат выходного файла

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

В следующей строке выведите содержимое каталога tmp, а в следующих M строках выведите содержимое каталогов FOLDER_1, FOLDER_2, ... , FOLDER_M соответственно. Содержимое каталога выводится в следующем формате: сперва выводится общее число файлов и подкаталогов, содержащихся непосредственно в данном каталоге, а затем список файлов и папок в том порядке, в котором они располагаются в каталоге. В этом списке файл под номером K обозначается FILE_K, а папка под номером \(K\) обозначается FOLDER_K. Символ «..» выводить не требуется.

Для лучшего понимания формата вывода рекомендуется изучить примеры.

Примеры
Входные данные
3
Выходные данные
3 0
3 FILE_1 FILE_2 FILE_3
Входные данные
5
Выходные данные
4 1
4 FOLDER_1 FILE_1 FILE_2 FILE_3 
2 FILE_4 FILE_5
Страница: << 103 104 105 106 107 108 109 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест