III Всероссийская олимпиада школьников по информатике

Красноярск, 1991 год,

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

1. "Черный ящик". (Степанов В.И.) На вход "черного ящика" подается любая таблица, содержащая символы латинского алфавита. На выходе получается 3 строки результата. Например:

а) , б) .

Опишите алгоритм, по которому мог бы работать этот "черный ящик".

2. "Караван". (Шостак Г.А.) Географическая карта местности задана квадратной сеткой определенного масштаба. В узлах сетки известна высота над уровнем моря. Между соседними узлами высота меняется плавно. Караван перемещается только по линиям сетки. (Перемещение по диагонали запрещается). Путь между двумя соседними точками с углом наклона больше 45 градусов считается непроходимым.

Провести караван из точки А(X1, Y1) в точку В(X2, Y2) по пути с наименьшим перепадом высоты или сообщить об отсутствии решения.

Примечание: Перепадом высот на маршруте называется разность высот между самой высокой и самой низкой точками маршрута.

3. "Царевна". (Шепелевский А.С.) В одной из клеток поля n*n (n>1) Кощей Бессмертный спрятал Марью Царевну, создав еще неизвестное число m (1<m<п*n) ее двойников в различных свободных клетках. И царевна, и ее двойники одинаково надежно укрыты и невидимы.

Отправившийся на поиски царевны Иванушка-дурачок попросил у благоволящей к нему щуки датчик биосигналов. Известно, что и Марья Царевна и ее двойники испускают незатухающие направленные биолучи, распространяющиеся параллельно сторонам и диагоналям поля.

Иванушка-дурачок также знает, что интенсивность биолуча Марьи Царевны в m раз выше интенсивности биолучей двойников. Иванушка может установить свой датчик в любую клетку поля и получить величину суммарной интенсивности биолучей, приходящих в клетку.

Помогите Иванушке определить местонахождение настоящей царевны.

4. "Часы". (Сенокосов А.И.) Фирма "Школьник" предлагает разработать для электронных часов младших школьников режимы работы и трехкнопочную систему управления ими.

Опишите режимы работы часов, содержание отображаемой информации в каждом из режимов, функции кнопок.

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

Практический тур

1. "Удав". (Жданов С.А.) Прямоугольная область задана своими координатами: (X1,Y1) - левая верхняя вершина и (X2,Y2) - правая нижняя вершина. По границе области ползет удав длины L со скоростью V. Внутри области движется точка со скоростью V1. Точка начинает движение вниз от границы области на заданном расстоянии S от ее верхнего левого угла и под углом A к нижней линии области. Точка движется, отражаясь от стенок до тех пор, пока не столкнется с удавом. Объекты начинают движение одновременно.

Составить программу, вычисляющую количество отражений точки от границ области и время до столкновения с удавом. Если при стократном отражении точка не столкнулась с удавом, программа прекращает работу, сообщив об этом событии.

2. "Полоска". (Ватолин Д., Прохоров В.В.) Расположенную вертикально прямоугольную бумажную ленточку с закрепленным нижним концом стали складывать следующим образом:

- на первом шаге ее согнули пополам так, что верхняя половина легла на нижнюю либо спереди (П - сгибание) либо сзади (З - сгибание),

- на последующих n-1 шагах выполняли аналогичное действие с получающейся на предыдущем шаге согнутой ленточкой, как с единым целым.

Затем ленточку развернули , приведя ее в исходное состояние. На ней остались сгибы - ребра от перегибов, причем некоторые из ребер оказались направленными выпуклостью к нам (К - ребра), а некоторые - от нас (О -ребра). Ребра пронумеровали сверху вниз числами от 1 до 2n-1 .

А. Составить программу, запрашивающую:

- строку символов из прописных букв "П" и "З", определяющую последовательность типов сгибаний,

- номер ребра, и сообщающую тип этого ребра, получившийся после заданной последовательности сгибаний.

Б. Составить программу, запрашивающую строку символов из прописных букв "О" и "К", где нахождение на i-том месте символа "О" или "К" определяет тип ребра на расправленной полоске, и выдающую строку из прописных "П" и "З", определяющих последовательность типов сгибаний, посредством которых получена ленточка с исходной последовательностью ребер. Если такой строки не существует, сообщить об этом.

Из запасов жюри

1. Числа. (Алексеев А.В.) Определить сколько и каких цифр понадобится, чтобы записать все натуральные числа в диапазоне от N1 до N2? Числа N1 и N2 вводятся.

Рассмотреть следующие частные случаи:

а) N1=1, N2 является степенью десяти;

б) N1 и N2 выбираются таким образом, что в диапазоне от N1 до N2 находятся все k-значные числа;

в) N1=1, N2 - произвольное натуральное число.

2. Дырокол. (Бабурин Е.А.) Дырокол пробивает на длинной полосе бумаги по два одинаковых отверстия за одно нажатие его рычага. По известным координатам отверстий на полосе определить возможную ширину между отверстиями дырокола.

3. Очередь. (Бабурин Е.А.) В г. Красноярске пока не введена талонная система продажи масла и его продают по одному куску каждому покупателю, но покупатель может встать в очередь несколько раз.

В магазин привезли N кусков масла и началась его продажа. Покупателей вначале не было, а потом они стали прибывать по одному через время T. Взяв масло покупатель снова становился в очерель последним. Время обслуживания одного покупателя равно t. Если в одно и то же время встают в очередь два покупателя: уже купивший масло и только пришедший, то последний оказывается в очереди впереди.

Определить номер покупателя, которому достался последний кусок масла.

Сколько покупателей ушло из магазина с покупками?

