--->
78 задач
<---
Источники
#9
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2005,
1 день,
Задача A
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.
Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя.
Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.
Входные данные
Первая строка входных данных содержит число N (2 ≤ N ≤ 50).
Во второй строке через пробел следуют N различных чисел от 1 до N — номера колечек, расположенных вдоль нити по часовой стрелке.
Выходные данные
Ваша программа должна вывести описание процесса упорядочения.
В каждой строке выходных данных, кроме последней, должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. В последней строке должен стоять ноль.
Количество выводимых строк не должно превышать 50000.
Если требуемого упорядочения колечек достичь не удается, программа должна вывести одно число –1
Примеры
Входные данные
4 3 1 2 4
Выходные данные
4 2 4 1 0
#18
Темы:
[Эвристические методы]
[Задачи на моделирование]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2006,
2 день,
Задача B
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Известный математик Соломон В. Голомб предложил название полимино для связной фигуры, вырезанной из клетчатой бумаги по линиям сетки. Фигура называется связной, если из любой ее клетки можно добраться в любую другую, переходя из клетки в клетку через их общую сторону. Шахматист, добавил Голомб, сказал бы, что из любой клетки полимино можно дойти ладьей в любую другую. На рис. 1 приведены примеры восьми полимино.
Рис. 1
Саша увлекается полимино. Для своих экспериментов она вырезает новое полимино из бумаги в клеточку или из старых полимино, оставшихся после предыдущих попыток. Далеко не всегда из старого полимино (рис. 2а, слева) можно вырезать новое (рис. 2а, справа). Поэтому Саша может перед вырезанием нового полимино разделить каждую клетку старого полимино на K2 одинаковых квадратных клеток меньшего размера (см. рис. 2б, здесь K = 2).
Рис. 2а Рис. 2б
Сашу заинтересовало, сколько существует различных способов вырезать новое полимино из старого при заданном значении K, если повороты, отражения и переворачивания как нового полимино, так и старого, недопустимы.
Например, на рис. 2б приведены все возможные способы вырезания полимино, приведенного на рис. 2а, при K = 2.
Напишите программу, которая ответит на интересующий Сашу вопрос.
Входные данные
Первая строка входных данных содержит число K (1 ≤ K ≤ 10 000).
Далее следуют описания двух полимино, сначала нового, затем старого. Каждое полимино задается следующим образом — в первой строке описания задаются размеры H (высота) и W (ширина) минимально возможного прямоугольника, в котором можно разместить данное полимино. Следующие Н строк содержат по W символов описания клеток. При этом клетка, входящая в полимино, обозначается символом « X» (прописная латинская буква «икс»), а не входящая — символом «.» (точка). Количество клеток в каждом полимино не превышает 300.
Выходные данные
Выведите одно число — количество различных способов вырезать заданное новое полимино из старого, каждая клетка которого разбита на K2 клеток.
Примеры
Входные данные
2 6 6 XXXXXX X....X X....X X....X X....X XXXXXX 5 5 XXXXX XXXXX XX.XX XXXXX XXXXX
Выходные данные
9
#25
Темы:
[Задачи на моделирование]
[Сканирующая прямая]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2007,
2 день,
Задача C
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
|
В городе Шахматовске два интернет-провайдера выполняют план по всеобщей интернетизации страны. Город расположен на бесконечной целочисленной решетке, по всем линиям которой проходят прямые улицы, а единичные квадраты сетки определяют кварталы. Координатами квартала считаются координаты вершины левого нижнего угла соответствующего единичного квадрата. Кварталы города окрашены в черный и белый цвета в шахматном порядке, при этом квартал с координатами (0, 0) окрашен в черный цвет.Интернет-провайдер «Черный интернет» занимается подключением кварталов черного цвета. Недавно стало известно, что жителям квартала, подключенного K-м, будет предоставлена скидка в 10%. В соответствии с планом компании «Черный интернет» интернетизация будет проводиться в течение N дней. В i-й день бригада сотрудников компании движется по какой-то из улиц города, начиная из точки (xi, yi). Бригада проходит li кварталов в заданном направлении. При этом она подключает ранее не подключенные кварталы черного цвета, граничащие по стороне с путем движения бригады (см. рис.). Требуется написать программу, которая определит координаты квартала, подключенного во время реализации плана K-м по очереди. Гарантируется, что в процессе реализации плана будет подключено не менее K кварталов. |
|
Входные данные
В первой строке задаются два целых числа N и K (1 ≤ N ≤ 2 000, 1 ≤ K ≤ 1018).
Далее следуют N строк с описанием плана развития компании. В i-й строке описания плана записан путь бригады в i-й день: xi и yi (–1015 ≤ xi ≤ 1015, –1015 ≤ yi ≤ 1015) — координаты начальной точки пути, символ ci — направление движения, и li (1 ≤ li ≤ 1015) — расстояние, которое пройдет бригада. Направление движения задается одним из следующих символов: «N» — север (по увеличению y-координаты), «E» — восток (по увеличению x-координаты), «S» — юг (по уменьшению y-координаты), «W» — запад (по уменьшению x-координаты).
Выходные данные
Выведите координаты x и y квартала, подключенного K-м.
Примеры
Входные данные
5 19 20 6 S 5 9 7 S 7 9 18 W 1 13 18 N 2 12 13 E 5
Выходные данные
15 13
#26
Темы:
[Задачи на моделирование]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
По новым правилам Московской командной олимпиады итоги олимпиады подводятся следующим образом.
Команды решают задачи и могут во время тура посылать их на проверку. Задача проверяется на системе тестов.
Каждая задача оценивается из 2-х баллов. 2 балла получает программа, которая проходит все тесты. Кроме того, 1 баллом оцениваются решения, которые проходят некоторое количество первых тестов в задаче (это количество определяется жюри, оно может быть различным в различных задачах, это количество, как и общее количество тестов по задаче, участникам не сообщается). Жюри может (однако не обязано) указать в условии дополнительные ограничения, которым удовлетворяют тесты, за прохождение которых ставится 1 балл.
Помимо баллов за решение задач, команды получают штрафное время. За каждую задачу штрафное время определяется следующим образом.
- Если за данную задачу у команды 0 баллов (независимо от того, делала команда попытки сдачи этой задачи или нет), штрафное время за эту задачу равно 0.
- Если у команды 1 балл за эту задачу, то штрафное время за задачу определяется как время в минутах от момента начала тура до момента, когда была сделана первая попытка, которая была оценена в 1 балл, плюс по 20 штрафных минут за каждую попытку по этой задаче, ей предшествовавшую. Заметьте, что все попытки, которые делаются после того, как команда получила 1 балл за задачу (но до того, как она получила 2 балла), не влияют на штрафное время и на баллы по задаче (даже если после этого будет сделана попытка, которая получит 0 баллов, 1 набранный балл у команды останется).
- Если у команды 2 балла за задачу, то штрафное время за эту задачу определяется как время в минутах от момента начала тура до момента, когда задача была сдана на 2 балла, плюс по 20 штрафных минут за каждую предшествовавшую неверную попытку по этой задаче (при этом неверными теперь считаются в том числе и попытки, получающие 1 балл). Заметьте, что все попытки, которые делаются после того, как команда решила задачу полностью, не влияют на штрафное время.
При этом если произошла ошибка компиляции программы, то такая попытка не учитывается при подсчете неверных попыток (то есть она вообще игнорируется).
Например, если на 1-й минуте команда послала программу, которая набрала 0 баллов, то штрафное время равно 0. Пусть на 2-й минуте команда послала решение, которое набрало 1 балл, тогда команда имеет за эту задачу 1 балл и штрафное время, равное 22 минутам (2 минуты от начала тура + 20 штрафных минут). Если на 3-й минуте команда сдала решение задачи на 2 балла, то результат по этой задаче у команды 2 балла, а штрафное время равно 43 минуты (3 минуты от начала тура + 2*20 минут за 2 предыдущие попытки).
И баллы, и штрафное время, полученное командой по разным задачам, суммируются (получаются суммарные баллы и суммарное штрафное время). Команды ранжируются сначала по баллам, а при равном количестве баллов — по штрафному времени (чем меньше штрафное время, тем выше место команды).
Напишите программу, которая по протоколу попыток, сделанных командой, вычисляет количество набранных командой баллов и штрафное время.
Входные данные
В первой строке задается число N — суммарное количество задач (1≤N
Далее идет M — количество сделанных командой попыток. Затем следуют M строк, каждая из которых содержит 3 числа: первое задает время в минутах от начала тура до момента совершения данной попытки, второе — номер задачи, третье — количество пройденных тестов (или –1, если произошла ошибка компиляции). Все попытки упорядочены по времени, ни в какую минуту команда не делала более одной попытки.
По правилам олимпиады общее количество попыток не превышает 200, продолжительность тура — 3-х месяцев (на самом деле, командная олимпиада длится обычно не более 5 часов, однако жюри олимпиады не исключает, что эти же правила когда-нибудь будут использоваться в заочном туре, который длится как раз 3 месяца).
Выходные данные
Выведите два целых числа — количество набранных командой баллов и суммарное штрафное время.
Примеры
Входные данные
1 20 10 3 1 1 0 2 1 10 3 1 20
Выходные данные
2 43
Входные данные
2 17 24 2 2 2 5 1 1 8 2 -1
Выходные данные
0 0
#31
Темы:
[Задачи на моделирование]
[Обход в ширину]
ограничение по времени на тест
20.0 second;
ограничение по памяти на тест
64 megabytes
В подземелье есть N залов, соединенных туннелями. В некоторых залах находятся роботы, которые одновременно получили команду собраться в одном месте.
Роботы устроены так, что, получив команду, они все начали двигаться с такой скоростью, что туннель между двумя любыми залами преодолевают за 1 минуту. Роботы не могут останавливаться (в том числе и в залах), а также менять направление движения, находясь в туннелях (однако попав в зал, робот может из него пойти по тому же туннелю, по которому он пришел в этот зал).
Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).
Входные данные
Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.
Выходные данные
Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).
Оценка задачи
1 балл получат программы, правильно решающие задачу в случае, когда встреча роботов произойдет в зале, при ограничениях N≤100, K≤2000, M≤100.
Примеры
Входные данные
4 5 1 2 2 3 3 4 1 4 1 3 3 1 2 4
Выходные данные
1
Входные данные
3 2 1 2 2 3 2 1 3
Выходные данные
1
Выбрано
:
|