Страница: 1 2 3 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано N точек. Из каждой точки исходят красные или синие ребра во все точки с большим номером. Требуется определить, существует ли пара точек такая, что из первой можно добраться до второй как по красным ребрам так и по синим.

Даны N точек, занумерованных числами 1, 2, ..., N. От каждой точки с меньшим номером к каждой точке с большим номером ведет стрелка красного или синего цвета. Раскраска стрелок называется однотонной, если нет двух таких точек A и B, что от A до B можно добраться как только по красным стрелкам, так и только по синим.

Ваша задача — по заданной раскраске определить, является ли она однотонной.

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

В первой строке входных данных содержится единственное число N (3 ≤ N ≤ 5000).

В следующих N–1 строках идет описание раскраски. В (i+1)-й строке  записано (N–i) символов R (красный) или B (синий), соответствующих цвету стрелок, выходящих из точки i и входящих в точки (i+1), (i+2), ..., N соответственно.

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

Выведите YES, если приведенная раскраска является однотонной, и NO в противном случае.

Оценка задачи

1 балл будут набирать решения, верно работающие для N ≤ 50.

Примеры
Входные данные
3
RB
R
Выходные данные
NO
Входные данные
3
RR
R
Выходные данные
YES
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дан невзвешенный граф, у которого вершины раскрашены в один из трех цветов. Необходимо перекрасить вершины графа таким образом, чтобы не было двух соседних вершин одного цвета, а также каждая вершина изменила цвет.

Петя нарисовал на бумаге n кружков и соединил некоторые пары кружков линиями. После этого он раскрасил каждый кружок в один из трех цветов – красный, синий или зеленый.

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

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

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

В первой строке вводятся два целых числа n и m – количество кружков и количество линий, которые нарисовал Петя, соответственно ( 1$ le$n$ le$1 000, 0$ le$m$ le$20 000).

Следующая строка содержит n символов из множества {'R', 'G', 'B'} – i-й из этих символов означает цвет, в который раскрашен i-й кружок ('R' – красный, 'G' – зеленый, 'B' – синий).

Далее в m строках задается по два целых числа – пары кружков, соединенных отрезками.

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

Выведите  одну строку, состоящую из n символов из множества {'R', 'G', 'B'} – цвета кружков после перекраски. Если решений несколько, выведите любое.

Если решения не существует, выведите  слово "Impossible''.

Примеры
Входные данные
4 5
RRRG
1 3
1 4
3 4
2 4
2 3
Выходные данные
GGBR
Входные данные
4 5
RGRR
1 3
1 4
3 4
2 4
2 3
Выходные данные
Impossible
ограничение по времени на тест
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 
ограничение по времени на тест
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 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест