Олимпиада по информатике 2008 - 2009

ЗАДАНИЯ ОЛИМПИАДЫ

Форма приема решений задач и визитных карточек

Задачи теоретической части

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

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

Решения задач теоретической части оформляются в виде документа Microsoft Word в соответствии с техническими требованиями и загружаются для проверки с помощью онлайн-формы.

1. Алгоритм

Что делает данный алгоритм?

алгоритм ДУМА(целые: n,k)
начало алгоритма
	n:=0
	i:=0
	цикл:пока i < k выполнить:
		n:=n + 2*i + 1	
		i:=i+1
	конец цикла
конец алгоритма

Ответ обосновать. (Предполагается, что на вход алгоритма подаются два целых числа – n и k. Считать, что переменная i является целочисленной.)

2. Обмануть обманщика

Коля загадал натуральное число от 1 до 30, а Петя пытается угадать его. Для этого Петя задает Коле несколько вопросов, на каждый из которых возможен ответ либо «да», либо «нет». После того, как заданы все вопросы, Петя должен назвать загаданное число. Однако при ответах на вопросы Коле разрешается не более одного раза солгать, то есть на один из задаваемых вопросов (конечно же, не указывая, на какой именно по счету) разрешается дать противоположный ответ. За какое наименьшее количество вопросов и каким именно образом Петя сможет гарантированно определить загаданное Колей число?

3.Зазеркалье

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

4. Коллективный разум

Подземелье замка Черного Властелина представляет собой квадрат 4x4, ячейками которого являются 16 комнат. В каждой комнате-ячейке в заточении сидит добрый волшебник. Каждый из них знает одну часть заклинания (причем каждый свою), но выбраться из подземелья волшебники могут только тогда, когда каждый из них будет знать все 16 частей заклинания. За один день волшебник может либо сообщить в соседнюю (за стеной) комнату все части заклинания, которые знает на данный момент, либо получить от одного из своих соседей (через стенку) известные тому части заклинания. За какое количество дней и каким образом все волшебники смогут получить все части заклинания?

5. Чудо инженерной мысли

На плоскости собрали некий механизм, состоящий из шестеренок с одинаковым шагом (т.е. расстоянием между соседними зубьями). Все шестеренки пронумерованы и для каждой из них известны номера шестеренок, с которыми она зацеплена. Описать алгоритм, определяющий, можно ли привести весь механизм в движение, вращая какую-нибудь из шестеренок.

6. Нить Ариадны

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

Задачи практической части

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

Для проверки отправляются только исходные тексты программ (файлы *.pas, *.c, *.cpp) в соответствии с техническими требованиями. Компилироваться программы будут жюри перед проверкой. Программы, не прошедшие компиляцию, к проверке не допускаются.

Программы будут проверены на комплекте тестов в полуавтоматическом режиме (внимательно следите за форматами выходных файлов: несоответствие формата выходного файла может привести к тому, что результат прохождения теста не будет засчитан).

Входные данные берутся из текстового файла input.txt, результат выполнения программы выводится в файл output.txt в установленном формате.

Ограничения на время выполнения программы по каждому из тестов: 10 секунд. Программы, не укладывающиеся во время прохождения теста в установленные ограничения или выдающие ошибку, считаются не прошедшими данный тест.

Для проверки работы загружаются через онлайн-форму.

1. Проще простого

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

Вход:файл input.txt, в котором записано единственное число N

Ограничения: 1<N≤30000

Выход: файл output.txt, содержащий единственное число (минимальное количество групп)

Пример:

Примечание к примеру: числа от 1 до 18 можно разбить на три группы с нужным свойством (например, 1+3+4+5+6+18, 2+7+8+9+10+11+12+13+14+17 и 15+16 с суммами 103, 37 и 31), на меньшее число групп, как легко показать, нельзя.

2. Острова

В океане расположен архипелаг из N островов, каждый из которых имеет форму выпуклого многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соединить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соединять пару островов, при этом суммарная длина мостов должна быть минимальной.

Вход: файл input.txt, имеющий следующую структуру: в первой строке входного файла записано число N – количество островов в архипелаге. Далее идет N строк с описанием островов. В каждой строке описывается один остров, который задаётся числом вершин (первое число строки) и далее их координатами в порядке обхода по часовой стрелке (у каждой вершины первой идет абсцисса, а второй - ордината). Координаты внутри строки разделяются пробелами.

Ограничения: число N – натуральное от 2 до 50 (включительно), для каждого острова число вершин не превосходит 20, все координаты – целые числа, не превосходящие по модулю 30000.

Выход: файл output.txt, содержащий два числа (по одному в строке), первая строка ¬- число: количество мостов; второе строка - число: суммарная длина мостов с точностью до 0.001

Примеры:

3. Шифр Цезаря

Некоторый русский текст, хранящийся в файле, зашифрован следующим образом: каждая буква текста циклически сдвигается на одно и тоже количество символов, а все остальные символы (знаки препинания и пробелы) остаются неизменными. При шифровке большие буквы переходят в большие, а маленькие в маленькие. Будем для простоты считать, что русский алфавит состоит из 32 букв (за буквой «е» следует буква «ж»). Требуется написать программу автоматической расшифровки текста.

Вход: файл input.txt c зашифрованным текстом.

Ограничения: длина текста не превосходит 250 символов.

Выход: Файл output.txt с расшифрованным текстом.

Пример:

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

СРОКИ ПРОВЕДЕНИЯ ОЛИМПИАДЫ:

• До 7 апреля - регистрация участников олимпиады.
• 9 апреля - публикация заданий на сайте олимпиады.
• 16 апреля - последний день приема решений через online систему.
• 7 мая - подведение итогов олимпиады.