Информатика

На числовой прямой в точке с координатой \(0\) сидит кузнечик. За одно действие он может выбрать любое целое неотрицательное число \(k\) и прыгнуть влево или вправо на расстояние \(2^k\).

Помогите кузнечику определить, какое минимальное количество действий ему понадобится выполнить, чтобы из точки с координатой \(0\) попасть в точку с координатой \(x\).

Формат входных данных
В первой строке дано одно целое число \(t\) — количество наборов входных данных (\(1 \le t \le 100\,000\)).

Каждый набор входных данных состоит из единственной строки, в которой дано целое число \(x\) — координата точки, в которую хочет попасть кузнечик (\(-10^{18} \le x \le 10^{18}\)).

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

Дано бесконечное бинарное дерево. У дерева есть корень и бесконечное число вершин, у каждой вершины есть левый и правый сын, у всех вершин кроме корня есть отец.

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

1. color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.

2. Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат выходных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).

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

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

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

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

Входные данные
В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы S_x, S_y, F_x, F_y - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа a_i, b_i, y_i, c_i - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (a_i < b_i, F_y < y_i < S_y, c_i - целое число, 0 ≤ c_i ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.

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

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

Два слова называются похожими, если можно удалить из каждого слова не более одной буквы так, чтобы слова стали одинаковыми, возможно пустыми. Например, слова "spot" и "sport" похожи, так как одно и то же слово "spot" можно получить из первого слова без удаления букв, а из второго - удалением буквы "r".

Требуется написать программу, которая для каждого слова проверяемого текста определяет количество похожих на него слов в словаре.

Входные данные
В первой строке входного файла через пробел записаны натуральные числа N ≥ 1 - общее количество слов в словаре и M ≥ 1 - количество слов в проверяемом тексте (N+M ≤ 20000) В последующих N строках записаны слова, входящие в словарь, по одному на строке. Все слова словаря различны. Далее следуют M строк, в которых записаны слова проверяемого текста, по одному слову в строке.

Слова состоят из строчных и прописных букв латинского алфавита (прописные и строчные буквы считаются различными). Любое слово состоит не менее чем из одной и не более чем из 12 букв.

Выходные данные
Для каждого слова из текста выведите в выходной файл строку, содержащую это слово, далее через пробел количество слов из словаря, на которые оно похоже. Если в словаре имеется единственное похожее слово, то также выведите в этой строке это слово (через пробел).

Бригада скорой помощи выехала по вызову в один из отделенных районов. К сожалению, когда диспетчер получил вызов, он успел записать только адрес дома и номер квартиры K₁, а затем связь прервалась. Однако он вспомнил, что по этому же адресу дома некоторое время назад скорая помощь выезжала в квартиру K₂, которая расположена в подъезда P₂ на этаже N₂. Известно, что в доме M этажей и количество квартир на каждой лестничной площадке одинаково. Напишите программу, которая вычилсяет номер подъезда P₁ и номер этажа N₁ квартиры K₁.

Входные данные
Во входном файле записаны пять положительных целых чисел K₁, M, K₂, P₂, N₂. Все числа не превосходят 1000.

Выходные данные
Выведите два числа P₁ и N₁. Если входные данные не позволяют однозначно определить P₁ или N₁, вместо соответствующего числа напечатайте 0. Если входные данные противоречивы, напечатайте два числа –1 (минус один).

Всемирно известный маг Дэвид Копперфильд любит показывать следующий трюк. Квадрат из N столбцов и N строк, в каждой клетке которого находится какая-нибудь картинка, появляется на экране телевизора. Пусть все картинки пронумерованы следующим образом:

1	2	…	N
N+1	N+2	…	2*N
:	:	…	:
N*(N–1)+1	N*(N–1)+2	…	N*N

Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем — на одну клетку вниз, затем — на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и — что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).

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

Входные данные
Во входном файле записано одно число N — размер квадрата (2<=N<=100).

Выходные данные
В выходной файл ваша программа должна печатать следующие строки чисел:

K₁ X_1,1 X_1,2 … X_1,m1

K₂ X_2,1 X_2,2 … X_2,m2

…

K_e X_e,1 X_e,.2 … X_e,me

где K_i — это число ходов, которые должны сделать телезрители, а X_i,1 … X_i,mi — номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все K_i должны удовлетворять условию 2N<=K_i<=10000 и все K_i должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать K_i ходов, Дэвид должен убирать хотя бы одну картинку. Каждое K_i должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.

