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

      1999

ЗАДАЧА A "Трудолюбивый Дятел"

Дятел решил позавтракать и заодно принести пользу родному лесу. Он выбрал сосну, под которой не было ни одной шишки, и начал охоту за жуками и гусеницами. Чтобы достать одного жука, дятлу надо ударить по сосне N раз, а одну гусеницу - M раз. При каждом ударе с сосны падает ровно одна шишка. После того, как дятел позавтракал и улетел, под сосной осталсь S шишек. Дятел никогда не бросает дело на полдороге и если он начал доставать добычу, он ее обязательно достанет.
Сколько жуков и гусениц добыл дятел?

Исходные данные:
N M S - целые положительные числа, не превышающие 2000.
Результат:
Если задача не имеет решения, то результирующий файл содержит единственное число 0.
Если задача имеет решение, то результирующий файл должен содержать столько строк, сколько имеется вариантов решения. На каждой строке должны быть выведены два числа: количество добытых жуков и гусениц. Варианты выводятся в порядке возрастания первого числа в строке ответа.

Пример 1.
Файл input.txt
        Файл output.txt
1 2 5
        1 2
          3 1
          5 0

Пример 2.
Файл input.txt
        Файл output.txt
4 2 5
        0

ЗАДАЧА B "Умный Паучок"

Паучок сплел паутину из N концентрических окружностей радиуса 1, 2, ..., N сантиметров. Эти концентрические окружности с помощью радиальных растяжек паучок укрепил на окрестных веточках. Для этого каждую окружность радиуса R паучок разделил на одинаковые сектора, число которых зависит от номера окружности: на окружности радиуса 1 четыре точки, на окружности радиуса 2 - восемь точек и т.д., т.е. на каждой следующей окружности точек в два раза больше, чем на предыдущей. Затем паучок провел из окружностей растяжки так, что каждая растяжка от окружности радиуса R соединяется со всеми окружностями большего радиуса. Паучок очень аккуратный и любит навести во всем порядок, поэтому все точки соединения нитей он пронумеровал номерами 1, 2,...,К, последовательно проходя по окружностям:

Когда паутина была полностью готова, паучок приступил к охоте и поймал M комаров. Есть свою добычу паучок не стал, а решил оставить ее про запас. В M точках с номерами a[1], a[2],..., a[M] паучок подвесил свою добычу, каждого пойманного комара в отдельной точке.
Сколько свободных точек на последней окружности осталось?

Исходные данные:
В первой строке исходного файла заданы N M - целые неотрицательные числа, не превышающие 10. Во второй строке исходного файла заданы целые числа a[1] a[2] ... a[M].

Результат:
На первой строке - число свободных точек на последней окружности.
На второй строке - номера этих точек в порядке возрастания номеров.

Пример 1.
Файл input.txt
3 5
3 27 13 6 26
Файл output.txt
13
14 15 16 17 18 19 20 21 22 23 24 25 28

Пример 2.
Файл input.txt
1 4
1 2 3 4
Файл output.txt
0

ЗАДАЧА C "Фальшивая монетка"

В банке "Сибирская звезда" получили информацию, что в полученной партии из N золотых монет имеется одна фальшивая. Все "правильные" монеты имеют одинаковый вес, а фальшивая монета - либо тяжелее, либо легче настоящей монетки (соотношение весов фальшивой и настоящей монеты неизвестно ). Весы в банке есть, а гирек к ним нет, поэтому взвесить отдельно каждую монету не представляется возможным. В банке решили взвешивать монетки по группам, накладывая на левую и правую чашку весов по одинаковому количеству монет при каждом взвешивании. На каждой монете фломастером написали ее номер, который изменяется от 1 до N. Затем провели K взвешиваний.
Ваша программа должна определить номер фальшивой монеты или указать, что однозначно определить номер невозможно.
Исходные данные:
В первой строке указаны N и K - целые положительные числа, не превышающие 100. Следующие 2*K строк описывают каждое взвешивание. Первая из них начинается целым числом P[i] - число монет, помещенных на левыю и правую чашку весов. После этого указаны 2*P[i] целых чисел - номера монет сначала на левой чашке весов, а затем на правой чашке. Следующая строка содержит один из трех символов: '<', '>', '='. Эти знаки означают следующее:

