Задания заочного тура олимпиады по информатике 2001-2002 уч.г.

Перед Вами задачи заочного тура по информатике. Количество баллов, которые можно получить за решение каждой из задач - 20, максимальное количество баллов - 100. Не смущайтесь, если Вам не удалось решить все задачи или Вы сомневаетесь в правильности их решения. Присылайте! По результатам проверки жюри определит, кого пригласить на очный тур фестиваля. Может быть, удачное решение всего одной задачи обеспечит Вам приглашение.

Требования к оформлению.

При оформлении работы следует каждую задачу делать на отдельном листе, четко описывать и обосновывать выводимые формулы и алгоритмы решения. Текст программ и алгоритм следует хорошо откомментировать. Очень желательно приложить дискеты с текстами программ. Дискеты могут быть возвращены на областном фестивале или лично при обращении в Институт математики и механики УрО РАН (Екатеринбург, ул. С.Ковалевской, 16).

Решения присылать по адресу: 620151, г.Екатеринбург, ул. Карла Либкнехта 2, каб.9. Прием работ проводится до 10 декабря 2001 года.

Слово

Пусть задано некоторое слово. Построим для этого слова "набор перестановок" -- набор слов (возможно - бессмысленных), полученных всевозможными перестановками символов исходного слова (например, для исходного слова "ФАРА" в набор входят "АРФА", "ФААР" и т.п.).

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

Родословная

В Голландии каждому новорожденному теленку присваивают уникальный номер. В паспорте теленка записывают его номер, затем номер отца, затем номер матери (например, 5 2 8).

Требуется написать программу, которая выводит информацию из N (N<=20) паспортов и проверяет ее непротиворечивость (например, теленок не может быть своим собственным отцом). Программа должна сообщать, что данные непротиворечивы или указывать конкретное противоречие.

Точки в круге

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

Минералка

Бутылка минералки стоит k рублей, а пустая бутылка стоит 1 рубль. Компания друзей, собравшаяся в понедельник на день рождения одного из них, располагала первоначальным капиталом в n рублей и купила минералки - столько, на сколько денег хватило. Употребив все купленное, они на следующий день сдали все пустые бутылки, добавили оставшиеся с предыдущего дня деньги и снова купили минералки - на сколько денег хватило. Данная процедура продолжалась каждый день, пока были деньги.

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

Лабиринт

Попав в лабиринт, состоящий из одинаковых квадратных комнат, каждая из которых может иметь от 1 до 4 дверей в соседние комнаты, путник долго блуждал по нему, пока не нашел клад. Во время поиска он составил описание своего маршрута, обозначая каждый переход из комнаты в комнату буквами: С (север), Ю (юг), З (запад), В (восток).

Требуется написать программу, определяющую по заданной записи самый короткий путь назад.

Председатель программного комитета
В.В. Прохоров
зав. лаб. визуальных систем ИММ УрО РАН