Каталог по темам

Задачи

Страница: << 24 25 26 27 28 29 30 >> [Всего задач: 155]

Задача 102948

[Микрофония ]

Тема:

[

Конечные автоматы

]

Сложность: 4+

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

Очередность выходов артистов на сцену и их уходов за кулисы указывается в режиссерском плане. Кроме того, в этом плане указывается, через какие кулисы выходит (или уходит) артист и поет ли он в данном выходе.

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

Входные данные
Первая строка входного файла содержит целое число N – количество артистов, участвующих в спектакле (1 ≤ N ≤ 1000). Во второй строке записано целое число K – количество выходов артистов на сцену (1 ≤ K ≤ 3000). Далее идут 2K строк, описывающих режиссерский план спектакля. Каждая из них содержит четверку A_iB_iC_iD_i (1 ≤ i ≤ 2K):
A_i – символ +, если в данный момент артист выходит на сцену, или символ -, если артист со сцены уходит;
B_i – номер артиста (целое число от 1 до N);
C_i – символ Л, если артист выходит (уходит) через левые кулисы, или символ П, если он выходит (уходит) через правые кулисы;
D_i – символ Д, если артист поет в данном выходе (пел перед данным уходом), или символ Н, если он не поет (не пел).

Выходные данные
Первая строка выходного файла должна содержать два целых числа. Первое число – количество микрофонов перед началом оперы с левой стороны, второе число – количество микрофонов с правой стороны. В каждой из последующих K строк необходимо вывести 1 или 0 в зависимости от того, берет ли с собой микрофон очередной выходящий на сцену артист (1 - берет, 0 - не берет).

Пример входного файла
3
4
+ 1 Л Д
- 1 Л Д
+ 2 Л Н
+ 3 Л Н
- 3 П Н
+ 1 П Д
- 1 Л Д
- 2 П Н

Пример выходного файла
1 0
1
0
1
1

Прислать комментарий Решение

Задача 98676

[Менеджер памяти]

Тема:

[

Куча

]

Сложность: 5
Классы: 8,9,10,11

Имя входного файла:

memory.in

Имя выходного файла:

memory.out

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

64 мегабайта

Максимальная оценка за задачу:

100 баллов

Пете поручили написать менеджер памяти для новой стандартной библиотеки языка H++. В распоряжении у менеджера находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера - обрабатывать запросы приложений на выделение и освобождение памяти.

Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом непосредственно перед самой первой ячейкой памяти выделяемого блока не должно располагаться свободной ячейки памяти. После этого выделенные ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется.

Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T - запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется.

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

Формат входных данных

Первая строка входного файла содержит числа N и M - количество ячеек памяти и количество запросов соответственно (1 ≤ N ≤ 2³¹ - 1; 1 ≤ M ≤ 10⁵). Каждая из следующих M строк содержит по одному числу: (i+1)-я строка входного файла (1 ≤ i ≤ M) содержит либо положительное число K, если i-й запрос - запрос на выделение с параметром K (1 ≤ K ≤ N), либо отрицательное число -T, если i-й запрос - запрос на освобождение с параметром T (1 ≤ T < i).

Формат выходных данных

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

Пример

memory.in	memory.out
6 8 2 3 -1 3 3 -5 2 2	1 3 -1 -1 1 -1

Прислать комментарий

Решение

Задача 98679

[Сетевая игра]

Темы:	[	Динамическое программирование (прочее)	]
Темы:	[	Теория игр	]

Сложность: 5
Классы: 8,9,10,11

Имя входного файла:

net.in

Имя выходного файла:

net.out

Максимальное время работы на одном тесте:

1 секунда

Максимальный объем используемой памяти:

64 мегабайта

Максимальная оценка за задачу:

100 баллов

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

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

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

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

Формат входных данных

В первой строке входного файла задано число N (1 ≤ N ≤ 50) - количество веревочек единичной длины, из которых состоит кусок сети. Следующие N строк входного файла содержат по две пары целых чисел - координаты концов веревочек. Каждая четверка чисел описывает отрезок единичной длины, параллельный одной из осей координат.

Координаты всех точек неотрицательны и не превосходят 50.

Формат выходных данных

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

Примечание

Максимальная оценка за решение задачи при N ≤ 13 равна 40 баллам.

Пример

net.in	net.out
11 1 1 1 2 2 3 2 4 3 1 3 2 1 2 1 3 1 1 2 1 2 1 2 2 2 1 3 1 1 2 2 2 2 2 3 2 1 3 2 3 2 3 3 3	1 6

