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

      2001
Оргкомитет олимпиады желает вам успехов! К пожеланиям успехов присоединяется и Винни-Пух, хорошо известный нетрадиционными методами решения сложных проблем. Задача про Винни-Пуха теперь всегда будет входить в число задач нашей олимпиады.
Задача Название задачи
A Планета Аккермана
B Проблемы на болоте
C Конвертор текста
D Сеть Dream Network Великого Повелителя снов
E Витражи
F Форточки для Билла Гейтса
G Казино Golden Winnie
K Великая китайская стена и предприниматель Вася
L Lexicon и лаборант Вася
M Илья Муромец и Соловей-разбойник
N Нос Буратино
P Праздник у вирусов

Задача A. Планета Аккермана

На днях все космические станции Земли приняли следующее сообщение, пришедшее с далекой планеты.

Приветствуем тебя, планета великих программистов. Программисты Земли, вы должны спасти нас! Мы люди с планеты Аккермана. Все началось с того, что наши предки тренировались для участия в командном чемпионате по программированию. На одной из тренировок они получили задание составить задачу с использованием функции Аккермана. Составили они ее, но решить так и не смогли. К ним присоединялись все новые и новые программисты, но никто не мог решить эту задачу. Днями и ночами думали они о том, как решить эту задачу, и люди стали косо смотреть на них, и тогда они создали свой клуб, но вскоре его запретили по всему миру, т.к. многие члены клуба сходили с ума и кончали жизнь самоубийством. Несмотря на всемирный запрет, задача не давала покоя программистам, и тогда они улетели на далекую планету и создали там свой мир. Свою планету они назвали именем функции Аккермана, их бог был назван Аккерманом, все было подчинено одному Аккерману. Но нам не нравится жить тут, у многих на Земле остались родители, дети, мужья, жены, друзья. Мы хотим вернуться на Землю, но мы знаем, что нам не даст покоя эта задача. О, великие программисты Земли, решите ее и спасите тем самым нас!

Вот условие задачи.

Функция Аккермана определяется на множестве натуральных чисел следующими соотношениями:

B(0,x)=2+x

B(n+1,0)=sg(n)

B(n+1,x+1)=B(n,B(n+1,x)), где sg(n)=1, если n>0, sg(n)=0, если n=0.

В файле input.txt задано некоторое число N<=100000.

В файл output.txt должны быть выведены все возможные пары чисел (n,x), n>=0 и х>2, такие, что |B(n,x)|<=N. Причем, значения должны выводится в определенном порядке. Пары сортируются по возрастанию аргумента n, а для равных n по возрастанию x.

Примеры :

Input.txt

6

Output.txt

1 3

Input.txt

10

Output.txt

1 3

1 4

1 5

2 3

Задача B. Проблемы на болоте

Давным-давно, в дремучем лесу на опушке стояла маленькая деревушка. И только одна тропинка соединяла её с остальным миром. К сожалению, эту тропинку прерывало проклятое болото, в котором частенько тонули жители деревушки. Много людей уходило в дремучий лес с целью поиска нового пути из деревни, но все их попытки не приносили никакого результата, и жителям приходилось пользоваться этой единственной небезопасной ниточкой, связывающей их с внешним миром.

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

К счастью для деревни, жил в ней Иванушка-Умный, который вместо того, чтобы тратить свои силы на поиск нового пути, решил обезопасить существующий. Для этого он просчитал все расстояния между кочками и выделил для каждой кочки те, на которые с неё мог бы допрыгнуть простой житель. А теперь он пытается пронумеровать их так, что, если Вы будете прыгать по кочкам в порядке возрастания их номеров, то точно доберётесь до противоположного берега.

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

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

В первой строке входного файла содержится число кочек N(1£ N£ 700).

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

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

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

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

Пример входного файла:

6

0 0 1 0 1 0

0 0 0 0 1 1

1 0 0 1 0 0

0 0 1 0 1 1

1 1 0 1 0 0

0 1 0 1 0 0

Пример выходного файла:

1 4 3 5 2 6

Задача C. Конвертор текста

