В стране Флатландия решили построить легкоатлетический манеж с 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 |
Около прямолинейного забора, состоящего из N одинаковых бетонных плит, проводится конкурс граффити, в котором участвуют M граффити-художников. Художники должны разрисовать все плиты своими произведениями за наименьшее возможное время.
Плиты пронумерованы числами от 1 до N, граффити-художники имеют номера от 1 до M. Первоначально i-й граффити-художник находится около плиты с заданным номером pi. Каждому художнику требуется b минут на разрисовывание любой плиты. Каждую плиту должен разрисовать ровно один граффити-художник.
В начале работы, а также после разрисовывания любой плиты граффити-художник может перейти к любой неразрисованной плите. Время перемещения граффити-художника от любой плиты к соседней с ней одинаково и равно a минут. Таким образом, чтобы перейти от плиты с номером i к плите с номером j художнику требуется a×|i – j| минут.
Требуется написать программу, которая поможет участникам конкурса разрисовать все плиты за минимальное возможное время.
В первой строке входного файла указаны числа N — количество плит в заборе и M — количество граффити-художников (1 ≤ N, M ≤ 100000). Во второй строке заданы два целых числа: a — количество минут, которое требуется для перехода от любой плиты к соседней, и b — количество минут, которое требуется граффити-художнику на разрисовывание одной плиты (1 ≤ a, b ≤ 106). В третьей строке заданы M чисел p1, p2, …, pM — начальные положения граффити-художников (1 ≤ pi ≤ N).
В первую строку выходного файла выведите минимальное количество минут, требуемых художникам для выполнения работы.
В последующих M строках выведите описание действий художников. В i-й из этих строк должно содержаться описание действий i-го художника: количество плит, которые должен разрисовать этот художник, и номера этих плит в очередности их разрисовывания. Если оптимальных решений несколько, можно вывести любое из них.
Примечание
Решения, корректно работающие при M ≤ 2, будут оцениваться из 40 баллов.
10 2 19 56 9 2
375 5 10 9 8 7 6 5 1 2 3 4 5
В кабинете информатики есть старый стековый калькулятор. Он содержит K ячеек памяти, организованных в виде стека. Первая ячейка называется вершиной стека. На индикаторе калькулятора отображается содержимое вершины стека, если стек непуст.
Над стеком может выполняться операция проталкивания. Применение этой операции приводит к записи числа на вершину стека. Перед этим, если в стеке уже были числа, то каждое из них перемещается в ячейку с номером на единицу больше. Если в стеке уже находится K чисел, то выполнение операции проталкивания невозможно.
Калькулятор позволяет выполнять арифметические операции. Они применяются к числам, хранящимся во второй и первой ячейках стека. Результат операции записывается в первую ячейку стека, а число из второй ячейки удаляется. После этого, если третья ячейка непуста, то число из неё переписывается во вторую, если есть число в четвертой ячейке — оно переписывается в третью и так далее до последней занятой ячейки, которая становится пустой. Для выполнения арифметической операции в стеке должно быть хотя бы два числа. Например, при выполнении операций сложения или умножения, значения соответственно суммы или произведения чисел из первой и второй ячеек помещаются на вершину стека. Операция вычитания выполняется так: из содержимого второй ячейки стека вычитается содержимое первой ячейки.
Известно, что калькулятор неисправен. Из цифровых клавиш работает только клавиша «1». Нажатие этой клавиши приводит к проталкиванию в стек числа 1. Например, попытка набрать число 11, два раза нажав клавишу «1», приводит к тому, что в стек два раза проталкивается число 1. Из операций работают только сложение (клавиша «+»), умножение (клавиша «*») и вычитание (клавиша «-»). Если в результате вычитания получено отрицательное число, то калькулятор зависает.
Легко заметить, что на индикаторе возможно получить произвольное натуральное число. Например, чтобы получить число 3, необходимо дважды нажать клавишу «1», затем клавишу «+» (на индикаторе после этого появится число 2), затем один раз нажать клавишу «1» и один раз — клавишу «+». При K > 2 того же результата можно достичь иначе, трижды нажав клавишу «1», а затем два раза клавишу «+». Дополнительно используя операции умножения и вычитания, в некоторых случаях число N можно получить быстрее, чем сложив N единиц.
Требуется написать программу, которая определяет, каким образом можно получить на индикаторе калькулятора заданное число N, выполнив минимальное количество нажатий клавиш. Стек изначально пуст.
В единственной строке входного файла записаны два натуральных числа — N и K (1 ≤ N ≤ 109, 2 ≤ K ≤ 100).
В первой строке выходного файла выведите минимальное количество нажатий клавиш, необходимых для получения числа N. Если число нажатий не превосходит 200, то дополнительно выведите во второй строке оптимальную последовательность нажатий, приводящих к появлению данного числа на индикаторе.
Последовательность необходимо выводить без пробелов. Клавиши обозначаются символами «1» — протолкнуть число 1 в стек, «+» — выполнить операцию сложения, «*» — выполнить операцию умножения, «-» — вычесть из значения второй ячейки стека значение первой ячейки.
В результате выполнения выведенной последовательности нажатий на индикаторе должно отображаться число N. Если оптимальных последовательностей нажатий несколько, разрешается выводить любую из них.
Примечания
Решения, корректно работающие при N ≤ 100 и K ≤ 10, будут оцениваться из 40 баллов.
Решения, корректно работающие при N ≤ 106 и K ≤ 100, будут оцениваться из 80 баллов.
1 2
1 1
9 3
11 11+1+11+1+*
Cреди всех прямоугольных параллелепипедов с натуральными длинами сторон и площадью поверхности не более \(n\) найти тот, объём которого максимален.
Начинающий программист Поликарп очень любит дарить подарки, особенно в коробках. Он давно заметил, что если коробка красиво оформлена, то радость от подарка возрастает многократно. Любой обёрточной бумаге он предпочитает клетчатую. В самом деле, после распаковки подарка на ней можно играть в крестики-нолики, морской бой, точки, а также решать задачи и писать программы.
Поликарп очень аккуратен. Он упаковывает подарок в коробку, имеющую форму прямоугольного параллелепипеда, и оклеивает всю её поверхность клетчатой бумагой. При этом каждая грань коробки представляет собой прямоугольник, состоящий из целых клеток. На рисунке изображён пример такой упаковки подарка.
В настоящий момент Поликарп собирается поздравить свою подругу, недавно вернувшуюся с очередной олимпиады. Он хочет подарить ей подарок в большой и красивой коробке.
У Поликарпа в наличии есть лист клетчатой бумаги, состоящий из \(n\) клеток. Каким будет максимальный объём коробки, которую можно оклеить с использованием этого листа бумаги описанным выше способом? Поликарп может разрезать лист клетчатой бумаги по границам клеток произвольным образом и оклеивать коробку получившимися фигурами, поэтому форма листа не важна, а имеет значение только количество клеток на нём. Поликарп может использовать для оклеивания коробки не все клетки.
Напишите программу, которая по заданному количеству клеток \(n\) находит размеры коробки максимального возможного объема.
Входной файл содержит одно целое число \(n\) (\(6\le n\le10^{13}\)) — количество клеток на листе клетчатой бумаги.
Выведите в первую строку выходного файла максимальный объём коробки, которую может подарить Поликарп. Объём следует выводить в «кубических клетках», то есть единицей измерения является куб со стороной, равной длине стороны клетки.
Во вторую строку выведите ширину, длину и высоту искомой коробки. Единица измерения — размер клетки. Числа разделяйте пробелами. Если решений несколько, то выведите любое из них.
Система оценивания
Решения, корректно работающие при \(n\le5\,000\), будут оцениваться из 30 баллов, а решения, корректно работающие при \(n\le10^8\), будут оцениваться из 70 баллов.
6
1 1 1 1
24
8 2 2 2
Задано множество из \(n\) станций и \(m\) трубопроводов, соединяющих некоторые пары станций. Требуется выбрать множество из \(k\) станций, чтобы один из двух концов каждого трубопровода лежал в выбранном множестве. Если построить граф, в котором станции будут служить вершинами, а трубопроводы — рёбрами, то искомое множество будет являться вершинным покрытием в этом графе.
Ханты-Мансийский автономный округ — Югра является важнейшим нефтяным регионом России. Добыча нефти составляет 267 млн т в год, её транспортировка осуществляется по трубопроводам, общая длина которых превышает длину экватора Земли.
Система транспортировки нефти представляет собой совокупность \(n\) распределительных станций и \(m\) трубопроводов. Каждый трубопровод соединяет две различные станции. Между любыми двумя станциями проложено не более одного трубопровода.
Эффективность работы станций существенно зависит от вязкости нефти. Поэтому компания «ЮграНефтеТранс», в ведении которой находится сеть трубопроводов, заказала инновационному исследовательскому предприятию разработку и изготовление новых сверхточных датчиков вязкости на основе самых современных технологий.
Изготовление датчиков — процесс трудоёмкий и дорогостоящий, поэтому было решено изготовить \(k\) датчиков (\(k\le40\)) и выбрать \(k\) различных станций, на которых датчики будут установлены. Необходимо осуществить выбор станций так, чтобы датчики контролировали все трубопроводы: для каждого трубопровода хотя бы один датчик должен быть установлен на станции, где начинается или заканчивается этот трубопровод.
Напишите программу, которая проверяет, существует ли требуемое расположение датчиков, и в случае положительного ответа находит это расположение.
В первой строке входного файла записаны три натуральных числа — \(n\), \(m\) и \(k\) (\(k\le n\le2000\), \(1\le m\le10^5\), \(1\le k\le40\)). Далее следуют \(m\) строк, каждая из которых описывает один трубопровод. Трубопровод задаётся двумя целыми числами — порядковыми номерами станций, которые он соединяет. Станции пронумерованы от 1 до \(n\). Гарантируется, что к любой станции подведён хотя бы один трубопровод и между любыми двумя станциями проложено не более одного трубопровода. Числа в каждой строке разделены пробелами.
В первую строку выходного файла выведите слово «Yes», если требуемое расположение датчиков существует, в противном случае — слово «No». В случае положительного ответа выведите во вторую строку выходного файла \(k\) различных целых чисел — номера станций, на которых необходимо установить датчики. Номера можно выводить в любом порядке. Если существует несколько подходящих расположений датчиков, выведите любое из них. Разделяйте числа во второй строке пробелами.
Система оценивания
Решения, корректно работающие при \(n\le100\) и \(k\le10\), будут оцениваться из 60 баллов.
9 12 4 1 2 2 3 1 4 4 5 1 6 6 7 1 8 8 9 2 5 4 7 6 9 8 3
Yes 2 4 6 8
8 12 4 7 4 7 5 3 1 2 8 4 3 3 2 6 1 1 2 1 4 6 5 8 6 8 7
No
4 3 1 3 1 3 2 3 4
Yes 3