На плоскости дано 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 определяется следующим образом:
- при b > 0, ab = a*a*...*a (b сомножителей)
- при b = 0, a <> 0 ab = 1
- при b < 0, a <> 0 ab = 1/a-b
- для остальных комбинаций a и b значение 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
SMS-сообщения на мобильном телефоне марки MOBILO набираются только заглавными английскими буквами. Для набора буквы нужно нажать кнопку, на которой эта буква написана, при этом если эта буква написана первой, то кнопку нужно нажать один раз, если второй – то два раза и т.д. Устройство клавиатуры телефона приведено на рисунке. 
Таким образом, чтобы набрать слово SMS, нужно нажать следующие кнопки:
<PQRS> <PQRS> <PQRS> <PQRS> <MNO> <PQRS> <PQRS> <PQRS> <PQRS>
Для набора двух букв, которые находятся на одной кнопке, при наборе нужно сделать паузу между их вводом. Например, чтобы набрать BA, нужно два раза нажать кнопку <ABC>, затем сделать паузу и затем нажать кнопку <ABC> еще раз.
Если на кнопке написано три буквы, то как только эта кнопка нажата три раза подряд, последняя из написанных на ней букв сразу же добавляется в сообщение, а дальнейшие нажатия на эту кнопку воспринимаются как ввод следующей буквы. То же самое, если на кнопке написано 4 буквы. Таким образом, 4-х кратное нажатие на кнопку <ABC>, затем пауза, и затем нажатие на эту кнопку еще раз приведет к вводу текста CAA.
К сожалению, в силу произошедшего глюка, телефон стал иногда игнорировать паузы при вводе, а, иногда, наоборот, вести себя так, как будто была пауза тогда, когда паузы не было. Например, при вводе слова MOSCOW могло в итоге (как один из вариантов) получиться слово OMSCMNW.
Вы получили SMS-сообщение, набранное на этом телефоне. Известно, что изначально оно состояло из N символов. Напишите программу, которая определит количество вариантов исходных сообщений, которые при вводе могли превратиться в то, что вы получили (если вариантов окажется 0, то это будет означать, что у телефона сломалось что-то еще).
Сначала записана длина исходного сообщения N (1≤N≤80). Вторая строка содержит полученное SMS-сообщение – последовательность не более чем из 80 заглавных латинских букв.
Выведите одно число – количество вариантов исходного сообщения.
4 MAMA
1
2 WWW
2
10 MAMA
0