Алтайский государственный технический университет им. И.И. Ползунова

      2002
Оргкомитет олимпиады желает вам успехов! К пожеланиям успехов присоединяется и Винни-Пух, хорошо известный нетрадиционными методами решения сложных проблем. Задача про Винни-Пуха всегда входит в число задач нашей олимпиады.
Задача Название задачи
A Винни-Тарзан
B Бои роботов
C Сессия ленивого Вовочки
D Деревенская олимпиада в Осинниках
E Любознательный жучок в Египте
F Про Васю-программиста
H Хакер Вася
K Путь камикадзе
L Любитель лимонада
M Кат Матроскин и новый забор
P Параллельные вычисления

Задача А. Винни–Тарзан.

Однажды Винни-Пух смотрел телевизор и увидел потрясающий аттракцион. Огромная толпа людей собралась у моста, ожидая своей очереди испытать радость. А всё ради чего? Дают тебе резинку, привязываешь один её конец к мосту, а другой к ноге, берёшь камень побольше и…

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

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

Входной файл input.txt:

В первой строке содержится M - число точек, которые Винни-Пух наметил для прыжка. Из каждой такой точки Винни прыгает вертикально вниз. Далее следуют M строк, каждая из которых содержит координаты точек прыжка. Затем идёт описание озера в виде многоугольника: на одной строке количество вершин многоугольника N(N<=1000), а на N последующих строк координаты вершин многоугольника перечисленные по часовой стрелке. Все координаты – целые числа, по модулю не превышающие 1000. Многоугольник без самопересечений.

Выходной файл:

В выходном файле должно быть количество точек, из которых прыжок безопасен

Пример

input.txt

3

1 2

2 4

6 3

5

0 0

0 5

5 5

5 1

3 2

output.txt

2

 

Задача B. Бои роботов

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

Соревнования проходили следующим образом: в лабиринт помещаются 2 робота, задаются координаты и начальное направление. После чего их включают, причем для простоты ходит сначала первый робот, затем второй. За один ход робот может либо сделать шаг на одну позицию в текущем направлении, либо повернуться на 90 градусов по часовой стрелке.

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

Помогите в проведении соревнований.

Входные данные (input.txt)

Размеры поля 1<=m,n<=100, координаты первого робота (x1,y1), координаты второго робота (x2,y2), заряд батареек, начальное направление (0-север, 1-восток, 2-юг, 3-запад), для каждого робота далее само поле.

Поле задается нулями и единицами: 0 - проход свободен, 1 - колонна, пройти нельзя.

Для примера:


(1,1) y

0 0 1 0 1

0 0 0 0 0

1 1 1 1 0

x 0 0 0 0 0

Выходные данные (output.txt)

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

Пример

Input.txt

4 5

1 1

4 1

10 10

2 1

0 0 1 0 1

0 0 0 0 0

1 1 1 1 0

0 0 0 0 0

Output.txt

2 1 4 1

 

 

Задача С. Сессия ленивого Вовочки

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

Помогите ему.

Исходный файл input.txt.

Первое целое число N<=16000 - количество заданий. Затем N целых чисел <=32767 - время на выполнения каждого задания.

Выходной файл output.txt.

Содержит N целых чисел, разделенных переводом строки – время, за которое Вовочка должен выполнить каждое задание.

Пример исходного и результирующего файла:

input.txt

20

315

336

318

345

316

303

323

339

336

336

317

345

326

302

322

312

310

324

302

332

output.txt

308

307

306

305

304

303

303

303

303

303

303

303

303

302

302

302

302

302

302

302

 

 

 

Задача D. Деревенская олимпиада в Осинниках

Давным-давно, более шестидесяти лет назад, в деревне Осинники у местных жителей не было никаких развлечений. Но однажды доярка Оля придумала, как скоротать долгие вечера. Так и появилась традиция проводить ежегодную олимпиаду по программированию. В то время в деревне Осинники было мало команд, и для сортировки результатов олимпиады использовали обычный “пузырек”. Со временем олимпиада в Осинниках приобретала все большую популярность, и программа сортировки “пузырьком” обрабатывала результат очень долго. В этом году в олимпиаде собираются принять участие до 80000 команд со всех краев этой деревни. Ваша задача переписать программу сортировки результатов так, чтобы она отработала не более чем за 20 секунд и выдала бы результат в той же последовательности, что и старая программа.

Программа сортировки “пузырьком” выглядит так.

For i:=1 to n do

For j:=1 to n-i do

If a[j]<a[j+1]

begin

temp:=a[j];

a[j]:=a[j+1];

a[j+1]:=temp;

end;

Исходные данные

