Задачи областного тура

XV олимпиада по информатике школьников Свердловской области
30-31 января 2002г.

Программный комитет: Прохоров В. В. (председатель), Лукоянов Н. Ю., Петров А. С., Прохорова М. Ф.

(Предложено Всероссийской методкомиссией, доработка В. В. Прохоров)

В театре имеется N мест, пронумерованных натуральными числами от 1 до N.

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

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

Требуется

определить количество зрителей, которые пересаживались в антракте согласно описанной процедуре.

Формат входных данных

1-я строка содержит натуральное число N (N<1001) - количество мест в театре.

2-я строка содержит последовательность из N целых чисел, записанных через разделитель, удобный для используемого языка программирования (следует указать в комментарии, какой разделитель следует использовать), где первое число - номер места в билете у зрителя, который перед антрактом занимал место с номером 1, второе - номер места в билете у зрителя, который занимал место с номером 2, и т.д. Если какое-то место было свободно, то соответствующее число равно 0.

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

Формат выходных данных

Одно число - количество зрителей, которые пересаживались в антракте (включая "зачинщика").

(Автор идеи - Н. Ю. Лукоянов, текст - В. В. Прохоров)

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

Требуется

(а) определить длину резинки в положении равновесия системы;

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

Формат входных данных

1-я строка содержит натуральное число N (N<21) - количество стержней;

в последующих N строчках задаются (через разделитель, удобный для используемого языка программирования - следует указать в комментарии, какой разделитель следует использовать) координаты x_i, y_i ( |x_i|<51, |y_i|<51, i=1,:, N) точек соединения стержней при обходе рамки в порядке соединения стержней;

последняя (N+2-я) строка содержит число -1, если все колечки могут перемещаться свободно по своим стержням, в противном случае - отношение расстояния от колечка, закрепленного на стержне с концами (x₁, y₁) и (x₂, y₂), до точки (x₁, y₁) к длине отрезка (x₁, y₁)-(x₂, y₂) (полагаем, что может быть закреплено только колечко, надетое на стержень с концами (x₁, y₁), (x₂, y₂).

Формат выходных данных

Число - длина резинки в положении равновесия с точностью не хуже 3-х значащих цифр.

(Автор идеи - А.С. Петров)

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

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

Требуется

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

Формат входных данных

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

Формат выходных данных

Если задача разрешима, то должна быть выдана строка

ДВП приготовить можно

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

Приготовить ДВП не получится

(Автор идеи - А. С. Петров, автор фабулы - В. В. Прохоров)

В пустое интернет-кафе, предоставляющее L компьютеров, зашла компания из N человек. Каждому из них необходимо лично отправить определенное количество электронных писем: 1-му - n₁ писем, 2-му - n₂, 3-му - n₃ и т.д. Процедура отправки любого из имеющихся электронных писем на любом из компьютеров интернет-кафе занимает ровно одну минуту. Компании хотелось бы потратить на все как можно меньше времени.

Требуется

для заданных L, N и n_i (i=1,:,N) определить минимальное время, через которое компания, отправив все сообщения, сможет пойти дальше.

Формат входных данных

1-я строка содержит натуральное число L (L<51).

2-я строка содержит натуральное число N (N<101).

3-я строка содержит последовательность из N целых чисел n_i (n_i<51, i=1,:,N), записанных через разделитель, удобный для используемого языка программирования.

Формат выходных данных

Одно число - минимальное время в минутах, за которое компания может отправить все сообщения.

(предложено Всероссийской методкомиссией)

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

Путь пчелы задается в виде последовательности пар следующего вида: сначала записывается буква (x, y или z), определяющая направление движения, затем - целое число задающее, на сколько сот пчела перемещается в этом направлении.

Требуется

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

Формат входных данных

В 1-й строке задается целое число N (N<=32000) - количество звеньев пути пчелы из начальной соты в конечную.

В последующих N строках содержатся описания звеньев пути пчелы из начальной соты в конечную в порядке ее перемещения. В каждой строке сначала идет буква (x, y или z), определяющая направление движения. А затем - целое число K, задающее, на сколько сот пчела перемещается в этом направлении. Буква и число разделяются ровно одним пробелом.

Формат выходных данных

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

(Автор идеи - А. С. Петров)

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

Требуется

определить, может ли панда составить некоторую фразу, если у нее есть следующий набор табличек (по 1 штуке каждого вида):

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

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

Формат входных данных

1-я строка содержит одно число - количество лап у панды (<=10),

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

Формат выходных данных

Если фразу составить можно, то

в 1-й строке - последовательность текстов на табличках через пробел в том порядке, в котором они составляют заданную фразу,

во 2-й строке - количество табличек, использованных при составлении фразы.

Если составление фразы невозможно, то следует вывести одно слово - "невозможно".