Вам дано $$$N$$$ натуральных чисел $$$a_1, a_2, \ldots, a_N$$$.
Определим функцию $$$f$$$ как $$$f(m)=(m \bmod a_1 ) + (m \bmod a_2 )+ \ldots +(m \bmod a_N)$$$, где $$$m$$$ — неотрицательное целое число.
Найдите максимальное значение функции $$$f(m)$$$ на всех возможных значениях аргумента $$$m$$$.
В первой строке дается целое число $$$N$$$ ($$$2 \leq N \leq 3000$$$) — количество чисел.
Вторая строка содержит $$$N$$$ целых чисел $$$a_i$$$ ($$$2 \leq a_i \leq 10^5$$$).
Выведите одно целое число — максимальное значение функции $$$f(m)$$$ на всех возможных значениях аргумента $$$m$$$.
3 3 4 6
10
В тестовом примере даны $$$3$$$ числа $$$a = [3, 4, 6]$$$. Рассмотрим несколько значений функции $$$f$$$:
- $$$f(1)=(1 \bmod 3)+(1 \bmod 4)+(1 \bmod 6) = 3$$$;
- $$$f(6)=(6 \bmod 3)+(6 \bmod 4)+(6 \bmod 6) = 2$$$;
- $$$f(11)=(11 \bmod 3)+(11 \bmod 4)+(11 \bmod 6) = 10$$$;
- $$$f(19)=(19 \bmod 3)+(19 \bmod 4)+(19 \bmod 6) = 5$$$.
Можно показать, что значение $$$10$$$ является наибольшим возможным для функции $$$f$$$ при заданных числах $$$a$$$.
В городе появились преступники, планирующие ограбить часть домов.
Всего в городе $$$N \times M$$$ домов, расположенных в виде прямоугольной сетки. Каждый дом задаётся двумя целочисленными координатами $$$(i, j)$$$ $$$(1 \le i \le N, 1 \le j \le M)$$$, где $$$(1, 1)$$$ — координаты левого верхнего дома, а $$$(N, M)$$$ — правого нижнего.
В доме с координатами $$$(i,j)$$$ хранятся ценности стоимостью $$$C_{i,j}$$$. Если преступники грабят дом, то они выносят все имеющиеся в нём ценности.
Чтобы не быть пойманными, преступники решили выбрать для грабежа такой набор домов, что никакие два дома из выбранных не будут соседними.
Два дома с координатами $$$(i_1, j_1)$$$ и $$$(i_2, j_2)$$$ являются соседними, если $$$|i_1 - i_2| + |j_1 - j_2| = 1$$$, где $$$|x|$$$ — абсолютное значение числа $$$x$$$.
Найдите максимально возможную суммарную стоимость ценностей, которыми могут овладеть преступники, если выберут оптимальный набор домов для грабежа.
В первой строке расположены два целых числа $$$N$$$ и $$$M$$$ $$$(2 \leq N \times M \leq 100)$$$ — размеры города.
В следующих $$$N$$$ строках находятся по $$$M$$$ целых чисел $$$C_{i,j}$$$ $$$(1 \le C_{i,j} \le 10^6; 1 \le i \le N, 1 \le j \le M)$$$ — стоимости ценностей в домах с соответствующими координатами.
В единственной строке выведите одно целое число — максимально возможную суммарную стоимость ценностей, которыми могут овладеть преступники, если выберут оптимальный набор домов для грабежа.
4 3 5 4 5 3 5 9 1 2 4 8 9 10
36
3 3 10 1 1 1 1 1 1 10 1
21
Первый тестовый пример
Преступникам оптимально выбрать следующие дома:
- $$$(1, 2)$$$ — стоимость $$$4$$$;
- $$$(2, 1)$$$ — стоимость $$$3$$$;
- $$$(2, 3)$$$ — стоимость $$$2$$$;
- $$$(3, 2)$$$ — стоимость $$$9$$$;
- $$$(4, 1)$$$ — стоимость $$$8$$$;
- $$$(4, 3)$$$ — стоимость $$$10$$$.
Общая суммарная стоимость ценностей в данных домах равна $$$4 + 3 + 2 + 9 + 8 + 10 = \textbf{36}$$$.
Обратите внимание, что преступники не могут взять вместе следующие пары домов:
- $$$(1, 3)$$$ и $$$(2, 3)$$$ — они являются соседними по координате $$$i$$$: $$$|1 - 2| + |3 - 3| = 1$$$;
- $$$(4, 2)$$$ и $$$(4, 3)$$$ — они являются соседними по координате $$$j$$$: $$$|4 - 4| + |2 - 3| = 1$$$.
Второй тестовый пример
Один из оптимальных вариантов выбора домов:
- $$$(1, 1)$$$ — стоимость $$$10$$$;
- $$$(1, 3)$$$ — стоимость $$$1$$$;
- $$$(3, 2)$$$ — стоимость $$$10$$$.
Общая суммарная стоимость ценностей в данных домах равна $$$10 + 1 + 10 = \textbf{21}$$$.
Обратите внимание, что вместо дома $$$(1, 3)$$$ преступники могут ограбить дом $$$(2, 3)$$$ — суммарная стоимость награбленного в таком случае не изменится.
Это интерактивная задача — ваша программа будет обмениваться данными с программой жюри через стандартный ввод и вывод (консоль).
Айбек агай спрятал ладью на шахматной доске $$$8 \times 8$$$. Вы очень хотите узнать её координаты.
Столбцы на шахматной доске обозначаются латинской заглавной буквой от $$$A$$$ до $$$H$$$, а строки — целым числом от $$$1$$$ до $$$8$$$. Например, клетка $$$D7$$$ расположена в $$$4$$$-м столбце и $$$7$$$-й строке.
Чтобы найти координаты ладьи, вы можете задавать Айбек агаю не более 4 раз следующий вопрос:
«Рассмотрим прямоугольник, образованный столбцами от $$$X_1$$$ до $$$X_2$$$ и строками от $$$Y_1$$$ до $$$Y_2$$$. Сколько клеток в данном прямоугольнике бьётся спрятанной ладьёй?»
Если ладья стоит в клетке $$$(X_R, Y_R)$$$, то клетка $$$(X, Y)$$$ бьётся ладьёй при выполнении хотя бы одного из условий:
- $$$X = X_R$$$
- $$$Y = Y_R$$$
В частности, это означает, что ладья бьёт клетку $$$(X_R, Y_R)$$$, на которой она расположена.
Обратите внимание, что
- Любое ваше сообщение должно завершаться переводом строки.
- После вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри:
- C++: cout « endl (перевод строки + очистка буфера), cout.flush() или fflush(stdout);
- Java: System.out.println() (перевод строки + очистка буфера), System.out.flush();
- Python: print() (перевод строки + очистка буфера), stdout.flush().
- Pascal: flush(output).
- При решении на С++ не отключайте синхронизацию cin/cout.
Все координаты столбцов должны выводиться только заглавными буквами.
Вопрос задаётся в формате $$$\textbf{?}$$$ $$$X_1Y_1$$$ $$$X_2Y_2$$$ ($$$A \le X_1 \le X_2 \le H$$$, $$$1 \le Y_1 \le Y_2 \le 8$$$) — вопросительный знак, координаты левого нижнего и правого верхнего углов прямоугольника из вопроса.
Всего вы можете задать вопрос не более 4 раз.
В ответ на вопрос программа жюри выводит целое число $$$K$$$ ($$$-1 \le K \le 8 \times 8$$$):
- При получении ответа $$$K = -1$$$ ваша программа должна немедленно завершиться. Данная ситуация означает вердикт Presentation error (некорректный формат запроса) или Wrong answer (превышено количество запросов).
- Иначе $$$K$$$ равно количеству клеток в прямоугольнике со столбцами от $$$X_1$$$ до $$$X_2$$$ и строками от $$$Y_1$$$ до $$$Y_2$$$, находящихся под боем спрятанной ладьи.
Окончательный ответ выводится в формате $$$\textbf{!}$$$ $$$X_RY_R$$$ ($$$A \le X_R \le H$$$, $$$1 \le Y_R \le 8$$$) — восклицательный знак и предполагаемые координаты ладьи.
После вывода окончательного ответа ваша программа обязательно должна завершиться.
5 4 0 1
? B5 F6 ? F1 G4 ? F7 F8 ? G5 G5 ! G5
В тестовом примере ладья стоит на клетке $$$G5$$$.
- Задаётся вопрос о прямоугольнике со столбцами от $$$B$$$ до $$$F$$$ и строками от $$$5$$$ до $$$6$$$.
Так как ладья находится в строке $$$5$$$, то она бьёт клетки $$$B5$$$, $$$C5$$$, $$$D5$$$, $$$E5$$$, $$$F5$$$ — всего 5 клеток.
- Задаётся вопрос о прямоугольнике со столбцами от $$$F$$$ до $$$G$$$ и строками от $$$1$$$ до $$$4$$$.
Так как ладья находится в столбце $$$G$$$, то она бьёт клетки $$$G1$$$, $$$G2$$$, $$$G3$$$, $$$G4$$$ — всего 4 клетки.
- Задаётся вопрос о прямоугольнике с единственным столбцом $$$F$$$ и строками от $$$7$$$ до $$$8$$$.
Ладья не бьёт ни одной клетки в данном прямоугольнике — поэтому ответ 0.
- Задаётся вопрос о прямоугольнике с единственным столбцом $$$G$$$ и единственной строкой $$$5$$$ — прямоугольник состоит из одной клетки.
Ладья стоит именно на этой клетке, поэтому она её бьет — ответ 1.
- Выводится ответ с координатами ладьи.
Вчера вечером случилось нечто неслыханное: уезжая со стоянки, кто-то из сотрудников поцарапал автомобиль Самого Главного Начальника!
Кто это был, пока неизвестно, но Самый Главный Начальник успел заметить, что кто-то из сотрудников был на перекуре ровно в момент проишествия.
Самый Главный Начальник в бешенстве! Он велит найти нарушителя, прямо здесь и сейчас. Вы, как начальник охраны, смогли немного успокоить Начальника и выбить немного времени.
Если точнее, то Самый Главный Начальник «в честь предстоящего $$$2023$$$ года» дал вам 23 дня на поиски.
Теперь ваша цель — найти того самого свидетеля-«перекурщика» и узнать у него личность нарушителя. Для этого вы планируете каждый день вызывать часть сотрудников компании на допрос.
Правда, есть два важных ограничения:
- Свидетель не сознается, если вместе с ним в один и тот же день вызовут нарушителя (не хочет портить отношения с коллегой);
- За один день вы можете допросить не более 70% работников компании (иначе производственные процессы совсем встанут).
Чтобы приступить к поискам, вам необходимо заранее подать в отдел кадров расписания всех допросов на все дни.
Для удобства всем сотрудникам присвоены уникальные номера от $$$1$$$ до $$$N$$$.
Помните, что из-за ограничения 1 вам необходимо запланировать все допросы таким образом, чтобы для каждой пары сотрудников ($$$i \ne j$$$) существовал хотя бы один допрос, что сотрудник $$$i$$$ присутствовал на допросе, а сотрудник $$$j$$$ — нет.
В единственной строке записано одно целое число $$$N$$$ ($$$2 \le N \le 2500$$$) — количество сотрудников, среди которых есть свидетель и нарушитель.
В первой строке выведите целое число $$$D$$$ ($$$1 \le D \le 23$$$) — количество дней, в течение которых вы будете проводить допросы.
Каждая из следующих $$$D$$$ строк описывает один допрос в формате $$$k$$$ $$$w_1$$$ $$$w_2$$$ $$$\dots$$$ $$$w_k$$$ ($$$1 \le k \le 0.7 \times N$$$; $$$1 \le w_i \le N$$$; $$$w_i \ne w_j$$$) — количество приглашенных на допрос сотрудников и уникальные номера этих сотрудников.
Ответ будет считаться корректным, если для каждой пары сотрудников ($$$i \ne j$$$) существует хотя бы один допрос, что сотрудник $$$i$$$ присутствует на этом допросе, а сотрудник $$$j$$$ — нет.
Если существует несколько корректных вариантов распределения сотрудников по допросам, то выведите любой.
4
4 1 1 1 2 1 3 1 4
3
3 2 2 3 2 1 3 2 1 2
6
9 3 1 2 3 3 4 5 6 2 1 2 2 3 1 2 3 2 2 4 5 2 6 4 2 5 6 2 1 3
Первый тестовый пример
Так как сотрудников для допроса всего $$$4$$$, то можно каждый день опрашивать ровно одного из них.
Это удовлетворяет обоим условиям:
- Так как каждый день опрашивается только один сотрудник, то свидетель и нарушитель никогда не окажутся на одном допросе.
- Каждый день вы вызываете только $$$1$$$ человека, что не превышает $$$0.7 \times 4 = 2.8$$$.
Второй тестовый пример
Во втором тестовом примере каждый день опрашивается по два сотрудника.
- Для каждой пары ($$$i \ne j$$$) существует день, когда $$$i$$$ присутствует, а $$$j$$$ — нет.
Например, если свидетель — $$$1$$$, а нарушитель — $$$3$$$, то во второй день свидетель не расскажет ничего, а в третий день — сообщит вам необходимую информацию.
- Каждый день вы вызываете $$$2$$$ сотрудника, что не превышает $$$0.7 \times 3 = 2.1$$$.
Айбек всегда знал, что «там» кто-то есть. И он даже знал, что «они» уже вступали в контакт с человечеством, причем не один раз. Ну точнее не знал, но был уверен в этом каждой частичкой своего разума — всё указывало на это.
Например, недавно Айбек наткнулся на фотографии поля, испещерённого полосами примятой травы в виде ломаной линии. «Это точно сообщение от них!» — подумал Айбек. Осталось лишь это сообщение расшифровать.
Айбек знает, что «они» общаются посредством треугольников (и никак иначе). Поэтому первым делом Айбеку нужно вычислить, сколько суммарно треугольников нарисовано на поле.
Так как вы — самый компетентный агроном из всех знакомых Айбека, он настоятельно просит вас вычислить суммарное количество различных невырожденных треугольников, образованных ломаной линией примятой травы на поле.
Ломаная линия — это набор точек $$$P_1$$$, $$$P_2$$$, $$$\dots$$$, $$$P_N$$$ и отрезков, проведенных между парами соседних точек $$$P_i$$$ и $$$P_{i + 1}$$$ $$$(1 \le i \lt N)$$$.
Треугольником в рамках данной задачи считается фигура, образованная тремя попарно пересекающимися непрерывными отрезками — сторонами треугольника.
 |  |
