---> 91 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Яблоки в форме окружностей задаются радиусом и верхней точкой. Одно из яблок начинает падать. Если яблоко при падении задевает другое яблоко, то второе также начинает падать. Необходимо определить, какие яблоки упадут.

У Пети в саду растет яблоня. Воодушевленный историей об Исааке Ньютоне, который, как известно, открыл закон всемирного тяготения после того, как ему на голову упало яблоко, Петя с целью повысить свою успеваемость по физике часто сидит под яблоней.

Однако, поскольку по физике у Пети твердая тройка, яблоки с его яблони падают следующим образом. В какой-то момент одно из яблок отрывается от ветки, на которой оно висит, и начинает падать строго вниз. Если в некоторый момент оно задевает другое яблоко, то то тоже отрывается от своей ветки и начинает падать вниз, при этом первое яблоко не меняет направление своего падения. Вообще, если любое падающее яблоко заденет другое яблоко на своем пути, то оно также начнет падать.

Таким образом, в любой момент каждое яблоко либо висит на ветке, либо падает строго вниз, причем все яблоки кроме первого, чтобы начать падать, должны сначала соприкоснуться с каким-либо другим падающим яблоком.

Выясните, какие яблоки упадут с Петиной яблони.

Входные данные

В первой строке вводится число $N$ - количество яблок на Петиной яблоне (1 <= $N$ <= 200). Следующие $N$ строк содержат описания яблок. Будем считать все яблоки шарами. Каждое яблоко задается координатами своей самой верхней точки (той, где оно исходно прикреплено к дереву, длиной черенка пренебрежем) $x_i$, $y_i$ и $z_i$ и радиусом $r_i$ ( -10000 <= $x_i$, $y_i$, $z_i$ <= 10000, 1 <= $r_i$ <= 10000, все числа целые). Гарантируется, что изначально никакие яблоки не пересекаются (даже не соприкасаются). Ось OZ направлена вверх.

Выходные данные

В первой строке выведите количество яблок, которые упадут с яблони, если начнет падать первое яблоко. В следующей строке выводите номера упавших яблок. Яблоки нумеруются, начиная с 1, в том порядке, в котором они заданы во входных данных.

Примеры
Входные данные
4
0 0 10 4
5 0 3 1
-7 4 7 1
0 1 2 6
Выходные данные
3
1 2 4 
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
16 megabytes

Город Мехико расположен в прекрасной долине, известной как Долина Мехико, на месте которой много лет назад было озеро. Около 1300 года ацтекские религиозные лидеры выпустили указ о том, что центр озера должен быть засыпан, чтобы построить столицу их империи. В настоящее время озеро полностью осушено.

Вокруг озера до появления ацтеков были расположены c прибрежных городов. Некоторые из этих городов заключили между собой коммерческие соглашения. Между городами, установившими коммерческие соглашения, по озеру на лодках перевозились различные товары. Любую пару городов можно было соединить отрезком прямой, полностью проходящим через озеро.

В какой-то момент короли городов решили упорядочить товароперевозки. Они разработали маршрут товароперевозок, который соединяет все города вокруг озера. Маршрут удовлетворяет следующим условиям:

*Он начинается в каком-либо городе, проходит через каждый прибрежный город и заканчивается в городе, отличном от того, в котором он начался.
*Маршрут проходит через каждый город ровно один раз.
*Любые два последовательно посещаемых города маршрута обязаны иметь между собой коммерческое соглашение.
*Маршрут состоит из отрезков прямых, каждый из которых соединяет два последовательно посещаемых города маршрута.
*Чтобы избежать столкновения лодок, маршрут не должен иметь самопересечений.


На рисунке показано озеро и города вокруг него. Тонкие и жирные линии отрезков обозначают коммерческие соглашения между городами. Жирные линии показывают маршрут грузоперевозок, начинающийся в городе 2 и заканчивающийся в городе 5.

Этот маршрут нигде не имеет самопересечений. Но если построить маршрут, идущий из города 2 в город 6, затем в город 5, а затем в город 1, то он будет неправильным, поскольку имеет самопересечения.