Алексей работает системным администратором в локальной домовой сети. Его сеть соединяет множество квартир и располагается в нескольких зданиях.

Сеть постоянно расширяется и Алексею поручено проложить новый участок сети. У него есть схема, на которой указаны все возможные соединения между парами квартир и для каждого соединения он знает длину провода, необходимого для его прокладки. Его цель состоит в том, чтобы все квартиры были подключены к сети (возможно через другие квартиры).

Компания, в которой работает Алексей покупает кабель только в одном специализированном магазине. В магазине продается кабель пятой и шестой категорий по цене P5 и P6 рублей за метр. При этом в наличии имеется только Q5 метров кабеля пятой категории и Q6 метров кабеля шестой категории.

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

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

В первой строке входного файла содержится число N — количество квартир, которые необходимо соединить и M — количество возможных соединений (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10 000).

Следующие M строк содержат описание возможных соединений. Каждое описание состоит из трех чисел A, B и L — где A и B задают номера квартир, а L — длина соединения между ними (1 ≤ L ≤ 100). Квартиры занумерованы от 1 до N.

Последняя строка входного файла содержит числа P5, Q5, P6, Q6 – цену и количество кабеля пятой и шестой категории соответственно (1 ≤ P, Q ≤ 10 000) .

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

Если все квартиры можно соединить в сеть, то следует вывести N строк, описывающих план сети. Первая строка должна содержать стоимость прокладки сети. Следующие N-1 строк должны содержать описание соединений, представленных двумя числами каждое: A_i и C_i, где A_i — номер соединения в списке возможных соединений (от 1 до M), а C_i задает категорию кабеля и может принимать значения 5 или 6. Если планов несколько — выведите любой из них.

Если все квартиры соединить невозможно выведите слово Impossible.

На проверку сдается код, содержащий только описание класса.

Объявите класс с именем ListMath, объекты которого можно создавать командами:

lst1 = ListMath() # должен создаваться пустой список
lst2 = ListMath([1, 2, -5, 7.68]) # список с начальными значениями

В качестве значений элементов списка объекты класса ListMath должны отбирать только целые и вещественные числа, остальные игнорировать (если указываются в списке). Например:

lst = ListMath([1, "abc", -5, 7.68, True]) # ListMath: [1, -5, 7.68]

В каждом объекте класса ListMath должен быть публичный атрибут:

lst_math - ссылка на текущий список объекта (для каждого объекта создается свой список).

Также с объектами класса ListMath должны работать следующие операторы:

lst = lst + 76 # сложение каждого числа списка с определенным числом
lst = 6.5 + lst # сложение каждого числа списка с определенным числом

Команда print(lst1) - в скобка указывается объект класса - должна выводить элементы массива в одной строку, разделяя элементы одним пробелом. В случае если список не содержит элементов, должна выводиться надпись Cписок пуст.

lst1 = ListMath()
print(lst1)    # Список пуст

lst2 = ListMath([1, "abc", -5, 7.68, True]) 
print(lst2)    # 1 -5 7.68

Фонд изучения дикой природы в течение \(t\) лет ежегодно выделяет денежные гранты в поддержку исследований северной фауны. На гранты претендуют три организации, одна из которых занимается изучением тюленей, вторая "— оленей, третья "— белых медведей.

Для упрощения бухгалтерского учёта фонд принял следующие решения:

В \(i\)-м году фонд планирует полностью распределить \(n_i\) денежных единиц, выделенных на гранты. Сравнивать результативность использования средств возможно только для грантов одинакового размера, выделенных каждой из трёх организаций. Такие гранты называются целевыми. Распределение денежных единиц на гранты между тремя организациям считается оптимальным, если как можно бОльшая часть общей суммы выделена на целевые гранты.

Например, если в текущем году на все гранты выделено 47 денежных единиц, то оптимальным вариантом распределения будет: выделить каждой из организаций целевые гранты размерами по 2 и 8 денежных единиц, что составит в сумме 30 единиц. Остальные 17 единиц можно распределить, например, выделив первой организации 16 денежных единиц, а третьей — 1 денежную единицу. Выделить более 30 денежных единиц на целевые гранты, распределяя 47 денежных единиц, нельзя.

Требуется написать программу, которая по заданной в \(i\)-м году общей сумме грантов \(n_i\) определяет, сколько денежных единиц следует выделить каждой из трёх организаций при оптимальном распределении грантов.

