Страница: << 33 34 35 36 37 38 39 >> Отображать по:

#112693

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

Городок Сторибрук проклят Злой Королевой, и Эмме просто необходимо разрушить её чары. Для того чтобы спасти жителей маленького городка штата Мэн, ей необходимо преобразовать имеющееся заклинание, которое по странному стечению обстоятельств является математическим выражением, в эквивалент более сильного заклинания. Изначально у Эммы имеется выражение +\(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

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

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

7
--+++--
2 1

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

#112694

Дружелюбный интерфейс

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

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

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

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

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

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

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

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

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

В первой строке входного файла находится единственное целое число 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 не может быть использован ни в одной передаче сообщения.

Примеры

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

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

YES

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

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

NO

#112695

Файловое дерево

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

У студента Альберта завтра очень ответственный экзамен. Посмотрев на часы, он понял, что не успевает выучить \(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 0
3 FILE_1 FILE_2 FILE_3

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

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

4 1
4 FOLDER_1 FILE_1 FILE_2 FILE_3 
2 FILE_4 FILE_5

#112696

Новая надежда

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

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

Уничтожение Звезды смерти, как и любая другая амбициозная задача, проходит этап компьютерного моделирования. По текущему плану, для уничтожения станции будет построен мощный ракетный крейсер, который станет флагманом сил Сопротивления и вступит в бой со Звездой смерти, пока остальной флот будет отвлекать внимание противника. Новый корабль будет стрелять ракетами мощностью A единиц и обладать щитами с энергией, достаточной для поглощения B единиц урона. Звезда смерти, в свою очередь, не может использовать в ближнем бою турболазер, способный уничтожать целые планеты, поэтому с неё будет вестись ответный огонь импульсами мощностью C единиц. Щиты Звезды смерти обладают энергией, достаточной для поглощения D единиц урона.

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

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

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

В первой и второй строках записаны два целых числа A и B ( 1 ≤ A , B ≤ 1 000 ) "— соответственно огневая мощь и энергия щитов флагмана флота Сопротивления.

В третьей и четвертой строках записаны два целых числа C и D ( 1 ≤ C , D ≤ 1 000 ) "— соответственно огневая мощь и энергия щитов Звезды смерти.

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

Если Сопротивление одержит победу, взорвав Звезду смерти на каком-то этапе, и сохранит свой флагман, выведите « WIN ».

Если флагман взорвётся, а станция уцелеет, выведите « LOSE ».

В случае, если противники уничтожат друг друга на одном и том же шаге боя, выведите « DRAW ».

Примеры

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

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

WIN

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

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

LOSE

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

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

DRAW

#112697

ABC

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

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

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

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

В первой строке ввода находится число N ( 3 ≤ N ≤ 32 ) "— количество задач, отобранных для олимпиады.

В каждой из следующих N строк содержится описание задачи, начинающееся с одной из пометок А , В , С , АВ , ВС или АВС , записанной заглавными латинскими буквами, за которой через пробел следует название задачи. Название задачи "— одно слово, состоящее из строчных или прописных латинских букв. Все названия задач являются различными. Длина каждой строки не превосходит 255 символов.

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

Выведите описания задач в требуемом порядке в том же формате, что и во входных данных. Все задачи, в пометку которых входит буква А , должны идти подряд, то же касается задач, пометка которых содержит букву В , и задач, пометка которых содержит букву С . Задачи, имеющие одинаковые пометки, могут идти в любом порядке.

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

Примеры

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

5
C Tetris
B DOOM
A WOW
C LINES
AB CS

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

A WOW
AB CS
B DOOM
C Tetris
C LINES

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

4
A a
B b
C c
ABC Abc

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

Impossible

Страница: << 33 34 35 36 37 38 39 >> Отображать по:

Выбрано

Отменить

Добавить в контест