Задачи второго тура
III-го этапа Всероссийской олимпиады школьников по информатике
(10-11 класс, 2005-2006 учебный год, Пермская область)

Задача A. Фибоначчиевая система счисления

Имя входного файла:	                  input.txt
Имя выходного файла:	                  output.txt
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти:	  64 мегабайта

Алфавит фибоначчиевой системы счисления состоит из двух цифр: 0 и 1, базисом являются числа последовательности Фибоначчи (в этой последовательности каждое число равно сумме двух предыдущих) – 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Написать программу, позволяющую перевести натуральное десятичное число, меньшее 1000000, в фибоначчиеву систему счисления. Если для некоторого числа имеется несколько представлений, то вывести все их в отдельной строке, расположив в порядке возрастания.

Формат входных данных

В каждой строке входного файла расположено по одному десятичному числу. Строк в файле не более 1000.

Формат выходных данных

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

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

input.txt	output.txt
2		10
5		110 1000
30		111101 1001101 1010001
4		101

Задача B. «Разрезание торта»

Имя входного файла:	                  input.txt
Имя выходного файла:	                  output.txt
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти:	  64 мегабайта

Мама испекла Мише на день рождения торт. Торт имеет форму выпуклого многоугольника с n вершинами. Вместе с гостями и родственниками у Миши на празднике оказалось k человек. В нужный момент Миша планирует разрезать торт на k частей. Каждый разрез должен представлять собой диагональ исходного многоугольника. Чтобы торт не развалился, разрезы не должны пересекаться нигде, кроме как в вершинах торта.

Как юного математика, Мишу заинтересовал вопрос — сколько существует способов разрезания торта на k частей указанным выше способом. Порядок выполнения разрезов не важен. Помогите Мише найти ответ на интересующий его вопрос.

Требуется написать программу, которая по заданным значениям чисел n и k определяет количество способов разрезания на k частей торта с n вершинами, как указано выше.

Формат входных данных

Входной файл содержит два целых числа n и k (1 ≤ k ≤ n ≤ 50, n ≥ 3).

Формат выходных данных

Выведите в выходной файл одно число — искомое количество способов разрезания торта.

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

input.txt	output.txt
4 2	2
6 4	14
3 2	0

Пояснение к примерам.

Все способы разрезания торта с шестью вершинами на четыре части приведены на следующем рисунке.

Задача C. Судоку

Имя входного файла:	                  input.txt
Имя выходного файла:	                  output.txt
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти:	  64 мегабайта

В нашей стране все большую популярность приобретает цифровая головоломка судоку (в переводе с японского «су» – цифра, «доку» – стоящая отдельно). Судоку покорила всю Европу и пришла к нам. Для ее решения нужно просто заполнить пустые клетки цифрами от 1 до 9 таким образом, чтобы в любой строке, любом столбце и любом блоке 3×3, выделенном на рисунке, не было двух одинаковых цифр.

Например, для поля, изображенного на рисунке

Напишите программу, решающую головоломку судоку, если известно, что количество пустых клеток в каждом из столбцов гарантированно не превышает пяти, а для всех предложенных примеров существует единственное решение.

Формат входных данных

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

Формат выходных данных

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

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

Задача D. Код Хаффмана

Имя входного файла:	                  input.txt
Имя выходного файла:	                  output.txt
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти:	  64 мегабайта

Дэвид Хаффман, возглавлявший кафедру компьютерных наук Массачусетского технологического института, широко известен как разработчик метода построения минимально избыточных кодов. Использование метода Хаффмана для кодирования текстовой информации, позволяет сократить объем, занимаемой текстом, за счет того, что часто встречающиеся символы кодируются более короткими кодами, а редко встречающиеся – более длинными. Для определения кодов символов подсчитывается частота встречаемости каждого символа в тексте и на основе этих частот строится дерево кодирования. Алгоритм построения дерева Хаффмана:

1. Символы входного алфавита образуют список свободных узлов. Каждый узел имеет вес, равный количеству вхождений символа в исходное сообщение.
2. В списке выбираются два свободных узла с наименьшими весами, после чего создается их узел – «родитель» с весом, равным сумме их весов, он соединяется с «потомками» дугами.
3. Одной дуге, выходящей из «родителя», ставится в соответствие бит 1, другой – бит 0.
4. «Родитель» добавляется в список свободных узлов, а двое его «потомков» удаляются из этого списка.
5. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Пример.

Построение дерева Хаффмана для текста «КOL_ОКОLО_КОLОКОLА»:

Дерево Хаффмана, получаемое в итоге:

Теперь для определения кода каждой конкретной буквы необходимо просто пройти от вершины дерева до этой буквы, выписывая нули и единицы по маршруту следования. В нашем примере символы получат следующие коды:

После кодирования исходного текста получим:

Таким образом, весь текст будет занимать 39 бит памяти, приблизительно 5 байт. Для сравнения: при использовании таблицы ASCII-кодов для хранения этого текста потребовалось бы 18 байт и коэффициент сжатия в нашем случае равен 18 / 5 = 3,6. Для восстановления сжатых данных так же необходимо воспользоваться деревом Хаффмана, полученным в самом начале.

Если построенное дерево Хаффмана содержит всего один узел (корень), не имеющий потомков, считать, что символ, соответствующий этому узлу кодируется одним битом, например, кодом 0.

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

Формат входных данных

Во входном файле находится сжимаемый текст. Признаком окончания текста служат символ #. В тексте могут встречаться только заглавные латинские буквы, пробел и знаки препинания ( . , : ; ! ? – “). Текст может состоять из нескольких строк. Строк в тексте не более 25, символов в одной строке не более 80. Символы перевода строки и возврата каретки, а также символ # не должны учитываться в исходном тексте.

Формат выходных данных

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

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

input.txt		output.txt
КОL ОКОLО КОLОКОLА#	39