Вологда 1998

Задача 1 "Частотный словарь"(25 баллов). Литературное произведение на русском языке записано в текстовом файле INPUT.TXT (размер файла до 1 Мб). Получить и записать в файл OUTPUT.TXT частотный словарь этого произведения, то есть алфавитный перечень слов (словоформ), встречающихся в тексте с указанием того, сколько раз входит в текст данное слово (словоформа). Словом считается последовательность букв, не содержащая пробелов и знаков препинания. Слова в исходном файле не переносятся.

Время работы программы не должно превышать 1 минуту.

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

Файл INPUT.TXT

Файл OUTPUT.TXT

ЦВЕТЫ По утрам умываясь росой, Как цвели они! Как красовались! Но упали они под косой, И спросил я: — А как назывались? И мерещилось многие дни Что-то тайное в этой развязке: Слишком грустно и нежно они Назывались "анютины глазки".

а             1 анютины       1 в             1 глазки        1 грустно       1 дни           1 и             3 как           3 косой         1 красовались   1 мерещилось    1 многие        1 назывались    2 нежно         1 но            1 они           3 по            1 под           1 развязке      1 росой         1 слишком       1 спросил       1 тайное        1 то            1 умываясь      1 упали         1 утрам         1 цвели         1 цветы         1 что           1 этой          1 я             1

Задача 2 "Языки"(25 баллов). Выражения языка L записываются по обычным правилам и строятся с помощью знаков арифметических действий +, –, *, / и круглых скобок. Операнды обозначаются буквами латинского алфавита. Выражения функционального языка F записываются только с помощью функций ADD(x,y) – сложение; SUB(x,y) – вычитание; MUL(x,y) – умножение; DIV(x,y) – деление, где x и y – выражения языка F. Ни в языке L, ни в языке F одноместные операции не предусмотрены.

Дана строка длиной до 80 символов, содержащая правильное выражение языка L. Получить запись этого выражения на языке F.

Пример правильной работы программы:

Введите выражение языка L: a + (b-c)/(c*d)

ADD(a,DIV(SUB(b,c),MUL(c,d)))

Задача 3 "Спички"(15 баллов). Имеется кучка из N (N <=10000) спичек. Двое играют в следующую игру. Ходят по очереди. За один ход играющий может взять из кучки спички в количестве pⁿ, где p – простое число, n=0, 1, 2, 3, ... (например, первый берет 25 спичек, второй – 27, первый – 1, второй – 5, первый – 32 и т. д.). Выигрывает тот, кто берет последнюю спичку. Составить программу реализующую игру в режиме человек-компьютер. Постараться разработать за компьютер оптимальный алгоритм. Программа должна проверять корректность ходов.

	y
	x

Задача 4 "Коробки"(20 баллов). Фирма занимается производством коробок, используя в качестве сырья квадратные стальные листы со стороной а. Для изготовления коробки из листа по его углам вырезают одинаковые квадраты, из полученной крестовидной заготовки сгибанием и свариванием получают готовое изделие. Вырезанные квадратные куски металла можно затем либо продать, либо использовать для изготовления коробок поменьше таким же способом и т.д. Из квадратиков не больше 5 см коробки уже не делают, но продать их можно. Как фирме следует распорядиться исходным листом, чтобы суммарный доход от продажи коробок и оставшихся квадратов был максимальным?

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

Соглашения.

Считается, что цена коробки пропорциональна ее объему v, затраты на вырезание и сваривание пропорциональны высоте y, а затраты на изгибание пропорциональны стороне основания коробки x. Выходит, цена коробки равна pv–lx–my. Цена металлического квадрата пропорциональна его площади (qS). p, l, m, q – заданные неотрицательные коэффициенты. Размеры задаются в сантиметрах, цены получаются в копейках.

Считается, что все размеры коробок и листов выражаются целым числом сантиметров. Размеры сторон листа не больше 3 метров. Соотношение между стороной основания и высотой коробки может быть любым (любые коробки пользуются устойчивым спросом).

Значения коэффициентов p, l, m, q и сторона стального листа а вводятся с клавиатуры. Результаты выводятся на экран.

Например:

при p=0.1, l=m=0.2, q=0.015, a=200 получаем:

Размеры квадратов 35, 6, 1. Доход 60374 коп.

Задача 5. "База данных"(15 баллов). База данных содержит одно поле, имеющее смысл даты, (часть дат записана в американском формате, часть в германском, часть в итальянском) и поле данных числового типа. Базу можно представить в одном из двух различных форматов: текстовом или .dbf.

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

Форматы дат имеют следующий вид:

Американский: <месяц>/<день>/<год> (05/23/97)
Германский: <день>.<месяц>.<год> (23.05.97)
Итальянский: <день>-<месяц>-<год> (23-05-97)