Результат:
Если однозначно определить фальшивую монету невозможно, то Ваша программа должна вывести 0. В противном случае вывести номер фальшифой монеты.

Пример 1.
Файл input.txt
5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=
Файл output.txt
3
Пример 2.
Файл input.txt
6 4
3 1 2 3 4 5 6
<
1 1 2
= 2 1 3 4 5
<
2 4 5 2 6
>
Файл output.txt
0

ЗАДАЧА D "Системы счисления"

Известно, что в позиционной системе счисления позиция каждой цифры в числе определяет вес этой цифры в общем значении числа. Например, в системе счисления с основанием 10 в числе 746 цифра 7 имеет вес 100, цифра 4 - вес 10, цифра 6 - вес 1, так что общее значение числа 746 равно 7*100+4*10+6*1.
Рассмотрим теперь пару чисел x и y, каждое их которых представлено в некоторой системе счисления. Цель Вашей программы - определить две такие системы счисления с такими минимальным основаниями N и M (N,M>1), что число x в системе счисления с основанием N равно числу y в системе счисления с основанием M. Числа x и y имеют не более 7 цифр. Цифры представляются знаками 0, 1, 2,...,9 и буквами A, B, C,...,Z. Таким образом, значение N и M не превышает 36.
Если для двух заданных чисел нельзя найти N,M<37 то Ваша программа должна выдать число 0.

Исходные данные: В единственной строоке исходного файла заданы два целых числа x и y.
Результат:
В выходной файл вы должны вывести строку
x(основание N) = y(основание M)

Пример 1.
Файл input.txt
12 5
Файл output.txt
12(основание 3) = 5(основание 6)
Пример 2.
Файл input.txt
132 456
Файл output.txt
0

ЗАДАЧА E "Робот-библиотекарь"

Книги в читальном зале стоят на полках. Перед открытием книги на каждой полке стоят в строгом порядке. Одну полку с наиболее часто спрашиваемыми книгами обслуживает робот. На этой полке N книг, где N не более 100. Робот умеет выполнять две команды читателей и одну команду директора читального зала:

Расставляя книги робот комментирует свои действия: Ваша программа должна вывести слова, произносимые роботом во время работы.

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

Результат:
Каждая строка результирующего файла представляют собой одну фразу, произнесенную роботом. Название книги должно быть заключено в кавычки. Если роботу нечего делать на все команды НАВЕДИ ПОРЯДОК, результирующий файл должен быть пустым.

Пример 1.
Файл input.txt
6
Отелло
WINDOWS-95 для чайников
С++
Программирование на языке ПАСКАЛЬ
Алиса в Зазеркалье
Месть крысы из нержавеющей стали
ДАЙ "С++"
ДАЙ "Алиса в Зазеркалье"
ДАЙ "Отелло"
ВОЗЬМИ "Алиса в Зазеркалье"
ДАЙ "WINDOWS-95 для чайников "
ВОЗЬМИ "С++"
ДАЙ "Программирование на языке ПАСКАЛЬ"
НАВЕДИ ПОРЯДОК
ВОЗЬМИ "Отелло"
ДАЙ "Алиса в Зазеркалье"
НАВЕДИ ПОРЯДОК
Файл output.txt
ставлю "C++" в начало полки
ставлю "Алиса в Зазеркалье" после "С++"
ставлю "Отелло" в начало полки

