II Олимпиада школьников Ленинграда по информатике

Ленинград, 1987 года

Задачи

Введение

В 1987 году олимпиада проводилась в три тура. Первый тур проводился по школам, причем единые для всех задачи не предлагались. Второй тур проводился по районам, предлагались задачи 10-12, вариант А, а для тех школ, чьи ученики успешно выступили в 1986 году, он проводился по школам с усложненными задачами (вариант Б). Третий тур проводился аналогично второму туру 1986 года, задачи 13-15.

Второй тур

Задача 10

Вариант А

Имеется N карточек. На каждой стороне каждой карточки написано одно целое число. Известно, что каждое из чисел 1, 2, ..., N встречается на карточках дважды. Требуется узнать, можно ли карточки выложить так, чтобы каждое из чисел 1, 2, ..., N было на верхней стороне одной из карточек; если можно, то указать для каждой карточки, как ее класть.

Вариант Б

Имеется N тетраэдров. На каждой грани каждого тетраэдра написано одно целое число. Известно, что каждое из чисел 1, 2, ..., N встречается на тетраэдах четыре раза. Требуется узнать, можно ли поставить тетраэдры на стол так, чтобы каждое из чисел 1, 2, ..., N было на верхних гранях трижды; если можно, то указать для каждого тетраэдра, как его ставить.

Задача 11

Вариант А

На клетчатой бумаге нарисовали окружность целого радиуса R с центром на пересечении линий. Найти K - количиство клеток, целиком лежащих внутри этой окружности.

Пример. Если R=5, то K=60.

Вариант Б

Трехмерное пространство разбито на кубики с ребром длины 1. Сколько из них помещается в сфере радиуса R, центр которой находится в вершине одного из кубиков?

Пример. В сфере радиуса 3 помещается 56 кубиков.

Задача 12

Вариант А

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

Вариант Б

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

Третий тур

Задача 13

На прямой окрасили N отрезков. Известны координата Li левого конца и координата Ri правого конца i-го отрезка для i = 1, 2, ..., N. Найти сумму длин всех окрашенных частей прямой.

Примечание. Число N столь велико, что на выполнение N 2 даже простейших операций не хватит времени.

Модификация. На окружности окрасили N дуг. Известны угловая координата Li начала и Ri конца i-ой дуги (от начала к концу двигались, закрашивая дугу, против часовой стрелки). Какая доля окружности окрашена?

Задача 14

Дана последовательность из N целых чисел, среди которых нет двух одинаковых. Требуется вычеркнуть минимально возможное количество чисел так, чтобы оставшиеся шли в порядке возрастания. На печать следует выдать K - количество оставшихся чисел и их самих в порядке из следования.

Примечание. Число N столь велико, что на выполнение N 2 даже простейших операций не хватит времени.

Модификация. Даны N положительных целых чисел. которые не делятся ни на какие простые числа, кроме 2 и 3. Требуется выкинуть минимально возможное количество чисел так, чтобы из любых двух оставшихся одно делилось на другое.

Задача 15

Нарисовать при помощи символа "звездочка" периодический узор в форме пчелиных сот, состоящий из одинаковых шестиугольников, максимально близких к правильным. Горизонтальные стороны шестиугольников должны быть образованы 2W + 1 звездочками, узор должен занимать L строк длиной 78 символов каждая (печатающее устройство может печатать до 80 символов в строке). Отношение расстояния по вертикали между соседними звездочками к расстоянию по горизонтали между соседними звездочками равно H.

Модификация. Будем считать, что соты рисовали не "звездочкой", а символом "восклицательных знак", а полученная распечатка - обои, которыми надо оклеить стену шириной M символов и высотой N строк. Каково минимальное значение L, которого вам для этого хватит?