Темы
Информатика(2656 задач)
--->
173 задач
<---
На бумаге нарисовали клетчатое поле NxM клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений «вправо», «вверх», «влево» или «вниз».
| ← | → | → | ↓ | ↑ |
| → | ↑ | ↓ | ← | → |
| ↓ | ↑ | → | → | ↓ |
| → | ↑ | ← | ← | ← |
| ← | → | ↓ | ↓ | ↓ |
| ↑ | ↑ | ← | ↓ | ↑ |
Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю и никогда не выйдет за его пределы.
Напишите программу, которая по заданному полю определит количество клеток, начав с которых фишка никогда не покинет пределы поля.
Во входном файле заданы сначала размеры поля – число строк N и число столбцов M (1≤N≤1000, 1≤M≤1000). Далее идет N строк по M чисел в каждой, задающих направления стрелочек в клетках. Число 1 обозначает стрелочку вправо, 2 – вверх, 3 – влево, 4 – вниз. Числа в строке разделяются пробелами.
В выходной файл выведите одно число – количество клеток, начав с которых фишка никогда не покинет пределы поля.
Комментарии к примерам тестов.
Пример №1.Соответствует приведенному рисунку. Клетки, начавс которых, фишка никогда не покинет пределов поля на рисунке выделены серым цветом.
6 5 3 1 1 4 2 1 2 4 3 1 4 2 1 1 4 1 2 3 3 3 3 1 4 4 4 2 2 3 4 2
23
2 2 1 2 3 4
0
На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.>
В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.
1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.
В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида A∙x+B∙y+C=0, где x, y – координаты точек прямой, A, B, C – такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа – A, B, C).
Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).
Если прямой не существует, выведите в выходной файл сообщение “No solution” (без кавычек).
3 0 1 0 0 1 1 0 1 2
1 0 0
5 0 2 0 2 4 1 1 3 2 1 3 -1 1 3 -2
3 -1 -5
3 0 1 0 1 2 1 -2 -1 2
No solution
Заданы целые числа X, Y, P, Q (–10100 <= X, Y, P, Q <= 10100). Требуется проверить равенство XY = PQ. Напомним, что ab определяется следующим образом:
Во входном файле записаны числа X, Y, P, Q, каждое в отдельной строке.
Выведите слово correct, если данное равенство для полученных входных данных выполняется, или incorrect, если равенство не выполняется, или хотя бы одна из степеней не определена.
2 4 4 2
correct
2 3 3 2
incorrect
Есть прямоугольная таблица размером NxM клеток. В каждой клетке таблицы находится лампочка. Изначально все лампочки выключены.
Разрешается за одну операцию выбрать какую-нибудь прямоугольную область этой таблицы, один из углов которой находится в клетке (1,1) и изменить состояние всех лампочек в этой области (включенные лампочки – выключаются, выключенные – включаются).
Требуется сделать так, чтобы лампочки в этой таблице горели в шахматном порядке. При этом допускается получить любой из вариантов: как тот, в котором лампочка в клетке (1,1) выключена, так и тот, в котором она включена.
Напишите программу, которая по размерам таблицы определит минимальное количество операций, за которое можно получить требуемую конфигурацию.
Во входном файле записаны два числа N и M, задающие размеры таблицы. 1≤N≤100000, 1≤M≤100000.
В выходной файл выведите одно число – минимальное количество операций, с помощью которого из всех выключенных лампочек можно получить конфигурацию, когда лампочки горят в шахматном порядке.
Пояснение ко второму примеру (показан один из возможных вариантов):
| ∙ | ∙ |
| * | ∙ |
| ∙ | * |
| ∙ | ∙ |
| * | ∙ |
| * | ∙ |
| Начальное состояние – все лампочки выключены |
| Первая операция – переключаются все лампочки в выделенном прямоугольнике |
| Вторая операция – переключаются все лампочки в выделенном прямоугольнике. В итоге получается «шахматная» конфигурация. | |||
1 2
1
2 2
2
Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (Ai, Bi).
Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (Ai, Bi) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах Ai и Bi и поменять их местами.
Например, если N=5. Тогда изначально Васей выписана последовательность
1 2 3 4 5
Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.
Например, он может последовательно получить следующие последовательности:
2 1 3 4 5 (поменяв числа на 1 и 2 местах)
2 5 3 4 1 (поменяв числа на 2 и 5 местах)
5 2 3 4 1 (поменяв числа на 1 и 2 местах).
Пете не показываются промежуточные последовательности, а выписывается лишь полученная на последнем шаге.
От Пети требуется проверить, мог ли Вася получить такую последовательность не нарушая правил игры, и если мог, то указать, в результате какой последовательности обменов (при этом не требуется, чтобы число обменов было минимально возможным).
Напишите программу, которая поможет Пете справиться с этой задачей.
Сначала записано число N (1≤N≤100) – количество чисел в последовательности. Дальше идет N чисел – последовательность, полученная Васей (в последовательности каждое из чисел от 1 до N встречается ровно один раз).
Далее идет число P (0≤P≤10000) – количество пар чисел, выписанных Петей. Далее записано P пар чисел (каждое число пары – из диапазона от 1 до N).
В первую строку выходного файла выведите сообщение YES (если такая последовательность могла быть честно получена Васей) и NO (если такую последовательность Вася не мог получить, не нарушая правил игры).
В случае, если такая последовательность могла быть получена, далее выведите способ ее получения (если вариантов несколько, выведите любой из них). Сначала выведите число K – количество операций обмена (оно не должно превышать 100000), а затем K пар чисел, задающих номера мест, на которых стоят обмениваемые элементы (числа в паре могут быть выданы в любом порядке). Гарантируется, что если решение существует, то существует решение с числом обменов, не превышающим 100000.
5 5 2 3 4 1 2 1 2 2 5
YES 3 1 2 2 5 1 2
5 2 3 4 5 1 2 1 2 2 5
NO