|
IX Всеукраинская олимпиада по информатике Первый тур
Черный ящик
Вам задается программа BLACKBOX.EXE - черный ящик. Ее параметром из командной строки является неотрицательное целое число. На виходе программа видает неотрицательное целое число - значения некоторой неизвестной функции от аргумента, заданного на входе. Например: blackbox 4 1
Задание. Напишите программу WHITEBOX, реализующую ту же самую функцию, что и BLACKBOX.EXE. Программа должна читать из входного файла BB.DAT числа - аргументи и записывать в виходной BB.SOL значения функции, заданной в черном ящике, от аргументов. Ваша программа не должна визывать BLACKBOX.EXE. Входные данные. Входной файл BB.DAT в первой строке содержит N - количество тестов (N<256); во второй - первый тест и т. д. Тест - это неотрицательное целое число. Выходные данные. Выходной файл BB.SOL должен содержать N строкв, в каждой из которых находится результат обработки теста - значение функции. Технические условия. Ваша программа должна называться WHITEBOX.*, где расширение * зависит от языка программирования. Аргументы и значения функции - неотрицательные целые числа, которые могут быть поданы в диапазоне длинных целых (1..20000000000).
Пример ввода и вывода
Планирование найма работников
Предприниматель планирует штат работников на N недель. Известны минимальные потребности работников на эти недели b1, b2, ... ,bn. Все работники виполняют одинаковую работу и имеют одинаковую недельную заработную плату K денежных единиц (независимо от того, есть ли у них работа). Если на очередную неделю (включая первую неделю работи) необходимо нанять p работников дополнительно к предыдущей (p > 0), затраты на найм составят L+p*M единиц. Увольнение затрат не требует. Вначале работи работников нет. Задание. Напишите программу, которая по этим данным вычислит количества работников кажной недели c1, c2, ... , cn, требующие наименьших возможных затрат S. Входные данные. Входной тестовый ASCII - файл EMPLOY.DAT в первой строке содержит количество тестов, далее следуют данные всех тестов, не отделенные пустыми строками. Данные каждого теста - числа в отдельных строках файла в такой последовательности: K, L, M, N, b1, b2,..., bn. Выходные данные. Виходной текстовый ASCII - файл EMPLOY.SOL должен содержать результаты для всех тестов. Для каждого теста в первой строке должна быть минимальная общая сумма затрат S, в последующих N строках - оптимальные количества работников c1, c2, ... , cn. Результаты для последовательных тестов отделены пустой строкой. Технические условия. Файл Вашей программы должен называться EMPLOY.* , где * - PAS, C, CPP в зависимости от языка программирования. Числа K, L, M, N, b1, b2, ... , bn не превосходят 100.
Пример ввода и вывода
Цепные дроби
Записью (X1, X2, ... , Xn) обозначим действительное число, представленное в виде конечной цепной дроби:
1
X1 + __________________________
1
X2 + ____________________
1
X3 + ______________
1
... Xn-1 + ___
Xn
где X1, ... , Xn - положительные целые числа. Записью (X1, X2, ... ,Xn [Y1, Y2, ... , Yk]) обозначим число
1
X1 + _________________________________________________
1
X2 + ____________________________________________
1
... Xn + _____________________________________
1
Y1 + _________________________________
1
Y2 + ____________________________
1
... Yk + _____________________
1
Y1 + _______________
1
Y2 + __________
... Yk + ...
где X1, ..., Xm, Y1, ..., Yk - положительные целые числа, причем Xm не равно Yk. Это бесконечная периодическая цепная дробь. Минимальную конечную повторяющуюся последовательность Y1, Y2, ... , Yk, будем называть периодом дроби. Известно, что квадратный корень произвольного натурального числа можно однозначно представить в виде конечной цепной дроби либо бесконечной периодической цепной дроби. Например, корень квадратный из 36( Задание. Написать программу, которая для заданного натурального числа M находит представление Входные данные. Входной файл CHAIN.DAT в первой строке содержит L - количество тестов; во второй - первый тест и т.д. Тест- это положительное целое число от 1 до 100. Выходные данные. Выходной файл CHAIN.SOL должен содержать L строк, в каждой из которых находится результат обработки теста. Запятые и скобки (круглые и квадратные)должны быть размещены строго с соответствующей записью цепной дроби, без пробелов. Технические условия. Файл Вашей программы должен называться CHAIN.*, где расширение * зависит от языка программирования.
Пример ввода и вывода
Второй тур
Проверка слов.
Рассмотрим такие элементарные преобразования слов, записанных строчными латинскими буквами: 1. Замена произвольной буквы на любую другую, например test -> text. 2. Удаление любой буквы, например text -> ext, или text -> txt. 3. Вставка любой буквы в начало, в середину или в конец, например each -> peach, bat -> boat, или test -> tests. 4. Взаимная перестановка двух соседних букв, например cat -> act. Определим расстояние между двумя словами как минимальное количество названных элементарных преобразований, которые необходимо сделать над одним из слов, чтобы получить второе. Задание. Задано два файла - текст и словарь. Напишите программу, которая для каждого слова текста находит все слова из словаря, которые находятся от этого слова на наименьшем расстоянии. Входные данные. Текст содержится в текстовом ASCII - файле TEXT.DAT, каждая строка которого имеет длину не более 80 символов и может содержать несколько слов. Соседние слова в строке разделяются пробелом. Знаков пунктуации (точек, запятых и т.п.) нет. Словарь содержится в текстовом ASCII - файле LEX.DAT, первая строка которого содержит количество слов (она не превосходит 4000), а каждая последующая строка содержит отдельное слово длиной не более 20 символов. Слова упорядочены по алфавиту. Выходные данные. Результат необходимо вывести в текстовый ASCII - файл NEAREST.SOL с такой структурой. Для каждого слова из TEXT.DAT нужно вывести в отдельной строке минимальное расстояние до слов LEX.DAT, в следующей строке - количество ближайших слов из LEX.DAT, а далее - все ближайшие слова из LEX.DAT в отдельных строках в алфавитном порядке. Ответы для слов из TEXT.DAT необходимо выводить последовательно согласно с порядком слов в тексте, не отделяя их пустыми строками. Технические условия. Ваша программа должна называться NEAREST.* , где расширение * зависит от языка программирования.
Пример ввода и вывода.
|
) равен (6); корень квадратный из 7(
) равен (2[,1,1,1,4]). 
в виде цепной дроби (конечной или бесконечной периодической). Полный архив олимпиады (108 Kb)
© Всеукраинский виртуальный центр олимпиад школьников "ОЛІМП"