В школе у Иэна проходит ежегодная ярмарка талантов, в которой решили принять участие $$$n$$$ существ. Рост каждого существа от $$$100$$$ до $$$1\,000$$$ сантиметров.
Для летописи, всех участников необходимо сфотографировать. Барли вызвался на роль фотографа. Чтобы на фотографии было отчётливо видно фотографируемых, организаторы съёмки ввели правила:
- На одной фотографии не должно быть больше трёх существ.
- На фотографии может быть три существа, если разница в росте самого высокого и самого низкого из них не превосходит $$$10$$$ сантиметров.
- На фотографии может быть два существа, если разница в их росте не превосходит $$$20$$$ сантиметров.
- На фотографии может быть одно существо, независимо от его роста.
Участников довольно много, а Барли хотел бы побыстрее освободиться. Помогите ему узнать, какое минимальное число фотографий ему придётся сделать, чтобы сфотографировать всех участников.
В первой строке дано одно целое число $$$n$$$ — число участников ярмарки ($$$1 \le n \le 1\,000$$$).
Во второй строке даны $$$n$$$ чисел $$$a_1, a_2, \dots a_n$$$ — рост каждого участника ($$$100 \le a_i \le 1000$$$).
Выведите одно число — минимальное число фотографий, которое придется сделать Барли.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке | |
| 1 | 20 | $$$n \le 3$$$ | полная | ||
| 2 | 20 | $$$n \le 10$$$ | 1 | первая ошибка | |
| 3 | 20 | $$$n \le 50$$$ и для любых $$$i, j: |a_i - a_j| | gt; 10$$$ | первая ошибка | |
| 4 | 40 | Без дополнительных ограничений | 1, 2, 3 | первая ошибка |
3 100 300 200
3
3 110 120 130
2
6 100 210 250 255 220 260
3
Пока Иэн и Барли ехали по шоссе, чтобы Барли не скучал, Иэн предложил ему посчитать количество волшебных троек. Тройка натуральных чисел $$$a$$$, $$$b$$$ и $$$c$$$ ($$$1 \le a \lt b \lt c \le n$$$) называется волшебной, если $$$a \cdot b$$$, $$$a \cdot c$$$ и $$$b \cdot c$$$ — квадраты натуральных чисел.
Помогите Барли решить задачку Иэна, найдите количество волшебных троек.
В единственной строке дано одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$).
Выведите одно число — количество волшебных троек.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | $$$n \le 100$$$ | первая ошибка | |
| 2 | 20 | $$$n \le 1\,000$$$ | 1 | первая ошибка |
| 3 | 30 | $$$n \le 10\,000$$$ | 1, 2 | первая ошибка |
| 4 | 40 | Без дополнительных ограничений | 1, 2, 3 | первая ошибка |
10
1
20
5
В первом примере единственной волшебной тройкой является $$$a = 1$$$, $$$b = 4$$$, $$$c = 9$$$.
Во втором примере существуют следующие волшебные тройки:
- $$$a = 1$$$, $$$b = 4$$$, $$$c = 9$$$
- $$$a = 1$$$, $$$b = 4$$$, $$$c = 16$$$
- $$$a = 1$$$, $$$b = 9$$$, $$$c = 16$$$
- $$$a = 4$$$, $$$b = 9$$$, $$$c = 16$$$
- $$$a = 2$$$, $$$b = 8$$$, $$$c = 18$$$
Иэн и Барли нашли древнюю книгу с заклинаниями, и Иэн решил испробовать одно из них.
К сожалению, в книге написано не само заклинание, а только его описание. Известно, что заклинание является правильной скобочной последовательностью (ПСП). ПСП это строка, состоящая из символов «(» и «)». Пустая строка является ПСП. Конкатенация двух, возможно разных, ПСП является ПСП. ПСП, взятая в скобки, является ПСП. Две скобки в ПСП называются парными, если подстрока, начинающаяся сразу после первой из скобок и заканчивающаяся прямо перед второй, является ПСП. Несложно доказать, что в любой ПСП длины $$$n \cdot 2$$$ есть ровно $$$n$$$ пар парных скобок. Для простоты, будем называть их просто парами скобок.
Известно, что заклинание содержит $$$n$$$ пар скобок. А также, известно мультимножество расстояний между скобками в каждой паре. Иными словами, для каждой пары скобок было найдено $$$a_i$$$ — количество символов между ними.
Теперь Иэн пытается восстановить заклинание. Помогите ему найти любую подходящую ПСП, либо сообщите, что такой не существует.
В первой строке дано одно целое число $$$n$$$ — количество пар скобок в заклинании ($$$1 \le n \le 20$$$). Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ — мультимножество расстояний между скобками в каждой паре ($$$0 \le a_i \le n \cdot 2$$$).
Если существует ПСП, которая удовлетворяет всем ограничениям, в первой строке выведите «Yes», а во второй — строку из символов «(» и «)» длины $$$n \cdot 2$$$ — подходящую ПСП. Если существует несколько решений, выведите любое.
Если подходящей ПСП не существует, в единственной строке выведите «No».
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | $$$n \le 3$$$ | первая ошибка | |
| 2 | 20 | $$$n \le 10$$$ | 1 | первая ошибка |
| 3 | 15 | $$$a_i \le 2$$$ | первая ошибка | |
| 4 | 20 | $$$a_i \le 4$$$ | 3 | первая ошибка |
| 5 | 35 | Без дополнительных ограничений | 1, 2, 3, 4 | первая ошибка |
1 0
Yes ()
2 0 0
Yes ()()
2 2 0
Yes (())
1 2
No
5 0 0 0 2 6
Yes ()(()(()))
Иэн и Барли добрались до цели своего путешествия. Им осталось лишь открыть сокровищницу, в которой их ждёт ещё один волшебный кристалл.
Латинским квадратом называется квадратная таблица размера $$$x \times x$$$, в которой ровно $$$x$$$ различных значений, и в каждой строке и каждом столбце все значения различны.
Из древнего манускрипта, братьям известна последовательность целых чисел $$$a_1 \lt a_2 \lt \dots \lt a_{n - 1} \lt a_n$$$. Чтобы скровищница открылась, нужно нарисовать на входе в неё квадратную таблицу размера $$$a_n \times a_n$$$, заполненную числами от $$$1$$$ до $$$a_n$$$. При этом, для всех $$$i$$$ подтаблица размера $$$a_i \times a_i$$$, верхний левый угол которой совпадает с верхним левым углом всей таблицы, должна являться латинским квадратом.
Помогите братьям нарисовать правильную таблицу, либо сообщите, что это невозможно.
В первой строке дано одно целое число $$$n$$$ — длина последовательности чисел ($$$1 \le n \le 1\,000$$$).
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 1\,000$$$, $$$a_i \lt a_{i + 1}$$$).
Если искомая таблица существует, в первой строке выведите «Yes», а в следующих $$$a_n$$$ строках по $$$a_n$$$ чисел со значениями от $$$1$$$ до $$$a_n$$$ — таблицу. Если решений несколько, выведите любое.
Если искомой таблицы не существует, в единственной строке выведите «No».
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке | |
| 1 | 10 | $$$n = 1$$$ | первая ошибка | ||
| 2 | 15 | $$$n \le 10$$$, $$$a_i = 2^{i - 1}$$$ | первая ошибка | ||
| 3 | 15 | $$$a_i \cdot 2 + 1 \ge a_{i + 1}$$$ для всех $$$1 \le i | lt; n$$$ | 1, 2 | первая ошибка |
| 4 | 35 | $$$a_n \le 100$$$ | первая ошибка | ||
| 5 | 25 | Без дополнительных ограничений | 1, 2, 3, 4 | первая ошибка |
1 3
Yes 1 3 2 2 1 3 3 2 1
3 1 2 4
Yes 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1
2 2 3
No
2 2 5
Yes 1 2 3 5 4 2 1 4 3 5 5 4 1 2 3 4 3 5 1 2 3 5 2 4 1