Города нумеруются целыми числами от 1 до $c$ по направлению часовой стрелки.

Задание

Напишите программу, которая по заданному числу городов $c$ и списку коммерческих соглашений между городами, найдет маршрут товароперевозок, удовлетворяющий указанным выше условиям.

Ограничения

3 ≤ $c$ ≤ 1000, $c$ – число городов вокруг озера

Входные данные

На вход Вашей программы поступают данные в следующем формате:

СТРОКА 1: Содержит целое число $c$.
СТРОКА 2: Содержит целое число $n$ – количество коммерческих соглашений.
СЛЕДУЮЩИЕ $n$ СТРОК: Каждая строка описывает одно коммерческое соглашение (одно соглашение описывается один раз). В строке задаются два целых числа, разделенных пробелами, которые соответствуют номерам городов, заключивших между собой коммерческое соглашение.

Выходные данные

Если возможно построить маршрут товароперевозок, выведите c строк, в каждой из которых записано целое число. Эти числа представляют собой порядок посещения городов по маршруту товароперевозок. Если невозможно построить маршрут товароперевозок, удовлетворяющий всем указанным требованиям, выведите одну строку, содержащую отрицательное целое число -1.

Замечание

Если существует несколько маршрутов товароперевозок, удовлетворяющих всем указанным требованиям, выведите любой из них.

Оценивание

Ряд тестов с общей суммой 30 баллов будет удовлетворять следующим ограничениям:
3 ≤ $m$ ≤ 10
3 ≤ $n$ ≤ 10

Примеры
Входные данные
7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7
Выходные данные
5
6
7
1
4
3
2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Заданы две фигуры из закрашенных клеток. Требуется совместить две фигуры так, чтобы образовалась ограниченная фигурами незакрашенная область наибольшего размера.

Андрюше на день рождения подарили хомячка. Пока Андрюша не купил для него клетку, он решил сделать ему клетку из подручных средств. Для изготовления клетки он решил использовать набор кубиков, подаренный ему на прошлый день рождения. Однако, неожиданно выяснилось, что сестра Андрюши склеила кубики суперклеем, и отделить их друг от друга не представляется возможным.

Все кубики оказались склеены в две фигуры. Любые два кубика в каждой из фигур либо не имеют общих точек, либо имеют общую грань, либо имеют общее ребро, но в последнем случае есть кубик, с которым каждый из них имеет общую грань. Каждую фигуру можно положить на стол так, что каждый кубик будет касаться стола одной из своих граней. Теперь Андрюша хочет положить эти две фигуры на стол так, чтобы получилась клетка для хомячка. Фигуры должны быть положены таким образом, чтобы каждый кубик касался стола гранью. Стороны нижних граней кубиков должны быть параллельны сторонам стола. Любые два кубика, принадлежащие различным фигурам, должны либо не касаться друг друга, либо иметь общую грань, либо иметь общее ребро. Фигуры разрешается поворачивать и переворачивать.

Положив фигуры, Андрюша собирается выпустить хомячка на стол. Чтобы он не упал со стола, у него не должно быть возможности добраться от точки, в которую Андрюша его выпустит, до края стола. Хомячок не может перелезать через кубики, и, в частности, не может пролезть между двумя кубиками, имеющими общее ребро. Стол существенно больше каждой из фигур.

Андрюша хочет, чтобы площадь, по которой может бегать хомячок, была как можно больше. Помогите ему выяснить, какая максимальная площадь может быть у территории, до которой сможет добраться хомячок. Площадь грани кубика будем считать равной единице.

Например, две фигуры, показанные на рисунке выше, можно расположить как показано на следующем рисунке. Если выпустить хомячка в точку, отмеченную стрелкой, то доступная ему территория будет иметь площадь, равную четырем.

Входные данные

