ТИИМ 2023-2024, Заключительный этап (10-11 классы)
Statement is not available in English language
1. Доблесть и честь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На этот раз царю Леониду предстоит защитить Спарту от врагов. В распоряжении у него имеется $$$N$$$ бойцов. $$$i$$$-й боец обладает верностью $$$A_i$$$ единиц. Этим бойцам предстоит отразить $$$M$$$ вражеских отрядов. Сила $$$i$$$-го отряда равна $$$B_i$$$ единиц. Полк бойцов отражает атаку $$$i$$$-го вражеского отряда, если каждый боец полка имеет верность строго больше $$$B_i$$$ и количество бойцов в полке не меньше количества бойцов во вражеском отряде (количество бойцов во вражеском отряде равно его силе). Каждый спартанец полка при столкновении с вражеским отрядом погибает смертью храбрых. Леонид хочет знать, может ли он сформировать несколько полков из спартанцев так, чтобы отбить атаки всех вражеских отрядов. (Замечание: один полк отбивает атаку только одного вражеского отряда)

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

В первой строке записано число $$$T$$$ ($$$1 \le T \le 100$$$) — количество тестов. После этого следует описание каждого тестового случая. В первой строке описания содержится целое число $$$N$$$ ($$$1 \le N \le 10^5$$$) — количество спартанцев. Во второй строке содержится массив $$$A$$$ из $$$N$$$ целых чисел ($$$1 \le A_i \le 10^9$$$) — верность каждого спартанца. В третьей строке содержится целое число $$$M$$$ ($$$1 \le M \le 10^5$$$) — количество вражеских отрядов. В четвертой строке содержится массив $$$B$$$ из $$$M$$$ целых чисел ($$$1 \le B_i \le 10^9$$$) — силу каждого отряда. Гарантируется, что сумма $$$N$$$ и $$$M$$$ по всем входным данным не превышает $$$10^5$$$.

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

В ответ выведите $$$T$$$ строк — ответ для каждого тестового случая: может ли Леонид собрать несколько полков. Если может, то выводите «Yes» (без кавычек), иначе «No».

Пример
Входные данные
3
5
4 6 9 2 1
2
1 3
5
3 8 5 10 4
2
3 1
5
9 7 9 6 9
2
5 4
Выходные данные
Yes
Yes
No

Statement is not available in English language
2. Прямоугольные треугольники
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На координатной плоскости заданы $$$N$$$ точек с целочисленными координатами.

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

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

Первая строка входных данных содержит число $$$N$$$ ($$$1 \le N \le 100$$$) — количество точек.

Каждая из следующих $$$N$$$ строк содержит пару чисел $$$x_k, y_k$$$ ($$$-10^9 \le x_k, y_k \le 10^9$$$) — координаты точек, разделённые пробелом.

Гарантируется, что все точки попарно различны.

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

Выведите одно число, искомое количество прямоугольных треугольников.

Пример
Входные данные
6
10 1
3 3
6 6
3 7
7 3
4 0
Выходные данные
3
Примечание

На рисунке ниже прямоугольными треугольниками являются треугольники $$$ACE$$$, $$$CDE$$$ и $$$BDE$$$.

Statement is not available in English language
Statement is not available in English language
4. Даня и тульские пряники
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Студент Даня получил стипендию, и на неё купил себе $$$T$$$ тульских пряников.

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

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

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

В первой строке содержится целое число $$$T$$$ ($$$1 \le T \le 50 $$$) — количество купленных тульских пряников.

Каждый тульский пряник описывается в первой строке двумя числами $$$N$$$ и $$$M$$$ ($$$1 \le N, M \le 500$$$) — высотой и шириной тульского пряника соответственно.

Затем следует $$$N$$$ строк по $$$M$$$ чисел, по модулю не превышающих $$$5 \cdot 10^4$$$ (но возможно отрицательных), которые описывают вкусность каждого кусочка пряника.

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

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

Для каждого тульского пряника в отдельной строке выведите максимальную сумму вкусностей по всем кусочкам квадратной формы.

