#1340

Темы: [Остатки] [Перебор с отсечением] [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2009, Задача D ]

В стране Флатландия решили построить легкоатлетический манеж с M одинаковыми прямолинейными беговыми дорожками. Они будут покрыты полосами из синтетического материала пружинкин. На складе имеются N полос пружинкина, длины которых равны 1, 2, …, N метров соответственно (i-я полоса имеет длину i метров).

Было решено использовать все полосы со склада, что определило длину дорожек манежа. Полосы пружинкина должны быть уложены без перекрытий и промежутков. Разрезать полосы на части нельзя. Полосы укладываются вдоль дорожек, ширина полосы пружинкина совпадает с шириной беговой дорожки.

Требуется написать программу, которая определяет, можно ли покрыть всем имеющимся материалом M дорожек, и если это возможно, то распределяет полосы пружинкина по дорожкам.

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

Во входном файле содержатся два целых числа, разделенных пробелом: M — количество дорожек и N — количество полос пружинкина (1 ≤ M ≤ 1000, 1 ≤ N ≤ 30000).

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

В случае, если распределить имеющиеся полосы пружинкина на M дорожек одинаковой длины невозможно, то в выходной файл выведите слово «NO».

В противном случае, в первую строку выведите слово «YES». В последующих M строках дайте описание использованных полос для каждой дорожки в следующем формате: сначала целое число t — количество полос на дорожке, затем t целых чисел — длины полос, которые составят эту дорожку. Если решений несколько, можно вывести любое из них.

В задаче есть группа на первые 17 тестов и она оценивается в 20 баллов. затем идёт потестовая оценка по 2 балла за пройденный тест.

Примеры входных и выходных данных

Ввод

Вывод

2 4

YES

2 1 4

2 3 2

3 4

NO

#3182

Колесо Фортуны

Темы: [Линейный поиск] [Остатки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 1 день, Задача B ]

Развлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.

Юный участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью $v$ градусов в секунду, и стрелка, переходя из сектора $X$ к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на $k$ градусов в секунду. При этом если $v \le k$, то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор $X$.

Юный участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от $a$ до $b$ градусов в секунду.

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

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

Первая строка входного файла содержит целое число $n$ — количество секторов колеса ($3 \le n \le 100$).

Вторая строка входного файла содержит $n$ положительных целых чисел, каждое из которых не превышает $1000$ — числа, записанные в секторах колеса. Числа приведены в порядке следования секторов по часовой стрелке. Изначально стрелка указывает на первое число.

Третья строка содержит три целых числа: $a$, $b$ и $k$ ($1 \le a \le b \le 10^9$, $1 \le k \le 10^9$).

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

В выходном файле должно содержаться одно целое число — максимальный выигрыш.

Примечание

В первом примере возможны следующие варианты: можно придать начальную скорость колесу равную 3 или 4, что приведет к тому, что стрелка преодолеет одну границу между секторами, или придать начальную скорость равную 5, что позволит стрелке преодолеть 2 границы между секторами. В первом варианте, если закрутить колесо в одну сторону, то выигрыш получится равным 2, а если закрутить его в противоположную сторону, то — 5. Во втором варианте, если закрутить колесо в одну сторону, то выигрыш будет равным 3, а если в другую сторону, то — 4.

Во втором примере возможна только одна начальная скорость вращения колеса — 15 градусов в секунду. В этом случае при вращении колеса стрелка преодолеет семь границ между секторами. Тогда если его закрутить в одном направлении, то выигрыш составит 4, а если в противоположном направлении, то — 3.

Наконец, в третьем примере оптимальная начальная скорость вращения колеса равна 2 градусам в секунду. В этом случае стрелка вообще не сможет преодолеть границу между секторами, и выигрыш будет равен 5.

Правильные решения для тестов, в которых $1 \le a \le b \le 1000$, будут оцениваться из 50 баллов.

Примеры

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

5
1 2 3 4 5
3 5 2

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

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

5
1 2 3 4 5
15 15 2

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

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

5
5 4 3 2 1
2 5 2

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

#111181

Крым-кола

Темы: [Остатки]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2012, Задача A ]

Завод по производству Крым-колы изготавливает ее не только для магазинов, но и для всемирно известной сети ресторанов быстрого питания.