В первой строке вводятся два числа: $h_1$ и $w_1$ (1 <= $h_1$, $w_1$ <= 10). Следующие $h_1$ строк содержат по $w_1$ символов и описывают первую фигуру, вид сверху. Каждый из этих символов - либо "*" (звездочка), либо "." (точка), звездочка обозначает кубик, а точка – пустое место.

Далее в отдельной строке вводятся два числа: $h_2$ и $w_2$ (1 <= $h_2$, $w_2$ <= 10). Следующие $h_2$ строк содержат по $w_2$ символов и описывают вторую фигуру в формате, аналогичном формату первой. Каждая из фигур связна и содержит хотя бы один кубик.

Выходные данные

Выведите одно число – максимальную площадь, которая может быть доступна хомячку. Если сделать клетку для хомячка невозможно, выведите 0.

Примеры
Входные данные
8 8
........
.***....
..**....
.*****..
...*.*..
...***..
****....
........
8 8
........
........
........
........
*******.
........
........
........
Выходные данные
4
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Необходимо по данной матрице построить матрицу, у которой сумма строк и столбцов совпадает с суммами исходной матрицы, все числа кратны заданному P, а также отличаются от соответствующих чисел исходной матрице не более, чем на P.

Рассмотрим таблицу, состоящую из $N$ строк и $M$ столбцов. Если в каждой ячейке такой таблицы стоит целое число, назовем такую таблицу целочисленной матрицей. Скажем, что эта матрица кратна чиcлу $p$, если все числа в ее ячейках кратны $p$.

Рассмотрим теперь суммы элементов матрицы по строкам и столбцам соответственно. Обозначим сумму чисел $i$-й строки за $H_i$, а сумму чисел $j$-го столбца за $V_j$. Упорядоченный набор чисел ($H_1$, $H_2$, …, $H_N$, $V_1$, $V_2$, …, $V_M$) назовем профилем матрицы. Скажем, что матрица почти кратна $p$, если все числа, входящие в ее профиль, кратны $p$. Почти кратная 5 матрица и ее профиль изображены на рисунке 1.

Если две матрицы $A$ и $B$ имеют одинаковый размер, причем элемент, стоящий на пересечении $i$-й строки и $j$-го столбца в матрице $A$ отличается от соответствующего элемента матрицы $B$ не более чем на $p$, скажем, что $A$ отличается от $B$ не более чем на $p$. Скажем, что матрица $B$ похожа на матрицу $A$ относительно числа $p$, если
1. отличается от не более чем на $p$
2. профили $B$ и $A$ совпадают.
На рисунке 2 изображены две похожие относительно числа 5 матрицы, первая из них почти кратна 5, а вторая кратна 5. Третья матрица на рисунке 2 тоже кратна 5, но непохожа на первую (хотя похожа на вторую).

Дано число p и почти кратная p матрица A. Ваша задача - найти такую матрицу B, чтобы она была кратна p и похожа на A относительно p.

Входные данные

В первой строке входных данных задаются целые числа $p$ (1 <= $p$ <= 10), $N$ и $M$ (1 <= $N$, $M$ <= 30). Следующие $N$ строк содержат по $M$ целых неотрицательных чисел, не превышающих 1000, которые являются элементами исходной матрицы $A$.

Выходные данные

Выведите матрицу $B$ по строкам - сначала $M$ элементов первой строки, затем $M$ элементов второй, и т. д. Разделяйте числа пробелами и/или переводами строк. Заботиться о красивом форматировании таблицы не надо. Если искомой матрицы не существует, выведите единственное число - "-1". Если решений несколько, выведите любое из них.

Примеры
Входные данные
3 3 3
1 2 3
2 3 1
3 1 2
Выходные данные
3 0 3 
0 3 3 
3 3 0 
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Из прямоугольного листа клетчатой бумаги ($M$ строк, $N$ столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

Входные данные

В первой строке находятся числа $M$ и $N$, в следующих $M$ строках - по $N$ символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= $M$, $N$ <= 100.

Выходные данные

Вывести одно число.

Примеры
Входные данные
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
Выходные данные
5

Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест