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

Задачи

Страница: 1 2 >> [Всего задач: 8]

Задача 102784

[Пустоты в кубе ]

Темы:	[	Разбор регулярных выражений	]
Темы:	[	Динамическое программирование (прочее)	]

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

Жюри составило отчет об учебно-тренировочных сборах по информатике и собирается распечатать его на стандартном листе бумаги. Весь отчет набран одним моноширинным шрифтом, т.е. все символы (включая пробелы) имеют одинаковую ширину. Длина строки при печати этим шрифтом на листе бумаги равна S.

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

Для достижения требуемого расположения текста на бумаге разрешается заменять произвольную пробельную последовательность (т.е. непустую последовательность подряд идущих пробелов и/или символов перевода строки) любой другой пробельной последовательностью.

Входные данные
Первая строка входного файла содержит целое число S (1 ≤ S ≤ 80). В последующих строках записан отчет, содержащий не более 500 слов. Длина каждой строки отчета не превосходит 250 символов, а длина каждого слова не превосходит S.

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

Пример входного файла
30
Победители летних учебно-тренировочных сборов по
информатике 1997 г.:
Владимир Мартьянов,
Анатолий Пономарев,
Николай Дуров, Андрей Лопатин.

Пример выходного файла
325
Победители летних
учебно-тренировочных сборов по
информатике 1997 г.: Владимир
Мартьянов, Анатолий Пономарев,
Николай Дуров, Андрей Лопатин.

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

Задача 102954

[Калькулятор дат ]

Тема:

[

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

]

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

Современные системы управления базами данных поддерживают широкий класс различных операций с датами. Для решения этой задачи Вы должны написать программу, реализующую некоторые из таких операций. Ваша программа должна обрабатывать выражения следующих типов:
    <Дата>
    <Дата> + <Сдвиг>
    <Дата> - <Сдвиг>
    <Дата> - <Дата>

Здесь <Дата> задается в одном из следующих трех форматов:
А) дд.мм.гггг (например, 21.06.1998 ). В этой записи день и месяц задаются в точности двумя десятичными цифрами, год – ровно четырьмя.
Б) д месяца г года (например, 21 июня 1998 года ). В этом формате могут присутствовать ведущие нули (например, 01 июня 198 года ).
В) сегодня – текущая дата, установленная в компьютере.
<Сдвиг> задается в виде [L лет ] [M месяцев ] [N недель ] [D дней ]. Квадратные скобки здесь означают, что некоторые из указанных четырех составных частей могут опускаться (но не все сразу). Слова «лет», «месяцев», «недель», «дней» склоняются по правилам русского языка: 1 год, 5 лет, 2 месяца, 5 месяцев и т.д.

Значением выражений первых трех типов является дата. В случае выражения первого типа значением является сама <Дата>. В случае выражений второго и третьего типа вычисление искомой даты происходит следующим образом: сначала прибавляется (либо вычитается) L лет, затем M месяцев, после чего N недель и, наконец, D дней. Если в течение этого процесса получается несуществующее число месяца, то берется последнее число этого месяца (см. пример). Результатом выражения четвертого типа является количество дней между двумя указанными датами.

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

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

Пример входного файла
30 января 1998 года + 1 месяц 1 день
21 июня 1998 года - 1.06.1998

Пример выходного файла
1 марта 1998 года, воскресенье
20

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

Задача 102785

[Шаблоны с ? и * ]

Темы:	[	Разбор регулярных выражений	]
Темы:	[	Динамическое программирование (прочее)	]

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

Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.

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

Входные данные
Заданные шаблоны записаны в первых двух строках входного файла. Длина каждого шаблона не превосходит 80 символов.

Выходные данные
В выходной файл следует вывести строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение «Строки не
существует!»

Пример входного файла
A*
*B

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

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

Задача 102956

[Типы данных ]

Тема:

[

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

]

Сложность: 4

Тип данных в языке Pascal представляет собой древовидную структуру, в листьях которой записаны базовые (предопределенные) типы данных (такие, как Integer или Char), а во внутренних узлах – конструкторы, позволяющие из одних типов данных строить другие (например, Array или Record). Вершины, соответствующие листьям, называются элементами данного типа. Имеются описания типов данных, взятые из первых строк программы, написанной на языке Turbo Pascal 7.0 (см. пример входного файла), и последовательность запросов, каждый из которых касается одного из описанных типов.

Всего существует три вида запросов:
    SizeInBytes(<Имя типа>) – определить, какое количество байт памяти занимает переменная указанного типа;
    SizeInBits(<Имя типа>) – найти количество бит, необходимых для хранения переменной указанного типа при условии, что для каждого элемента этой переменной отводится минимально возможное число бит, способных закодировать все возможные значения этого элемента;
    <Имя типа>($<Последовательность 16-х цифр>) – по дампу (т.е. содержимому) участка памяти, занимаемому переменной указанного типа, определить значения всех элементов этой переменной.
Напишите программу, которая вводит описания типов данных и обрабатывает заданную последовательность запросов. Описания типов не будут содержать типов-указателей, типов-файлов, типов-объектов и процедурных типов.

Процесс разработки Вашей программы постройте по следующей схеме:
    А) Научите Вашу программу воспринимать стандартные типы данных, используемые в языке Turbo Pascal 7.0.
    Б) Введите перечислимый тип и тип-диапазон, граничные значения которого заданы константами.
    В) Реализуйте конструкторы типов данных.
    Г) Добавьте возможность использования функций и операций при построении константного выражения.
    Д) Реализуйте остальные возможности, допускаемые языком.

Входные данные
Входной файл начинается с ключевого слова «Definitions», за которым следуют описания типов данных. Далее следует ключевое слово «Queries» и список запросов. Каждый запрос записан в отдельной строке входного файла. Учтите, что длина строки с запросом может превышать 255 символов.

Выходные данные
Ваша программа должна вывести в выходной файл результаты обработки запросов в том же порядке, в котором запросы встречаются во входном файле.
На запрос первого или второго вида в отдельную строку выходного файла следует выдать сообщение «Type <Имя типа> requires x bytes/bits», где
x – искомое целое число. На запрос третьего вида необходимо перечислить значения всех элементов переменной указанного типа в том порядке, в котором эти элементы хранятся в оперативной памяти. Для каждого из элементов в отдельную строку выходного файла следует выдать строку «<Имя элемента> = <Значение>». Формат выходного файла должен соответствовать приведенному ниже примеру.

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

Definitions

Type TClass = 1..11;
TScore = 0..100;
TTour = 1..10;
TStrange =
Array [1..SizeOf(Input)
Div Ord('A')]
Of Boolean;
TExample =
Record a :
Array [1..2]
Of
Record b,c :
Set
Of 0..2
End

End ;
TShortStr =
String [3];

Type TParticipant =
Record
Sex : (Male, Female);
Name :
String [20];
Class : TClass;
Place : ShortInt;
TotalSum : 0..High(TScore)*(High(TTour)-Low(TTour)+1);
DayScores :
Array [TTour]
Of TScore;

End ;

{ Команда России для участия в международной олимпиаде }
TTeam =
Array [1..5]
Of TParticipant;

Queries
SizeInBytes(TStrange)
SizeInBits(TClass)
SizeInBits(TShortStr)
TParticipant( $ 01118AAEABECE6AEA2A02091A2A5E2ABA0ADA00000000A0B4501461D082319501C280A00 )
TExample( $01020304 )
SizeInBits(TParticipant)

Пример выходного файла
Type TStrange requires 3 bytes
Type TClass requires 4 bits
Type TShortStr requires 26 bits
Sex = Female
Name = 'Кольцова Светлана'
Class = 10
Place = 11
TotalSum = 325
DayScores[1] = 70
DayScores[2] = 29
DayScores[3] = 8
DayScores[4] = 35
DayScores[5] = 25
DayScores[6] = 80
DayScores[7] = 28
DayScores[8] = 40
DayScores[9] = 10
DayScores[10] = 0
a[1].b = [0]
a[1].c = [1]
a[2].b = [0,1]
a[2].c = [2]
Type TParticipant requires 258 bits

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

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

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

Решение

Страница: 1 2 >> [Всего задач: 8]