Университет | Вологодские школьные олимпиады по информатике
Содержание | Положение об олимпиаде-1999 | 1998 | 1999 | 2000 | 2001 | 2002 | 2003 | 2004 | 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017

Задачи Онлайн-проверка решений Результаты

I Межвузовская олимпиада по программированию
Вологда 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) спичек. Двое играют в следующую игру. Ходят по очереди. За один ход играющий может взять из кучки спички в количестве pn, где p – простое число, n=0, 1, 2, 3, ... (например, первый берет 25 спичек, второй – 27, первый – 1, второй – 5, первый – 32 и т. д.). Выигрывает тот, кто берет последнюю спичку. Составить программу реализующую игру в режиме человек-компьютер. Постараться разработать за компьютер оптимальный алгоритм. Программа должна проверять корректность ходов.

 

  y

 
 

 x 

 
    
 
 

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

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

Соглашения.

  • Считается, что цена коробки пропорциональна ее объему v, затраты на вырезание и сваривание пропорциональны высоте y, а затраты на изгибание пропорциональны стороне основания коробки x. Выходит, цена коробки равна pvlxmy. Цена металлического квадрата пропорциональна его площади (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)


    Также доступен текст задач в формате gif: страница 1, страница 2.
    Задачи Онлайн-проверка решений Результаты

    Университет | Вологодские школьные олимпиады по информатике
    Содержание | Положение об олимпиаде-1999 | 1998 | 1999 | 2000 | 2001 | 2002 | 2003 | 2004 | 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017