Исходные данные находятся в файле input.txt. Первое число 1<N<=80000 - число команд частниц олимпиады. Далее N строк, в каждой из которых 2 числа разделенных пробелом, первое - номер команды от 0 до 79999, второе число задач, решенных этой командой (от 0 до 100).

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

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

Пример

Input.txt

6

4 0

5 7

0 2

1 7

3 3

2 2

Output.txt

5 7

1 7

3 3

0 2

2 2

4 0

 

 

Задача Е. Любознательный жучок в Египте

Жучок по имени Сергей был очень любознательным и очень любил считать. Также умел он измерять длину и не упускал возможности что-нибудь измерить. Однажды на каникулах он попал в Египет. Там он захотел измерить периметр знаменитого лабиринта. Лабиринт имеет некоторую закономерность. Эту закономерность легко понять, если ввести некоторые определения.

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

Требуется посчитать периметр лабиринта заданного порядка.

Исходные данные

Исходные данные находятся в файле input.txt - это два целых числа: n<=10000 и длина стороны самого маленького квадрата.

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

Выходные данные пишутся в файл output.txt - это единственное число в экспоненциальной форме, содержащее 14 знаков мантиссы.

Пример

Input.txt

1

1

Output.txt

0.40000000000000Е+0

 

 

Задача H. Хакер Вася

Вася Пупкин решил скопировать с закрытого сервера несколько файлов. Чтобы его было труднее обнаружить, он подключался к серверу через сеть платных маршрутизаторов. Некоторые из них связаны между собой. На сервере, с которого Вася собрался копировать файлы, установлена “умная” защита: как только какой-либо файл был скопирован, сервер проверял легальность такого копирования. Если копирование было нелегальным, сервер блокировал ближайший к нему маршрутизатор, через который файл был скопирован.

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

Входной файл

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

Выходной файл

В результирующем файле (OUTPUT.TXT) требуется выдать минимальную сумму денег, необходимую для копирования файлов, и строку “No solution.”, если все необходимые файлы скопировать нельзя.

Пример 1

Input.txt

4 3 4 2

0 0 0 8

7 0 0 2

14 5 0 30

0 0 0 0

Output.txt

27

 

Пример 2

Input.txt

4 1 3 4

0 14 30 5

0 0 8 0

0 0 0 0

0 7 2 0

Output.txt

No solution.

 

 

Задача F. Про Васю программиста

Жил-был молодой программист Вася. И очень любил он язык Lisp. И вот зародилась в голове у Васи идея - организовать конкурс программистов на Lisp'e. Конкурс он решил сделать многоэтапным, а для одного из этапов он придумал такое задание - написать программу с максимальной вложенностью скобок.

Вася очень занят подготовкой к конкурсу и просит Вас ему помочь - написать программу для подсчета уровня вложенности скобок. Чтобы Вам было легче, Вася ограничил правилами сложность Lisp-программы.

В итоге программа должна быть такой:

* Программа - это список

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

* Элементом списка может быть атом - последовательность латинских букв и цифр, например ABC

* Элементом списка может быть список

* Список может быть пустой

Вот пример списка: ( ABC BCD () (JKL () MNO ))

Входной файл input.txt:

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

Выходной файл:

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

Пример 1

input.txt :

