Интересная задачка с муниципального этапа Кемеровской области 2012.
Моя огромная благодарность Ганиловой Татьяне, за помощь в подготовке учащихся нашей гимназии к олимпиаде и подбор задач. Тесты у меня.
Паркет
Ограничение по времени: 1 секунда
Ограничение по памяти: 16 Мб
В далекой заморской земле в самом большом здании
города, представляющем собой прямоугольник размерами N * M,
решено положить новый паркетный пол. После продолжительных обсуждений на
всеобщем городском совете был, наконец, одобрен следующий проект: фигурками
вида (только такие паркетные доски и производит местная паркетная фабрика):
Ясно, что некоторые из приобретенных фигурок при
укладке рисунка придется распилить. При этом возможно, некоторые части, на
которые разделили фигурку, не будут участвовать в формировании рисунка. Вам
необходимо определить минимальное количество фигурок требующих распила.
Например, если размеры здания 3x4, то можно будет
уложить 2 целых фигурки, а еще одну придется распилить. На рисунке ниже части,
на которые распилили дополнительную фигурку, закрашены серым цветом.
Формат входного файла: В единственной строке
входного файла содержатся два натуральных числа N и M,
не превосходящие 109 – размеры прямоугольника, который необходимо
замостить указанными фигурками.
Формат выходного файла: Необходимо вывести одно
целое число – количество фигурок, которые придется распилить при укладке
рисунка.
Пример:
2 9 3
parket.in
|
parket.out
|
3 4
|
1
|
2 6
|
2
|
Словарь
Ограничение по времени: 1 секунда
Ограничение по памяти: 16 Мб
В языке одного из племен, затерянных на
марсианских просторах, все слова одной и той же длины N, причем буквы в каждом
слове попарно различны. В алфавите этого племени насчитывается N
букв. Ученые-марсологи выяснили, что в словарь входят все возможные перестановки
из N букв.
Переводчик в своем походном марсианско-русском
словаре обозначает первую букву марсианского алфавита за «A»,
вторую за «B» и так далее (N не превосходит 20).
Разумеется, слова в словаре упорядочены по алфавиту. И когда он встречает в какой-нибудь
марсианской книге редко используемое слово, ему приходится долго листать
словарь в поисках перевода. Помогите переводчику по марсианскому слову
определить его порядковый номер в словаре.
Формат входного файла: В первой строке файла
записано натуральное число N, не превосходящее 20, -
длина слова. Следующая строка содержит марсианское слово для перевода. Слово
состоит из заглавных латинских букв.
Формат выходного файла: Необходимо вывести одно
целое число – порядковый номер этого слова в марсианско-русском словаре.
Примеры:
slovar.in
|
slovar.out
|
3
ABC
|
1
|
3
BCA
|
4
|
Школа
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 Мб
В школе некоторые из ребят хотели бы перейти из
своего класса в другой, параллельный. Однако сделать это можно только в том
случае, если кто-то из учеников этого класса также решит сменить класс – и
освободит, таким образом, место. Скажем, ученик «10А» Антон сможет перейти в
«10Г», если, например, Вера из «10Г» захочет перейти в «10Б», а Лена из «10Б» –
в «10А».
Вам известны предпочтения ребят (ровно одно для
каждого ученика). Необходимо определить длину максимальной цепи переходов
учеников из класса в класс. Например, в разобранном выше случае длина цепи
переходов составляет 3.
Формат входного файла: В первой строке входного
файла задано количество N учеников, желающих перейти
в другой класс. Каждая из следующих N строк состоит из имени
ученика, буквы класса (отделенной от имени одним пробелом), в котором он
учится, и отличной от нее буквы класса (также отделенной одним пробелом), куда
хочет перейти. Используются только латинские буквы. Буквы класса – прописные.
Длина имени ученика не превосходит 20.
Формат выходного файла: Одно целое число – длина
максимальной цепи переходов.
Пример:
school.in
|
school.out
|
5
Anton A G
Petr G A
Roma B V
Vera G B
|
3
|
Примечание. В приведенном примере возможны две
цепочки переходов:
1. Anton из A в G, Petr из G в A – цепочка длины 2;
2. Anton из A в G, Vera из G в B,Lena из B в A –
цепочка длины 3.
1. Anton из A в G, Petr из G в A – цепочка длины 2;
2. Anton из A в G, Vera из G в B,