- На левом рисунке нет треугольников — ломаная $$$(1, 1)$$$, $$$(1, 6)$$$, $$$(1, 11)$$$, $$$(6, 6)$$$, $$$(1, 1$$$);
- На правом рисунке один треугольник — ломаная $$$(1, 1)$$$, $$$(1, 11)$$$, $$$(6, 6)$$$, $$$(1, 1$$$).
Невырожденным является треугольник, имеющий строго положительную площадь.
Два треугольника являются различными, если различаются их множества точек — вершин.
В первой строке задано целое число $$$N$$$ $$$(4 \le N \le 100)$$$ — количество точек в ломаной линии.
В следующих $$$N$$$ строках находится по $$$2$$$ целых числа $$$x_i$$$ и $$$y_i$$$ $$$(0 \le |x_i|, |y_i| \le 256; 1 \le i \le N)$$$ — координаты $$$i$$$-й точки.
Выведите единственное целое число — суммарное количество невырожденных треугольников, образованных ломаной линией.
7 0 0 10 10 10 0 0 10 0 0 0 10 10 0
2
6 -5 -7 0 7 5 -7 -7 3 7 3 -5 -7
10
7 -5 0 1 1 3 3 3 3 -5 -5 7 7 0 -5
0
Первый тестовый пример
Данная ломаная образует всего 2 различных треугольника:
- $$$(0, 0)$$$, $$$(0, 10)$$$, $$$(5, 5)$$$;
- $$$(10, 10)$$$, $$$(10, 0)$$$, $$$(5, 5)$$$.
Второй тестовый пример
Данная ломаная образует 10 треугольников:
- $$$5$$$ «малых» треугольников — «лучи» звезды;
Пример «малого» треугольника: $$$(7, 0)$$$, $$$(\frac{-10}{7}, 3)$$$, $$$(\frac{10}{7}, 3)$$$;
- $$$5$$$ «больших» треугольников;
Пример «большого» треугольника: $$$(-5, -7)$$$, $$$(\frac{-10}{7}, 3)$$$, $$$(7, 3)$$$;
Третий тестовый пример
В этом случае ломаная вообще не образует ни одного невырожденного треугольника.
Зато Айбек указал две одинаковые точки подряд $$$(3, 3)$$$ и несколько точек на одной и той же прямой.
Группа археологов обнаружила древний подземный город. Город состоит из $$$N$$$ пещер, расположенных по кругу, каждой пещере присвоен номер от $$$1$$$ до $$$N$$$.
Пещеры, между которыми расстояние по кругу равно в точности $$$K$$$, соединены двусторонними тоннелями.
На рисунке ниже приведен пример города с $$$N=8$$$ и $$$K=3$$$.
Археологи не просто так спустились в данный город: они точно знают, что в некоторых пещерах лежат сокровища. В группе $$$M$$$ археологов, и каждый из них рассказал остальным ровно об одной пещере с сокровищами.
Археологи хотят поскорее добраться до всех сокровищ — город древний, поэтому в любой момент своды могут начать обрушаться. В то же время каждый археолог не может унести более одного сокровища.
Вам, как главному аналитику экспедиции, необходимо определить минимальное количество часов, за которое каждый археолог сможет добраться до одной из пещер с сокровищами:
- Все тоннели имеют одинаковую длину: археолог проходит тоннель за $$$1$$$ час;
- В одной и той же пещере и тоннеле могут находиться два и более археологов;
- В одной и той же пещере могут находиться два и более сокровищ;
- Каждый археолог может унести ровно одно сокровище — если в пещере $$$K$$$ сокровищ, то и добраться до них должны $$$K$$$ археологов.
В первой строке заданы целые числа $$$N$$$, $$$K$$$, $$$M$$$ ($$$3 \leq N \leq 10^6$$$; $$$1 \leq K \lt \frac{N}{2}$$$; $$$1 \leq M \leq 1000$$$) — количество пещер в городе, расстояние между cоединенными тоннелем пещерами и количество археологов и сокровищ соответственно.
Во второй строке дано $$$M$$$ целых чисел $$$A_i$$$ ($$$1 \le A_i \le N$$$) — номера пещер, где изначально находятся археологи.
В третьей строке дано $$$M$$$ целых чисел $$$T_j$$$ ($$$1 \le T_j \le N$$$) — номера пещер, в которых находятся сокровища.
Выведите единственное целое число — минимальное число часов, за которое все $$$M$$$ сокровищ будут достигнуты и распределены по $$$M$$$ археологам.
Если археологи не могут добраться до всех сокровищ за любое количество времени, выведите $$$-1$$$.
8 3 3 1 4 6 4 5 7
3
5 2 5 5 2 2 2 5 3 4 1 4 3
2
6 2 1 1 2
-1
Первый тестовый пример
Карта города соответствует рисунку в условии задачи.
Археологи расположены в пещерах с номерами $$$1$$$, $$$4$$$ и $$$6$$$, а сокровища — в пещерах $$$4$$$, $$$5$$$ и $$$7$$$.
Один из примеров оптимального поиска сокровищ:
- Археолог из пещеры $$$1$$$ добирается до сокровища в пещере $$$7$$$ по маршруту $$$1 \rightarrow 4 \rightarrow 7$$$ за 2 часа.
- Археолог из пещеры $$$4$$$ забирает сокровище из пещеры $$$4$$$, никуда не перемещаясь — всего 0 часов.
- Археолог из пещеры $$$6$$$ добирается до сокровища в пещере $$$5$$$ по маршруту $$$6 \rightarrow 3 \rightarrow 8 \rightarrow 5$$$ за 3 часа.
В ответ пойдет максимальное из времён — 3 часа. Можно показать, что невозможно добраться до всех трёх сокровищ быстрее.
Второй тестовый пример
В городе $$$N = 5$$$ пещер, а тоннели расположены между пещерами на расстоянии $$$K = 2$$$:
- между $$$1$$$ и $$$3$$$;
- между $$$2$$$ и $$$4$$$;
- между $$$3$$$ и $$$5$$$;
- между $$$4$$$ и $$$1$$$;
- между $$$5$$$ и $$$2$$$.
Три археолога расположены в пещере $$$2$$$, а еще двое — в пещере $$$5$$$.
В пещерах $$$3$$$ и $$$4$$$ расположены по два сокровища; еще одно сокровище расположено в пещере $$$1$$$.
Один из примеров оптимального поиска сокровищ:
- Археолог из пещеры $$$5$$$ добирается до сокровища в пещере $$$3$$$ по маршруту $$$5 \rightarrow 3$$$ за 1 час.
- Археолог из пещеры $$$5$$$ добирается до сокровища в пещере $$$1$$$ по маршруту $$$5 \rightarrow 3 \rightarrow 1$$$ за 2 часа.
- Археолог из пещеры $$$2$$$ добирается до сокровища в пещере $$$4$$$ по маршруту $$$2 \rightarrow 4$$$ за 1 час.
- Археолог из пещеры $$$2$$$ добирается до сокровища в пещере $$$4$$$ по маршруту $$$2 \rightarrow 4$$$ за 1 час.
- Археолог из пещеры $$$2$$$ добирается до сокровища в пещере $$$3$$$ по маршруту $$$2 \rightarrow 5 \rightarrow 3$$$ за 2 часа.
В ответ пойдет максимальное из времён — 2 часа.
Третий тестовый пример
В городе $$$N = 6$$$ пещер, а тоннели расположены между пещерами на расстоянии $$$K = 2$$$:
- между $$$1$$$ и $$$3$$$;
- между $$$2$$$ и $$$4$$$;
- между $$$3$$$ и $$$5$$$;
- между $$$4$$$ и $$$6$$$;
- между $$$5$$$ и $$$1$$$;
- между $$$6$$$ и $$$2$$$.
Археолог расположен в пещере $$$1$$$, а сокровище — в пещере $$$2$$$. Легко понять, что по системе тоннелей археолог никак не может добраться до сокровища.
Тридевятое царство состоит из $$$N$$$ городов, соединенных $$$N-1$$$ дорогой таким образом, что от каждого города можно доехать до любого другого города, двигаясь только по дорогам.
Организаторы чемпионата по программированию «Тридесятый кубок» решили провести очный тур чемпионата на площадках в нескольких городах царства.
При этом они хотят гарантировать, что расстояние от любого города царства до ближайшей площадки проведения не превышает двух дорог. То есть для любого города должно выполняться хотя бы одно из условий:
- Либо в самом городе есть площадка проведения;
- Либо в одном из соседних городов есть площадка;
- Либо в одном из соседних к одному из соседних городов есть площадка.
В то же время в целях экономии организаторы стремятся минимизировать количество площадок. Вам, как лучшему игроку царства в пошаговые стратегии, предстоит помочь организаторам найти данное количество.
Первая строка содержит целое число $$$N$$$ $$$(2 \le n \le 100)$$$ — количество городов в царстве.
В каждой из следующих $$$N-1$$$ строк содержатся по два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le N$$$) — номера городов, между которыми проложена одна из дорог царства.
Гарантируется, что от любого города можно добраться до любого другого города, двигаясь только по описанным дорогам.
Выведите единственное целое число — минимальное число городов, выбранных для проведения очного тура чемпионата, чтобы для каждого города выполнялось хотя бы одно из условий:
- Либо в самом городе есть площадка проведения;
- Либо в одном из соседних городов есть площадка;
- Либо в одном из соседних к одному из соседних городов есть площадка.
8 6 5 2 1 8 7 2 3 3 4 1 5 5 7
2
Тестовый пример
Для проведения чемпионата:
- одну из площадок можно разместить в городах $$$2$$$, $$$3$$$ или $$$4$$$;
- другую площадку можно разместить в одном из городов $$$5$$$ или $$$7$$$.
Например, один из вариантов размещения — пара городов $$$4$$$ и $$$5$$$. В таком случае ближайшая площадка расположена:
- Город $$$1$$$: в соседнем городе $$$5$$$;
- Город $$$2$$$: в городе $$$4$$$, являющемся соседним к соседнему городу $$$3$$$;
- Город $$$3$$$: в соседнем городе $$$4$$$;
- Город $$$4$$$: в самом городе;
- Город $$$5$$$: в самом городе;
- Город $$$6$$$: в соседнем городе $$$5$$$;
- Город $$$7$$$: в соседнем городе $$$5$$$;
- Город $$$8$$$: в городе $$$5$$$, являющемся соседним к соседнему городу $$$7$$$.
Как известно, в кыргызском языке есть 8 кратких гласных букв: а, э(е), ы, и, о, ө, у, ү.
Айбек считает родной язык очень важной частью культуры, поэтому стремится сделать какой-то ощутимый и полезный вклад — расширить возможности языка.
Недавно Айбек изобрёл новый вид слов — «гласнометия». Гласнометием является слово, состоящее только из гласных букв.
Оказалось, что некоторые гласнометия произносить очень легко, а некоторые — невероятно трудно. Айбек предполагает, что всему виной отверстия в буквах:
- в буквах и, у, ү отверстий нет вообще;
- в буквах а, ы, о есть ровно одно отверстие;
- в букве ө целых два отверстия;
- у буквы э(е) одно отверстие на два различных написания — по логике Айбека это ровно половина отверстия на одно написание.
Айбек выдвинул гипотезу, что проще всего произносить гласнометия, которые сбалансированы — количества «отверстий» на четных и нечетных позициях совпадают.
Теперь Айбек просит вас, как знатока $$$100500$$$ диалектов компьютерного кыргызского сленга, вычислить количество сбалансированных гласнометий, состоящих ровно из $$$N$$$ букв.
Так как количество может быть слишком велико для осознания простого смертного, Айбек хочет узнать лишь остаток от деления искомого количества на $$$2022$$$.
В единственной строке задано целое число $$$N$$$ $$$(1 \le N \le 2022)$$$ — количество букв в интересующих Айбека гласнометиях.
Выведите единственное целое число — остаток от деления на $$$2022$$$ количества различных сбалансированных гласнометий, состоящих ровно из $$$N$$$ букв.
1
3
2
20
3
105
1234
174
Первый тестовый пример
Полный список сбалансированных гласнометий длины $$$1$$$: и, у, ү — в данных словах $$$0$$$ отверстий как на чётных позициях, так и на нечётных.
Второй тестовый пример
Полный список сбалансированных гласнометий длины $$$2$$$:
- ии;
- иу;
- иү;
- уи;
- уу;
- уү;
- үи;
- үу;
- үү;
- ээ;
- аа;
- ао;
- аы;
- оа;
- оо;
- оы;
- ыа;
- ыо;
- ыы;
- өө.
- В словах $$$1$$$ - $$$9$$$ на чётных и нечётных позициях по $$$0$$$ отверстий;
- В слове $$$10$$$ на чётных и нечётных позициях по $$$0.5$$$ отверстий;
- В словах $$$11$$$ - $$$19$$$ на чётных и нечётных позициях по $$$1$$$ отверстию;
- В слове $$$20$$$ на чётных и нечётных позициях по $$$2$$$ отверстия;
Третий тестовый пример
Некоторые из сбалансированных гласнометий длины $$$3$$$:
- аөы — по $$$2$$$ отверстия;
- эоэ — по $$$1$$$ отверстию;
- иыа — по $$$1$$$ отверстию;
- үиу — по $$$0$$$ отверстий.
В поисках ответа на главный вопрос жизни, вселенной и всего такого Айбек отправился в Ханой.
Почему в Ханой? Потому что за свою жизнь много раз слышал о «Ханойских башнях» — раз все об этом говорят, то надо обязательно изучить вживую.
И Айбеку улыбнулась удача. Первая же башня (а точнее её древние развалины), которые он нашёл, состояла из каменных круглых дисков, насаженных центром на один большой столб.
Что еще более заинтересовало Айбека — каждый следующий в направлении к небу диск имел радиус не больше, чем у предыдущего.
«Наверное, так богам на небесах было видно больше различных дисков», — подумал Айбек.
Чтобы проверить свою гипотезу, Айбек просит вас (как самого опытного экскурсовода по Вьетнаму) вычислить количество дисков, которые видно, если смотреть на центральную ось башни строго сверху с очень-очень большой высоты.
Диск видно, если его радиус строго больше всех радиусов дисков, расположенных ближе к небу.
В первой строке расположено одно целое число $$$N$$$ $$$(1 \le N \le 3 \cdot 10^5)$$$ — количество дисков Ханойской башни.
Во второй строке через пробел задано $$$N$$$ целых чисел $$$r_i$$$ $$$(1 \le r_n \le r_{n-1} \le \dots \le r_2 \le r_1 \le 10^6)$$$ — радиусы дисков в направлении от земли к небу.
Выведите единственное целое число — количество дисков, которые видно, если смотреть на центральную ось башни строго сверху с очень-очень большой высоты.
3 42 13 8
3
7 9 9 4 2 2 2 1
4
Первый тестовый пример
У всех дисков башни радиус различен, поэтому каждый диск будет видно с «высоты богов».
Второй тестовый пример
Боги точно увидят диски под номерами $$$2$$$, $$$3$$$, $$$6$$$ и $$$7$$$:
- Диск $$$1$$$ не видно, так как он полностью скрыт диском $$$2$$$;
- Диски $$$4$$$ и $$$5$$$ полностью скрыты диском $$$6$$$.