Прислать комментарий

Решение

Задача 102943

[Блиц-тур по комбинаторике ]

Темы:	[	Генерация объектов любым методом	]
	[	Генерация объектов по номеру и номера по объекту	]
	[	Построение перечислителя	]
	[	Длинная арифметика как инструмент	]
	[	Динамическое программирование (прочее)	]

Сложность: 5

Уважаемые господа! Сегодня вам предлагается для каждого из следующих типов комбинаторных объектов:
    1) перестановки N-элементного множества (лексикографический порядок);
    2) K-элементные подмножества N-элементного множества (лексикографический порядок);
    3) разбиения N-элементного множества на K непустых подмножеств (лексикографический, т.е. алфавитный, порядок);
    4) разбиения числа N на слагаемые;
    5) правильные скобочные последовательности из 2N скобок;
    6) двоичные деревья с N вершинами;
    7) цепочки из нулей и единиц длины N без двух единиц подряд;
    8) перестановки N-элементного множества (порядок, в котором соседние перестановки отличаются транспозицией соседних элементов);
    9) K-элементные подмножества N-элементного множества (порядок, в котором соседние подмножества отличаются двумя элементами);
    10) все подмножества N-элементного множества (порядок, в котором соседние подмножества отличаются добавлением или удалением одного элемента);
    11) подвешенные деревья с N вершинами;
решить следующие две подзадачи:
    найти общее количество объектов и породить M объектов, начиная с L-го;
    по заданным объектам получить их номера.
В качестве N-элементного множества везде подразумевается множество {1, ..., N}. Там, где порядок порождения комбинаторных объектов не указан, Вы можете выбрать его по своему усмотрению. Нумерация объектов начинается с нуля.

Таким образом, Вам предстоит написать 11 программ. Задача засчитывается, если Ваша программа прошла все тесты, в противном случае
Вам начисляются штрафные баллы за неверный подход (20% от стоимости задачи), и Вы имеете возможность исправить решение.
В зависимости от того, какую из подзадач требуется решить, входной и выходной файлы имеют один из следующих двух форматов (тем самым, Ваша программа должна сама определять номер решаемой подзадачи).

Входные данные для подзадачи 1
N K L M

Выходные данные для подзадачи 1
<Число объектов>
<Объект номер L>
...
<Объект номер L+M-1>
Каждый объект должен выводиться с новой строки. Формат вывода объектов
остается на Ваше усмотрение с условием, что он должен быть читабельным.

Входные данные для подзадачи 2
N K
<Объект 1>
...
<Объект M>
Формат записи объектов будет соответствовать выходному формату, используемому Вашей программой при решении подзадачи 1.

Выходные данные для подзадачи 2
<Номер объекта 1>
...
<Номер объекта M>
Каждый номер должен быть выведен с новой строки.

Технические ограничения
Если в данной задаче число K не используется, то вместо него будет указан нуль. Числа N и K во всех задачах не превосходят 100, число L не превышает 2·10⁹ , число M – 10 000. Номера объектов в подзадаче 2 не будут превышать 2.1·10⁹. Все входные данные корректны.

Прислать комментарий Решение

Задача 102957

[Язык описания данных DDL ]

Тема:

[

Синтаксический разбор (прочее)

]

Сложность: 5

Базовые типы данных
Имеются несколько базовых типов данных: Integer, Char, Boolean и String. Константы этих типов записываются следующим образом.

