Аргайл — узор из ромбов или квадратов, расположенных в шахматном порядке и образующих параллельные и поперечные полосы разных цветов. Название происходит от имени шотландского клана Кампбелл в графстве Аргайл. Особенную популярность этот орнамент получил в XX веке. Это случилось благодаря компании «Pringle of Scotland», которая стала выпускать элитный трикотаж с орнаментом «Аргайл», после чего он стал визитной карточкой аристократии. С тех пор узор не выходит из моды. Существует огромное количество цветовых решений этого орнамента. Особенно популярен этот узор на свитерах, жилетах, кардиганах, платьях, шарфах, носках и гетрах.
Определите количество квадратов красного и зелёного цветов на ткани размером $$$n \times n$$$.
Единственная строка входных данных содержит натуральное число $$$n$$$ ($$$1 \le n \le 10^{9}$$$).
$$$\textbf{Обратите внимание}$$$, что при заданных ограничениях для хранения ответа необходимо использовать $$$64$$$-битный тип данных, например $$$\textbf{long}$$$ $$$\textbf{long}$$$ в $$$\textbf{C++}$$$, $$$\textbf{int64}$$$ в $$$\textbf{Free}$$$ $$$\textbf{Pascal}$$$, $$$\textbf{long}$$$ в $$$\textbf{Java}$$$.
Выведите в двух строках два неотрицательных целых числа — ответ на вопрос задачи. В первой строке выведите количество квадратов красного цвета, во второй — зелёного.
Решения, правильно работающие при $$$n \le 10^{5}$$$, будут оцениваться в 50 баллов.
3
1 1
4
1 4
Петя и его друзья собираются отпраздновать успешное окончание учебного года. Для этого они решили приобрести $$$n$$$ упаковок апельсинового сока и $$$m$$$ упаковок яблочного сока и выделили на эти цели $$$s$$$ рублей.
Одна упаковка любого сока стоит $$$r$$$ рублей. Однако можно приобретать сок коробками. Одна коробка содержит $$$k$$$ упаковок сока одного вида и стоит $$$p$$$ рублей (известно, что $$$k \cdot r \gt p$$$).
Друзья хотят приобрести как можно больше упаковок сока на имеющиеся деньги, но так, чтобы при этом было не менее $$$n$$$ упаковок апельсинового сока и не менее $$$m$$$ упаковок яблочного.
Сколько упаковок сока смогут приобрести друзья при таком условии?
В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — необходимое количество упаковок апельсинового сока.
Во второй строке содержится целое число $$$m$$$ $$$(1 \le m \le 5 \cdot 10^5)$$$ — необходимое количество упаковок яблочного сока.
В третьей строке содержится целое число $$$r$$$ $$$(1 \le r \le 1000)$$$ — цена одной упаковки сока (любого вида).
В четвёртой строке содержится целое число $$$k$$$ $$$(2 \le k \le 10^6)$$$ — количество упаковок сока в коробке.
В пятой строке содержится целое число $$$p$$$ $$$(1 \le p \lt k \cdot r)$$$ — цена коробки, содержащей $$$k$$$ упаковок сока.
В шестой строке содержится целое число $$$s$$$ $$$(1 \le s \le 10^9)$$$ — количество денег, выделенных на покупку сока.
Выведите целое число — максимально возможное суммарное количество упаковок сока, которые получится приобрести.
Если невозможно приобрести сок, соблюдая описанные условия, выведите $$$-1$$$.
Решения, правильно работающие, когда хотя бы одна из величин $$$n$$$ или $$$m$$$ делится на $$$k$$$ нацело, будут оцениваться в $$$25$$$ баллов.
878053701400
18
878052251200
25
878053751100
-1
В первом примере из условия нужно купить $$$8$$$ упаковок апельсинового сока и $$$7$$$ упаковок яблочного сока. Одна упаковка стоит $$$80$$$ рублей, а коробка из $$$5$$$ упаковок — $$$370$$$ рублей. На $$$1110$$$ рублей можно купить $$$3$$$ коробки сока, например, две коробки апельсинового и одну коробку яблочного. Останется $$$1400-3\cdot 370=290$$$ рублей: $$$240$$$ рублей хватит на $$$3$$$ упаковки яблочного сока (или $$$2$$$ упаковки яблочного и $$$1$$$ — апельсинового), $$$50$$$ рублей останется. Условия будут выполнены, всего будет приобретено $$$3\cdot5 + 3=18$$$ упаковок сока.
Во втором примере на $$$1200$$$ рублей можно приобрести $$$5$$$ коробок сока по $$$225$$$ рублей. Если взять три коробки апельсинового сока и две коробки яблочного, то условия будут выполнены. Останется $$$1200 - 5 \cdot 225= 75$$$ рублей, на которые ничего нельзя купить.
В третьем примере на $$$1100$$$ рублей можно купить $$$2$$$ коробки сока по $$$375$$$ рублей: коробку апельсинового и коробку яблочного. Останется $$$1100 - 2 \cdot 375=350$$$ рублей, на которые нужно купить ещё три упаковки апельсинового и две упаковки яблочного сока. При стоимости упаковки в $$$80$$$ рублей это сделать нельзя.
Арт-объект представляет собой $$$n$$$ колонн высотой $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ сантиметров. Критики считают, что арт-объект станет выглядеть лучше, если высоты колонн будут идти по неубыванию, то есть высота каждой колонны должна быть не меньше высоты предыдущей колонны ($$$a_i\ge a_{i-1}$$$ для всех $$$i\ge2$$$).
Поскольку порядок колонн нельзя менять (это разрушит замысел автора), колонны можно расположить на лестнице, высота ступеньки которой равна $$$d$$$. При этом на каждой ступеньке будет стоять одна колонна, а первая колонна должна стоять на первой ступеньке. Тогда высота первой колонны $$$a_1$$$ увеличится на $$$d$$$, высота второй колонны $$$a_2$$$ увеличится на $$$2d$$$, значение $$$a_3$$$ увеличится на $$$3d$$$ и так далее.
Чтобы арт-объект не стал слишком громоздким, нужно найти минимальную подходящую высоту ступеньки $$$d$$$, при которой высоты колонн станут неубывающими.
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — количество колонн.
В следующих $$$n$$$ строках записаны высоты колонн $$$a_i$$$, $$$1\le a_i \le 10^9$$$.
Программа должна вывести минимальную подходящую высоту ступеньки $$$d$$$. Если высоты колонн уже неубывают, необходимо вывести число 0.
Решения, правильно работающие при $$$n \le 2$$$, будут оцениваться в $$$20$$$ баллов.
Решения, правильно работающие при $$$a_i \le 10$$$, будут оцениваться в $$$30$$$ баллов.
515275
3
В первом примере высоты колонн равны $$$1, 5, 2, 7, 5$$$. Если использовать лестницу со ступенькой $$$d=3$$$, то высоты колонн станут $$$4, 11, 11, 19, 20$$$. Если взять ступеньку $$$d=2$$$, то получатся высоты $$$3, 9, 8, 15, 15$$$, и тогда колонна номер 2 будет выше колонны номер 3.
В одном из ресторанов между $$$n$$$ поварами возник спор — какой длины должен быть рис? Каждый повар считает по-своему: $$$i$$$-й повар считает, что длина должна быть равна $$$h_i$$$ миллиметрам.
Повар может переубедить другого повара, если представления поваров о длине риса отличаются на единицу (то есть $$$i$$$-й повар может переубедить $$$j$$$-го, если $$$|h_i - h_j| = 1$$$). Если $$$i$$$-й повар переубедил $$$j$$$-го, то значение $$$h_j$$$ станет равно значению $$$h_i$$$. Переубеждённый повар может затем снова изменить своё мнение.
Менеджеру по закупкам ресторана нужно закупить рис одной длины. Определите, какому максимальному количеству поваров можно угодить после того, как какие-то повара смогут переубедить друг друга (иными словами — наибольшее количество поваров, которые могут прийти к единому мнению о длине риса).
Первая строка входных данных содержит одно натуральное число $$$n$$$ ($$$1 \leqslant n \leqslant 10^5$$$) — количество поваров.
Каждая из следующих $$$n$$$ строк содержит одно натуральное число $$$h_i$$$ ($$$1 \leqslant h_i \leqslant 10^9$$$) — идеальную длину риса по мнению $$$i$$$-го повара.
Программа должна вывести одно число — максимальное количество поваров, которые могут прийти к единому мнению о длине риса.
Решения, правильно работающие, когда $$$n \leqslant 10^3$$$ и все $$$h_i$$$ различны, будут оцениваться в 20 баллов.
Решения, правильно работающие, когда $$$n \leqslant 10^3$$$, будут оцениваться в 60 баллов.
72342687
4
В примере из условия повара имеют следующие предпочтения о длине риса: 2, 3, 4, 2, 6, 8, 7. Сначала второй повар переубедит третьего в том, что длина риса должна быть равна 3. Затем первый повар переубедит второго и третьего в том, что длина риса 2 подходящая. Также четвёртый повар считает, что 2 — подходящая длина, поэтому 4 повара сошлись в мнении о том, что длина 2 будет подходящей.
Вася — начинающий художник. Поскольку опыта у него немного, сейчас он практикуется в рисовании гармоничных полосок.
Каждая полоска, рисуемая Васей, состоит из $$$n$$$ последовательных ячеек, каждая из которых может быть покрашена в один из $$$m$$$ цветов. Яркостью полоски в таком случае называется сумма модулей разностей цветов соседних ячеек. Например, яркость полоски $$$\{3, 1, 5, 2\}$$$ равна $$$|3-1| + |1-5|+|5-2|=9$$$, а яркость полоски $$$\{1, 1, 2\}$$$ равна $$$|1-1|+|1-2|=1$$$.
Как у любого художника, у Васи очень сильно развито чувство прекрасного, и оно подсказывает ему, что полоска будет тем красивее, чем меньше будет её значение яркости. На текущий момент краски цвета $$$i$$$, имеющейся у Васи, хватит для того, чтобы покрасить не более $$$a_i$$$ ячеек. Помогите художнику — определите, какую минимальную яркость может иметь полоска, нарисованная Васей.
В первой строке содержится число $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — размер полоски.
Во второй строке содержится число $$$m$$$ ($$$1 \leq m \leq 3 \cdot 10^5$$$) — количество доступных Васе цветов.
В $$$i$$$-й из следующих $$$m$$$ строк содержится число $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) — количество ячеек, на покраску которых хватит краски цвета $$$i$$$, имеющейся у Васи.
Гарантируется, что $$$n \leq a_1+\dots+a_m$$$ (т.е. Васе хватит краски, чтобы раскрасить все ячейки).
В единственной строке выведите одно число — минимальную яркость, которую может иметь полоска, нарисованная Васей.
Решения, правильно работающие при $$$m \leq 3$$$, будут оцениваться в 20 баллов.
Решения, правильно работающие при $$$n, m \leq 6$$$, будут оцениваться в 25 баллов.
Решения, правильно работающие при $$$m \leq 100$$$, будут оцениваться в 60 баллов.
Решения, правильно работающие при $$$m \leq 1500$$$, будут оцениваться в 70 баллов.
7502311
3
63143
1