У Билла большая семья: трое сыновей, девять внуков. И всех надо кормить. Поэтому Билл раз в неделю ходит в магазин.
Однажды Билл пришел в магазин и увидел, что в магазине проводится акция под названием «каждый \(k\)-й товар бесплатно». Изучив правила акции, Билл выяснил следующее. Пробив на кассе товары, покупатель получает чек. Пусть в чеке \(n\) товаров, тогда \(n/k\) округленное вниз самых дешевых из них достаются бесплатно.
Например, если в чеке пять товаров за 200, 100, 1000, 400 и 100 рублей, соответственно, и \(k = 2\), то бесплатно достаются оба товара по 100 рублей, всего покупатель должен заплатить 1600 рублей.
Билл уже выбрал товары, и направился к кассе, когда сообразил, что товары, которые он хочет купить, можно разбить на несколько чеков, и благодаря этому потратить меньше денег.
Помогите Биллу выяснить, какую минимальную сумму он сможет заплатить за выбранные товары, возможно разбив их на несколько чеков.
Первая строка входного файла содержит два целых числа \(n\), \(k\) (\(1 \le n \le 100\,000\), \(2 \le k \le 100\)) — количество товаров, которые хочет купит Билл и параметр акции «каждый \(k\)-й товар бесплатно».
Следующая строка содержит \(n\) целых чисел \(a_i\) (\(1 \le a_i \le 10\,000\)) — цены товаров, которые покупает Билл.
5 2 200 100 1000 400 100
1300
В приведенном примере Билл может разбить товары на два чека: в один чек пойдут товары за 1000 и за 400 рублей, товар за 400 рублей в этом чеке достанется бесплатно, а в другой — остальные товары, в нем бесплатно достанется один товар за 100 рублей. Итого Биллу придется заплатить 1300 рублей.
В Берляндии готовятся к проведению очередного этапа по гонкам машин класса I2011.
Известно, что машины этого класса не могут двигаться со скоростью, превышающей \(v\) м/с, при разгоне мощности двигателя хватает, чтобы развить любое ускорение, не превышающее \(a\) м/с\(^2\), а при торможении абсолютная величина ускорения не превышает \(b\) м/с\(^2\).
Трасса в Берляндии устроена следующим образом. Сначала идет длинная прямая, на которой машины могут разогнаться до любой скорости от 0 до \(v\). Затем следует линия старта, после которой следует отрезок длиной \(x\) м, поворот на 90\(^\circ\) и отрезок длины \(y\) м, после которого находится линия финиша. Линию финиша машина может пересечь на любой скорости.
Для прохождения поворота рекомендуется использовать управляемый занос. Для этого необходимо затормозить таким образом, чтобы скорость оказалась равна 0 в точности в повороте. После этого, сделав резкое движение рулем по направлению поворота и резко нажав газ, можно, не теряя времени, уйти на второй отрезок трассы.
Виталий планирует участвовать в соревнованиях. Он решил рассчитать, за какое минимальное время он сможет пройти трассу. Помогите ему это сделать.
Входной файл содержит пять целых чисел: \(v\), \(x\), \(y\), \(a\), \(b\) (\(1 \leq v, x, y, a, b \leq 10^6\)).
Выведите в выходной файл минимальное время, за которое возможно пройти всю трассу. Ваш ответ должен иметь абсолютную или относительную погрешность не больше \(10^{-8}\).
4 10 12 1 2
8.5
В приведенном примере следует действовать так. На прямой разгона следует разогнаться до максимальной возможной скорости в 4 м/с. После старта следует проехать 6 м на максимальной возможной скорости за 1.5 с, затем за 2 с затормозить до 0, используя максимальное возможное торможение, заодно проехав оставшиеся 4 м до поворота. Войдя с заносом в поворот, следует нажать на газ и с максимальным ускорением разогнаться за 4 с до максимальной скорости в 4 м/с, пройдя за это время 8\,м. После этого оставшиеся 4 м до финиша следует пройти за 1 с на максимальной скорости. Общее время на прохождение трассы равно \(1.5+2+4+1=8.5\) с.
Члены жюри Всероссийской командной олимпиады школьников по программированию очень любят пить чай. Но, к сожалению, в их распоряжении всего один чайник, имеющий объем \(v\) мл. Работа жюри хорошо отлажена, поэтому точно известно, кто и когда отправиться пить чай, и сколько воды ему для этого нужно.
Рассмотрим действия, предпринимаемые членами жюри для получения желанного напитка.
Когда человек из жюри подходит к чайнику, то если никого больше у чайника нет, он смотрит, достаточно ли в чайнике воды. Если в чайнике не хватает воды для этого человека, то он доливает в чайник воды до полного объема в \(v\) мл. Если же воды достаточно, то вода в чайник не доливается. После этого чайник включается и доводит воду до температуры 100 градусов. После этого член жюри наливает себе необходимый объем кипятка для заварки чая и отходит от чайника.
Если в момент прихода к чайнику член жюри обнаруживает других людей, ожидающих кипятка, то он становится в очередь и дожидается, пока все предыдущие люди выполнят свои действия с чайником.
Температура кипения воды составляет 100 градусов Цельсия. Мощность чайника составляет \(N\), что означает, что если в чайнике \(x\) мл воды, то температура воды в чайнике изменяется по формуле \(T(t) = T_0 + \frac{Nt}{x}\), где \(T_0\) — температура воды в момент включения чайника, а \(t\)~— время в секундах, прошедшее с момента включения чайника. Когда температура воды достигает 100 градусов, чайник автоматически выключается.
Когда чайник выключен, вода в нем начинает остывать. Вне зависимости от количества жидкости в чайнике, температура воды падает со скоростью \(k\) градусов в секунду. Когда вода достигает комнатной температуры в 20 градусов, остывание прекращается.
Заливаемая в чайник вода имеет комнатную температуру 20 градусов. При доливании воды в чайник температура воды усредняется, а именно, если в чайнике было \(w\) мл воды температуры \(T\), то температура воды в чайнике после его заполнения станет \(\frac{wT + 20(v-w)}{v}\).
Известны времена, когда члены жюри идут пить чай, а также количество кипятка им необходимое. Требуется для каждого члена жюри вывести в какой момент он начнет пить чай. Считается, что разливают воду по чашкам и заваривают чай члены жюри моментально, при этом всегда наливая себе ровно необходимый им объем. Изначально чайник пуст.
Первая строка входного файла содержит четыре целых числа \(m\), \(v\), \(N\) и \(k\) (\(1 \le m \le 100\,000\), \(1 \le v, N, k \le 1000\)) — количество членов жюри, пьющих чай, объем чайника в мл, мощность чайника и скорость остывания воды в чайнике. Далее следуют \(m\) строк — описания людей, пьющих чай. В каждой строке два целых числа \(t_i\) и \(a_i\) (\(1 \le t_i \le 10^6\); \(1 \le a_i \le v\)) — время в секундах от начала олимпиады, когда член жюри отправиться пить чай, и необходимый ему объем воды в мл. Никакие два члена жюри не отправляются пить чай одновременно.
В выходной файл выведите \(m\) строк по одному числу в каждой — время в секундах от начала олимпиады, когда соответствующий член жюри начнет пить чай. Ответ должен иметь абсолютную или относительную погрешность не более \(10^{-7}\).
3 1000 200 1 1 500 501 300 551 300
401.0 701.0 1021.0
Совсем скоро начнется первый тур очередной всероссийской командной олимпиады школьников по палеонтологии (ВКОШП). На олимпиаду приехали команды из \(n\) школ, от каждой школы приехало ровно по две команды. Команды уже заняли свои места, когда обнаружилось, что некоторые команды из одной школы сидят слишком близко. Перед организаторами олимпиады встала серьезная задача — пересадить участников олимпиады.
Столы, за которыми сидят команды, расставлены в один ряд. Расстояние между рабочими местами соседних команд оказалось равно 10 метрам. Организаторы хотят, чтобы минимальное расстояние между двумя командами из одной школы было как можно больше.
Пересаживая команду, организатором необходимо перенести на новое место все оборудование, приготовленное командой для исследований. Поэтому организаторы хотят пересадить команды так, чтобы сумма расстояний между старыми и новыми рабочими местами команд была как можно меньше.
Например, пусть в соревновании принимают участие по две команды школ 1, 2, 3 и 4. Пусть исходно команды распределены по рабочим местам следующим образом: 1, 3, 2, 2, 1, 4, 4, 3 (для каждой команды указан номер школы, которую она представляет). При таком распределении по рабочим местам команды из школы 2 сидят слишком близко, как и команды из школы 4. Пересадив команды в следующем порядке: 1, 3, 2, 4, 1, 3, 2, 4, жюри может добиться своего: команды из одной школы сидят на местах, расстояние между которыми не меньше 40\,м, большего расстояния добиться нельзя. Сумма расстояний между старыми и новыми позициями для данного примера равна \(0 + 0 + 0 + 20 + 0 + 20 + 30 + 10 = 80\)\,м, для исходного распределения команд она минимальна.
Вам задано исходное распределение команд по рабочим местам. Требуется пересадить их так, чтобы минимальное расстояние между командами из одной школы было как можно больше. При этом среди возможных новых размещений команд следует выбрать такое, чтобы сумма расстояний между старыми и новыми местами рабочими команд была минимально возможной.
В первой строке входного файла задано число \(n\) — количество команд (\(1 \le n \le 100\)). Во второй строке задано исходное распределение команд по рабочим местам — последовательность \(a_1, a_2, \ldots, a_{2n}\). Для каждой команды указан номер школы, которую она представляет. Гарантируется, что последовательность состоит из чисел от одного до \(n\) и каждое число встречается ровно два раза.
В единственную строку выходного файла выведите, каким образом следует пересадить команды, чтобы минимальное расстояние между командами из одной школы было как можно больше. При этом среди возможных новых размещений команд следует выбрать такое, чтобы сумма расстояний между старыми и новыми рабочими местами команд была минимально возможной. Если оптимальных ответов несколько, можно вывести любой из них.
4 1 3 2 2 1 4 4 3
1 3 2 4 1 3 2 4
Маленький Вася очень любит поезда. На день рождения ему подарили игрушечную железную дорогу. В комплект к железной дороге входит поезд, состоящий из \(n\) вагонов, пронумерованных числами от 1 до \(n\).
Любимым занятием Васи стала сортировка поездов с использованием специального сортировочного тупика.
Справа к тупику подъезжает поезд, составленный из всех \(n\) вагонов. Затем вагоны по одному загоняются в сортировочный тупик и выгоняются из него налево. Васе нравится, если ему удается отсортировать поезд с помощью сортировочного тупика — добиться того, чтобы слева от тупика вагоны были расположены по порядку от 1 до \(n\).
Например, пусть в исходном поезде 4 вагона, которые следуют в порядке 3, 1, 2, 4. Его можно отсортировать следующим образом. Загоняем вагон 3 в тупик. Загоняем вагон 1 в тупик. Выгоняем вагон 1 из тупика. Загоняем вагон 2 в тупик. Выгоняем вагон 2 из тупика. Выгоняем вагон 3 из тупика. Загоняем вагон 4 в тупик. Выгоняем вагон 4 из тупика.
Не все поезда можно отсортировать таким образом. Например, поезд из 3 вагонов, следующих в порядке 2, 3, 1, отсортировать нельзя.
Вася выписал на листке в лексикографическом порядке все поезда длины \(n\), которые можно отсортировать с помощью тупика. Поезд \((a_1, a_2, \ldots, a_n)\) идет раньше поезда \((b_1, b_2, \ldots, b_n)\) в лексикографическом порядке, если существует такое \(i\) (\(1 \le i \le n\)), что для всех \(j < i\) выполняется \(a_j = b_j\), а \(a_i < b_i\). Например, все поезда из трех вагонов, которые можно отсортировать с помощью тупика, в лексикографическом порядке выписываются следующим образом: \((1, 2, 3)\), \((1, 3, 2)\), \((2, 1, 3)\), \((3, 1, 2\)), \((3, 2, 1)\).
Вася потерял свой листок, и его интересует вопрос: какой поезд был выписан на его листке под номером \(k\). Помогите ему выяснить это.
Входной файл содержит два целых числа — \(n\) и \(k\) (\(1 \le n \le 30\), \(1 \le k \le 10^{18}\)).
Выведите в выходной файл \(n\) целых чисел: \(k\)-й в лексикографическом порядке поезд из \(n\) вагонов, который можно отсортировать с помощью тупика.
Если с помощью тупика можно отсортировать менее \(k\) поездов из \(n\) вагонов, выведите \(-1\).
4 1
1 2 3 4
4 3
1 3 2 4
4 15
-1