В первой строке входных данных записано целое число \(t\) — количество лет (\(1 \le t \le 100\)). В каждой из последующих \(t\) строк записано целое число \(n_i\)"— общая сумма грантов, которую необходимо полностью распределить в \(i\)-м году.

Выходные данные должны содержать \(t\) строк по три целых числа в каждой — суммы грантов, которые следует выделить каждой из трёх организаций в соответствующий год. Если оптимальных вариантов распределения несколько, необходимо вывести любой из них.

На кафедре пингвиноведения Южного Антарктического университета проводятся исследования популяций пингвинов. Фотографии скоплений плотно стоящих пингвинов обрабатываются студентами. Распознавание пингвинов на снимках производится следующим образом: на фотографии выбирается характерная полоса высотой в один пиксель, каждый пиксель которой входит в изображение одного из пингвинов.

У всех пингвинов исследуемой популяции живот белый, а спина и крылья — чёрные. Таким образом, если у пингвина на фотографии видна только спина, то на характерной полосе ему соответствует отрезок из чёрных пикселей, а если только живот, то из белых. В остальных случаях, например, когда чёрные крылья видны поверх белого живота, пингвину соответствует отрезок из чёрных и белых пикселей. Для продолжения исследований необходимо, чтобы каждому пингвину соответствовал отрезок, состоящий либо только из чёрных, либо только из белых пикселей.

Для \(i\)-й фотографии известно максимальное количество пингвинов \(k_i\), изображение которых могло попасть на характерную полосу. Поэтому эту полосу пикселей необходимо заменить на упрощённую полосу той же длины, которая будет состоять не более чем из \(k_i\) отрезков, каждый из которых либо полностью чёрный, либо полностью белый. Из всех возможных упрощённых полос нужно выбрать оптимальную — то есть ту, которая получается из характерной путём изменения цвета минимального числа пикселей.

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

Входные данные
В первой строке входных данных содержится число \(t\) — количество фотографий. Далее следуют \(t\) пар строк, \(i\)-я пара строк описывает \(i\)-ю фотографию.

Первая строка описания фотографии содержит два числа: \(n_i\) — длину характерной полосы \(i\)-й фотографии, и \(k_i\) — максимальное количество пингвинов, которые могут быть на ней изображены (\(k_i \le n_i\)).

Вторая строка описания состоит из \(n_i\) символов 0 и 1, где 0 обозначает чёрный, а 1 — белый пиксель.

Выходные данные
Выходные данные должны содержать \(t\) строк, где \(i\)-я строка состоит из \(n_i\) символов 0 и 1 и описывает упрощённую полосу, полученную из характерной полосы \(i\)-й фотографии. Если оптимальных упрощённых полос несколько, выведите любую из них.

Одна из центральных площадей Архангельска замощена прямоугольными плитками размера \(1 \times k\). Если ввести систему координат, так что левый нижний угол одной из плиток будет иметь координаты \((0, 0)\), то левые нижние углы плиток будут иметь координаты \((i \cdot k+j,j)\) для всех целых \(i\) и \(j\).

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

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

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

Входные данные
Первая строка входных данных содержит два числа \(n\) и \(k\) — количество вершин в основании памятника и размер плитки.

Каждая из последующих \(n\) строк содержит два целых числа \(x_i\), \(y_i\) — координаты \(i\)-й вершины основания. Координаты перечислены в порядке обхода против часовой стрелки.

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

Замечание

Школа юных программистов решила разработать собственную социальную сеть, которая должна автоматически подбирать для каждого пользователя потенциальных друзей. При регистрации каждому пользователю сети предлагается пройти психологическое тестирование, по результатам которого определяются значения трёх психологических характеристик этого пользователя. Значение каждой характеристики — целое положительное число.

Считается, что если у двух пользователей различаются значения всех трёх психологических характеристик, то они будут постоянно ссориться, а если совпадают значения двух или трёх характеристик, то им будет скучно. Таким образом, потенциальными друзьями являются только такие пары пользователей, у которых совпадают значения ровно одной характеристики, а значения двух других — различаются.

Требуется написать программу, которая по данным \(n\) тройкам \((a_i, b_i, c_i)\) значений характеристик каждого из пользователей определяет количество пар потенциальных друзей, то есть таких пар индексов \(i < j\), что из трёх равенств \(a_i = a_j\), \(b_i = b_j\), \(c_i = c_j\) выполняется ровно одно.

