Начало
СоревнованияПодразделы
Другие разделы
Дата и время
16/11/2024 15:18:33
Задачи 1 тура Чемпионата Урала 2003
1. Кодовый замок
Эйлеров путь/циклОлимпиадные задачи на русском языке
| 23/04/2003 | 7-й Чемпионат Урала. 1 тур (1) |
| 19/05/2007 | Практическое занятие 19 (D) |
| 13/12/2008 | Занятие 11 (E) |
| 26/03/2014 | Занятие 18 (A) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Однажды конструктор Трурль заглянул в гости к Клапауцию, и тот похвастался новым кодовым замком, стоящим на двери секретной лаборатории.
– Вот, смотри – на замке несколько кнопок с буквами. Можно нажимать кнопки сколько угодно – дверь не откроется, пока K (я установил K равным трем) последних нажатых букв не совпадут с правильной комбинацией. Буквы в этой комбинации не должны повторяться, так как в замок встроен специальный защитный механизм. Если среди любых K последних введенных букв есть хотя бы две одинаковые, то на мой пейджер поступает сообщение, что кто-то пытается открыть дверь, подбирая код.
Через несколько дней, когда Клапауций отправился на собрание Артели Свободных Механиков, Трурль проник в его дом, чтобы ознакомиться с новыми изобретениями Клапауция в его секретной лаборатории. Чтобы открыть кодовый замок нужно было всего лишь перебрать все комбинации, не вызвав тревоги. И следовало бы поторопиться, так как Клапауций мог явиться с собрания в любой момент.
Напишите программу, которая по количеству букв в комбинации для открытия кодового замка и количеству кнопок на замке определит минимальную последовательность нажатий кнопок замка, которая содержит все возможные комбинации и не вызывает тревоги.
Ввод
В первой строке ввода содержатся два целых числа `K` и `N\ (1≤K≤N≤26,\ N^K≤60000)`, разделенных пробелом – количество букв в комбинации для открытия кодового замка и количество кнопок на замке. Кнопки обозначаются последовательными прописными латинскими буквами, начиная с А.
Вывод
Вывести минимальную последовательность нажатий кнопок замка, содержащую все возможные комбинации. Если существует несколько вариантов, то вывести один (любой) из них. Если перебрать все комбинации без тревоги не удастся, то вывести сообщение "IMPOSSIBLE".
Пример ввода
3 4
Вывод для примера
ABCABDACBACDBADCBDCADBCDAB
2. Бутерброд
Дерево Штерна-БрокоПоиск экстремума функции
Олимпиадные задачи на русском языке
| 23/04/2003 | 7-й Чемпионат Урала. 1 тур (2) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Конструктор Трурль сидел за столом и завтракал, когда к нему вбежал Клапауций.
– Я только что с собрания, еще не завтракал.
– У меня только один бутерброд.
– Будь другом, поделись, – и, схватив нож, одним взмахом Клапауций поделил бутерброд на две части, да так ловко, что
каждому достались равные кусочки хлеба и колбасы.
Рассмотрим задачу о делении бутерброда в двумерном случае. Предположим, что кусочек колбасы имеет
круглую форму, а кусочек хлеба треугольную. Напишите программу, которая по заданным координатам хлеба
и колбасы определит коэффициенты уравнения прямой `"Ax"\ +\ "By"\ =\ С`, разрезающей и хлеб, и колбасу на две части, отличающие по площади не более чем на `10^{-3}`.
Во входном файле в первой строке содержатся три целых числа, разделенных пробелом – координаты центра круглого
кусочка колбасы и его радиус. Во второй строке содержатся шесть целых чисел, разделенных пробелом – координаты
углов треугольного кусочка хлеба. Все координаты положительны и не превосходят 1000.
В выходной файл в первой строке вывести три целых числа, не превышающих по абсолютному значению `10^9` и разделенных
пробелами – коэффициенты
уравнения искомой прямой `A`, `B` и `С`. Коэффициенты `A` и `B` не должны одновременно обращаться в 0, кроме того, наибольший
общий делитель трех чисел `|A|`,`|B|` и `|С|` должен быть равен 1. Если существует несколько вариантов, то
вывести один (любой) из них.
Пример ввода
100 1 10 50 10 150 10 100 200
Вывод для примера
1 0 100
3. Меандр
Полный переборОлимпиадные задачи на русском языке
| 23/04/2003 | 7-й Чемпионат Урала. 1 тур (3) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
После завтрака друзья решили сыграть в свою любимую игру “меандр”, требующую от игроков недюжинного
интеллекта и необычайного хитроумия.
Трурль сделал очередной ход, но через секунду воскликнул:
– Черт, не надо было мне так ходить.
Трурль потянулся к доске.
– Нет уж, перехаживать нельзя, – возразил Клапауций.
– Теперь ты можешь выиграть, если только найдешь как.
Трурль откинулся в кресле и начал фальшиво насвистывать. Клапауций пытался сообразить,
какой из восьми возможных ходов позволит ему добиться победы. “Хорошо бы воспользоваться помощью компьютера,
он бы быстро рассмотрел все варианты и подсказал верный ход”. И Клапауций представил, что компьютер в
форме кольца надет у него на палец, и стоит только протянуть руку к нужной фишке, как компьютер…
– Хватит руками над доской водить, ходи, наконец! – Голос Трурля прервал мечты Клапауция.
В игре “меандр” 24 одинаковые плитки раскладывают на доске с бортиками так, как показано на рисунке
справа вверху. Одна клетка остается свободной. Игроки делают ходы поочередно, перемещая одну
плитку или столбик из двух, трех или четырех плиток, расположенных по горизонтали или вертикали.
Плитки перемещаются по поверхности доски, их нельзя поворачивать. Игра продолжается до тех пор,
пока один из игроков не выиграет, сложив узор, в котором по крайней мере три плитки образуют непрерывную линию,
соединяющую два края доски (либо противоположные, либо смежные, сходящиеся в одном углу). Такой
узор показан на рисунке слева (победная линия выделена жирной линией).
Напишите программу, которая подсказывает игроку, что уже получен победный узор, или каким
ходом можно получить победный узор.
Во входном файле содержится пять строк по пять символов в каждой строке. Символом ‘*’ обозначается
свободная клетка. Символом ‘/’ обозначается плитка 
, а символом ‘\’ – плитка 
. Во входном файле ровно один символ ‘*’ и по 12 символов ‘/’ и ‘\’.
, а символом ‘\’ – плитка . Во входном файле ровно один символ ‘*’ и по 12 символов ‘/’ и ‘\’.В выходной файл вывести или сообщение WIN, если узор уже является победным, или ход, который создает
из заданного непобедного узора победный узор, в форме направление движения (L – влево,
R – вправо, D – вниз, U – вверх) и количество сдвигаемых
плиток (от 1 до 4), например, U2 (если существует несколько вариантов, то
вывести один (любой) из них), или сообщение NO WIN, если задан непобедный узор и добиться победы одним ходом невозможно.
Пример ввода
*/\// \/\\\ \//// /\\\\ \//\/
Вывод для примера
WIN
4. Н
АвтоматыОлимпиадные задачи на русском языке
| 23/04/2003 | 7-й Чемпионат Урала. 1 тур (4) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Чтобы помочь Трурлю проверить машину, напишите программу, которая в заданном тексте
выделяет слова на букву "н". Программа должна сделать прописной первую буквы всех слов, начинающихся с
буквы "н" и длиной не менее трех букв. Под словом будем понимать непрерывную последовательность русских букв,
непосредственно перед и после которой нет других русских букв.
Во входном файле содержится текст – не менее одной строки длиной не более 255 символов. Текст состоит
только из строчных и прописных русских букв (используется кодировка cp866 (DOS)) и знаков препинания.
В выходной файл вывести текст из входного файла, превращая первые буквы слов, начинающихся с “н” (ASCII код 173), в
прописные (ASCII код 141). Разбиение текста на строки, пробелы и знаки препинания должны сохраниться.
Пример ввода
Конструктор Трурль создал однажды машину, которая умела делать всё на букву ”Н”. Закончив эту машину, он для пробы заставил её сделать нитки, потом связать из ниток носки, одеть их на ноги, а затем бросить всё это в нору, окружённую незабудками и наличниками. Машина выполнила задание безукоризненно, но Трурль ещё не был уверен в её исправности и стал думать, какие вещи на букву ”Н” можно приказать сделать машине.
Вывод для примера
Конструктор Трурль создал однажды машину, которая умела делать всё на букву ”Н”. Закончив эту машину, он для пробы заставил её сделать Нитки, потом связать из Ниток Носки, одеть их на Ноги, а затем бросить всё это в Нору, окружённую Незабудками и Наличниками. Машина выполнила задание безукоризненно, но Трурль ещё не был уверен в её исправности и стал думать, какие вещи на букву ”Н” можно приказать сделать машине.
6. Замощение
Алгоритм ЭвклидаОлимпиадные задачи на русском языке
| 23/04/2003 | 7-й Чемпионат Урала. 1 тур (6) |
| 09/09/2014 | Занятие 2 (E) |
| 26/06/2024 | Лето 2024-2 простые (A) |
| 27/06/2024 | 3 курc: диофантовы уравнения и ко (проводит BOGAT) (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Конструктор Клапауций решил замостить свой прямоугольный дворик плиткой. Для замощения Клапауций приготовил
квадратные плитки двух разных размеров. При мощении плитки не должны накладываться друг на друга,
выходить за пределы дворика, и не должно остаться незамощенных мест. Кроме того, Клапауций хотел бы как
можно меньше использовать плитки первого типа, так как ему не нравится их цвет.
Напишите программу, которая определяет, возможно ли замощение двора плитками двух
заданных размеров, и, если возможно, то какое количество плиток каждого размера следует взять.
Во входном файле в первой строке содержится четыре целых числа, разделенных пробелами: размеры
дворика `W` и `H` в сантиметрах (`1\ ≤\ W\ ≤\ 10^5`, `1\ ≤\ H\ ≤\ 10^5`) и размеры плиток `R_1` и `R_2` в сантиметрах
(`1\ ≤\ R_1\ ≤\ 1000`, `1\ ≤\ R_2\ ≤\ 1000`).
В выходной файл в первой строке вывести два целых числа, разделенных пробелом – количество плиток
размером `R_1` и количество плиток размером `R_2`, которые потребуются для замощения дворика. Количество
плиток первого типа должно быть минимальным. Если замощение невозможно, то нужно вывести сообщение IMPOSSIBLE.
Пример ввода
7 4 1 2
Вывод для примера
4 6
7. Бочка
Бинарный поискРешение уравнений (дихотомия, метод Ньютона)
Олимпиадные задачи на русском языке
| 23/04/2003 | 7-й Чемпионат Урала. 1 тур (7) |
| 19/10/2006 | Практическое занятие 6 (B) |
| 01/11/2008 | Занятие 7 (A) |
| 31/03/2012 | Занятие 13 (C) |
| 25/06/2012 | 1 курс, дорешивание (8C2) |
| 04/07/2012 | 1 курс, день 8, группа 2 (C2) |
| 06/05/2013 | Занятие 27 (A) |
| 10/03/2015 | Занятие 16 (A) |
| 18/11/2015 | Занятие по темам "Бинарный поиск, сканирование" (B) |
| 11/07/2018 | Лето 2018 - 8 (все) (A) |
| 15/07/2020 | Лето 2020 - 7 (все) (A) |
| 30/06/2023 | Лето 2023-3 сложные (командное) (G) |
| 28/10/2023 | Марафон 80 задач, 2 этап (B) |
| 28/06/2024 | Лето 2024-3 сложные (командное) (G) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Как-то раз Трурль заглянул к Клапауцию и увидел, что тот бегает с огромной линейкой вокруг большой бочки, лежащей на боку.
– Что ты делаешь? – удивился Трурль.
– Да вот, хочу нанести разметку, чтобы всегда знать, сколько литров машинного масла у меня в запасе.
На днище бочки была прорезана вертикальная щель, закрытая стеклом. На нем Клапауций собирался делать отметки.
– Чтобы нанести отметку, например, 5000 литров, мне нужно вычислить на каком уровне будет находиться поверхность масла.
– Ну, это просто, делим объем на длину бочки, получаем площадь. Потом… – тут Трурль замолчал и начал лихорадочно чертить формулы в блокноте. Исписав несколько листков, Трурль сказал, что тут необходим принципиально другой подход.
Сказано – сделано! Трурль и Клапауций собрали под электронным микроскопом из отдельных атомов несколько миллионов созданьиц ненамного крупнее микробов, нарекли их ангстремиками и привили им склонность к командным соревнованиям по программированию. Поместив культуру ангстремиков в цивилизационный инкубатор, конструкторы отправились обедать. Так как время в инкубаторе сжималось в 480 тысяч раз, через полчаса знания и умения ангстремиков стали достаточными для решения задачи о бочке.
Напишите программу, которая рассчитает расположение отметок для нескольких заданных объемов масла в бочке. Предполагается, что бочка лежит абсолютно горизонтально.
Ввод
Во входном файле в первой строке содержатся три целых числа, разделенных пробелами – диаметр бочки в метрах `D\ (1≤D≤10)`, длина бочки в метрах `L\ (1≤L≤10)` и количество отметок `N\ (1≤N≤10)`. Далее следует `N` строк. В каждой строке содержится одно целое число – объем масла в бочке в литрах `V_i`. Объем масла `V_i` не превышает емкости бочки.
Вывод
В выходной файл вывести `N` строк. В каждой строке выводится уровень в метрах, на котором будет находиться поверхность `V_i` литров масла, с 7 десятичными знаками.
Пример входа
2 4 2 10000 5000
Пример выхода
1.4842576 0.8389023
8. Лифты
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 23/04/2003 | 7-й Чемпионат Урала. 1 тур (8) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Чтобы получить разрешение на строительство Омнигенерического Ультимата в полом нутре Рапундры, огромной
луны недотяпов, конструктор Клапауций отправился в столицу их планеты, где обнаружил, что все министерства
планеты размещались в новом многоэтажном здании, и теперь для получения необходимых подписей и печатей
посетителям не требовалось ездить в разные концы города.
Здание было снабжено сложной системой лифтов. Лифты не управлялись пассажирами, а двигались
автоматически. Например, один из лифтов останавливался для высадки и посадки пассажиров через
каждые 5 этажей, а другой – через каждые 12 этажей. При этом время поездки на любом из лифтов
не зависело от количества этажей и равнялось 1 пякунде (единица измерения времени недотяпов, около 5 секунд).
Например, пусть лифт в 10-этажном здании, который проезжает за поездку 3 этажа, находится на пятом этаже
и движется вниз. Тогда через пякунду он будет на втором этаже, затем опять на пятом, потом на
восьмом, затем спустится на пятый и так далее. Движение лифтов было синхронизировано таким образом,
что в конце каждой пякунды все лифты останавливались, и можно было выйти и перейти в другой лифт,
если он в этот момент был на том же этаже. Кроме того, в здании имелась лестница, по которой
можно было за одну пякунду подняться или спуститься на один этаж. Можно также стоять
на этаже и ждать лифта.
Напишите программу, которая поможет Клапауцию быстро путешествовать по зданию.
Во входном файле в первой строке содержатся четыре целых числа,
разделенных пробелами – количество этажей в здании `H` (`1\ <\ H\ ≤\ 1000`), количество лифтов `N` (`1\ ≤\ N\ ≤\ 100`),
номер этажа `A` (`1\ ≤\ A\ ≤\ H`), на котором находится Клапауций, и номер этажа `B` (`1\ ≤\ B\ ≤\ H`), на который
требуется попасть Клапауцию. Далее следует `N` строк, содержащих по три целых числа, разделенных
пробелами – номер этажа `P_i` (`1\ ≤\ P_i\ ≤\ H`), на котором находится лифт в начальный момент путешествия
Клапауция, число этажей `S_i` (`1\ ≤\ S_i\ ≤\ H/2`), на которое лифт поднимается или спускается за одну
пякундную поездку, и направление движения лифта в следующий интервал времени `D_i` (`D_i\ =\ 1`, если лифт
поедет вверх, `D_i\ =\ –1`, если лифт поедет вниз).
В выходной файл вывести одну строку, содержащую два целых числа, разделенных пробелом – время в пякундах,
необходимое Клапауцию, чтобы добраться до нужного этажа, и количество этажей, которое Клапауцию придется
пройти по лестнице. Требуется минимизировать в первую очередь время путешествия, а затем количество этажей, на
которое Клапауцию придется подняться или спуститься без помощи лифта.
Пример ввода
10 2 1 9 5 3 –1 1 1 1
Вывод для примера
4 1
