Правила и задания для олимпиады.

Олимпиада по программированию проводится 13 марта 2007 года с 11.00 до 16.00 в аудитории 219А. С 10.00 до 11.00 студенты имеют возможность подготовить своё рабочее место, проверить наличие и корректную работу компиляторов, интерпретаторов и сред программирования. При возникновении проблем или пожеланий просьба обращаться к комитету олимпиады. Подготовка олимпиадных заданий и проверка решений возлагаются на комитет олимпиады, в состав которого входят Пирогов В.Ю., к.ф-м.н, профессор, зав. кафедрой прикладной информатики Шадринского пединститута и Слинкин Д.А., к.п.н, доцент, начальник вычислительного центра Шадринского пединститута.

Комитет олимпиады оставляет за собой право поощрять (до +3 баллов) высокоэффективные решения.

Для решения задач каждый студент может использовать языки программирования Pascal (FreePascal, TurboPascal, Delphi), C++ (GCC, BCPP, Visual C++, C++Builder), PHP5 (Linux, консоль), PHP4 (Windows, консоль), JavaScript (версия 1.5, firefox, ввод данных ч/з элемент textarea).

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

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

Для Windows:

c:\ivanov\1\решение задачи 1

c:\ivanov\2\решение задачи 2

c:\ivanov\5\решение задачи 5

Для Linux:

/home/student/ivanov/1/решение задачи 1

/home/student/ivanov/2/решение задачи 2

/home/student/ivanov/5/решение задачи 5

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

Подведение итогов олимпиады запланировано на 14 марта 2007 года, 14.30.

Победители олимпиады будут награждены ценными призами и подаркам, предоставленными оргкомитетом студенческого научно-практического форума.

Задания для олимпиады

Этап 1. Разминка

1. Поворот (2 балла)

Реализовать функцию F, которая получив на входе целое число N в десятичном формате, возвращает число M в десятичном же формате (M=F(N)). Число M имеет в двоичном представлении обратный порядок двоичных разрядов. Во входном файле input.txt содержит набор чисел в десятичном формате (одно число - одна строка). В выходном файле output.txt содержаться результаты воздействия функции на F на числа из файла input.txt (одно число - одна строка).

Пример файла Input.txt	Пример файла Output.txt
32 16 7 6 8 4 65534 2 1 255 126 254	1 1 7 3 1 1 32767 1 1 255 63 127

2. Функция (3 балла)

Функция F(n) для целых неотрицательных n определена так: F(0)=0, F(1)=1, F(2n)=F(n), F(2n+1)=F(n)+F(n+1). Для данного N найти и напечатать функцию F(N). Обязательное условие: N - может быть столь велико, что не возможно использовать массив из N элементов. Файл input.txt содержит значения N (одна строка, одно значение, количество строк - произвольное), файл output.txt - содержит значение функции F(N).

Пример файла Input.txt	Пример файла Output.txt
4 3 10 5 20 25	1 2 3 3 3 7

3. Пересечения (3 балла)

Исходный файл (Input.txt) содержит в каждой строке координаты двух точек, определяющих прямую на плоскости в формате X1,Y1,X2,Y2. Выходной файл должен содержать координаты точек пересечения: одна точка - одна строка (формат X Y).

Пример файла Input.txt	Пример файла Output.txt
0 1 1 0 0 -2 2 0 10 10 4 6 2 3 4 1 -2 -3 -4 2 0 1 8 2 -1 2 -2 2	1.50 -0.50 -1.40 2.40 -6.00 7.00 0.00 1.00 -1.00 2.00 16.00 14.00 3.50 1.50 -1.71 -3.71 3.43 1.43 4.00 2.00 1.00 4.00 -3.58 0.95 -4.31 0.46 -2.00 2.00 -8.67 13.67 3.56 1.44 3.00 2.00 -3.43 0.57 -4.00 2.00 8.00 2.00

4. Окраска прямой (3 балла)

На оси 0X было окрашено N отрезков. Отрезки заданы координатами своих концов (x1,x2). Необходимо найти длину окрашенной части. Входной файл input.txt содержит координаты отрезков: один отрезок - одна строка (в формате x1 x2). Выходной файл output.txt содержит число L - длину окрашенной части.

Пример файла Input.txt	Пример файла Output.txt
0 2 1 3 4 5 3 4 6 9 1 4	8

Этап 2. Мозговой штурм.

5. Объем каталогов (5 баллов)

Смоделировать результаты применения конвейера из GNU-утилит du и sort:

du -b | sort -n -r

Утилита du используется для подсчёта объема каталогов на основе объема содержащихся в них файлов и подкаталогов. Опция -b применяется для указания размера каталогов в байтах. Утилита sort используется для сортировки переданных ей строк. Опция -n применяется для упорядочивания по числовому значения переданных строк, опция -r обеспечивает отсортированный по убыванию вывод.

Исходный файл input.txt содержит размер и полное имя файла в unix-нотации в каждой строке. Для упрощения будем считать, что 1) любой каталог является только контейнером для хранения других файлов (каталогов) и не занимает места в файловой системе; 2) в полном имени файла пробелов быть не может.

Пример input.txt:

5050 /usr/include/libglade-2.0/glade/glade-build.h
1465 /usr/include/libgen.h
9175 /usr/include/c++/4.1.1/ext/pb_assoc/detail/assoc_cntnr_base.hpp
4922 /usr/include/c++/4.1.1/debug/debug.h
4270 /usr/include/c++/4.1.1/bits/allocator.h
2307 /usr/include/c++/4.1.1/bits/atomicity.h
9296 /usr/X11R6/man/man1/xli.1.bz2
2039 /usr/X11R6/man/man1/xlito.1.gz
13004 /bin/basename
470980 /bin/bash
105 /etc/chroot.d/.provides.sh
5906 /etc/chroot.d/functions
489 /etc/chroot.d/mysql.conf

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

