Начало
Соревнования
Задачи очного тура личного первенства 1999
1. Международный Васюкинский турнир 19** года
МоделированиеОлимпиадные задачи на русском языке
| 29/10/1999 | Личное первенство университета по программированию (1) |
| 26/03/2008 | Занятие 18 (A) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Фантазия великого комбинатора сбылась – в городе Васюки
(Калмыкия) через 3 часа должен начаться международный
шахматный турнир. "Сотни тысяч людей, богато обеспеченных
людей, устремились в Васюки… По фуникулерам подымаются в
город мордатые иностранцы, шахматные леди, австралийские
поклонники индийской защиты, индусы в белых тюрбанах –
приверженцы испанской партии, немцы, французы, новозеландцы,
жители бассейна реки Амазонки и, завидующие васюкинцам, –
москвичи, ленинградцы, киевляне, сибиряки и одесситы…" Для
того, чтобы все желающие могли наблюдать за ходом турнира, из
Японии был доставлен огромный экран (размером 98x167 метров) и
специальный контроллер-компьютер для него. Но во время
транспортировки потерялась маленькая дискета с программным
обеспечением. Ваша задача – к началу шахматного турнира
написать новую программу для управления контроллером экрана.
В программу поступает информация о ходах, сделанных
гроссмейстерами; результатом работы программы является
изображение доски, передаваемое в контроллер для отображения
на экране. Шахматная фигура на изображении обозначается двумя
символами: первый символ – тип фигуры (один из следующих:
P-пешка, R-ладья, N-конь, B-слон, Q-ферзь, K-король), второй
символ – цвет фигуры (w-белый, b-черный). Пустая черная клетка
обозначается символами "//" (два знака деления), а пустая белая –
".." (две точки).
Во входном файле содержится несколько строк (ноль или
более) – последовательность ходов, сделанных из начальной
позиции. В каждой строке информация об одном ходе: в нечетных
строках – ходы гроссмейстера, играющего белыми, в четных –
черными. Информация о ходе имеет следующий синтаксис:
обозначение вертикали (A-H) и горизонтали (1-8) клетки, из
которой был сделан ход, затем знак – (при простом ходе) или :
(при взятии фигуры, а также при взятии на проходе), затем
обозначение вертикали и горизонтали конечной клетки, затем
возможно следует указание фигуры, в которую превратилась
пешка, дойдя до последней горизонтали. Исключение: короткая
рокировка обозначается 0-0 (цифра 0), а длинная – 0-0-0.
Примеры ходов: E2-E4, F7-F8Q, H1:H6, 0-0. Проверять
правильность хода не требуется – предполагается, что
гроссмейстеры знают правила игры и ходят правильно.
В выходной файл вывести изображение доски после указанной
последовательности ходов – восемь строк по шестнадцать
символов.
Пример ввода
E2-E4 E7-E5 F1-C4 B8-C6 D1-H5 G8-F6 H5:F7
Пример вывода
Rb//BbQbKbBb..Rb PbPbPbPb//QwPbPb ..//Nb//..Nb..// //..//..Pb..//.. ..//Bw//Pw//..// //..//..//..//.. PwPwPwPw..PwPwPw RwNwBw..Kw..NwRw
Примечание для тех, кто знает о шахматах меньше, чем
О.Бендер. Начальная позиция в шахматах и нумерация
горизонталей и вертикалей:
8 RbNbBbQbKbBbNbRb
7 PbPbPbPbPbPbPbPb
6 ..//..//..//..//
5 //..//..//..//..
4 ..//..//..//..//
3 //..//..//..//..
2 PwPwPwPwPwPwPwPw
1 RwNwBwQwKwBwNwRw
A B C D E F G H
Рокировка: один раз в партии, если король и ладья еще не
ходили, поля доски между ними свободны и король не атакован,
может быть сделан одновременный ход короля и ладьи –
рокировка: король передвигается в сторону ладьи через поле
(соответственно вправо или влево), а ладья переносится через
короля и ставится рядом с ним. Рокировка с ближней ладьей (вертикаль H) называется короткой
и обозначается 0-0, c дальней (вертикаль A) – длинной (0-0-0).
Взятие на проходе: если пешка, делая двойной ход,
проходит мимо поля, находящегося под ударом пешки противника,
она может быть взята этой пешкой "на проходе"; взявшая пешка
передвигается по диагонали на поле, пройденное взятой пешкой.
Двойной ход пешки возможен только из начального
положения, например E2-E4.
2. "Рога и копыта"
Полный переборСокращение перебора с помощью идеи
Олимпиадные задачи на русском языке
| 29/10/1999 | Личное первенство университета по программированию (2) |
| 26/03/2008 | Занятие 18 (B) |
Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В конторе "Рога и копыта", симулируя активную деятельность
по заготовке рогов и копыт, очень любили играть в следующую
разновидность "Быков и коров". Два игрока загадывают по одному
четырехзначному числу из цифр от 1 до 7. Пусть первый игрок
задумал число 3321. Другой игрок делает попытку угадать это
число, называя произвольное число, например 1223, и получает
ответ о числе точных и неточных попаданий, в данном случае
"1 рог и 2 копыта". Рог – это одинаковые цифры в одинаковых разрядах,
копыто – одинаковые цифры в разных разрядах, каждый разряд учитывается только один раз.
Затем пытается угадать число первый игрок, и так далее,
пока один из игроков не получит ответ "4 рога". Этот игрок
становится победителем.
Чемпионом конторы, без сомнения, был великий комбинатор.
Шура и Паниковский предложили Вам на выбор любую из половинок
"золотой гири" за программу, которая поможет им выиграть.
Программа должна:
- проанализировать числа-попытки игрока и полученные ответы;
- сообщить минимальное количество оставшихся попыток в самом неблагоприятном случае;
- предложить число, которое следует называть следующим для достижения указанного минимума ходов.
Т.е. если следовать советам программы, потребуется не более
указанного количества ходов и не существует ходов, которые
приводили бы к гарантированному выигрышу за меньшее количество
ходов.
Во входном файле содержится в первой строке количество
попыток `T` (`0\ ≤\ T\ ≤\ 10`), которое было сделано игроком. В
последующих `T` строках содержится число-попытка `N` (от 1111 до
7777) и количество обнаруженных рогов `R` (`0\ ≤\ R\ ≤\ 3`) и копыт `K`
(`0\ ≤\ K\ ≤\ 4`) в попытке (т.е. ответ противника; выполняется
условие `K+R\ ≤\ 4`) через один пробел.
В выходной файл вывести минимальное число оставшихся
попыток и рекомендуемое четырехзначное число-попытку через
один пробел. Если ответам противника не соответствует ни одно
число, вывести строчку с числом 0.
Пример ввода
6 7753 0 1 2374 0 2 6264 0 1 3323 1 0 2775 0 0 5212 1 0
Пример вывода
1 3411
Примечание: Количество попыток 1 означает, что на рекомендуемое
число-попытку последует ответ "4 рога".
3. Фрактальная раздробленность
Комбинаторика, теория ПойаОлимпиадные задачи на русском языке
| 29/10/1999 | Личное первенство университета по программированию (3) |
| 26/03/2008 | Занятие 18 (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Старгородский "Союз меча и орала", куда обратились за
материальной помощью великий комбинатор и "гигант мысли, отец
русской демократии и особа, приближенная к императору", имел
довольно сложную структуру. Во-первых, союз делился на две
неравные фракции (одна из которых придерживалась монархических
взглядов, другая стояла за республику), но ни одна из фракций
не превышала другую по численности в 2 или более раза.
Во-вторых, каждая из фракций, в свою очередь, аналогичным
образом делилась на две подфракции (например, сторонников
абсолютной и конституционной монархии, парламентской и
президентской республики). В-третьих, каждая из подфракций
опять делилась на две фракции. И так далее `N` раз (должно
получиться `2^N` субфракций нижнего уровня). Для каждой фракции
(и всего союза), которая делится на подфракции, выполняется
следующее условие: пусть `k` и `m` – число членов в подфракциях
данной фракции, тогда `k\ >\ 0`, `m\ >\ 0`, `k\ ≠\ m`, `2*k\ >\ m`, `2*m\ >\ k`. Требуется
определить возможность разбиения союза численностью `L` на
фракции `N` раз по указанным правилам.
Во входном файле содержится несколько строк (более одной),
в каждой строке содержится два целых числа `L` (`1\ ≤\ L\ ≤\ 1\ 000\ 000`) и
`N` (`1\ ≤\ N\ ≤\ 20`) через один пробел. Строка, в которой содержится
только число 0, служит признаком завершения тестового файла.
В выходной файл для каждой строки с `L` и `N` из входного файла
вывести строку с сообщением "YES", если возможно существование
союза с численностью `L` и степенью раздробленностью `N`, и "NO", в
противном случае.
Пример ввода
2 1 3 1 5 1 1000 3 0
Пример вывода
NO NO YES YES
4. "Грузите апельсины бочках братья Карамазовы"
Вычислительная геометрияПолный перебор
Поворот, увеличение и другие способы выявления особых точек
Олимпиадные задачи на русском языке
| 29/10/1999 | Личное первенство университета по программированию (4) |
| 26/09/2007 | Занятие 3 (D) |
| 14/03/2009 | Занятие 15 (H) |
| 04/05/2011 | Занятие 24 (E) |
| 25/11/2015 | Занятие по темам "Cканирование, выявление особых точек" (C) |
| 07/10/2023 | Тренировка 1 (проводит gribanov) (A) |
| 02/12/2023 | Марафон 80 задач, 7 этап (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Предположим, что все апельсины имеют форму куба со стороной
`A` (новейшее достижение учения Мичурина), а бочки являются
цилиндрическими (внутренний диаметр `D` и высота `H`). Бочки
разрешается транспортировать только в стоячем положении.
Апельсины необходимо размещать в бочках слоями, параллельными
днищу (земле), все слои должны быть одинаковы, каждый слой
должен состоять из параллельных рядов, соприкасающихся друг с
другом, апельсины в разных рядах могут быть смещены друг
относительно друга.
Вид сверху внутрь бочки для A=10см, D=37см
Вопрос: какое максимальное количество апельсинов согласно
правилам транспортировки сможет поместить в каждую бочку
гражданин Корейко?
Во входном файле в первой строке содержатся три целых числа
`A\ \ (3\ ≤\ A\ ≤\ 25)`, `D\ (20\ ≤\ D\ ≤\ 200)` и `H\ (20\ ≤\ H\ ≤\ 200)` через один
пробел – размеры апельсинов и бочки в сантиметрах.
В выходной файл вывести одно целое число – максимальное
количество апельсинов, помещающихся в бочке указанных размеров
согласно правилам.
Пример ввода
10 37 45
Вывод для примера
28
5. Heads
Реализация заданного алгоритмаОлимпиадные задачи на английском языке
| 29/10/1999 | Личное первенство университета по программированию (5) |
| 26/03/2008 | Занятие 18 (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
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.
The probability of `n` heads in a row tossing a fair coin is `2^{-n}`.
Input
`r` lines containing each one an integer number `n`. The values
of `r` and `n` are as follows: `0\ <\ r\ ≤\ 10`, `0\ <\ n\ ≤\ 9000`.
Output
Print `r` lines each with the value of `2^{-n}` for the given
values of `n`, using the format:
2^-`n` = `x`.`"xxx"`E-`y`
where each `x` is a decimal digit and each `y` is a decimal
integer with no leading zeroes or spaces.
Input Sample
8271 6000 1
Output Sample
2^-8271 = 1.517E-2490 2^-6000 = 6.607E-1807 2^-1 = 5.000E-1
