на первую страницу

УСЛОВИЯ ЗАДАЧ

Задачи практического тура:

Задача 1. (25 баллов)

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

Входные данные (каждый элемент данных вводится с новой строки):

M – количество участников, 0<M<1000
ai - список результатов каждого участника для i от 1 до M (целые числа).

Предполагается, что за минуту никто не может нажать Escape больше чем 32767 раз и нажимает хотя бы один раз.

Выходные данные: целое число, показывающее, сколько раз мылась тряпка.

Пример:

Входные данные

Выходные данные

M 5

2

a1 1
a2 3
a3 2
a4 3
a5 10

 

Задача 2. Живые клетки.

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

а) ГИБЕЛЬ. Если живая клетка имеет соседние клетки либо обе живые, либо обе пустые, то она погибает (клетка становится пустой) от перенаселенности или одиночества соответственно.

б) ВЫЖИВАНИЕ. Если живая клетка имеет обе соседние клетки различными (одна - живая, другая - пустая), то эта клетка выживает.

в) РАЗМНОЖЕНИЕ. Если пустая клетка имеет соседями обе живые клетки, то она становится живой (происходит рождение новой особи).

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

Входные данные (каждый элемент данных вводится с новой строки):

N - кол-во клеток на ленте
S - строка длины N, состоящая из символов '0' и '1', при этом '0' означает, что соответствующая клетка пуста, а '1' - клетка живая. Индекс элемента в строке показывает номер клетки.
M - целое число шагов (M>=0)

Выходные данные: целое число живых клеток на ленте после M-го шага.

Пример:

Входные данные

Выходные данные

Пример жизни клеток

N 8

3

S

00111010

S 00111010 Шаг 1

00101100

M 2 Шаг 2

00011100

 

Задача 3. Контур из стрелок

В графическом редакторе нарисованы N (2<N<250) стрелочек, исходящих из одной точки. Все они являются отдельными объектами, имеют уникальный номер от 1 до N, о каждой известна ее длина и угол наклона (от 0 до 359 градусов) к горизонтальной координатной оси. Требуется, применяя только параллельный перенос этих стрелок, построить не самопересекающийся замкнутый ориентированный контур, обязательно используя все стрелки. Считается, что из заданного набора стрелок это сделать можно.

Входные данные (каждый элемент данных вводится с новой строки):

N – количество стрелок,
Li – список длин каждой стрелы для i от 1 до N
aiуглы наклона каждой стрелы для i от 1 до N

Выходные данные: Pi (для i от 1 до N) - набор неповторяющихся натуральных
чисел от 1 до N, задающих порядок следования стрелок в замкнутом ориентированном контуре. Номера стрелок соответствуют порядку их ввода.

Пример:

Входные данные

Выходные данные

N 4

P1

4

L1 1

P2

3

L2 1

P3

2

L3 1

P4

1

L4 1
a1 45
a2 135
a3 225
a4 315

 

Задача 4. День рождения Христа.

 

Отпраздновав очередной раз свой День Рождения (на этот раз по Православному обычаю), Иисус Христос застал учеников своих в печали. Иисус спросил, почему они так печальны, и они ответили, что считают День Рождения Иисуса великим праздником, а он отмечается как обычный День Рождения. Тогда Иисус решил рассказать им о том, как нужно праздновать Рождество. Для этого он попросил учеников сесть вокруг него кругом. Вам нужно определить, сколькими способами можно было бы рассадить N апостолов вокруг Иисуса (3? N? 12), имея в виду, что способ рассаживания определяется соседями каждого из апостолов. Иными словами, если они пересели, но у каждого соседи остались те же (даже если правый сосед стал тем, кто раньше был левый), то следует считать, что они расселись тем же способом.

Входные данные: N – целое число, соответствует количеству апостолов.

Выходные данные: целое число, соответствующее количеству возможных способов рассаживания апостолов.

Пример:

Входные данные

Выходные данные

N 3

1

 

Задача 5. Шахматы.

 

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

Входные данные (каждый элемент данных вводится с новой строки):

F1 – номер столбца расположения фигуры
F2 – номер строки расположения фигуры
K1 - номер столбца расположения коня
K2 - номер строки расположения коня

Выходные данные: 1, если конь бьет фигуру за один ход
                                        0, иначе

Пример:

                  Входные данные   Выходные данные
                 

F1

5

 

1

                 

F2

5

   
        Ф        

K1

3

   
    К            

K2

4

   
                         
                         
                         

 

Задача 6. Слияние массивов.

 

Даны два числовых массива размерности M и N соответственно (0<M,N? 10). Первый из них упорядочен по возрастанию, а другой по убыванию. Написать программу, которая бы осуществляла слияние массивов в один, причем все элементы в полученном массиве были бы упорядочены по возрастанию.

Входные данные (каждый элемент данных вводится с новой строки):

M – количество элементов первого массива,
N – количество элементов второго массива,
Xi (i от 1 до M) – элементы первого массива,
Yj (j от 1 до N) – элементы второго массива.

Выходные данные: Zk (k от 1 до M+N) – сформированный массив чисел.

Пример:

Входные данные

Выходные данные

M 3

Z1

1

N 2

Z2

2

X1 1

Z3

5

X2 5

Z4

6

X3 8

Z5

8

Y1 6
Y2 2

Задачи теоретического тура.

1. Сейф. (25 баллов)

Оргкомитет олимпиады состоит из 11 человек. Материалы олимпиады хранятся в сейфе. Сколько замков должен иметь сейф и как надо снабдить каждого члена оргкомитета ключами, чтобы доступ в сейф был возможен, когда соберутся любые 6 членов оргкомитета, и не был возможен, если соберется меньше 6 членов?

