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

Задачи

Страница: << 50 51 52 53 54 55 56 >> [Всего задач: 277]

Задача 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 < > = <= >= <> (унарные) (мультипликативные) (аддитивные) (сравнения) Высший Низший

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

Решение

Задача 98680

[Сталкер]

Темы:	[	Кратчайшие пути в графах	]
Темы:	[	Построение графа	]

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

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

stalker.in

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

stalker.out

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

2 секунды

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

128 мегабайт

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

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

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

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

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

В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.

В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i - количество дорог, обозначенных на i-ой карте. Затем идут r_i строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r₁+ r₂ + ... + r_K ≤ 300 000).

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

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

Примеры

stalker.in	stalker.out		stalker.in	stalker.out
5 3 1 3 4 3 1 2 1 3 2 4 1 4 5	2		5 3 2 3 2 4 5 1 2 1 2 1 3 5 4	-1

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

Решение

Задача 98677

[Казино]

Тема:

[

Двойное динамическое программирование

]

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

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

casino.in

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

casino.out

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

2 секунды

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

64 мегабайта

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

100 баллов

Вновь открытое казино предложило оригинальную игру.

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

Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому - на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.

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

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

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

В первой строке входного файла записано число K (1 ≤ K ≤ 26) - количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число X_i (1 ≤ X_i ≤ 150, i = 1..K) - цена фишки соответствующего цвета.

В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задается L строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.

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

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

В выходной файл выведите единственное целое число - максимальную сумму денег, которую может получить игрок.

Пример

casino.in	casino.out
6 a 1 b 4 d 2 x 3 f 1 e 3 fxeeabadd 2 aba ed	16

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

Решение

Задача 66544

Темы:	[	Геометрия на клетчатой бумаге	]
Темы:	[	Перебор (прочее)	]

Сложность: 3
Классы: 6,7

Автор: Бакаев Е.В.

Царь пообещал награду тому, кто сможет на каменистом пустыре посадить красивый фруктовый сад. Об этом узнали два брата. Старший смог выкопать 18 ям (см. рис. слева). Больше нигде не удалось, только все лопаты сломал. Царь рассердился и посадил его в темницу. Тогда младший брат Иван предложил разместить яблони, груши и сливы в вершинах равных треугольников (см. рис. справа), а остальные ямы засыпать.

Царь ответил так:
— Хорошо, если деревьев каждого вида будет ровно по три и они будут расти в вершинах равных треугольников, выйдет красиво. Но три вида — слишком мало. Если кроме яблонь, груш и слив будут ещё и абрикосы — отпущу брата. Если добавишь пятый вид — черешню — заплачу за работу. Мне ещё миндаль нравится, но шесть треугольников ты тут не сможешь разместить.
— А если смогу?
— Тогда проси чего хочешь!
Иван задумался, не получить ли заодно и полцарства. Подумайте и вы: разместите как можно больше видов деревьев в вершинах равных треугольников. (Равенство треугольников означает равенство всех его сторон и углов, то есть точное совпадение при наложении; треугольники можно поворачивать и переворачивать. В одной яме может расти только одно дерево.)

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

Задача 66715

Темы:	[	Теория чисел. Делимость (прочее)	]
Темы:	[	Десятичная запись числа	]

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

Автор: Евдокимов М.А.

Назовём девятизначное число красивым, если все его цифры различны.
Докажите, что существует по крайней мере а) 1000; б) 2018 красивых чисел, каждое из которых делится на 37.

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

Решение

Страница: << 50 51 52 53 54 55 56 >> [Всего задач: 277]