На этот раз царю Леониду предстоит защитить Спарту от врагов. В распоряжении у него имеется $$$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
На координатной плоскости заданы $$$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$$$.
Студент Даня получил стипендию, и на неё купил себе $$$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
Компьютер записывает «биографию» белой шахматной пешки в течение партии на доске $$$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$$$.
Бизнесмен Владимир является владельцем самого крупного банка в мире «Банк-Вованк». Чтобы подчеркнуть свой статус, он каждый день приходит в автосалон с целью прикупить новых машин в свою коллекцию.
В автосалоне есть $$$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