Ежедневно завод отгружает один и тот же объем колы в литрах. Служба доставки сети ресторанов обычно использует для транспортировки колы емкости объемом или только 50 литров, или только 70 литров. Если доставка осуществляется с помощью емкостей в 50 литров, то для перевозки имеющегося объема колы необходимо A емкостей. А если с помощью емкостей в 70 литров, то необходимо B емкостей. При этом в каждом из случаев одна из емкостей может быть заполнена не полностью.

Недавно сеть ресторанов решила утвердить новый объем емкостей для доставки колы — 60 литров. Сколько емкостей теперь может понадобиться для доставки того же самого объема колы?

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

Входные данные содержат 2 числа A и B, расположенных каждое в отдельной строке (1 ≤ A, B ≤ 10 000 000).

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

Выведите все возможные значения для количества емкостей по 60 литров, которые окажутся заполненными (в том числе одна возможно частично), в порядке возрастания или число - 1, если значения A и B противоречат друг другу, то есть они были записаны неверно.

Примеры тестов

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

3
2

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

2 3

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

1
2

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

-1

Примечание

В первом примере колы могло быть, например, 115 литров, в этом случае понадобится две емкости в 60 литров, а могло быть — 135 литров, в этом случае понадобятся уже три емкости по 60 литров. Четыре емкости не могут понадобиться никогда.

Online-группа тестов оценивается в 60 баллов, в этой группе 1 ≤ A, B ≤ 1 000.

Offline-группа тестов оценивается в 40 баллов.

#111652

Купе

Темы: [Остатки] [Условный оператор (if)]

Источники: [ Личные олимпиады, Золотая середина (Новосибирск), 2013, Задача A ]

Два юных шамана Егор и Саша отправились на Всероссийский Конкурс Опытных Шаманов Профессионалов. До места проведения ВКОШП можно добраться только на поезде. Всего в вагоне поезда восемь купе по четыре места в каждом. Схема нумерации мест первого купе представлена на рисунке.

$\text{[math]}$

Вам известны номера мест Егора и Саши. В данный момент друзья находятся на перроне и хотят узнать, попадут ли они в одно купе и на каких полках (верхних или нижних) будут ехать.

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

В единственной строке содержатся два натуральных числа — номера мест Саши и Егора соответственно. Гарантируется, что они не будут превышать количество мест в вагоне, описанном в условии. Также гарантируется, что у Егора и Саши билеты на разные места.

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

В первой строке выведите "YES", если друзья попадут в одно купе, и "NO" — иначе. Во второй строке выведите "LOW", если Саша будет ехать на нижнем месте, и "HIGH", если на верхнем. В третьей строке выведите положение места Егора в том же формате

Примечание

В этой задаче всего 50 тестов, каждый оценивается в 2 балла независимо от других.

Примеры

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

1 2

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

YES
LOW
HIGH

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

1 5

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

NO
LOW
LOW

#113100

Три сына

Темы: [Остатки] [Конструктив]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 2 день, Три сына ] [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 2 день, Задача A ]

Во владениях короля Флатландии находится прямая дорога длиной $n$ километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.

У короля три сына: младший, средний и старший. Король решил, что в заповедник не войдут участки лесного массива, которые он оставит сыновьям в наследство. При составлении завещания король хочет, чтобы для участков выполнялись следующие условия:

каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры $a \times a, b \times b$ и $c \times c$;
стороны квадратов должны полностью покрывать дорогу: величина a + b + c должна быть равна $n$;
участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство $a < b < c$;
суммарная площадь участков $a^2 + b^2+ c^2$ должна быть минимальна.

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

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

Входной файл содержит одно целое число $n$ ($6 \le n \le 10^9$ ).

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

Выходной файл должен содержать три целых положительных числа, разделенных пробелами: $a$, $b$ и $c$ – длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.

Пояснение к примеру

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Подзадача 1 (25 баллов)

$n \le 50$

Подзадача 2 (25 баллов)

$n \le 2000$

Подзадача 3 (25 баллов)

$n \le 40000$

Подзадача 4 (25 баллов)

$n \le 10^9$

Примеры

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

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

1 2 3