Пример output.txt:

529008 /
483984 /bin/
38524 /usr/
27189 /usr/include/
20674 /usr/include/c++/4.1.1/
20674 /usr/include/c++/
11335 /usr/X11R6/man/
11335 /usr/X11R6/man/man1/
11335 /usr/X11R6/
9175 /usr/include/c++/4.1.1/ext/pb_assoc/
9175 /usr/include/c++/4.1.1/ext/pb_assoc/detail/
9175 /usr/include/c++/4.1.1/ext/
6577 /usr/include/c++/4.1.1/bits/
6500 /etc/chroot.d/
6500 /etc/
5050 /usr/include/libglade-2.0/glade/
5050 /usr/include/libglade-2.0/
4922 /usr/include/c++/4.1.1/debug/

6. Игра (5 баллов)

Даны числа N и M (M>N). Два игрока, назовем их А и В, играют в следующую игру: каждый из игроков по очереди называет число от 1 до M. Названные числа складываются. Выигрывает тот из игроков, чей очередной ход даст в результате сумму равную N. Например: N=10, M=5. А-4, В-2, А-4, т.о. А выиграл. Написать программу, которая на входе содержит числа N M (файл input.txt содержит в первой строке два числа через пробел), а на выходе (в файле output.txt) содержит все возможные варианты игры игроков А и В, в которых выигрывает А (А начинает играть). Не должны учитываться неправдоподобные варианты, когда игрок может выиграть за один ход, но не делает это. Например, при N=10, M=5 не должен учитываться вариант А-4, В-2, А-2, В-2.

Пример файла Input.txt	Пример файла Output.txt
8 6	1 1 6 1 2 5 1 3 4 1 4 3 1 5 2 1 6 1
6 2	1 1 1 1 2 1 1 1 2 1 2 2 2
10 5	1 1 1 2 5 1 1 1 3 4 1 1 1 4 3 1 1 1 5 2 1 1 2 1 5 1 1 2 2 4 1 1 2 3 3 1 1 2 4 2 1 1 2 5 1 1 2 1 1 5 1 2 1 2 4 1 2 1 3 3 1 2 1 4 2 1 2 1 5 1 1 4 5 1 5 4 2 1 1 1 5 2 1 1 2 4 2 1 1 3 3 2 1 1 4 2 2 1 1 5 1 2 3 5 2 4 4 2 5 3 3 2 5 3 3 4 3 4 3 3 5 2 4 1 5 4 2 4 4 3 3 4 4 2 4 5 1

7. Поиск по шаблону (7 баллов)

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

Задание: по заданному упрощенному wildmat-шаблону определить соответствующие ему строки в исходном файле.

Wildmat-шаблон строится на основе 5 правил (http://en.wikipedia.org/wiki/Wildmat), из которых будем использовать первое, второе и пятое:

1. Знак '*' соответствует любому количеству (от нуля) любых символов.
2. Знак '?' соответствует одному произвольному символу.
3. Не используем
4. Не используем
5. Знак '\' используется для экранирования специальных символов. При использовании этого знака непосредственно перед знаками '*', '?' и '\' последние рассматриваются как обычные, а не как специальные символы.

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

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

Пример input.txt:

***.abc?.*dsaa\?\**
wer.abc.-.dsaa?*q
rrra****aasd.abc1sdsddsa.abcd.dsaa?*
index.html
.abcx.----------.dsaa?*11
**aasd.abcz.sdsddsaabcd.dsaa?*--
123abc..dsaa*
.abc*.*aasd.abcz.sdsddsaabcd.dsaa*--

В результирующем файле output.txt присутствуют только те из имен, которые соответствуют шаблону.

Пример output.txt:

rrra****aasd.abc1sdsddsa.abcd.dsaa?*
.abcx.----------.dsaa?*11
**aasd.abcz.sdsddsaabcd.dsaa?*--

8. Автостоянка (11 баллов)

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

На приведенном ниже рисунке точки въезда на стоянку обозначены цифрами, а размещенные на стоянке автомобили - красными квадратами. Точка 1 обеспечивает 5 стояночных мест, точки 2 и 6 - 20 стояночных мест, точки 3, 4 и 5 - 42 стояночных места. Таким образом, при длине кортежа, например, в 4 автомобиля, подходящей является точка 1, для 10 автомобилей - точки 2 и 6, а для 50 автомобилей таких точек нет.

1						2
									6
4				5					3

Исходные данные: файл input.txt содержит количество автомобилей кортежа, а также строки, кодирующие набор стояночных мест и точки въезда на автостоянку. Цифрой "0" обозначается свободное стояночное место, цифрами от "1" до "9" - точки въезда на автостоянку, знаком "*" - размещенные на автостоянке автомобили. Для приведенного рисунка и кортежа из 20 автомобилей содержимое файла input.txt будет следующим:

20
10000*2000
*****00000
**000*0006
000*0*0*00
0*0*0*0000
0*0*00****
0*0*0*0000
0*0*0*0**0
0*000*0*00
4000500*03

Результирующие данные: файл output.txt содержит в порядке возрастания (через пробел) номера точек въезда на автостоянку или цифру 0, если подходящих точек нет. Для приведенного примера содержимое файла output.txt будет следующим:

2 6