Каким покупателям и сколько максимально досталось кусков масла?

4. Воины. (Шепелевский А.С.) Клетчатое поле n*n охраняется m воинами царя Артаксеркса, занимающими различные клетки этого поля. Царь хочет расположить воинов так, чтобы обеспечить максимальную суммарную защищенность границы своего владения, то есть 4(n+1) клеток непосредственно примыкающих к полю. Каждый воин охраняет те приграничные клетки, которые он "видит" по горизонтали, вертикали и диагоналям. При этом, защищенность клетки пропорциональна количеству воинов ее охраняющих. Помогите Артаксерксу найти хотя бы одно положение воинов по его желанию.

5. Троллейбус. (Касаткин В.Н.) В Крыму действует высокогорная троллейбусная трасса. При движении по этой трассе "в гору" троллейбус берет энергию из сети. При движении "под гору" его мотор работает как генератор электрического тока и выработанная им энергия возвращается в сеть.

Сказанное позволяет поставить следующую задачу.

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

Найти такие отрезки трассы пути, на которых суммарные затраты энергии будут наибольшими.

6. Заказ. (Сенокосов А.И.) Директор школы дал заказ центру программирования написать программу, поздравляющую всех учеников школы с днем рождения в любом заданном интервале (например, поздравить только тех, кто родился в этот день или в эту неделю и т.п.).

Данные для программы заводятся с помощью любого текстового редактора.

Разработайте удобную структуру данных и напишите программу, максимально упростив ввод большого объема информации (в школе не менее 1500 учеников).

Примечание: данные будут заводиться из школьного журнала, а там структура такова:

Фамилия, имя дата рождения

7. Палиндромы. (Жданов С.А.) Палиндрономическими называются числа, которые остаются без изменения при чтении в обратном порядке, например, 79488497 палиндрономично в десятичной системе счисления.

Составить программу, которая на интервале [10, 1011] находит и печатает числа, являющиеся палиндрономическими одновременно в десятичной и двоичной системах счисления.

8. Дробь. (Жданов С.А.) Составить программу для определения длины (s) и цифр периода десятичного представления дроби m/n, где m и n - целые числа.

Результат представить в виде m/n=a.a1...ar(q1...qs); период s=<число>,

где m и n - вводимые целые числа; a - целая часть; ai, 1ir, цифры перед периодом; qt, 1ts - цифры периода десятичной дроби.

Используя написанную программу вычислить: а) 149/665; б) 84/1991.

9. Диаграмма. (Жданов С.А.) На плоскости задано некоторое множество точек, обозначенных буквами латинского алфавита. Точки могут быть соединены отрезками. Пересечения отрезков, соединяющих заданные точки, не учитываются. Назовем такую конфигурацию геометрических объектов диаграммой Хассена. Диаграмма задается перечнем точек и отрезков. Любая часть (фрагмент) диаграммы также является диаграммой.

Введем обозначения:

(A) - отдельно стоящая точка;

(A,B) или (B,A) - отрезок, соединяющий точки A и B;

(Г) - диаграмма, где Г либо последовательность точек или отрезков, либо диаграмма, либо их сочетание;

( ),(( ),( )), ... ( ) - последовательность объектов.

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

Например, треугольник ((A,B),(B,C),(A,C))(((A,B),C)).

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

Примечание: длина входной строки не превышает 200 символов.

10. Числа. (Серегин И.А.) Получить десять тридцатиразрядных чисел, состоящих из 0 и 1 и таких,что:

а) в старшем разряде всегда стоит 1,

б) в числе нет 3-х подряд идущих единиц.

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

Определить существует ли в получившемся числе последовательность нулей и единиц, идентичная одной из исходной.

11. Корабль. (Серегин И.А.) В звездной системе ТЕТТА вокруг звезды массой Mз на расстоянии Lп по окружности движется планета массой Mп со скоростью Vп. На расстоянии от планеты Lкп и от звезды Lкз в звездную систему влетает космический корабль. Вектор его скорости Vк.

Промоделировать полет космического корабля в звездной системе.

12. Кубики. (Серегин И.А.) У четырех кубиков грани окрашены в четыре разных цвета: красный, синий, зеленый и оранжевый. Развертки этих четырех кубиков выглядят следующим образом:

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

13. Кенгуру. (Серегин И.А.) Кенгуру возраста K может прыгать вперед на любое из расстояний от 1 до K. Ей нужно двигаясь по прямой попасть из точки 0 в точку N.

А. Сколькими способами кенгуру может это сделать.

Б. Показать все эти способы.

14. Карта. (Серегин И.А.) Карта горной местности представлена массивом G(M,N) высот поверхности. По заданной карте построить карту RV(M,N), на которой будут нанесны только изоконтуры (линии с одинаковыми высотами).

15. Дама. (Серегин И.А.) Дама собирается пригласить семерых своих друзей на несколько званых обедов. Ее стол, однако, невелик, да и обед "в узком кругу" несомненно гораздо приятнее. Поэтому она решает приглашать каждый раз лишь троих гостей. Кроме того ей хочется, чтобы каждые двое ее друзей непременно встретились за ее столом, причем она предпочла бы, чтобы они встретились лишь однажды. Как хозяйке распределить приглашения по дням?

16. (Серегин И.А.) У N-угольника числами помечаются стороны и вершины. Расставить так 2*N числа по сторонам и вершинам N-угольника, чтобы число, стоящее на стороне равнялось сумме чисел, стоящих на вершинах, примыкающих к данной стороне. Все числа должны быть разными и составлять натуральный ряд чисел от 1 до 2*N.