X городская олимпиада школьников
Санкт-Петербурга по информатике

5 февраля 1995 года

Теоретический тур

Задачи

Задача A. Лесенки

Исходные данные - натуральное число N. Составьте программу, которая вычисляет количество различных лесенок, состоящих ровно из N одинаковых кубиков. Здесь лесенка - это набор из ступенек, размер которых уменьшается снизу вверх. Лесенка содержит по крайней мере две ступеньки, ступенька состоит по крайней мере из одного кубика. На рисунке приведен пример такой лесенки для N=11, а для N=5 таких лесенок две.

Задача B. Нули и единицы

Рассматриваются цепочки из нулей и единиц одинаковой (большой) длины. Над ними можно выполнять следующие операции:

• NOT - все нули заменяются единицами, а единицы - нулями (у этой операции один аргумент);
• AND - операция с двумя аргументами: числа, стоящие в одинаковых местах, умножаются, и полученное число записывается в то же место результата;
• OR - операция с двумя аргументами: числа, стоящие в одинаковых местах, сравниваются, и наибольшее из них записывается в то же место результата. Таким образом, OR(a, b) = NOT(AND(NOT(a), NOT(b))).

Напишите программу, которая вводит натуральное число N (N ≤ 1995), четыре цепочки a, b, c и d длины N и определяет:

1. можно ли последовательным применением перечисленных операций получить d из a, b и c;
2. при утвердительном ответе строит нужную последовательность операций (достаточно одной последовательности).

Пример 1. Для N=6, a=011000, b=111010, c=010001 и d=100010, вывод программы может быть следующим:

    
(1) Да 
(2) AND(NOT(a),OR(b,a)) 

Пример 2. Для N=6, a=011000, b=111010, c=010001 и d=000010, ответ на пункт (1) отрицательный.

Задача C. Двоичная яблоня

Яблоня называется двоичной, если в каждой точке ветвления ствол или ветвь разветвляется надвое. Точки ветвления, корень и концы веток - это узлы дерева. Известна масса каждого участка яблони между двумя соседними узлами. Первоначально в яблоне N узлов, а нужно оставить M. Яблоню можно резать в основаниях ветвей, при этом ветвь и вся часть дерева, растущая выше, удаляются.

Исходные данные: N, M (1 < M < N ≤ 100) и список из N-1 тройки. Каждая тройка содержит номера узлов, определяющих участок и его массу (узлы перенумерованы от 1 до N).

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

Например, для исходных данных: N=8, M=3 и набора троек (1, 2, 19), (2, 4, 13), (3, 2, 12), (3, 8, 17), (3, 6, 11), (5,8,10) и (8,7,8), вывод программы может быть следующим:

    
Обрезать ветки: (2,4),(3,8),(3,6).