Многие пользователи персональных компьютеров до сих пор работают на текстовых редакторах типа Lexicon, которые производят форматирование строк по ширине с помощью вставки дополнительных пробелов. Современные текстовые редакторы между словами оставляют по одному пробелу, а форматирование по ширине осуществляют с помощью изменения интервала между буквами. В связи с этим при загрузке текстовых файлов, набранных в редакторе Lexicon, возникает проблема с лишними пробелами. Как правило, их приходится удалять вручную. От Вас требуется написать препроцессор для конвертора текстовых файлов в файлы Microsoft Word. Ваша программа должна прочитать входной файл input.txt, в котором находится исходный текст, и вывести результат в файл output.txt. В результирующем тексте между всеми словами ваша программа должна оставить лишь по одному пробелу. Разбиение на строки необходимо сохранить.

Замечание:

Все строки во входном файле не длинее 250 символов и объем входного файла не более 100 Кб.

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

**Всем**известно,**что**очень**многие**до*сих

пор**работают**на**текстовых**редакторах**тип

Lexicon,**которые**производят**форматирование

cтрок*по*ширине*с*помощью*пробелов.****

********

**ВСЕ!!!***

 

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

**Всем*известно,*что*очень*многие*до*сих

пор*работают*на*текстовых*редакторах*тип

Lexicon,*которые*производят*форматирование

cтрок*по*ширине*с*помощью*пробелов.

********

**ВСЕ!!!

 

Замечание: В примере для наглядности пробелы заменены звездочками. Ваша задача должна выводить текст с пробелами.

Задача D. “Сеть Dream Network Великого Повелителя снов

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

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

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

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

Количество снов, которое может быть отправлено за ночь (количество может быть дробным и должно быть получено с точностью 3 знака после точки).

Если количество снов бесконечно, то вывести в файл число: 1000000000.000.

Пример:

Input.txt

10 1 1 22

 

Output.txt

2.000

Input.txt

9 1 1 25

 

Output.txt

2.500

Input.txt

0 0 1 25

 

Output.txt

1000000000.000

Задача Е. “Витражи “

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

Долго мой знакомый переворачивал стекла, соединял друг с другом, но не мог собрать нужный прямоугольник. И тогда он обратился ко мне за помощью. Я же решил дать вам эту задачку. Можно ли из данных кусочков стекла собрать заданный прямоугольник?

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

Мастер предоставил мне список кусочков в файле input.txt . В первой строке расположены два числа - размеры рамки. Во строке число N (N<=10) - количество стекол для витража. На остальных N строчках по два числа - размеры каждого кусочка. Все размеры целые и меньше 1000.

         

Это пример витража из

         

прямоугольников

         

к задаче Е

           

 

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

Поместите в фаил output.txt строчку "YES", если используя все кусочки можно собрать прямоугольный витраж, иначе поместите "NO" .

Пример
input.txt
50 40
8
10 30
10 10
10 30
20 10
20 20
10 10
10 20
10 40
output.txt
YES

Задача F. “Форточки для Билла Гейтса “

Компания MicroSoft объявила о приеме на работу новых специалистов, в том числе и программистов. Президент компании обратился в наш ВУЗ с просьбой помочь найти необходимых ему людей. Мы, конечно, не смогли отказать. Для проведения отборочного тура господин. Bill Geits предложил следующее задание (это задание используется для отбора специалистов по всему миру).

Имеется операционная система с оконным интерфейсом. На экране монитора расположены два окна (возможно одно перекрывает другое). Необходимо определить: возможно ли так расположить окна, чтобы они не перекрывали друг друга и занимали полностью весь экран. При этом окна можно растягивать только пропорционально, т.е. пропорции окна не должны меняться. Например, пусть у нас имеется окно размером 80х40, т.е. его пропорции 2:1. Мы можем увеличить окно в 2,5 раз, получим окно размером 200х100. Легко заметить что пропорции окна остались 2:1.

Во входном файле input.txt содержится следующая информация:

MaxX, MaxY - два целых положительных числа (не более 10000) -

размер экрана по x и y соответственно.

Затем следуют две пары целых чисел - размер первого и второго окна соответственно.

Например: input.txt

640 480

160 60

160 60

Здесь 640 480 - размер экрана.

160 60 - размер первого окна.

160 60 - размер второго окна.

В выходном файле output.txt должно быть одно число:

1 - если окна можно расположить указанным образом,

0 - если такое сделать невозможно.

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

Задача G. Казино Golden Winnie “

Однажды Винни-Пух, насмотревшись телевизора, решил открыть в своём лесу казино “Golden Winnie”. Всем жителям леса было в диковинку такое новое заведение, и все толпой, как заколдованные, пошли на манящий блеск огоньков, которые Винни развесил у входа в норку. Самой интересной игрой были кости на пятом столе, который все звери и окружили. Правила игры были очень просты.