Примеры
Входные данные
1
4 3
-6 2 1
-3 -5 -4
-6 7 -6
5 -9 -10
Выходные данные
7
Входные данные
3
2 5
1 2 -1 -3 5
-4 -1 -2 1 5
3 4
-3 8 6 4
-8 -7 -5 3
-5 -5 8 6
2 2
-5 5
4 -6
Выходные данные
8
18
5

Statement is not available in English language
5. Жизнь пешки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компьютер записывает «биографию» белой шахматной пешки в течение партии на доске $$$8 \times 8$$$.

Начальное положение пешки — клетка E2.

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

Компьютер в начале игры и после каждого хода белых записывает позицию пешки по вертикали. Если пешка была «взята», запись позиции прекращается. Считать, что пешку могут взять сразу после первого хода. При этом пешка не может двигаться вперёд с позиции E8, но может стоять на этой позиции сколько угодно ходов до конца партии.

Вам дана длина шахматной партии, найдите количество всех возможных «жизненных путей» пешки по модулю $$$998244353$$$.

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

Единственная строка входных данных содержит целое число $$$N$$$ ($$$1 \le N \le 10^6$$$) — длину партии.

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

В ответе выведите искомое количество различных шахматных путей по модулю $$$998244353$$$.

Примеры
Входные данные
2
Выходные данные
10
Входные данные
99
Выходные данные
582018135
Примечание

$$$10$$$ возможных путей, если партия длилась два хода: $$$22$$$, $$$23$$$, $$$24$$$, $$$222$$$, $$$223$$$, $$$224$$$, $$$233$$$, $$$234$$$, $$$244$$$, $$$245$$$.

Statement is not available in English language
6. Владелец банка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бизнесмен Владимир является владельцем самого крупного банка в мире «Банк-Вованк». Чтобы подчеркнуть свой статус, он каждый день приходит в автосалон с целью прикупить новых машин в свою коллекцию.

В автосалоне есть $$$N$$$ различных марок машин. Количество машин $$$i$$$-й марки равно $$$A_i$$$, каждая из них имеет цену $$$B_i$$$ бурлей. Владимир будет приходить в автосалон в течение $$$Q$$$ дней. В $$$i$$$-й день он хочет купить $$$C_i$$$ самых дорогих машин, стоимость каждой из которых не превышает $$$D_i$$$ бурлей (при этом не обязательно все машины должны иметь различную марку). При этом при равенстве в цене он отдаёт приоритет машинам, у которых номер марки меньше (т.е. той марке, которая раньше записана во входных данных). Если нашлось столько машин с подходящей стоимостью, Владимир купит все эти машины. Однако если столько машин не нашлось, он не будет покупать ничего.

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

Первая строка содержит число $$$N$$$ ($$$1 \le N \le 10^5$$$) — количество марок машин в автосалоне. Вторая строка содержит массив $$$A$$$ из $$$N$$$ чисел ($$$1 \le A_i \le 10^9$$$) — количество машин каждой марки. Третья строка содержит массив $$$B$$$ из $$$N$$$ чисел ($$$1 \le B_i \le 10^9$$$) — стоимость одной машины каждой марки. Четвёртая строка содержит число $$$Q$$$ ($$$1 \le Q \le 10^5$$$) — в течение скольки дней Владимир будет приходить в автосалон. Пятая строка содержит массив $$$C$$$ из $$$Q$$$ чисел ($$$1 \le C_i \le 10^9$$$) — количество машин, которое он хочет купить каждый день. Шестая строка содержит массив $$$D$$$ из $$$Q$$$ чисел ($$$1 \le D_i \le 10^9$$$) — ограничение на стоимость машин каждый день.

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

Для каждого дня в отдельной строке выведите «Yes», если Владимир совершил покупку, либо «No», если не совершил (выводите без кавычек). В последней строке выведите $$$N$$$ чисел — количество оставшихся машин каждой марки (в том же порядке, что и во входных данных).

Система оценки

Решения, правильно работающие для $$$N \cdot Q \le 10^6$$$, будут набирать не менее 50 баллов.

Пример
Входные данные
5
4 6 9 2 1
1 8 3 8 5
3
10 4 8
6 9 7
Выходные данные
Yes
Yes
No
4 2 0 2 0