Задачи 1 тура чемпионата 2012 года

Открытый турнир СыктГУ по программированию Первый личный тур

1 декабря 2012 года

Задача A.  Шахматный конь

Ограничение по времени:            2 секунды
Ограничение по памяти:              64 мегабайта

Межгалактический отдел звездных головоломок «МОЗГ» очень престижная организация, прежде чем принять на стажировки очередную «светлую голову» она проводит массу тестов для соискателей. Один из низ касается любимой игры этого узкого круга ученых — шахматы. Первым является тест на скорость, наниматель говорит клетку стандартной шахматной доски 8x8, а вы называете, сколько клеток бьет стоящий на этой клетке конь.
Формат входного файла
В единственной строке задана клетка поля в формате А1 (латинская буква + цифра)
Формат выходного файла
Вывести количество клеток, которые может бить конь.
Пример входного и выходного файлов
input    output
А1         2
D4         8
G6         6

Задача B.  Любопытство

Ограничение по времени:            2 секунды
Ограничение по памяти:              64 мегабайта

Межгалактический отдел звездных головоломок «МОЗГ» продолжает исследования на красной планете. В данный момент Curiosity находится находится в кратере потухшего вулкана и должен собрать по 40 образцов красного и синего камней (заумные названия оставим ученым). Сначала марсоход делает одно движение — берет камень и кладет его в отсек для красных камней, если все правильно — продолжаем набирать камни, если же взятый камень оказался синим, система предупреждает об этом, и марсоход делает — второе движение — перекладывает камень в отсек для синих камней, либо отбрасывает в сторону, если отсек заполнен (мы уже нашли 40 синих камней). Как только «красный» отсек заполнен — продолжаем все те же действия для синих камней. Спектральный анализ показал, что вокруг Curiosity лежит А красных камней и В синих.
Формат входного файла
В одной строке даны числа А, В (40 <= А, В <= 100).
Формат выходного файла
Вывести максимальное количество движений, которое может сделать робот в наихудшем случае, чтобы заполнить отсеки нужным количеством камней.
Пример входного и выходного файлов
input             output
40 40             120
100 40           239

Задача C.  Светлячки

Ограничение по времени:            2 секунды
Ограничение по памяти:              64 мегабайта
Межгалактическому отделу звездных головоломок «МОЗГ» необходимо совершить совершенно рутинную операцию — перезарядить батарею плазменной пушки, которая используется для разрушения подлетающих к базе астероидов и планетарных осколков. Заряжается батарея шарообразными сгустками энергетической плазмы ака «светлячками». Принцип довольно простой: контейнер открывается и в батарею начинают быстро влетать «светлячки» с определенными зарядами. Но корпус батареи может выдержать конечное количество энергии, иначе разорвет оболочку. Что радует, контролировать процесс перегрузки ненужно, при попадании в батарею «светлячка», которые начинает перегружает батарею, она автоматически отторгает по очереди «светлячков» с минимальными зарядами, чтобы сохранить последний влетевший.
К примеру вместимость батареи 10 Гигаватт, в нее влетают по очереди «светлячки» с энергией 3, 1, 2, 7, 9 Гигаватт соответственно. Тогда при попадании заряда в 7 Гигаватт батарея отторгнет заряды 1 и 2 по очереди, чтобы заряд остался 10, при попадании следом заряда в 9 Гигаватт, батарея отторгнет заряды 3 и 7 — в таком порядке.
Необходимо определить порядок отторжения зарядов и конечный заряд батареи.
Формат входного файла
В первой строке содержится два числа N (1 <= N <= 105) и Е (1 <= Е <= 106) — количество «светлячков» и максимальный заряд батареи.
Во второй строке содержится N целых чисел Ks (1 <= Ks <= E) — заряды «светлячков» в порядке запуска.
Формат выходного файла
В первой строке необходимо вывести финальный заряд батареи. Во второй строке нужно вывести заряды в порядке отторжения.
Пример входного и выходного файлов
input                                  output
5 10                                   9
3 12 7 9                             12 3 7

5 20                                   19
10 9 2 1 9                          9 12

Задача D.  Странный язык

Ограничение по времени:            2 секунды
Ограничение по памяти:              64 мегабайта
На одной из глухих планет, недалеко от офиса МОЗГ, живет странный народец. В их словаре всего 6 слов — in, input, out, output, one, puton. Пишут они в одну строчку и без пробелов. К одному из сотрудников МОЗГ попал странный клочок бумаги, очень похожий на письменность этой планеты. Необходимо понять, может ли это быть запиской с глухой планеты, или же это чья-то шифровка, не имеющая к ней никакого отношения.
Формат входного файла
Строка S — запись на найденной бумажке.
Формат выходного файла
Выведите S — если записка может содержать послание с соседней планеты — выведите YES, иначе — NO.
Примеры входных и выходных файлов
input                                     output
puton                                    YES
inonputin                              NO
oneputonininputoutoutput    YES

Задача E.  Очередь

Ограничение по времени:            2 секунды
Ограничение по памяти:              64 мегабайта
Любой спортсмен должен держать свое тело в тонусе, это очевидно. Так и ученые из МОЗГ решили держать в тонусе свой мозг. А поэтому каждый день на обед в столовую они выстраиваются в порядке новой К-ой перестановки из имеющихся N сотрудников. Число К задается прямо перед обедом, и нужно очень быстро высчитать, какую позицию занять в очереди, не успеешь — останешься голодным и потратишь обед на тренировку мозгов, а не желудка.
Небольшая группа математиков-лентяев очень хочет есть уже четвертый день, помогите им составить программу, которая высчитывала бы К-ую перестановку из N сотрудников.
Формат входного файла
В первой строке целые числа N (1 <= N <= 12) и К (1 <= К <= N!).
Формат выходного файла
Выведите К-ую перестановку из N сотрудников.
Примеры входных и выходных файлов
input    output
4  1        1   2   3   4
3  1        1   2   3
3  2        1   3   2
3  3        2   1   3