Игрок бросал три кости, на гранях которых имеются цифры 1, 2, 3. 4, 5, 6. Затем для каждой кости подсчитывалась сумма очков, которая равнялась сумме цифр на верхней и на нижней грани. И если эта сумма для всех трёх костей была одна и та же, то выигрывал игрок, иначе ставки уходили владельцу казино.

Первым свой горшочек мёда проиграл Пятачок. Затем опустошил своё ведро моркови Кролик. И только после того, как ослик Иа отдал свой хвост, который ему только что подарили на день рождения, умная Сова воскликнула: “Друзья, а кубики-то, наверное, неодинаковые!”. Тут поднялся шум и крик. Кто требовал вернуть награбленное, кто хотел наказать Пуха, а кто просто стоял в стороне и улыбался. В этот момент Винни бросил на стол кости и сказал: “Если ты, Сова, такая умная, покажи, какой же здесь кубик отличается от других!”. Сова задумалась…

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

Входные данные в файле input.txt

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

Выходные данные Ваша программа должна записать в файл output.txt

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

Пример входного файла input.txt

6

4 2 3

1

5

4 2 3

1

4

1 2 6

3

Пример выходного файла:

2

Задача K. “Великая китайская стена и предприниматель Вася

Мелкий предприниматель Вася решил стать крупным бизнесменом и заработать много денег. Всем известно, что сейчас кирпич в цене. Вася подумал: “а зачем китайцам такая толстая Великая стена? Они не обидятся, если я позаимствую у них внешний слой кирпича с Великой стены”. Таким образом, Вася решил демонтировать внешний слой кирпича с Великой стены. (Почему верхний? Да чтоб никто не догадался!) Но Вася не знает, сколько метров кирпича в длину ему нужно демонтировать, однако он знает, сколько денег он хочет заработать. Условия у Васи следующие.

1) Вася демонтирует кирпичи по вертикальным рядам, т.е. вертикальный ряд кирпича – это минимальная единица длины, которую Вася может демонтировать.

2) Известно, что один кирпич стоит на рынке M рублей. Вася хочет заработать N рублей

3) Вася не жадный человек и он хочет демонтировать минимальное количество рядов, чтобы ему хватило их на заработок N рублей и не более.

4) Если кирпич не целый, то Вася его не считает кирпичом.

Таким образом, Вася хочет знать, сколько рядов кирпичей ему необходимо демонтировать.

Историческая справка: Великая стена простирается в длину на бесконечное расстояние. Фундамент у Великой стены на всем ее протяжении строго горизонтальный. Верхняя граница стены описывается функцией: , первый вертикальный ряд кирпича – это x=0. Крипич считается целым, если высота его левой вертикальной стороны совпадает с H - высотой целого кирпича.

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

0<=N, M, H, W, A, B, C, D<=2000000000, где H – высота кирпича, W – ширина кирпича. Все числа целые.

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

Количество рядов, которое необходимо демонтировать.

Пример:

Input.txt

2 1 1 1 2 0 0 2

Ouput.txt

2

Input.txt

1 1 1 2 2 0 1 0

Output.txt

2

Input.txt

2 1 1 2 2 0 1 0

Output.txt

3

 

Задача L. “Lexicon и лаборант Вася

Студент АлтГТУ Вася решил подработать Медицинском Институте в качестве лаборанта. Умея работать на компьютере нарисовал Вася однажды табличку по учету больных. Компьютер там стоит Intel-286 с 1 мегабайтом оперативной памяти и 40 мегабайтным винчестером, так что пришлось Васе работать в текстовом редакторе.

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

Испорченная таблица находится в файле input.txt, после работы программы исправленная таблица должна находиться в файле output.txt, причем таблица должна быть минимальной ширины, т.е. слова могут касаться линий таблицы и все слова должны быть придвинуты до конца влево. В таблице могут быть только знаки пробела и английские буквы (на компьютере у Васи нет русификатора), колонки таблицы ограничены знаками +, -, |. Длина строк не более 250 символов и их количество не более 100.

Замечание: ASCII коды символов таблицы: “+” – 2Bh, “-” – 2Dh, “|” – 4Ch.

Пример файла Input.txt:

+------------+---------------------------------------+

| number | Name |

+------------+---------------------------------------+

| 001 | Kolosov|

| 22| Shalnev A |

| 3| Radchenko |

| 33| Chertenkov |

+--------+-------------------+