Входные данные
Первая строка входных данных содержит число \(n\) — количество пользователей (1 ≤ n ≤ 100 000). Каждая из последующих \(n\) строк содержит три целых положительных числа \(a_i\), \(b_i\) и \(c_i\) — значения характеристик \(i\)-го пользователя (1 ≤ a_i , b_i , c_i ≤ 100)

Выходные данные
Выходные данные должны содержать искомое количество пар потенциальных друзей.

Примечание
В первом примере потенциальную пару друзей образуют пользователи 1 и 2, а также 2 и 3. В обоих случаях у пользователей совпадает значение первой характеристики и различаются значения второй и третьей характеристик. Пользователи 1 и 3 имеют одинаковые значения первых двух характеристик, поэтому они не образуют пару потенциальных друзей.

Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.

Ограничение по времени выполнения программы - 1 секунда, ограничение по используемой памяти - 64 мегабайта.

Входные данные
Во входных данных записано натуральное число N (2 ≤ N ≤ 10⁹)

Выходные данные
Выведите два искомых числа A и B. Если решений несколько, выведите любое из них.

На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.

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

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

Гарантируется, что во входных данных содержится информация, которой достаточно для однозначного определения размеров прямоугольников.
 

0	2	2	2	2
0	2	2	2	2
1	1	2	2	2
1	1	0	0	0

Входные данные
В первой строке входного файла записаны целые числа N, M, K (1≤N≤200, 1≤M≤200, 1≤K≤255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.

Выходные данные
В выходной файл необходимо выдать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами R C H W (R и C должны описывать координаты левого нижнего угла прямоугольника, а H и W — координаты правого верхнего угла). Числа должны разделяться пробелом.

Оси координат устроены следующим образом: начало координат находится в нижнем левом углу поля, а оси координат направлены вдоль сторон поля (ось Ox — вдоль нижней стороны, а ось Oy — вдоль левой стороны). Клетки поля имеют размер 1x1. Таким образом, координаты левого нижнего угла поля — (0,0), правого верхнего — (M,N). Заметьте, что вы должны вывести координаты углов прямоугольников (как точек) в этой системе координат, а не координаты угловых клеток, покрытых прямоугольниками.

Учительница задала Пете домашнее задание — в заданном тексте расставить ударения в словах, после чего поручила Васе проверить это домашнее задание. Вася очень плохо знаком с данной темой, поэтому он нашел словарь, в котором указано, как ставятся ударения в словах. К сожалению, в этом словаре присутствуют не все слова. Вася решил, что в словах, которых нет в словаре, он будет считать, что Петя поставил ударения правильно, если в этом слове Петей поставлено ровно одно ударение.

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

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

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤100).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 30000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.




Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.

Входные данные
Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

Выходные данные
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.

 

Примеры

№	Входные данные	Выходные данные	Примечание
1	3 3 2 1	YES	Надо весь поезд завезти в тупик, а затем целиком вывезти его на 2-й путь.
2	4 4 1 3 2	YES	Сначала надо в тупик завезти два вагона, один из которых оставит в тупике, а второй — вывезти на 2-й путь, после чего завезти в тупик еще два вагона и вывезти 3 вагона, стоящие в тупике, на 2-й путь
3	3 2 3 1	NO

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

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

Входные данные
Вводится одно натуральное число N (1≤N≤1000).

Выходные данные
Выведите одно число — искомое количество способов заполнения массива.

Примечание
Массив можно заполнить единственным способом: 3 2
 

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

Вася положил ключи в некоторые из копилок (он помнит, какой ключ лежит в какой из копилок). Теперь Вася собрался купить машину, а для этого ему нужно достать деньги из всех копилок. При этом он хочет разбить как можно меньшее количество копилок (ведь ему еще нужно копить деньги на квартиру, дачу, вертолет…). Помогите Васе определить, какое минимальное количество копилок нужно разбить.

Входные данные
В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

Выходные данные
Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Примечание
Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.
Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
 

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Объявите в программе класс Car, в котором реализуйте объект-свойство с именем model для записи и считывания информации о модели автомобиля из локальной приватной переменной __model.

Объект-свойство объявите с помощью декоратора @property. Также в объекте-свойстве model должны быть реализованы проверки:

- модель автомобиля - это строка;
- длина строки модели должна быть в диапазоне [2; 100].

Если проверка не проходит, то локальное свойство __model остается без изменений.

Объекты класса Car создаются командой:

car = Car()

и далее работа с объектом-свойством происходит следующим образом:

car.model = "Toyota"

Ваша задача написать ТОЛЬКО класс.