Вам задается программа BLACKBOX.EXE - черный ящик. Ее параметром из командной строки является неотрицательное целое число. На виходе программа видает неотрицательное целое число - значения некоторой неизвестной функции от аргумента, заданного на входе.

Предприниматель планирует штат работников на N недель. Известны минимальные потребности работников на эти недели b₁, b₂, ... ,b_n. Все работники виполняют одинаковую работу и имеют одинаковую недельную заработную плату K денежных единиц (независимо от того, есть ли у них работа). Если на очередную неделю (включая первую неделю работи) необходимо нанять p работников дополнительно к предыдущей (p > 0), затраты на найм составят L+p*M единиц. Увольнение затрат не требует. Вначале работи работников нет.

Задание. Напишите программу, которая по этим данным вычислит количества работников кажной недели c₁, c₂, ... , c_n, требующие наименьших возможных затрат S.

Входные данные. Входной тестовый ASCII - файл EMPLOY.DAT в первой строке содержит количество тестов, далее следуют данные всех тестов, не отделенные пустыми строками. Данные каждого теста - числа в отдельных строках файла в такой последовательности: K, L, M, N, b₁, b₂,..., b_n.

Выходные данные. Виходной текстовый ASCII - файл EMPLOY.SOL должен содержать результаты для всех тестов. Для каждого теста в первой строке должна быть минимальная общая сумма затрат S, в последующих N строках - оптимальные количества работников c₁, c₂, ... , c_n. Результаты для последовательных тестов отделены пустой строкой.

Технические условия. Файл Вашей программы должен называться EMPLOY.* , где * - PAS, C, CPP в зависимости от языка программирования. Числа K, L, M, N, b₁, b₂, ... , bn не превосходят 100.

Записью (X₁, X₂, ... , X_n) обозначим действительное число, представленное в виде конечной цепной дроби:

                     1 
X1 + __________________________ 
                       1 
    X2 + ____________________ 
                          1 
        X3 + ______________ 

                               1 
     ...         Xn-1 +  ___ 
                                Xn 
  

где X₁, ... , X_n - положительные целые числа.

Записью (X₁, X₂, ... ,X_n [Y₁, Y₂, ... , Y_k]) обозначим число

                                                         1 
X1 + _________________________________________________ 
                                                        1 
   X2 + ____________________________________________ 
                                                      1
 ...   Xn + _____________________________________
                                                    1 
          Y1 + _________________________________
                                                  1
            Y2 + ____________________________ 
                                                1
             ...    Yk + _____________________ 
                                               1 
                         Y1 + _______________
                   	               1 
                             Y2 + __________ 
                                     ... Yk + ... 

где X₁, ..., X_m, Y₁, ..., Y_k - положительные целые числа, причем X_m не равно Y_k. Это бесконечная периодическая цепная дробь. Минимальную конечную повторяющуюся последовательность Y₁, Y₂, ... , Y_k, будем называть периодом дроби.

Известно, что квадратный корень произвольного натурального числа можно однозначно представить в виде конечной цепной дроби либо бесконечной периодической цепной дроби. Например, корень квадратный из 36() равен (6); корень квадратный из 7() равен (2[,1,1,1,4]).

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

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

Задание. Задано два файла - текст и словарь. Напишите программу, которая для каждого слова текста находит все слова из словаря, которые находятся от этого слова на наименьшем расстоянии.

Входные данные. Текст содержится в текстовом ASCII - файле TEXT.DAT, каждая строка которого имеет длину не более 80 символов и может содержать несколько слов. Соседние слова в строке разделяются пробелом. Знаков пунктуации (точек, запятых и т.п.) нет.

Словарь содержится в текстовом ASCII - файле LEX.DAT, первая строка которого содержит количество слов (она не превосходит 4000), а каждая последующая строка содержит отдельное слово длиной не более 20 символов. Слова упорядочены по алфавиту.

Выходные данные. Результат необходимо вывести в текстовый ASCII - файл NEAREST.SOL с такой структурой. Для каждого слова из TEXT.DAT нужно вывести в отдельной строке минимальное расстояние до слов LEX.DAT, в следующей строке - количество ближайших слов из LEX.DAT, а далее - все ближайшие слова из LEX.DAT в отдельных строках в алфавитном порядке. Ответы для слов из TEXT.DAT необходимо выводить последовательно согласно с порядком слов в тексте, не отделяя их пустыми строками.

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