2. Шифровка. (25 баллов)

Экспериментальным путем установлено, что русские буквы можно расположить в следующем порядке, согласно доли появления их в тексте (в процентах):

И,й О Е,ё А Т Н С Л К Р В Д М П У Ы
10 9,4 9,2 7,6 6,3 5,9 5,5 5,2 4,2 4,1 3,9 3,3 3,2 2,8 2,5 2,1
Б Я Г З Ь Ч Ж Х Ш Ю Э Щ Ц Ф Ъ
1,9 1,8 1,7 1,7 1,5 1,2 1 1 0,9 0,8 0,4 0,3 0,3 0,2 0,1

Имеется также зашифрованный текст, в котором каждая буква заменена некоторым символом, причем каждой букве соответствует только один символ, знаки препинаний опущены, все слова написаны с маленькой буквы:

w5b8x 2wctwcx 3b tw849xywcw b qb 3x2x f47 qbc42 3bywuwc b qb 3x2 f42buxfx 3b t4qcvs342 sbuxfw b qb 3x2x ubfx 3b 5u424x 94hbfw t48fx 3b f4hk8w 8dtk t bt7424hx8w qbxexfx t 7ub2tbxexfw rbhb 3b 2w78w wcv7 x 92w679o yuo3xfx rv67 tcuvz xq y4ct4u473x 97ubs3kx tw8xfb3 ukrxx x v9b7kx 7bubfb3 7bubfb3 7bubfb3 7bubfb3xnw 43 ukex7 x fuxex7 x v9b2x swtw8x7 y4z4cx7w 3w 9ywsx7w o tb9 2xz42 yu4z84ev yu4z84ev yu4z84ev 3w y42x8v6 qtwux qbcu4rb8x t 4h24u4f vyb8x t48fx 47 x9yvzb 9fvsb8x cuvz cuvzb hwc3kx fu4f4cx8 rbhv yu4z847x8 b 9843x5b t9o cu4rb 7bf x 9w8b 3b wrb

Подсчитана доля появления каждого символа в зашифрованном тексте в процентах:

b x 4 w u 3 f 8 7 t 2 v c 9
12 11,9 8,7 6,5 6,3 5,2 5 4,8 4,8 3,9 3,9 3,5 3,5 3

 

y z q h r e k s o 5 6 n d
2,8 2,2 2 1,5 1,5 1,5 1,5 1,3 0,9 0,7 0,7 0,2 0,2

Расшифруйте текст, анализируя обе таблицы и зашифрованный текст.

3. Король и королева Треф. (15 баллов)

Герцогиня спросила у Алисы:

- Могла ли я, будучи в здравом уме сказать тебе, что Король Треф думает, что Королева Треф думает, что Король Треф думает, что Королева Треф не в своем уме?

Что ответит Алиса Герцогине ("да, могла" или "нет, не могла") и почему?

4. Шаблоны имен файлов. (10 баллов)

При указании имен группы файлов часто используют шаблоны. В шаблоне, кроме обычных литер (буквы, цифры, точка и подчеркивание), можно применять символы '*', '?' и квадратные скобки '[' и ']'. Символ '*', если он не внутри квадратных скобок, обозначает произвольное количество любых символов (в том числе, нулевое). Символ '?' обозначает любую литеру, которая должна обязательно присутствовать в данном месте имени файла. В квадратных скобках явно указываются литеры, которые могут стоять в данном месте имени. Например, шаблону '*-a?[0123456789]' будут удовлетворять следующие имена файлов:

aaa- az0, x-a12, -a-9, q12-at0

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

03-125.MPG ABCDEFGHIJ
AM_5.MP3
AZ-AZ.MP3
AZ-AZU1.MP3

DINDIN.MP3
DUO-125.MP3
FAN-TOUR.MP3
KA-12.1.MP3
LZ-AZU1.MP3
MV-QWE5.MPG
MV-ZA4MP3
QU-5.MP3
QU-QWE5.MP QU-WE5.MPG
RE-AD.ME READ.ME
T-ZA.MP3
T-ZA4.MP3
TA-ZA4MP3
UL-E4MP3.M
UU-12-1.MP3
V5-ADD.MPG
ZA-ZA.MP2

 

5. Числовая последовательность. (5 баллов)

Сформулируйте закон, по которому составляется данная последовательность:

1, 100, 1001, 10000, 11001, 100100, 110001 …….

Ответ обоснуйте.

6. Странный алгоритм. (20 баллов)

Ученые секретной лаборатории разработали новейшую версию программируемого робота, который способен выполнять следующие команды:

Right - сдвинутся на шаг вправо;
Left - сдвинутся на шаг влево;
Forward - сдвинутся на шаг вперед;
Back - сдвинутся на шаг назад;
Speed up N - увеличить скорость выполнения команд передвижения в N раз;
Speed down N - уменьшить скорость выполнения команд передвижения в N раз;
Кроме того, в программе допускается использование меток, переходы к которым осуществляются по команде Goto.

Команды передвижения требуют от робота, для своего выполнения, определенное время, а команды изменения скорости и Goto выполняются им практически мгновенно.

Девочка Ада (дальняя родственница одного из разработчиков), играя с Роботом ввела в него следующую программу:

NEXT:

Forward
Left
Forward
Right
Right
Back
Left
Speed up 2
Goto NEXT

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

а) Определите, через сколько секунд после старта Робот завершил выполнение программы, если известно, что он на самое первое выполнение команд тела цикла он потратил t секунд.

б) На сколько шагов удалился Робот от точки старта?

e-mail: mdia{at}cs.karelia.ru
(C) 2002-03 karelia.ru