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).

 

Пример ввода и вывода

 

BB.DAT

BB.SOL

3

7

36

5

0

1

0

 

 

 

 

Планирование найма работников

 

Предприниматель планирует штат работников на 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.

 

Пример ввода и вывода

 

EMPLOY.DAT

EMPLOY.SOL

2

3

4

2

5

5

7

123{перший тест}

5

8

8

6

6

 

8

4

6

1 {другий тест}

1

1

3

2

2

9 {другий тест}

2

2

2

 

 

 

Цепные дроби

 

Записью (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() равен (6); корень квадратный из 7() равен (2[,1,1,1,4]).

Задание. Написать программу, которая для заданного натурального числа M находит представление в виде цепной дроби (конечной или бесконечной периодической).

Входные данные. Входной файл CHAIN.DAT в первой строке содержит L - количество тестов; во второй - первый тест и т.д. Тест- это положительное целое число от 1 до 100.

Выходные данные. Выходной файл CHAIN.SOL должен содержать L строк, в каждой из которых находится результат обработки теста. Запятые и скобки (круглые и квадратные)должны быть размещены строго с соответствующей записью цепной дроби, без пробелов.

Технические условия. Файл Вашей программы должен называться CHAIN.*, где расширение * зависит от языка программирования.

 

Пример ввода и вывода

CHAIN.DAT

CHAIN.SOL

3

7

36

5

(2[,1,1,1,4])

(6)

(2[,4])

 

 

 

Второй тур

 

Проверка слов.

 

Рассмотрим такие элементарные преобразования слов, записанных строчными латинскими буквами:

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.* , где расширение * зависит от языка программирования.

 

Пример ввода и вывода.

 

TEXT.DAT

LEX.DAT

NEAREST.SOL

the quick brown

fox jumps over

the lazy dog

 

 

 

 

 

 

 

11

box

crazy

crown

god

grow

jump

overflow

overlap

overload

ox

queen

the

0

1

the

3

1

queen

1

1

crown

1

2

box

ox

1

1

jump

3

3

overlap

ox

0

1

the

2

1

crazy

2

3

box

god

ox

Повний архів олімпіади (180 Kb)


© Всеукраинский виртуальный центр олимпиад школьников "ОЛІМП"

© LIKT 1998-2018