Петя решил зашифровать свой дневник, чтобы никто без его ведома не смог его прочитать. Для этого он воспользовался следующим шифром.
Он изготовил трафарет NxN клеток (N — четное), в котором вырезал клеток так, что при наложении трафарета на лист бумаги четырьмя возможными способами (трафарет можно поворачивать, но нельзя переворачивать) каждая клетка листа видна ровно один раз.
Пример такого трафарета показан на рисунке ниже:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С помощью этого трафарета шифруется текст из N2 символов следующим образом. Сначала в прорези трафарета вписываются первые букв шифруемого текста (буквы вписываются в вырезанные клетки по строкам сверху вниз, в каждой строке — слева направо). Например, если Петя шифрует слово ОЛИМПИАДА, то оно будет вписано в клетки следующим образом:
| О |
|
|
| Л |
|
|
| И |
| М |
|
|
|
|
|
|
| П |
|
|
|
| И |
|
| А |
| Д |
|
|
|
|
|
|
|
|
| А |
|
|
Далее трафарет поворачивается на 90 градусов по часовой стрелке, и в вырезанные клетки в том же порядке вписываются следующие букв шифруемого текста. И так далее. Если шифруемый текст состоит меньше, чем из N2 символов, то (когда текст кончается) оставшиеся клетки остаются пустыми.
Например, если Петя шифрует текст ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА при помощи приведенного трафарета, то процесс шифрования будет устроен так. Как зашифровать слово ОЛИМПИАДА, мы уже показали. Для удобства здесь и далее пробел будем обозначать знаком подчеркивания. При втором прикладывании трафарета Пете удастся зашифровать _ПО_ИНФОР:
| О | _ |
|
| Л | П |
|
| И |
| М | О |
|
|
|
| _ |
| П |
|
| И |
| И |
| Н | А |
| Д |
|
| Ф |
| О |
|
|
| Р | А |
|
|
При третьем прикладывании трафарета Петя зашифрует МАТИКЕ_20:
| О | _ | М |
| Л | П |
|
| И |
| М | О | А |
| Т |
| _ | И | П |
|
| И | К | И |
| Н | А |
| Д |
| Е | Ф | _ | О |
|
| 2 | Р | А |
| 0 |
При четвертом прикладывании трафарета Петя зашифрует 06_ГОДА. Остальные клетки окажутся пустыми (будем считать, что в них записан пробел, который мы обозначаем подчеркиванием):
| О | _ | М | 0 | Л | П |
| 6 | И | _ | М | О | А |
| Т | Г | _ | И | П | О |
| И | К | И | Д | Н | А |
| Д | А | Е | Ф | _ | О |
| _ | 2 | Р | А | _ | 0 |
После этого получившийся текст Петя выписывает в строчку:
О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0
Для повышения надежности Петя решил зашифрованный текст зашифровать тем же методом с помощью того же трафарета еще раз, затем получившийся текст — еще раз и т.д. После нескольких повторов Петя с удивлением заметил, что зашифрованный текст совпал с исходным.
Напишите программу, которая для данного трафарета определит, после какого наименьшего количества процедур шифрования Петя получит исходный текст независимо от содержания текста?
Сначала во входном файле записано число N — размер трафарета (2≤N≤150). Затем идет N2 чисел (каждое из которых 0 или 1), описывающих трафарет. 1 обозначает вырезанную клетку, 0 — не вырезанную. Гарантируется, что данная последовательность описывает корректный трафарет для данного способа шифрования.
В выходной файл выведите одно число — через какое минимальное количество повторов операции шифрования Петя получит исходный текст независимо от его содержания.
2 1 0 0 0
2
6 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0
120
Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 — нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.
Дана последовательность. Требуется определить, какое наименьшее количество ее членов нужно вычеркнуть, чтобы оставшаяся последовательность оказалась пилообразной.
В первой строке входного файла записано одно число N (1≤N≤100000) — количество членов последовательности. Во второй строке записано N натуральных чисел, не превосходящих 10 000 — члены последовательности.
В выходной файл выведите одно число — минимальное количество членов, которые необходимо вычеркнуть.
5 1 2 3 1 2
1
5 1 2 1 3 2
0
5 1 2 3 4 5
3
5 1 1 2 1 1
2
Оператор сотовой связи решил разработать несколько безлимитных тарифных планов, отличающихся между собой ежемесячной абонентской платой и набором дополнительных услуг. Менеджерам по работе с клиентами удалось выяснить, сколько каждый из VIP-абонентов компании готов тратить в месяц на услуги сотовой связи. Теперь сотовая компания хочет предложить каждому из абонентов свой тарифный план, но, к сожалению, комитет по антимонопольной политике разрешает сотовой компании иметь не более K безлимитных тарифных планов.
Помогите менеджерам компании разработать эти K тарифных планов, чтобы максимизировать доходы компании.
В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1≤N≤100) и количество тарифных планов K (1≤K≤100).
Далее записано N целых чисел Ai — сумма, которую i-ый абонент готов тратить на связь в месяц (0≤Ai≤100000).
Выведите в выходной файл K натуральных чисел — размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 109.
Считается, что каждому абоненту будет предложен тарифный план, в котором абонентская плата максимально возможная, но не превышающая Ai, и этот абонент будет обслуживаться по этому тарифному плану. Если такого тарифного плана не окажется, абонент не будет обслуживаться компанией.
Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.
Комментарии к примерам тестов
1. Мы не будем обслуживать абонента, который готов платить 1. Абонента, который готов платить 4, мы подключим к первому тарифному плану. Абонентов, готовых платить 5 — ко второму, готовых платить 8 и 9 — к третьему, и готового платить 80 — к четвертому. Итого суммарный доход компании составит 4 + 5*4 + 8*2 + 80 = 120
2. Подключаем каждого абонента к своему тарифу, 4-й тариф не используем. Суммарный доход — 1+2+30=33
3. Подключаем всех, кроме первого и третьего абонентов, к единственному тарифу. Суммарный доход — 4*4 = 16
4. Поскольку мы не имеем права делать тариф с нулевой абонентской платой, то 1-го и 3-го абонентов обслуживать не будем.
9 4 9 1 5 5 5 5 4 8 80
4 5 8 80
3 4 1 2 30
1 2 30 31
6 1 0 4 3 5 13 6
4
3 2 0 1 0
1 2
Игра в трехмерные шахматы ведется на кубическом поле N×N×N. Трехмерная ладья может ходить на любое число клеток по прямой в любом из шести направлений (в любую сторону в каждом из трех направлений).
На таком поле расставлены K ладей. Напишите программу, которая определит, бьют они все поле или нет.
В первой строке входного файла записано натуральное число N (1≤N≤1000), задающее размеры игрового куба, и количество ладей K (0≤K≤106). Далее записано K троек чисел, задающих координаты ладей (координата по каждому измерению — натуральное число от 1 до N).
Выведите в выходной файл слово YES, если эти ладьи бьют весь куб, и слово NO в противном случае. В случае NO выведите во второй строке координаты какой-нибудь клетки, которая не бьется ни одной из ладей.
2 2 1 1 1 2 2 2
YES
2 2 1 1 1 1 1 2
NO 2 2 1
Недавно археологической командой «Раскопай» были обнаружены остатки древней цивилизации. Особое внимание привлекла карта с месторасположением народов, живших в то время. Карта представляет собой прямоугольный лист, разлинованный горизонтальными линиями на M полос и вертикальными линиями на N столбцов. Таким образом формируются M*N клеток — древних поселений, которые заселялись сообществами. В каждой клетке этой карты написано натуральное число — идентификатор народа, к которому принадлежит это сообщество людей (рукопись с соответствием между идентификаторами и народами также была обнаружена).
<>Группа историков «Разузнай» имеет такую же карту, но только на тысячелетие древнее. Естественно, она может отличаться от той, которую нашли археологи — ведь за такой срок сообщества могли переселяться в другие поселения. Историками была высказана идея о механизме переселения народов.Чтобы объяснить этот процесс введем систему координат на карте так, что границы карты параллельны осям координат. Пусть координаты (0,0) соответствуют самой верхней левой клетке, а (N–1, M–1) — самой нижней правой. Переселение народов проходит в несколько этапов. Опишем как проходит каждый этап.
Назовем квадратом множество всех поселений с координатами (x,y) такими, что x1≤x≤x2, y1≤y≤y2, где x2–x1=y2–y1. Соответственно клетка (x1,y1) является левой верхней клеткой квадрата, (x2,y2) —нижней правой.
На каждом этапе переселения переселяются сообщества внутри некоторого квадрата по следующему правилу. Если переселение происходит внутри квадрата, левой верхней клеткой которого является клетка (x1,y1), а правой нижней — (x2,y2), то сообщество, проживавшее в поселении с координатами (x,y) (x1≤x≤x2, y1≤y≤y2) переселяется в поселение с координатами (x2–(y2–y),y2–(x2–x)), при этом, возможно, что некоторые сообщества остаются на своих местах. Все сообщества, живущие вне квадрата, в котором происходит переселение, остаются на своих местах.
Историки из «Разузнай» хотят для подтверждения (или опровержения) своей теории переселений проверить, могла ли в результате таких переселений из карты, которая есть в распоряжении «Разузнай» получиться карта, которую нашли археологи. Помогите им — напишите программу, которая будет это делать.
На первой строке входного файла заданы через пробел 2 натуральных числа M и N, где M — количество строк, а N — количество столбцов (1≤M≤30, 1≤N≤30). Далее описывается карта историков. После нее записана карта археологов.
Каждая карта описывается в M строках, в каждой из которых записано по N чисел — идентификаторы народов, проживающих в соответствующих поселениях. В первой строке описания записаны народы, проживающие в поселениях с координатами (0,0), (1,0), (2,0),…,(N–1,0), во второй — в поселениях (0,1), (1,1), (2,1),…,(N–1,1), в M-ой — с координатами (0, M–1), (1,M–1),…,(N–1,M–1). Идентификаторы народов — натуральные числа, не превышающие 2∙109. Некоторые идентификаторы могут не использоваться (например, на карте могут встречаться народы с номерами 1 и 3, и не встречаться народ с идентификатором 2).
Если гипотеза историков подтверждается, то в выходной файл выведите количество этапов переселения народов и дальше сами эти этапы, в результате которых из карты историков получается карта археологов. Каждый этап должен быть описан четырьмя числами — x1, y1, x2, y2 (координатами углов квадрата, который переселяется). Обратите внимание, что добиваться минимального количества переселений всех народов, или же минимального количества этапов не требуется. Важно, чтобы общее число этапов не превышало 10000 (математики из общества «Докажи» доказали, что в указанных ограничениях это всегда возможно).
Если гипотеза историков неверна, т.е. из карты историков карта археологов с помощью только таких переселений получиться не могла, то выведите в выходной файл одно число –1 (минус один).
Пояснение к примеру 1
Переселение проходит в 2 этапа: на рисунке ниже закрашены квадраты, в которых происходили переселения сообществ.
3 4 1 4 2 2 1 3 3 1 2 1 1 1 1 1 2 3 4 3 1 1 2 2 1 1
2 2 0 3 1 0 0 2 2
2 2 6 8 5 8 6 8 5 9
-1