Константа типа String – это последовательность (длиной от 0 до 255) символов, заключенная либо в апострофы (▓), либо в двойные кавычки ("). При этом, если ограничители – апострофы, то внутри них апостроф удваивается, а кавычка нет. Аналогично, внутри кавычек двойная кавычка удваивается, а апостроф нет. В качестве символов будут использоваться ASCII-символы с кодами от 32 до 255. Единственная допустимая операция над строками – конкатенация (+).

Константа типа Char – это константа типа String длины 1. Определена операция Ord(<символ>), возвращающая ASCII-код заданного символа
(значение типа Integer), и Chr(<ASCII-код>), возвращающая символ с указанным ASCII-кодом (значение типа Char).

Константы типа Integer – целые числа из диапазона [-32768, 32767] – записываются в следующей форме (здесь и далее символы ▒<▓, ▒>▓, ▒[▓, ▒]▓, ▒{▓, ▒}▓ используются в качестве метасимволов, т.е. относятся к языку формул Бэкуса-Науэра, а не к описываемому языку):
<число> ::= [<знак>]<цифра>{<цифра>}
<знак> ::= +|-
<цифра> ::= 0|1|2|3|4|5|6|7|8|9
Над константами этого типа определены следующие операции: унарные + и -, бинарные + (сложение) и - (вычитание), а также * (умножение), / (целочисленное деление), Mod (остаток от деления нацело).

Константы типа Boolean могут иметь только два значения: True и False. Над ними определены операции Or (или), And (и), Not (не).

Кроме того, над всеми базовыми типами определены операции сравнения (<, >, =, <=, >=, <>), которые возвращают результат типа Boolean. При этом False < True.

Конструкторы типов
Из описанных базовых типов мы можем конструировать новые типы при помощи следующих конструкторов типов:
<тип> ::= <имя типа> | <имя базового типа> | <ограниченный тип> | <перечислимый тип> | <тип-последовательность> | <тип-множество> | <тип-выражение>

Здесь:

1. <имя типа> – это идентификатор типа, который может быть определен как до, так и после данного описания.

2. <перечислимый тип> ::= (<идентификатор 0> {,<идентификатор i>}) (i = 1, ..., N)
По этому описанию заводится N+1 константа с указанными идентификаторами и им ставятся в соответствие значения от 0 до N по порядку. Константами данного типа являются только указанные идентификаторы.

Возможны следующие операции над константами перечислимого типа:
    операции сравнения (константы перечислимого типа сравниваются как соответствующие им числовые значения);
    Ord(<идентификатор>) – возвращает значение (типа Integer), соответствующее константе;
    Pred(<идентификатор>) – возвращает предыдущую константу этого типа (Pred(<идентификатор 0>) = <идентификатор N>)
    Succ(<идентификатор>) – возвращает следующую константу этого типа (Succ(<идентификатор N>) = <идентификатор 0>)

3. <ограниченный тип> ::= <значение 1>..<значение 2>

Здесь <значение 1> и <значение 2> – константы одинакового типа, который может быть одним из следующих: Integer, Char, Boolean, либо каким-то из <перечислимых типов>. Если <значение 1> ? <значение 2>, то константы <ограниченного типа> могут принимать любое значение из промежутка [<значение 1>, <значение 2>]. Иначе множество констант этого типа пусто. Над константами <ограниченного типа> допустимы те же операции, что и над константами того типа, которому принадлежат <значение 1> и <значение 2>.

4. <тип-последовательность> ::= Sequence Of <тип> | Sequence (<поле> {, <поле>}) <поле> ::= [Optional] <тип>

Константами <типа-последовательности>, описанного как Sequence Of <тип>, являются конечные последовательности констант типа <тип>. Константами <типа-последовательности>, описанного как Sequence (<поле> {, <поле>}), являются упорядоченные наборы из констант указанных типов (в том порядке, в котором они встречаются в описании). Однако при этом можно опускать те элементы, перед типами которых указано ключевое слово Optional. Константы <типа-последовательности> записываются следующим образом: {<Константа> {, <Константа>}}. Пустая последовательность обозначается символами { }.

Над <типами-последовательностями> определена операция конкатенации <тип 1>@<тип 2>, результатом которой является новый тип, все константы которого получаются дописыванием к произвольной константе-последовательности <типа 1> справа константы-последовательности <типа 2>. К образованным таким способом новым типам опять можно применять операцию конкатенации.

Аналогично, операция конкатенации определена и для констант рассматриваемых типов. Кроме того, если для констант каждого из типов из
описания <типа-последовательности> определена некоторая операция, то такая же операция, действующая поэлементно, определена и над константами этого <типа-последовательности> одинаковой длины. Например, {1, 'a'}+{2,'b'} = {3, 'ab'}.

5. <тип-множество> ::= [Multi] Set Of <тип> | Set (<тип> {, <тип>})

Константами <типа-множества>, описанного как Set Of <тип>, являются конечные множества констант указанного типа <тип>. В случае описания Multi Set Of <тип> это будут конечные мультимножества (т.е. множества, в которых элементы могут повторяться более одного раза).

Константами <типа-множества>, описанного как Set (<тип> {, <тип>}) являются конечные мультимножества, полученные взятием произвольных констант указанных в описании типов (по одной константе каждого типа с учетом кратности).

Константы <типа-множества> записываются следующим образом: {<Константа> {, <Константа>}}. Пустое множество обозначается символами { }.

Над <типами-множествами> возможны следующие операции (результатом которых является, как легко заметить, опять некоторый <тип-множество>): Plus (объединение), Minus (разность), Mul (пересечение). Например, константы типа A Mul B – это те (мульти-) множества, которые одновременно являются константами типа A и константами типа B. Эти же операции определены (с учетом кратности элементов) и для констант <типов-множеств>. Например, {1, 2, 2} Minus {2, 3} = {1, 2}, {3, 3, 5} Mul {3, 5, 5} = {3, 5}.

6. <тип-выражение> ::= <тип>@<тип> | <тип> Plus <тип> | <тип> Minus <тип> | <тип> Mul <тип>

Определения этих операций см. выше.

Структура программы
Программа на языке DDL (Data Description Language) имеет следующую структуру:
<программа> ::= <предложение> {; <предложение>}
<предложение> ::= <описание типа> | <описание константы> | <пусто>
<пусто> ::=
<описание типа> ::= Define type <имя типа> = <тип>
<описание константы> ::= Define constant <имя константы> = <выражение>
<имя типа> ::= <идентификатор>
<имя константы> ::= <идентификатор>
Здесь <выражение> – это корректно записанное с помощью допустимых операций, операндов и круглых скобок выражение, значение которого присваивается константе.
<Идентификатор> – это непустая последовательность символов, состоящая из больших и маленьких латинских и русских букв, цифр и знаков ▒.▓, ▒$▓, ▒_▓, ▒?▓, которая удовлетворяет следующим требованиям:
    идентификатор не может начинаться с цифры;
    точка может быть только первым символом идентификатора;
    длина идентификатора – любая, но значащими являются только первые 8 символов;
    идентификатор не может совпадать ни с одним из ключевых слов, описанных выше.
Большие и маленькие буквы в тексте программы не различаются. Ни один из идентификаторов (в т.ч. идентификаторы констант перечислимых типов) не описывается дважды. Там, где допустим один пробел (перевод строки), допустимо любое количество пробелов и переводов строки.

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

Задание
Во входном файле находится программа на языке DDL, содержащая описания типов данных и констант. Длина программы не превышает 60 килобайт, а общее число идентификаторов в ней не более 100. Требуется написать программу, которая:
    1. Проверяет заданное описание на наличие ошибок и при наличии таковых выводит соответствующее сообщение в выходной файл.
    2. Если ошибок не обнаружено, то выводит в выходной файл все константы из исходной программы (определенные оператором Define constant) с указанием для каждой из них ее имени, списка имен возможных типов для этой константы и ее значения по формату: <имя константы>: <тип 1> {, <тип>} = <значение>.
    3. Если ни одного допустимого типа для заданной константы нет, то вместо списка возможных типов должен идти конструктор, описывающий любой из типов, соответствующих этой константе.
Имена констант и имена типов должны быть выведены строчными буквами. Имена констант должны следовать в алфавитном порядке (сначала цифры, потом по порядку буквы английского, затем русского алфавитов).

Пример входного файла
Define Constant целое=(23/54);
Define Type seq = sequence of integer; // Это комментарий
DeFiNe CoNsTaNt abc={12, 12, 14, 'Жюри', 'Жюри'} ;
Define Constant cba={6/2,14, 'Жюри'};
Define Type Тип_для_abc1 = sequence (integer, integer, integer, string, string );
Define Type Тип2 = sequence (optional integer, optional integer, optional string);
Define Type St=Set (integer, integer, integer, integer, string, string, string)
Define Type st2=set (integer, integer, string)
Define constant q={{123},{'Жюри'},{}}
Define Type Type1=sequence of Тип2

Пример выходного файла
abc: st, тип_для_abc1, тип_для_abc2 = {12, 12, 14, 'Жюри', 'Жюри'}
cba: st, st2, тип2 = {3, 14, 'Жюри'}
q: type1 = {{123}, {'Жюри'}, {}}
целое: integer = 0

Список ключевых слов Integer Char Boolean String True False Or And Not Sequence Set Multi Of Optional Plus Minus Mul Ord Chr Pred Succ Mod Define Constant Type

Приоритеты операций Not + - * / Mod And Mul + - Or @ Plus Minus < > = <= >= <> (унарные) (мультипликативные) (аддитивные) (сравнения) Высший Низший

Прислать комментарий

Решение

Страница: << 24 25 26 27 28 29 30 >> [Всего задач: 155]