| 19999| Year|

+---+----------------------------------------------+

| 3 | Kruchkova |

+-----------+----------+

Пример файла оutput.txt:

+------+----------+

|number| Name |

+------+----------+

|001 |Kolosov |

|22 |Shalnev A |

|3 |Radchenko |

|33 |Chertenkov|

+------+----------+

|19999 |Year |

+------+----------+

|3 |Kruchkova |

+------+----------+

Задача M. Илья Муромец и Соловей-разбойник

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

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

Разгневался князь, ведь Соловей младший остался на свободе. Приказал князь Илье вспомнить сколько, в какой последовательности и какие удары он наносил по щиту Соловья младшего, а своего советника заставил записать все это в файле “input.txt”. Структура файла:

1) на первой строке находятся два целых числа - начальные размеры щита по оси X и по оси Y (оба значения не более 100);

2) на второй строке находится целое число N - количество ударов мечом (N<= 100);

3) на каждой N последующих строк описан один удар. Это две пары целочисленных координат (x1,y1)-(x2,y2) такие, что если через них провести прямую, то она пройдет точно по месту удара мечом по щиту. Все значения координат по модулю меньше 100.

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

Ваша задача – помочь советнику создать макет оставшегося щита у Соловья к моменту окончания боя, чтобы оценить достаточно ли храбро дрался Илья, или он просто отпустил Соловья младшего. Вы должны сформировать файл “output.txt”. В файл Вы должны записать:

    1. число вершин щита, оставшегося в руках у Соловья;
    2. координаты всех углов щита в порядке обхода против часовой стрелки. Угловые точки необходимо перечислять начиная от ближней к началу координат вершины. Если таких точек несколько, то Вы должны начинать перечисление с той точки, у которой меньше координата Y. Вычисленные Вами координаты должны быть с точностью 3 знака после точки.

Пример:

Input.txt:

10 10

1

1 0 0 2

 

Output.txt:

5

1.000 0.000

0.000 2.000

0.000 10.000

10.000 10.000

10.000 0.000

Input.txt:

10 10

2

1 0 0 1

6 0 6 1

Output.txt:

5

1.000 0.000

0.000 1.000

0.000 10.000

6.000 10.000

6.000 0.000

Input.txt:

10 10

2

1 0 0 1

4 1 4 2

Output.txt:

4

4.000 0.000

4.000 10.000

10.000 10.000

10.000 0.000

 

Задача N. Нос Буратино

Буратино потерял свой золотой ключик. дверь в каморке папы Карло имеет N (N<=9) различных по глубине замочных скважин. Хитрый Буратино пытается открыть дверь, засовывая свой длинный нос в скважины. Дверь откроется тогда, когда длина носа строго совпадет с глубиной какой-либо из скважин. С каждой попыткой нос у Буратино удлиняется или уменьшается на целое число сантиметров. Изменение длины носа Буратино зависит от номера замочной скважины.

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

Исходные данные находятся в файле input.txt. Первая строка содержит два целых числа N и К число замочных скважин и первоначальная длина носа у Буратино. Остальные N строк содержат через пробел два целых числа – глубину скважины и число, указывающее, на сколько изменится нос Буратино при неудачной попытке засунуть нос в эту скважину. Скважины упорядочены по возрастанию номеров, начиная с нулевой.

Результат Ваша программа должна записать в файл output.txt. Этот файл должен содержать номера скважин, засовывая в которые в указанном порядке нос, Буратино откроет дверь. Следите , чтобы у Буратино оставался хоть какой-то нос. Носов нулевой или отрицательной длины не существует, а тем более у Буратино!

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

4 15 0 2 3

3 –10

7 5

9 –1

4 2

Задача P. Праздник у вирусов

Однажды летом на нашу планету упал метеорит, на котором прилетели неизвестные земной науке вирусы. При проходе метеорита через плотные слои атмосферы выжили всего N вирусов (0<N<300). Земля вирусам очень понравилась, и они решили здесь обосноваться. Каждый вирус порождает в день M потомков. Каждый вирус живёт бесконечно долго. (Например, если на Землю прилетели 3 вируса, то уже на следующий день их будет 3+3M.)

У вирусов наступает праздник "Х" если сумма цифр их популяции делится на X. Вам нужно определить, сколько праздников "Х" отметят вирусы за K (K<100) дней.

Во входном файле input.txt задано четыре целых числа, N, M, K, X.

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

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

2 2 1 4

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

1