(DEFUN F (L)

(COND

((NULL (CDDR L)) (R (CAR L) (CAR (CDR L))))

(T (IF (L (F (CDR L)) (F (CAR L) (CDR L)))

(PROG ()

(SETQ X (LIST)

(RETURN (F (CDR L)))

)

(PROG ()

(RETURN (F (CAR L) (CDR L)))

)

))

)

)

output.txt

45

Пример 2

Input.txt

(())

Output.txt

10

 

Задача К. Путь камикадзе.

Усама Бен Ладен сидел на склоне горы и пристально смотрел на северо-восток. Где-то там, вдалеке, расположена ненавистная американская военная база. Вечерело. Усама достал карту местности и задумался. Нужно было провести самолет с юго-запада к базе так, чтобы он остался незамеченным американскими средствами ПВО. Карта была разбита на квадранты, в каждом из которых нанесены свежие разведданные. Из данных было ясно, что средства ПВО в каждом квадранте различны и могут засечь самолет, только начиная с определенной высоты. Кроме того, рельеф местности не позволял проводить самолет ниже определенной отметки. Усама поднял уголек с земли и пометил в каждом квадранте карты, на какой высоте следует в нем вести самолет. Проблема оставалась за малым: как это сделать, используя минимальное количество топлива?

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

В первой строке входного файла (input.txt) записаны два целых числа X, Y, определяющие размерность карты (0< X, Y <= 100). Далее в файле задана матрица из X столбцов и Y строк. Значения в матрице – это целые числа, не превышающие 100, записанные Бен Ладеном на карте в каждом квадранте. Карта ориентирована по сторонам света.

Выходной файл

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

Пример Input.txt.

5 4

3 5 2 3 6

6 9 3 7 1

2 4 7 8 2

7 5 3 1 6

Пример Output.txt

22

 

 

Задача L. Любитель лимонада

Мальчик Петя, друг Васи, очень любил программировать. Вот однажды, сидя на студенческой олимпиаде по программированию, он сильно захотел пить. У Пети была бутылка с лимонадом объемом M. Но так как Петя обладал нестандартным мышлением, он решил пить лимонад следующим образом: каждый i-ый раз он выпивал K-тую часть от объема стакана, где K – i-ое число Фибоначчи. Объем стакана V.

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

Необходимо, чтобы Вы посчитали объем оставшегося в бутылке лимонада. Округлить и вывести 4 знака после запятой.

P.S. Числа Фибоначчи вычисляются следующим образом:

С(i)=C(i-1) + C(i-2) т.е. каждое число равно сумме двух предыдущих.

Начальные числа Фибоначчи: 1 1 2 3 5...

Исходные данные(input.txt):

Известно, что данные корректны.

M,V - вещественные, 0<=M<=100, 0<=V<=M

N - целое, 0<=N<=40.

Выходные данные(output.txt):

Дробное число - оставшийся объем лимонада, выведенное с точностью до четырех знаков.

Пример:

input.txt:

2

0.5

2

output.txt:

1.0000

 

 

Задача М. Кот Матроскин и новый забор.

Однажды в студеную зимнюю пору, поссорившись с Шариком, кот Матроскин решил построить себе новую виллу в деревне Простоквашино. Известный своей рачительностью и бережливостью Матроскин заказал архитектору проект виллы, экономя пространство (земля в тех местах была очень дорогая и приходилось экономить каждый квадратный метр), но так, чтобы было где развернуться. Архитектор попросил умного человека рассчитать оптимальный вариант и после 3 дней раздумий он выдал такой ответ: "Оптимальным вариантом является тот, где контур дома будет выпуклым многоугольником". Архитектор согласовал все с Матроскиным , и вот уже стоит в Простоквашино новый дом в 4 этажа. В целях безопасности Матроскин попросил построить высокий забор на расстоянии не меньше 6 метров от дома, чтобы он мог спокойно гулять там.

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

Исходный файл input.txt :

Первая строка файла содержит число вершин многоугольника. Далее файл

содержит столько строк, сколько вершин имеет многоугольник. Каждая строка содержит два целых числа – X и Y (-100000 <=X,Y <= 100000) , координаты вершины многоугольника. Вершины перечислены в порядке обхода многоугольника по часовой стрелке.

Количество строк не больше 100000.

Записать в output.txt число, равное длине забора, с точностью до третьего знака после запятой.

Пример

input.txt

4

1 1

1 3

3 3

3 1

output.txt

14.283

 

 

ЗАДАЧА Р. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ

Широко известная компьютерная фирма выпустила на рынок новый суперкомпьютер, способный выполнять параллельные вычисления на N процессорах. Для этого суперкомпьютера был разработан специальный язык программирования, в который встроены операторы PAR и SEQL - операторы явного указания на последовательный или параллельный характер вычислений операторов, которые следуют за ключевыми словами PAR или SEQL. Каждый оператор должен заканчиваться знаком точки с запятой. Последовательность операторов может заключаться в операторные скобки "{" и "}" (как, например, в языке Си). За ключевыми словами PAR или SEQL обязательно следуют операторные скобки. В начале программы SEQL может не указываться, т.к. предполагается, что вычисления выполняются последовательно.

Найти максимальное число параллельно работающих процессоров, которое может потребоваться для выполнения заданной программы.

Например, последовательность операторов

PAR {

for (i=0; i<n; i++) alpha[i][j]+=alpha[i+1][j+1];

if (Num==func(c,d)) r+=f(Num,34.15);

}

потребует для выполнения 2 процессора, т.к. в операторных скобках после PAR стоят два оператора.

Последовательность операторов

SEQL {

a=b; b=c; c=a;

}

выполняется на одном процессоре.

А последовательность операторов

PAR {

d=4; a=3.14*r;

PAR {

s1=1; s2=2; s3=3;

}

}

потребует для выполнения 5 процессоров.

 

Исходные данные.

Программа для суперкомпьютера. Комментарии в программе не допускаются. Длина файла - не более 10000 символов.

Пример файла input.txt

PAR {

d=4; a=3.14*r;

PAR {

s1=1; s2=2; s3=3;

}

}

Пример файла output.txt

5