Перед Вами задачи заочного тура по информатике. Количество баллов, которые можно получить за решение каждой из задач - 20, максимальное количество баллов - 100. Не смущайтесь, если Вам не удалось решить все задачи или Вы сомневаетесь в правильности их решения. Присылайте! По результатам проверки жюри определит, кого пригласить на очный тур фестиваля. Может быть, удачное решение всего одной задачи обеспечит Вам приглашение.
Требования к оформлению.
При оформлении работы следует каждую задачу делать на отдельном листе, четко описывать и обосновывать выводимые формулы и алгоритмы решения. Текст программ и алгоритм следует хорошо откомментировать. Очень желательно приложить дискеты с текстами программ. Дискеты могут быть возвращены на областном фестивале или лично при обращении в Институт математики и механики УрО РАН (Екатеринбург, ул. С.Ковалевской, 16).
Решения присылать по адресу: 620151, г.Екатеринбург,
ул. Карла Либкнехта 2, каб.9.
Прием работ проводится до 10 декабря 2001 года.
Слово
Пусть задано некоторое слово. Построим для этого слова "набор перестановок" -- набор слов (возможно - бессмысленных), полученных всевозможными перестановками символов исходного слова (например, для исходного слова "ФАРА" в набор входят "АРФА", "ФААР" и т.п.).
Требуется написать программу, которая по произвольному введенному слову выдает следующее за ним по алфавиту слово из его набора перестановок.
Родословная
В Голландии каждому новорожденному теленку присваивают уникальный номер. В паспорте теленка записывают его номер, затем номер отца, затем номер матери (например, 5 2 8).
Требуется написать программу, которая выводит информацию из N (N<=20) паспортов и проверяет ее непротиворечивость (например, теленок не может быть своим собственным отцом). Программа должна сообщать, что данные непротиворечивы или указывать конкретное противоречие.
Точки в круге
Требуется написать программу, которая по заданному числу N выдает координаты центра и радиус круга, содержащего в себе ровно N целочисленных точек, то есть точек с целыми координатами на плоскости.
Минералка
Бутылка минералки стоит k рублей, а пустая бутылка стоит 1 рубль. Компания друзей, собравшаяся в понедельник на день рождения одного из них, располагала первоначальным капиталом в n рублей и купила минералки - столько, на сколько денег хватило. Употребив все купленное, они на следующий день сдали все пустые бутылки, добавили оставшиеся с предыдущего дня деньги и снова купили минералки - на сколько денег хватило. Данная процедура продолжалась каждый день, пока были деньги.
Требуется написать программу, которая бы определяла минимальный начальный капитал, при котором в пятницу друзьям будет, что употребить.
Лабиринт
Попав в лабиринт, состоящий из одинаковых квадратных комнат, каждая из которых может иметь от 1 до 4 дверей в соседние комнаты, путник долго блуждал по нему, пока не нашел клад. Во время поиска он составил описание своего маршрута, обозначая каждый переход из комнаты в комнату буквами: С (север), Ю (юг), З (запад), В (восток).
Требуется написать программу, определяющую по заданной записи самый короткий путь назад.
Председатель программного комитета
В.В. Прохоров
зав. лаб. визуальных систем ИММ УрО РАН
Эту страницу можно найти на сайте Уральские олимпиады по адресу http://sp.urfu.ru/school/obl2002/i_z_prob.html