Многие головоломки (судоку, башенки и т.п.), требуют заполнения квадратного поля $$$ n \times n $$$ числами таким образом, чтобы в каждой строке и в каждом столбце числа $$$ 1...n $$$ встречались ровно по одному разу.
Для компьютерного построения таких головоломок необходимо уметь генерировать квадратное поле, обладающее указанным свойством.
Напишите программу, которая по заданной первой строке заполнит оставшиеся клетки таблицы так, чтобы каждая строка и каждый столбец содержали все числа от $$$ 1 $$$ до $$$ n $$$.
Первая строка содержит размер таблицы $$$ n $$$ ($$$ 1 \leq n \leq 100 $$$). Вторая строка содержит $$$ n $$$ чисел, разделенных пробелами – содержимое первой строки таблицы. Строка состоит из неповторяющихся чисел от $$$ 1 $$$ до $$$ n $$$.
Вывести $$$ n $$$ строк по $$$ n $$$ чисел в каждой – предлагаемое заполнение таблицы. Соседние числа в строке должны быть разделены ровно одним пробелом.
4 1 2 3 4
1 2 3 4 2 3 4 1 4 1 2 3 3 4 1 2
Игорь и Ира решили определить главного в семье, для этого они проведут турнир по стрельбе из лука. Турнир проходит по простым правилам: каждый из участников делает по $$$n$$$ выстрелов (сначала все свои выстрелы делает первый участник, потом второй). Мишень — круг, состоящий из $$$k$$$ колец, за попадание в каждое из которых начисляется от $$$1$$$ до $$$k$$$ очков. Главным в семье будет тот, кто сможет набрать большее количество очков.
Игорь уже произвел свои $$$n$$$ выстрелов и набрал $$$p$$$ очков, теперь очередь Иры. Она уже приноровилась к стрельбе из лука, и теперь всегда попадает в мишень, в отличие от Игоря. При выстреле Ира попадает в каждое кольцо с одинаковой вероятностью.
Помогите Ире определить количество выигрышных комбинаций из $$$n$$$ выстрелов.
В единственной строке записаны три целых числа $$$n$$$, $$$k$$$, $$$p$$$ $$$(1\leq n, k\leq 300, 0 \le p\leq k\cdot n)$$$ — количество выстрелов, количество колец на мишени и количество очков, набранных Игорем.
В единственной строке выведите число — количество комбинаций из $$$n$$$ выстрелов Иры в мишень, таких, что сумма набранных очков будет больше, чем $$$p$$$.
Выведите ответ по модулю 1000000007$$$(10^9+7)$$$.
3 3 7
4
5 5 6
3119
В первом тесте существуют следующие комбинации попаданий Ирой в мишень, при которых она набирает очков больше, чем Игорь.
$$$[2,3,3]$$$ сумма очков: 8
$$$[3,2,3]$$$ сумма очков: 8
$$$[3,3,2]$$$ сумма очков: 8
$$$[3,3,3]$$$ сумма очков: 9
Многие рекуррентные последовательности приобретают новые интересные свойства, если вычислять их по модулю какого-то числа. В силу конечности остатков от деления, последовательности превращаются в циклы или петли. Числа Фибоначчи являются хорошим примером зацикливающейся последовательности.
Напомним, что последовательность Фибоначчи задается рекуррентным соотношением $$$ F_i = F_{i-1} + F_{i-2} $$$, где $$$ F_0 = 0, F_1 = 1 $$$.
При вычислении такой последовательности по модулю числа $$$ n $$$, после некоторого числа шагов, происходит возврат к начальным значениям $$$ 0 $$$ и $$$ 1 $$$. Минимальное количество шагов, необходимых для зацикливания последовательности, обозначается как $$$ \pi(n) $$$ и называется периодом Пизано. Число $$$ \pi(n) $$$ существует для любого $$$ n $$$. Для каждого $$$ \pi(n) $$$ справедливо $$$ F_{i} \equiv F_{i+\pi(n)} (mod~n) $$$ при любом $$$ i $$$.
Взаимосвязь между длиной периода Пизано $$$ \pi(n) $$$ и самим числом $$$ n $$$ достаточно сложна и сводится к вычислению периодов Пизано для простых чисел. Для простого числа $$$ p $$$ значение $$$ \pi(p) $$$ вычисляется по следующим правилам:
- Выделяются два специальных случая: $$$ \pi(2) = 3 $$$ – единственный период с нечетной длиной, и $$$ \pi(5) = 20 $$$.
- Если $$$ p \equiv \pm 1 (mod~5) $$$, то $$$ \pi(p) $$$ будет делителем числа $$$ (p - 1)$$$.
- Если $$$ p \equiv \pm 2 (mod~5) $$$, то $$$ \pi(p) $$$ будет делителем числа $$$ (2p + 2)$$$.
Например, $$$ 47~mod~5 = 2 $$$, а $$$ \pi(47) = 32 $$$, а число $$$ 32 $$$ является делителем числа $$$ 2 \cdot 47 + 2 = 96 $$$. Или $$$ 89~mod~5 = 4 (-1) $$$, и $$$ \pi(89) = 44 $$$, ведь $$$ 44 $$$ – делитель числа $$$ 89 - 1= 88 $$$.
Напишите программу, которая по заданному простому числу $$$ p $$$ ($$$ 2 \leq p \leq 10^9 $$$) вычислит для него $$$ \pi(p) $$$.
В единственной строке содержится простое число $$$ p $$$ ($$$ 2 \leq p \leq 10^9 $$$).
В единственной строке выведите число – длину периода Пизано $$$ \pi(p) $$$.
11
10
5
20
В коническое пожарное ведро высотой $$$ h $$$ и верхним диаметром $$$ d $$$ тонкой струйкой насыпают песок. Песок насыпается строго по центру ведра, установленного вертикально, и образует кучу. Как только верхушка кучи достигает верхнего среза ведра, процесс останавливается. Определите объем песка, насыпанного в ведро, если известно, что угол при основании кучи песка, насыпанной на плоскую поверхность, составляет 34 градуса.
В единственной строке содержатся два целых числа $$$ h $$$ ($$$ 1 \leq h \leq 1000 $$$) и $$$ d $$$ ($$$ 1 \leq d \leq h $$$), разделенные пробелом.
Выведите единственное число – объем песка, насыпанного в ведро, указанный с точностью до $$$ 10^{-6} $$$.
10 10
146.39985672107267
5 1
1.1487958374076184
Картинка:
Сегодня Игорь и Ира вместе с друзьями — Сашей и Лешей — играют в новую настольную игру «Brass Birmingham».
В каждом раунде игроки по очереди делают ходы. Во время хода игрок может построить производство в городах или дорогу, которая соединяет два города, либо выполнить действие. За все свои постройки игроки платят деньги, ведь в этой игре, как и в реальном мире, всё стоит денег. В конце своего хода игрок выстраивает башенку из потраченных монет и кладет её рядом со своей фигуркой в поле оплаты, а в конце раунда потраченные монеты возвращаются в банк.
Игорь хочет как можно быстрее начать следующий раунд, поэтому решил оптимизировать процесс возвращения денег в банк. Так, за одну операцию он собирает монеты одного номинала со всех верхушек башенок. Сколько раз Игорю придется повторить эту операцию, чтобы начать новый раунд как можно быстрее?
В первой строке содержится целое число $$$n$$$ $$$(1\leq n\leq 30)$$$ — количество различных номиналов монет.
Во второй строке содержатся четыре целых числа $$$m_i$$$ $$$(1\leq m_i\leq 30, 1\leq i\leq 4)$$$ — количество монет в башенке $$$i$$$-го игрока.
В последующих четырёх строках содержится описание башенок каждого игрока. В $$$i$$$-й из них записано $$$m_i$$$ целых чисел $$$k_{ij}$$$ $$$(1\leq k_{ij}\leq n,\; 1\leq i\leq 4,\; 1\leq j\leq m_i)$$$ — номинал монеты с номером $$$j$$$. Монеты нумеруются снизу вверх.
В единственной строке выведите число — минимальное количество операций, необходимое Игорю, чтобы вернуть все монетки в банк.
5 2 2 2 2 1 1 1 2 1 3 1 4
4
5 3 2 3 2 1 1 1 3 2 2 2 3 4 5
6
Сегодня Игорь и Ира вместе с их друзьями - Сашей и Лешей, решили поиграть в новую настольную игру «Brass Birmingham».
В каждом раунде игроки делают ходы по очереди. Во время хода игрок может построить производство в городах или дорогу, которая соединяет два города, либо выполнить действие.
Для того, чтобы выполнить действие или что-нибудь построить у каждого игрока есть на руках по $$$K$$$ карт. Карты бывают двух типов: карты городов с названием определенного города, позволяющие построить любое предприятие в данном городе, и карты предприятий, позволяющие построить данное предприятие в любом городе, до которого есть дорога игрока.
Игорь придерживается своей стратегии и хочет поставить стальной завод в городе Бирмингем, в котором можно построить только один завод. По его мнению, если поставить именно стальной завод в этом городе, то он гарантированно победит в игре.
По правилам игры все игроки ходят по очереди, в этот раз Игорь будет ходить последним. В данном раунде все игроки могут построить либо одно здание, либо дорогу (действия делать они не хотят).
По правилам игрок может построить здание в городе:
1) Если у игрока есть карточка соответствующего города, тогда он ее играет и сбрасывает с руки.
2) Если у игрока есть карточка с соответствующим предприятием и есть либо здание в этом городе, либо дорога данного игрока, ведущая в этот город. Данная карта также играется и сбрасывается.
Игорь понимает, что остальные игроки обязательно построят стальной завод в Бирмингеме, чтобы ему помешать, если у них будет такая возможность.
Весь ход игры Игорь записывает в свой блокнотик, поэтому он знает, какие карточки уже вышли из игры, так же он знает, сколько изначально было карточек для каждого города и для каждого предприятия.
С какой вероятностью Игорь сможет поставить стальной завод в городе Бирмингем?
В первой строке введено три целых числа $$$N$$$, $$$K$$$ и $$$M$$$ $$$(2\leq N \leq 10^3,1\leq K, M \leq 10^3)$$$ — количество городов в игре, количество карточек в руке у каждого игрока и количество карточек, которое осталось в колоде.
Во второй строке записано четыре целых числа $$$C$$$, $$$R$$$, $$$G$$$, $$$H$$$ $$$(0\leq C + R\leq 4K+M,$$$ $$$ 0\leq G\leq C,$$$ $$$0\leq H\leq R)$$$ — количество оставшихся в игре карточек с городом Бирмингем, количество оставшихся в игре карточек с производством стальной завод, количество карточек с городом Бирмингем в руке Игоря, количество карточек с производством стальной завод в руке Игоря.
В третьей строке записано 4 целых числа $$$a_i$$$ $$$(0\leq a_i\leq 1,1\leq i\leq 4)$$$, $$$a_i=0$$$ означает, что у игрока $$$i$$$ нет дороги к Бирмингему и зданий в этом городе, иначе $$$a_i = 1$$$. Сам Игорь считает себя игроком под номером 1.
Выведите одно вещественное число с точностью до 4 знаков после запятой — вероятность того, что Игорь сможет построить стальной завод в городе Бирмингем.
5 4 12 3 3 2 2 1 0 0 0
0.50000000
5 4 12 2 2 2 1 0 1 1 1
0.50000000
9 1 20 4 2 0 1 1 1 0 0
0.51835121
3 1 6 1 1 1 0 0 0 1 1
0.77777778
Сегодня Игорь и Ира вместе с друзьями — Сашей и Лешей — решили поиграть в новую настольную игру «Brass Birmingham».
В каждом раунде игроки делают ходы по очереди. Во время хода игрок может построить производство в городах, дорогу, соединяющую два города, либо выполнить действие.
В свой ход Игорь хочет открыть как можно больше своих заводов. Для того, чтобы открыть один завод, игроку требуется перенести к заводу ровно один бочонок «пива», ведь без бочонка «пива» не получится торжественно открыть предприятие. Таким образом, чем больше бочонков «пива» Игорь подвезёт, тем больше заводов он сможет открыть.
Бочонки «пива» располагаются на пивоварнях, ранее построенных игроками. На каждой пивоварне располагается ровно один бочонок «пива».
Для открытия заводов Игорь хочет использовать свои бочонки «пива», которые он заготовил ранее. Если их окажется недостаточно, то Игорю придется использовать бочонки «пива» других игроков.
Правила игры гласят, что бочонки «пива» со своих пивоварен можно использовать без ограничений. Если же игрок хочет перенести бочонок «пива» с чужой пивоварни для построения своего завода, то данное действие можно сделать, только если завод и пивоварня находятся в одном городе, либо между пивоварней и заводом существует путь по дорогам.
Какое количество своих и чужих бочонков «пива» использует Игорь?
В первой строке записано целое число $$$N$$$ $$$(2\leq N\leq 10^5)$$$ — количество городов в игре.
Во второй строке записано целое число $$$M$$$ $$$(1\leq M\leq 10^5)$$$ — количество заводов, которые хочет открыть Игорь.
В третьей строке записано $$$M$$$ целых чисел $$$m_i$$$ $$$(1\leq m_i\leq N)$$$ — города, в которых Игорь хочет открыть заводы. В одном городе может быть несколько заводов.
В четвертой строке записано целое число $$$K$$$ $$$(1\leq K\leq 10^5)$$$ — количество пивоварен Игоря.
В пятой строке записано $$$K$$$ целых чисел $$$k_i$$$ $$$(1\leq k_i\leq N)$$$ — города, в которых располагаются пивоварни Игоря. В одном городе может быть несколько пивоварен Игоря.
В шестой строке записано целое число $$$L$$$ $$$(1\leq L\leq 10^5)$$$ — количество пивоварен других игроков.
В седьмой строке записано $$$L$$$ целых чисел $$$l_i$$$ $$$(1\leq l_i\leq N)$$$ — города, в которых располагаются пивоварни других игроков. В одном городе может быть несколько пивоварен других игроков.
В восьмой строке записано целое число $$$G$$$ $$$(1\leq G\leq 10^5)$$$ — количество уже построенных дорог.
В следующих $$$G$$$ строках записаны пары целых чисел $$$a_i, b_i$$$ $$$(1\leq a_i,b_i\leq N)$$$ — города, которые соединяются дорогой с номером $$$i$$$.
В единственной строке выведите два целых числа, разделенных пробелом: количество своих и количество чужих бочонков «пива», которое потребуются Игорю.
8 4 1 4 3 2 2 2 8 4 8 7 6 5 4 1 2 2 3 4 3 4 5
2 1
6 5 2 3 5 2 5 2 1 2 8 2 2 1 6 4 1 2 3 9 4 3 5 2 4 6 1 2 5 6 6 5 1 2 3 4 6 1
2 3
Сегодня Игорь и Ира вместе с друзьями — Сашей и Лешей — решили поиграть в новую настольную игру «Brass Birmingham».
В каждом раунде игроки делают ходы по очереди. Во время хода игрок может построить производство в городах, дорогу, соединяющую два города, либо выполнить действие.
Игра закончилась поздней ночью, и пришло время подводить итоги. Игорю доверили посчитать количество очков за построение дорог. Каждая построенная игроком дорога приносит ему количество очков, равное суммарному числу предприятий, открытых в городах, соединяемых этой дорогой.
К сожалению, Игорь случайно опрокинул игровое поле так, что все карточки перемешались. Огорчившись, он вспомнил, что во время игры записывал в блокнот действия каждого игрока. Помогите Игорю посчитать очки за дороги, полученные каждым игроком.
В первой строке записано целое число $$$N$$$ $$$(2\leq N\leq 10^5)$$$ — количество городов в игре.
Далее для каждого из четырех игроков указано:
В первой строке целые числа $$$M_k,G_k$$$ $$$(1\leq M_k,G_k\leq 10^4)$$$ — количество производств и количество дорог, построенных $$$k$$$-м игроком.
В следующей строке $$$M_k$$$ целых чисел $$$m_{ki}$$$ $$$(1\leq m_{ki}\leq N)$$$ — города, в которых располагаются производства $$$k$$$-го игрока.
Далее $$$G_k$$$ строк, в каждой из которых располагаются по два целых числа $$$a_{ki},b_{ki}$$$ $$$(1\leq a_{ki},b_{ki}\leq N)$$$ — города, которые соединяются дорогой $$$k$$$-го игрока.
Выведите $$$4$$$ целых числа через пробел – количеств очков за дороги, которые получил каждый из игроков.
4 1 1 1 1 2 3 1 1 2 3 2 3 4 2 1 4 2 3 3 1 4 2 1 4 3 1 3 2 3 3 4 1 2
5 5 9 20
В 1932 году Лотар Коллатц (Lotar Collatz) сформулировал простую, на первый взгляд, задачу, которая не решена до сих пор.
Пусть у нас есть некоторое число $$$ n $$$, тогда, если оно четное, то разделим его на $$$2$$$, а если нечетное – умножим на $$$3$$$ и добавим единицу. Назовем такое преобразование шагом Коллатца. Гипотеза, не доказанная до сих пор, утверждает, что после определенного числа шагов любое целое число превращается в единицу. Для всех чисел до $$$ 10^{22} $$$ проверено, что это так.
Обозначим за $$$ t(n) $$$ количество шагов, необходимых для того, чтобы число $$$ n $$$ превратилось в единицу, и запишем последовательные значения $$$ t(1), t(2), t(3), \dots $$$:
$$$ 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, \dots $$$
Анализируя получившуюся последовательность, можно обнаружить, что в ней очень часто встречаются пары одинаковых значений, то есть такие, что $$$ t(i) = t(i + 1) $$$. По некоторым оценкам, до половины элементов последовательности образуют такие пары. Существуют и более длинные отрезки повторяющихся значений, например, первая тройка встречается уже на $$$28$$$-м месте $$$ t(28) = t(29) = t(30) = 18 $$$.
Напишите программу, которая на интервале длиной $$$ w $$$, начинающемся с элемента $$$ s $$$, найдет самый длинный отрезок из одинаковых значений $$$ t() $$$. Если таких отрезков несколько, то нужно найти самый левый из них (с минимальным первым элементом). Элементы, попадающие за пределы интервала $$$ [s, s + w - 1] $$$, не учитывать.
В единственной строке содержатся два целых числа $$$ s $$$ ($$$ 1 \leq s \leq 10^{10} $$$) и $$$ w $$$ ($$$ 1 \leq w \leq 10^6 $$$), разделенные пробелом.
В единственной строке выведите два целых числа, разделенных пробелом: $$$ l $$$ – длина отрезка, $$$ x $$$ – его начало. Отрезок $$$ [x, x + l - 1] $$$ должен полностью принадлежать интервалу $$$ [s, s + w - 1] $$$.
1 50
3 28
На отрезке из $$$50$$$ чисел, начинающемся с $$$1$$$, есть 6 пар: $$$ t(12) = t(13) $$$, $$$ t(14) = t(15) $$$, $$$ t(18) = t(19) $$$, $$$ t(20) = t(21) $$$, $$$ t(22) = t(23) $$$, $$$ t(34) = t(35) $$$ и $$$3$$$ тройки: $$$ t(28) = t(29) = t(30) $$$, $$$ t(36) = t(37) = t(38) $$$, $$$ t(44) = t(45) = t(46) $$$. Из тройки $$$ t(49) = t(50) = t(51) $$$ в интервал попадают только $$$2$$$ значения, образуя «виртуальную» пару $$$ t(49) = t(50) $$$.
Самой левой из троек является тройка, начинающаяся с $$$ 28 $$$.
Профессор Ш. с недавних пор увлёкся теорией чисел. В частности, его очень заинтересовало разложение числа на простые множители. Напомним, что натуральное число называют простым, если оно имеет ровно два различных натуральных делителя: единицу и само число. Профессор Ш. называет число N интересным, если оно представимо в виде произведения ровно шести попарно различных простых чисел. К сожалению, слишком большие числа профессор не умеет проверять на интересность.
Помогите Профессору – напишите программу, которая по заданному числу N будет выяснять, является ли оно интересным.
В единственной строке содержится целое число N (2 ≤ N ≤ 1018).
В единственной строке выведите « - 1», если число интересным не является, или 6 простых чисел в порядке возрастания – делители числа N.
2
-1
3
-1
6
-1
Игорь хочет заняться самоорганизацией, поэтому он решил составить огромный список дел и план, которого он будет придерживаться $$$k$$$ дней.
В списке оказалось $$$n$$$ дел. Занятие с номером $$$i$$$ из этого списка Игорь посчитал необходимым повторять через $$$a_i$$$ дней, чтобы выработалась привычка. Определившись со списком и периодичностью повторения дел, Игорь незамедлительно выполнил все дела из списка, чтобы в дальнейшем их только повторять. Поэтому он очень устал и совсем забыл составить план на следующие $$$k$$$ дней.
Помогите Игорю составить план, указав для каждого из последующих дней количество дел, которое Игорю необходимо будет выполнить.
В первой строке записаны два целых числа $$$n$$$, $$$k$$$ $$$(1\leq n,k\leq 10^5)$$$ — количество дел в списке Игоря и количество дней, в течение которых Игорь хочет придерживаться плана.
Во второй строке записаны $$$n$$$ целых чисел $$$a_i$$$ $$$(0\leq a_i\leq 10^5,1\leq i\leq n)$$$ — количество дней, через которое необходимо повторить $$$i$$$-е дело.
В единственной строке выведите $$$k$$$ чисел $$$m_j$$$, разделенных пробелом. $$$m_j$$$ — количество дел, запланированных Игорем на $$$j$$$-й $$$(1\leq j\leq k)$$$ день.
2 10 1 2
0 1 1 1 0 2 0 1 1 1
2 6 0 1
1 2 1 2 1 2
3 15 1 2 3
0 1 1 2 0 2 0 2 1 1 0 3 0 1 1
Работая с перестановками чисел от $$$ 1 $$$ до $$$ n $$$, программист Вася заметил, что некоторые из них обладают интересными свойствами. Например, в перестановках «3 1 2» и «3 2 1» первый элемент равен сумме всех других элементов. В перестановке «1 2 3 4 5» уже конкатенация (приписывание одного числа к другому) двух первых элементов равна сумме оставшихся ($$$ 12 = 3 + 4 + 5 $$$).
Вася задался вопросом: а для любого ли $$$ n $$$ можно найти такую перестановку чисел $$$ 1..n $$$, что первый элемент, либо конкатенация двух первых, будет равна сумме оставшихся?
Напишите программу, которая по данному числу $$$ n $$$ определит, какие элементы нужно поставить в начало перестановки, чтобы либо первый элемент, либо конкатенация двух первых, дали сумму всех оставшихся. Если таких элементов нет, то программа должна сообщить об отсутствии решения.
В единственной строке содержится число $$$ n $$$ ($$$ 1 \leq n \leq 10^{9} $$$) – количество элементов в перестановке.
В единственной строке выведите $$$ 0 $$$, если решения не существует. Если существует один элемент, который равен сумме оставшихся, то выведите через пробел два числа: «1» и найденный элемент. Если существуют два элемента, конкатенация которых дает число, равное сумме оставшихся элементов, то выведите «2», а затем два числа разделённые пробелом – два элемента в том порядке, в котором их нужно приписывать друг к другу.
3
1 3
5
2 1 2
2
0
На карамбольном столе (биллиардный стол без луз) длиной $$$ l $$$ и шириной $$$ w $$$ расположены два биллиардных шара. Шары расположены в точках $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, где $$$ 1 \leq x_i \lt l, 1 \leq y_i \lt w $$$, а оси координат идут вдоль бортов стола (ось абсцисс – вдоль «длинного» борта, ось ординат – вдоль «широкого»). Необходимо попасть первым шаром во второй, сделав ровно три борта.
Для простоты будем считать, что шары – это точки, а угол отражения шара не зависит от силы удара и равен углу попадания в борт. При попадании шара точно в угол он отражается строго в обратном направлении, и считается, что он попал в оба борта, образующих угол. Попаданием считается точное совпадение координат точек.
Напишите программу, которая рассчитает удар первым шаром, который, отразившись от борта три раза, попадет во второй, и преодолев при этом минимальное расстояние.
В первой строке записаны два целых числа $$$ l $$$ и $$$ w $$$ ($$$ 2 \leq l, w \leq 1000 $$$), разделенные пробелом.
Вторая строка содержит четыре целых числа: $$$ x_1, y_1, x_2, y_2 $$$, разделенные пробелами – позиции первого и второго шара соответственно ($$$ 1 \leq x_i \lt l, 1 \leq y_i \lt w $$$).
Выведите единственное число с точностью $$$ 10^{-6} $$$ – длину траектории оптимального удара.
16 3 1 1 7 1
10.00000000
Оптимальная траектория удара для данных из примера:
(1, 1) $$$\rightarrow$$$ (0, $$$\frac{1}{4}$$$) $$$\rightarrow$$$ ($$$\frac{1}{3}$$$, 0) $$$\rightarrow$$$ ($$$4\frac{1}{3}$$$, 3) $$$\rightarrow$$$ (7, 1)
Картинка:
Помимо теории чисел и строковых алгоритмов Профессор Ш. любит заниматься массивами, но не простыми, а отсортированными по неубыванию элементов. Сегодня Профессор Ш. придумал отличную задачу и делится её формулировкой с вами.
Изначально имеется массив $$$a$$$, состоящий из $$$N$$$ чисел, элементы которого расположены в порядке неубывания. К данному массиву можно применять запросы $$$2$$$ типов:
- Сдвинуть массив циклически влево или вправо на $$$k$$$ позиций.
- Проверить, есть ли в массиве число $$$x$$$. Если такое число есть, вывести его номер в массиве (возможно, измененном). Если число входит в массив несколько раз, следует вывести номер его первого вхождения в массив.
Так как Профессор Ш. умеет работать только с отсортированными массивами, он не всегда умеет проверять, есть ли в массиве число $$$x$$$. Помогите Профессору – напишите программу, которая будет верно отвечать на запросы обоих типов.
В первой строке содержится число $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – количество элементов массива.
Во второй строке содержатся $$$N$$$ чисел $$$a_i$$$ $$$(-10^{18} \le a_i \le 10^{18})$$$ – элементы массива $$$a$$$. Гарантируется, что изначально элементы массива отсортированы по неубыванию.
В третьей строке содержится число $$$Q$$$ $$$(1 \le Q \le 3 \cdot 10^5)$$$ – количество запросов.
В следующих $$$Q$$$ строках содержатся запросы. Запросы задаются следующим образом:
- $$$s~k$$$ $$$(1 \le |k| \lt N)$$$ – сдвинуть массив циклически на $$$k$$$ позиций. Если число $$$k$$$ отрицательное, то сдвиг осуществляется влево, в противном случае сдвиг должен быть осуществлён вправо.
- $$$?~x$$$ – проверить, есть ли в массиве число $$$x$$$.
Для каждого запроса вида «$$$?~x$$$» выведите в отдельной строке число – номер числа $$$x$$$ в массиве. Если числа $$$x$$$ в масиве нет, в отдельной строке выведите «$$$-1$$$». Считается, что элементы массива нумеруются с $$$1$$$.
7 1 2 3 4 5 6 7 7 ? 9 s 2 ? 4 s -2 ? 3 s -5 ? 6
-1 6 3 1
7 1 1 2 2 3 3 4 7 ? 9 s 2 ? 4 s -1 ? 2 s -5 ? 1
-1 2 4 4
Рассмотрим первый пример.
Изначально массив $$$a = [1, 2, 3, 4, 5, 6, 7]$$$.
- Так как число $$$9$$$ больше любого элемента массива $$$a$$$, выведем $$$-1$$$.
- После запроса $$$s~2$$$ нужно сдвинуть массив вправо на $$$2$$$ позиции, он станет равен $$$[6, 7, 1, 2, 3, 4, 5]$$$.
- Число $$$4$$$ находится на позиции $$$6$$$, поэтому выводим $$$6$$$.
- После запроса $$$s~-2$$$ массив примет исходный вид $$$[1, 2, 3, 4, 5, 6, 7]$$$
- Число $$$3$$$ находится на позиции $$$3$$$, поэтому выводим $$$3$$$
- После запроса $$$s~-5$$$ массив сдвигается на $$$5$$$ позиций влево: $$$[6, 7, 1, 2, 3, 4, 5]$$$
- Число $$$6$$$ находится на позиции $$$1$$$, поэтому выводим $$$1$$$.
Профессор Ш. – достаточно пожилой человек, у него есть внук по имени Влад, который учится в Головодском государственном университете. Чтобы учёба сильно не утомляла, порой не мешает и отдохнуть от неё. Влад не тратит время на глупые компьютерные игры, проводя всё своё свободное время за игрой «Морской бой» против своего дедушки. Суть игры такова: есть поле размером $$$10 \times 10$$$, на котором расставлены $$$10$$$ кораблей: $$$4$$$ однопалубника, $$$3$$$ двухпалубника, $$$2$$$ трёхпалубника и $$$1$$$ четырёхпалубник, корабли на поле можно располагать только горизонтально или вертикально. Влад — виртуоз этой игры, поэтому никогда не проигрывает, и нас лишь интересуют события, происходящие на поле Професссора Ш. Во время игры Влад может запросить следующие команды:
- команда «SHOT $$$X~Y$$$» - выстрелить в клетку с координатами $$$(X, Y)$$$ $$$(1 \le X \le 10, 1 \le Y \le 10)$$$.
- команда «SHOW» - вывести количество целых, подбитых и потопленных кораблей на поле Профессора Ш.
Ваша задача заключается в следующем: по логу команд, проведённых Владом, восстановить картину боя.
В первых $$$10$$$ строках ввода содержатся по $$$10$$$ символов, описывающих игровое поле противника до начала игры: если $$$j$$$-й символ $$$i$$$-й строки равен «#», это означает, что клетка с координатами $$$(i, j)$$$ содержит фрагмент корабля, символ «*» означает, что в данной клетке находится «море».
В $$$11$$$-й строке ввода содержится число $$$q$$$ ($$$1 \le q \le 100$$$) – количество команд, которые запросил Влад. Гарантируется, что корабли расставлены на поле корректно, то есть не пересекаются друг с другом.
В следующих $$$q$$$ строках содержатся команды $$$2$$$ типов, которые запросил Влад.
Для каждого запроса «SHOW» в отдельной строке вывести $$$3$$$ числа в следующем порядке: количество целых, подбитых и потопленных кораблей на поле Профессора Ш.
*******#** *####****# *********# ****#*#*** ******#*** *##******* ********#* *#******#* *****#**#* ###******* 5 SHOW SHOT 1 8 SHOW SHOT 9 9 SHOW
10 0 0 9 0 1 8 1 1