Задачи очного тура университетских соревнований по программированию
(личное первенство 29 октября 1999г.)
Во всех задачах ввод данных производится из файла
INPUT.TXT, а вывод результатов - в файл OUTPUT.TXT. Формат
входного файла соответствует спецификации, дополнительные
проверки не нужны.
Пояснения для некоторых участников:
Строка - это последовательность из 0 или более символов,
заканчивающаяся символом перехода на новую строку.
Время теста указано для тестирующего компьютера жюри
(P-166МГц).
Задачи, за исключением персонажей и прямых цитат, взятых в
кавычки, не имеют отношения к произведениям Ильфа и Петрова.
--------------------------------------------------------------
1. "Международный Васюкинский турнир 19** года" (2 сек на тест)
Фантазия великого комбинатора сбылась - в городе Васюки
(Калмыкия) через 3 часа должен начаться международный
шахматный турнир. "Сотни тысяч людей, богато обеспеченных
людей, устремились в Васюки... По фуникулерам подымаются в
город мордатые иностранцы, шахматные леди, австралийские
поклонники индийской защиты, индусы в белых тюрбанах -
приверженцы испанской партии, немцы, французы, новозеландцы,
жители бассейна реки Амазонки и, завидующие васюкинцам, -
москвичи, ленинградцы, киевляне, сибиряки и одесситы..." Для
того, чтобы все желающие могли наблюдать за ходом турнира, из
Японии был доставлен огромный экран (размером 98x167 метров) и
специальный контроллер-компьютер для него. Но во время
транспортировки потерялась маленькая дискета с программным
обеспечением. Ваша задача - к началу шахматного турнира
написать новую программу для управления контроллером экрана.
В программу поступает информация о ходах, сделанных
гроссмейстерами; результатом работы программы является
изображение доски, передаваемое в контроллер для отображения
на экране. Шахматная фигура на изображении обозначается двумя
символами: первый символ - тип фигуры (один из следующих:
П-пешка, Л-ладья, К-конь, С-слон, Ф-ферзь, Ш-король), второй
символ - цвет фигуры (Б-белый, Ч-черный). Пустая черная клетка
обозначается символами // (два знака деления), а пустая белая-
.. (две точки).
Во входном файле содержится несколько строк (ноль или
более) - последовательность ходов, сделанных из начальной
позиции. В каждой строке информация об одном ходе: в нечетных
строках - ходы гроссмейстера, играющего белыми, в четных -
черными. Информация о ходе имеет следующий синтаксис:
обозначение вертикали (A-H) и горизонтали (1-8) клетки, из
которой был сделан ход, затем знак - (при простом ходе) или :
(при взятии фигуры, а также при взятии на проходе), затем
обозначение вертикали и горизонтали конечной клетки, затем
_возможно_ следует указание фигуры, в которую превратилась
пешка, дойдя до последней горизонтали. Исключение: короткая
рокировка обозначается 0-0 (цифра 0), а длинная - 0-0-0.
Примеры ходов: E2-E4, F7-F8Ф, H1:H6, 0-0. Проверять
правильность хода не требуется - предполагается, что
гроссмейстеры знают правила игры и ходят правильно.
В выходной файл вывести изображение доски после указанной
последовательности ходов - восемь строк по шестнадцать
символов.
Пример INPUT.TXT: OUTPUT.TXT для примера:
E2-E4 ЛЧ//СЧФЧШЧСЧ..ЛЧ
E7-E5 ПЧПЧПЧПЧ//ФБПЧПЧ
F1-C4 ..//КЧ//..КЧ..//
B8-C6 //..//..ПЧ..//..
D1-H5 ..//СБ//ПБ//..//
G8-F6 //..//..//..//..
H5:F7 ПБПБПБПБ..ПБПБПБ
ЛБКБСБ..ШБ..КБЛБ
Примечание для тех, кто знает о шахматах меньше, чем
О.Бендер. Начальная позиция в шахматах и нумерация
горизонталей и вертикалей:
8 ЛЧКЧСЧФЧШЧСЧКЧЛЧ
7 ПЧПЧПЧПЧПЧПЧПЧПЧ
6 ..//..//..//..//
5 //..//..//..//..
4 ..//..//..//..//
3 //..//..//..//..
2 ПБПБПБПБПБПБПБПБ
1 ЛБКБСБФБШБСБКБЛБ
A B C D E F G H
Рокировка: один раз в партии, если король и ладья еще не
ходили, поля доски между ними свободны и король не атакован,
может быть сделан одновременный ход короля и ладьи -
рокировка*: король передвигается в сторону ладьи через поле
(соответственно вправо или влево), а ладья переносится через
короля и ставится рядом с ним.
Взятие на проходе: если пешка, делая двойной ход**,
проходит мимо поля, находящегося под ударом пешки противника,
она может быть взята этой пешкой "на проходе"; взявшая пешка
передвигается по диагонали на поле, пройденное взятой пешкой.
(БСЭ, 3 издание).
--------
*Рокировка с ближней ладьей (вертикаль H) называется короткой
и обозначается 0-0, c дальней (вертикаль A) - длинной (0-0-0).
**Двойной ход пешки возможен только из начального
положения, например E2-E4.
--------------------------------------------------------------
2. "Рога и копыта" (15 секунд на тест)
В конторе "Рога и копыта", симулируя активную деятельность
по заготовке рогов и копыт, очень любили играть в следующую
разновидность "Быков и коров". Два игрока загадывают по одному
четырехзначному числу из цифр от 1 до 7. Пусть первый игрок
задумал число 3321. Другой игрок делает попытку угадать это
число, называя произвольное число, например 1223, и получает
ответ о числе точных и неточных попаданий, в данном случае
"1 рог и 2 копыта".
/------\
+-+ +=+ +-+ |
|3| 3 #2# |1| \-рог - одинаковые цифры в одинаковых разрядах
+-+ +=+ +-+
+-+ +=+ +-+ /-копыто - одинаковые цифры в разных разрядах
|1| 2 #2# |3| |
+-+ +=+ +-+ | каждый разряд учитывается только один раз
\---------\--/
Затем пытается угадать число первый игрок, и так далее,
пока один из игроков не получит ответ "4 рога". Этот игрок
становится победителем.
Чемпионом конторы, без сомнения, был великий комбинатор.
Шура и Паниковский предложили Вам на выбор любую из половинок
"золотой гири" за программу, которая поможет им выиграть.
Программа должна:
1. проанализировать числа-попытки игрока и полученные
ответы;
2. сообщить минимальное количество оставшихся попыток в
самом неблагоприятном случае;
3. предложить число, которое следует называть следующим для
достижения указанного минимума ходов.
Т.е. если следовать советам программы, потребуется не более
указанного количества ходов и не существует ходов, которые
приводили бы к гарантированному выигрышу за меньшее количество
ходов.
Во входном файле содержится в первой строке количество
попыток T (0
Пример INPUT.TXT: OUTPUT.TXT для примера*:
6 1 3411
7753 0 1
2374 0 2
6264 0 1
3323 1 0
2775 0 0
5212 1 0
-------
*Количество попыток 1 означает, что на рекомендуемое
число-попытку последует ответ "4 рога".
--------------------------------------------------------------
3. Фрактальная раздробленность (4 сек на тест)
Старгородский "Союз меча и орала", куда обратились за
материальной помощью великий комбинатор и "гигант мысли, отец
русской демократии и особа, приближенная к императору", имел
довольно сложную структуру. Во-первых, союз делился на две
неравные фракции (одна из которых придерживалась монархических
взглядов, другая стояла за республику), но ни одна из фракций
не превышала другую по численности в 2 или более раза.
Во-вторых, каждая из фракций, в свою очередь, аналогичным
образом делилась на две подфракции (например, сторонников
абсолютной и конституционной монархии, парламентской и
президентской республики). В-третьих, каждая из подфракций
опять делилась на две фракции. И так далее N раз (должно
получиться 2^N субфракций нижнего уровня). Для каждой фракции
(и всего союза), которая делится на подфракции, выполняется
следующее условие: пусть k и m - число членов в подфракциях
данной фракции, тогда k>0, m>0, k!=m, 2*k>m, 2*m>k. Требуется
определить возможность разбиения союза численностью L на
фракции N раз по указанным правилам.
Во входном файле содержится несколько строк (более одной),
в каждой строке содержится два целых числа L (1<=L<=1000000) и
N (1<=N<=20) через один пробел. Строка, в которой содержится
только число 0, служит признаком завершения тестового файла.
В выходной файл для каждой строки с L и N из входного файла
вывести строку с сообщением YES, если возможно существование
союза с численностью L и степенью раздробленностью N, и NO, в
противном случае.
Пример INPUT.TXT: OUTPUT.TXT для примера:
2 1 NO
3 1 NO
5 1 YES
1000 3 YES
0
--------------------------------------------------------------
4. "Грузите апельсины бочках братья Карамазовы" (2 сек на тест)
Предположим, что все апельсины имеют форму куба со стороной
A (новейшее достижение учения Мичурина), а бочки являются
цилиндрическими (внутренний диаметр D и высота H). Бочки
разрешается транспортировать только в стоячем положении.
Апельсины необходимо размещать в бочках слоями, параллельными
днищу (земле), все слои должны быть одинаковы, каждый слой
должен состоять из параллельных рядов, соприкасающихся друг с
другом, апельсины в разных рядах могут быть смещены друг
относительно друга.
. .
. +---+ .
.+---+ +---+.
. | +---+ | .
. +---+ +---+ . вид сверху внутрь бочки
. | +---+ | . A=10 см, D=37 см
.+---+ +---+.
. +---+ .
. . ^стенка бочки
Вопрос: какое максимальное количество апельсинов согласно
правилам транспортировки сможет поместить в каждую бочку
гражданин Корейко?
Во входном файле в первой строке содержатся три целых числа
A (3<=A<=25), D (20<=D<=200) и H (20<=H<=200) через один
пробел - размеры апельсинов и бочки в сантиметрах.
В выходной файл вывести одно целое число - максимальное
количество апельсинов, помещающихся в бочке указанных размеров
согласно правилам.
Пример INPUT.TXT: OUTPUT.TXT для примера:
10 37 45 28
--------------------------------------------------------------
5. Heads (ACM 545) (2 сек на тест)
O.Bender and K.Vorob'yaninov like to play tossing coins. If
all coins lie heads up then Kisah wins else Ostap wins.
Calculate the probability of Kisah's win.
-n
The probability of n heads in a row tossing a fair coin is 2
Input
r lines containing each one an integer number n. The values
of r and n are as follows: 0
Output -n
Print r lines each with the value of 2 for the given
values of n, using the format:
2^-n = x.xxxE-y
where each x is a decimal digit and each y is a decimal
integer with no leading zeroes or spaces.
Sample INPUT.TXT Sample OUTPUT.TXT
8271 2^-8271 = 1.517E-2490
6000 2^-6000 = 6.607E-1807
1 2^-1 = 5.000E-1