Пример 2.
Файл input.txt
6
Отелло
WINDOWS-95 для чайников
С++
Программирование на языке ПАСКАЛЬ
Алиса в Зазеркалье
Месть крысы из нержавеющей стали
ДАЙ "С++"
НАВЕДИ ПОРЯДОК
ДАЙ "Алиса в Зазеркалье"
ДАЙ "Отелло"
ДАЙ "WINDOWS-95 для чайников "
ДАЙ "Программирование на языке ПАСКАЛЬ"
НАВЕДИ ПОРЯДОК
НАВЕДИ ПОРЯДОК
Файл output.txt

ЗАДАЧА E "Новоселье Бабы Яги"

Баба Яга решила переехать в новую избушку на курьих ножках. Она упаковала все свои пожитки в N коробков и узелков. Вес i-го багажа равен a[i] килограммов. Личный транспорт Бабы Яги известен - ступа грузоподъемностью S килограммов. Сможет ли Баба Яга перевезти все свое добро не более чем за К рейсов? Если сможет, то Ваша программа должна дать один из способов такой перевозки.
Значения K и N не превышают 6; значения S и всех a[i] - целые неотрицательные числа, не превышающие 200.

Исходные данные:
В Первой строке исходногофайла указаны три целых числа S, K, N. Вторая строка содержит N целых чисел a[1], a[2],...,a[N].

Результат:
Если решения нет, то результирующий файл содержит единственное число 0. Если решение есть, то результирующий файл содержит K строк, в каждой j-ой строке которого указаны номера вещей, перевозимых за j-ый рейс. Если за один рейс Баба Яга перевозит несколько вещей, то они должны быть указаны в порядке возрастания номеров.

Пример 1.
Файл input.txt
5 2 3
4 2 4
Файл output.txt
0
Пример 2.
Файл input.txt
6 2 3
4 2 4
Файл output.txt
1 2
3

ЗАДАЧА F "Старинный парк"

Границы старинного парка много раз изменялись в течение столетий, поэтому городские архитекторы решили заняться реконструкцией его границ.
План старинного парка представляет собой многоугольник (не обязательно выпуклый) c N вершинами. Многоугольник задан координатами вершин. Вершины заданы своими координатами и перечислены в порядке обхода границы парка по часовой стрелке. Сколько дополнительных участков можно присоединить к парку, если построить дополнительные прямые между точками вершин границы парка так, чтобы многоугольник стал выпуклым?

Исходные данные:
В первой строке исходного файла указано целое число положительное число N, не превышающее 100. Последующие N строк содержат пары целых чисел x[1] y[1]
x[2] y[2]
...
Здесь все x[i] и y[i] - все целые положительные числа, не превышающие 100.
Результат:
Вы должны вывести целое число - количество присоединенных к парку участков.

Пример 1.
Файл input.txt
7
0 0
2 1
2 2
0 4
5 3
4 1
5 0
Файл output.txt
2

ЗАДАЧА G "Али-Баба и программист"

Али-Баба, сорок разбойников и один программист решили добыть сокровища - каждый своим способом. Али-Баба, зная тайное слово, пошел к пещере с сокровищами. Сорок разбойников засели в кустах у дороги, чтобы поймать Али-Бабу, когда тот будет возвращаться из пещеры. А программист решил "взломать" шифр - найти тайное слово для доступа к сокровищам. Для этого он решил перебирать слова, составленные из букв алфавита, которым пользуется Али-Баба. В алфавите N букв. Известно, что тайное слово имеет не более L символов длины. Какое максимальное количество слов может сгенерировать программа?
Например, если в алфавите Али-Бабы только два символа А и Б, то для L=3 программист может сгенерировать следующие 14 слов: А, Б, АА, АБ, БА, ББ, ААА, ААБ, АБА, АББ, БАА, БАБ, ББА, БББ.

Исходные данные:
В исходном файле указаны два целых числа N и L, не превышающие 100.

Результат:
В выходной файл Вы должны вывести единственное целое число - количество различных слов из N символов длины не более L.

Пример 1.
Файл input.txt
2 3
Файл output.txt
14
Пример 2.
Файл input.txt
2 4
Файл output.txt
30