Информатика и информационные технологии

Задания телекоммуникационной олимпиады по информатике – 2007

Уважаемые участники олимпиады!

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

Участники предоставляют работы в виде нескольких файлов.

Решения задач теоретической части предоставляются в формате документа Microsoft Word (*.doc или *.rtf) в соответствии с требованиями, приведенными в Приложении.
Решения задач практической части предоставляются в виде исходных файлов программ на языке Паскаль (файлы *.pas) или Си (файлы *.c или *.cpp) в соответствии с требованиями, указанными в Приложении.
Визитная карточка команды (участника) присылается в виде документа Microsoft Word (*.doc или *.rtf), либо презентации Microsoft PowerPoint (*.ppt или *.pps), либо мини-сайта (файл или файлы с расширением *.html, иллюстрации *.gif или *.jpg, присылаются в виде единого архивного файла) в соответствии с требованиями, указанными в Приложении.

ВНИМАНИЕ!
Работы принимаются до 5 марта 2007 года, 18:00 (время московское).
Прислать свои работы Вы сможете с помощью on-line формы на сайте проекта.

Вопросы можно задать координатору олимпиады по электронной почте или в форуме.

Теоретическая часть

1. Эскалатор

Вася и Петя бегут вниз по эскалатору. Дано отношение их скоростей. Также известно, сколько ступенек насчитал каждый из них. Описать алгоритм подсчета количества ступеней на неподвижном эскалаторе.

2. Треугольники

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

3. Функция

Функция натурального аргумента f(n) задана соотношениями: f(1)=1; f(2n)=f(n); f(2n+1)=f(n)+f(n+1). Опишите алгоритм ее вычисления при больших значениях n.

4. Блоха и куб

Блоха находится в вершине куба. За один прыжок она может переместиться в любую соседнюю вершину. Сколькими различными путями она ровно за N прыжков может оказаться в противоположной вершине?

5. Получение единицы

Заданное число либо уменьшают на 1, либо делят пополам, если оно чётно. Описать и обосновать алгоритм получения 1 за наименьшее количество действий.

Практическая часть

1. Словарь

Петя выписал несколько слов из словаря племени Мумбо-Юмбо, не нарушив порядка их следования в словаре (лексикографический порядок). Опишите алгоритм определения, в каком порядке следуют буквы в алфавите племени. Если возможны разные варианты, должен быть указан один из них. (Считать, что племя Мумбо-Юмбо использует 26 букв латинского алфавита, расположенных в некотором порядке)

Ограничения:
Длина слова: M<100
Количество выписанных слов: N<500

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

Результат
помещается в файл output.txt
в 26 строках располагаются 26 букв (по 1 букве в строке) в том порядке, в котором они следуют в алфавите Мумбо-Юмбо.

Предполагается, что файлы input.txt и output.txt располагаются в той же папке, что и программа. Ограничение на время работы программы: 5 секунд.

2. Минимальное число

Дано N. Найдите минимальное число, из которого вычеркиванием цифр можно получить любое число от 1 до N.

Ограничение:
N<500

Входные данные
Натуральное число N, расположенное в первой строке файла input.txt

Результат
помещается в файл output.txt
В первой строке располагается указанное в условии задачи число.

3. Сумма цифр

Найдите все числа, которые в N раз больше суммы своих цифр. Если чисел больше 10, то выведите их количество и одно из них.

Ограничение:
N<10000

Входные данные
Натуральное число N, расположенное в первой строке файла input.txt

Результат
помещается в файл output.txt
В первой строке выходного файла располагается количество удовлетворяющих условию чисел.
Если количество удовлетворяющих условию чисел больше 10, то во второй строке располагается одно из удовлетворяющих условию чисел. Иначе (если таких чисел не больше 10) все эти числа приводятся в выходном файле, начиная со второй строки (по одному числу на строке).

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

Предоставляемые документы Microsoft Word должны удовлетворять следующим требованиям:

допустимые шрифты: Times New Roman, Arial или Courier (Courier New);
не допускается включение макросов в документ;
формулы допустимы в одном из следующих видов:
1. текстовая строка;
2. графический объект (картинка);
3. объект Microsoft Equation 3.0.
рисунки (фотографии) включаются в документ в виде вставки графического объекта (рисунка);
размер бумаги: А4;
поля: не менее 2 см каждое;
размер шрифта для основного текста: 12 или 14 пунктов;
размер документа (с решениями задач) не более 2 мегабайт.

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

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

Отдельные требования для документов-визиток:

размер документа не более 500 Кб;
визитная карточка располагается не более чем на 3 листах А4.

Предоставляемые презентации Microsoft PowerPoint (визитные карточки) должны удовлетворять следующим требованиям:

размер одного файла: не более 500 Кb;
визитка располагается не более чем на 3 слайдах;
ссылки в презентациях не должны указывать на внешние источники (сайты, документы).

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

суммарный размер всех файлов: не более 500 Кb;
визитка располагается не более чем на 4 страницах;
графические файлы размером не более 30 Кб.

Мини-сайты присылаются в виде единого архивного файла в формате ZIP или RAR.

Предоставляемые программы должны удовлетворять следующим требованиям:

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

Желаем удачи!

Со всеми вопросами обращайтесь: E-mail:

inform@edu.yar.ru