--->
71 задач
<---
Источники
Дана последовательность попарно различных чисел A = [ A 1 , A 2 , ..., A N ] , требуется переставить числа так, чтобы было верно A 1 < A 2 < ... < A m > A m + 1 > ... > A N (где m лежит между 1 и N включительно) Переставлять можно только пары соседних чисел, требуется минимизировать количество обменов.
1 ≤ A i ≤ 10 9 1 ≤ N ≤ 1000 A i попарно различны.
В задаче есть две группы тестов:
1.
1 ≤
N
≤ 10
- оценивается в 35 баллов
2.
1 ≤
N
≤ 1000
- оценивается в 65 баллов
В первой строке число N . Вторая строка содержит N чисел: A 1 , ..., A N .
Выведите одно число - минимальное количество обменов
3 1 2 3
0
5 1 8 10 3 7
1
У мальчика Вити скоро день рождения, который он хочет провести с друзьями. Какой же праздник без праздничной олимпиады? Для своих друзей Витя подготовил олимпиаду по программированию.
Когда все гости собрались, именинник распределил их по m командам. Витя очень старался сбалансировать силы команд, и у него это получилось. Каждую из предложенных n задач олимпиады любая команда решает ровно за a i минут и всегда с первой попытки. Ребята не любят распыляться, поэтому если команда берется писать задачу i , то все ее участники непрерывно решают задачу в течении a i минут. При этом команда может начинать решать следующую задачу сразу после того, как решила предыдущую.
Однако, Витя не хотел поссорить своих друзей, поэтому исключил элемент борьбы между командами — команды не соперничают, а помогают друг другу. Целью команд на олимпиаде является решение всех задач. Таким образом каждую задачу решает только одна команда. При этом друзьям засчитывается штрафное время, равное числу минут, прошедших от начала олимпиады до момента сдачи задачи. Единственная цель, которую преследуют друзья — сдать все задачи с наименьшим суммарным штрафным временем.
Например, пусть участвуют две команды, которым предложено в олимпиаде три задачи с временами решения 5, 10 и 15 минут. Пусть первая команда решает сначала вторую, а потом первую задачу. Таким образом за решение второй задачи друзья получат 10 штрафных минут, а за решение первой 15. Вторая команда с начала олимпиады решает только третью задачу, за которую друзья получат 15 штрафных минут. В сумме друзья Вити получат 40 штрафных минут.
В то время, когда друзья будут решать задачи, Витя будет управлять порядком, в котором команды будут их решать. Помогите Вите — напишите программу, которая вычислит наименьшее суммарное штрафное время, требуемое для сдачи всех задач.
В первой строке входного файла содержатся два числа n и m — число задач и команд, соответственно ( 0 ≤ n ≤ 50000 , 1 ≤ m ≤ 10000 ). Во второй строке содержится n целых чисел a i — количество времени, необходимое для решения задачи i любой из команд ( 0 ≤ a i ≤ 30 ).
Выведите в выходной файл наименьшее суммарное штрафное время, которое могут получить друзья Вити за решение всех задач.
3 2 10 15 5
35
2 3 23 30
53
Коренной житель Ирландии лепрекон Патрик однажды крупно поссорился со своей женой Клариссой и решил в срочном порядке убежать на остров Бора-Бора. Для этого у мудрого Патрика есть n спрятанных на одной прямой горшочков с лепреконским золотом. Ссора произошла спонтанно, поэтому Патрик не смог запастись достаточным количеством магических амулетов и талисманов, а это значит, что его магических сил хватит лишь на одну телепортацию, но зато в любое место, например — к любому из горшочков с золотом. Эту телепортацию необходимо использовать, до начала сбора горшочков с золотом.
Так как лепреконы по природе своей не очень хорошие бегуны, без помощи телепортаций Патрик может перемещаться со скоростью 1 метр в минуту. Но на один из горшочков Кларисса наложила заклинание исчезновения, и он пропадет через t минут, но ровно в t минут Патрик еще может успеть схватить исчезающий горшочек. Помогите Патрику за минимальное время собрать все горшочки с золотом! Если он не заберет хотя бы один из них, ему не хватит золота на путешествие.
В первой строке число n — количество горшочков с золотом — и число t — время исчезновения (в минутах) одного из них ( 2 ≤ n , t ≤ 100 ). В следующей строке n чисел — координаты горшочков в метрах. Все числа различны и по абсолютной величине не превосходят 100. Координаты горшочков даны в порядке возрастания. В следующей строке записан номер горшочка, который исчезнет через t минут.
В первой строке выведите минимальное время, которое потребуется Патрику для сбора всего золота. В следующей строке выведите n чисел — порядок, в котором следует собирать горшочки.
5 5 1 4 9 16 25 2
24 1 2 3 4 5
6 4 1 2 3 6 8 25 5
31 5 1 2 3 4 6
Длина автомобильной дороги составляет N километров. Часть дороги необходимо отремонтировать. При обследовании дорога была разбита на N участков длиной 1 километр, и для каждого участка было определено, нуждается ли он в ремонте или нет, после чего был составлен план дороги, на котором отмечены участки, нуждающиеся в ремонте.
Для ремонта дороги можно привлечь несколько компаний-подрядчиков. Каждая компания может отремонтировать только непрерывный фрагмент дороги. При этом из-за требований антимонопольного законодательства длина фрагмента дороги, который ремонтирует одна компания, не должна превышать L километров (даже если на фрагменте, который ремонтирует одна компания, есть не нуждающиеся в ремонте участки, общая длина данного фрагмента не должна превышать L километров).
Определите, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги.
Первая строка входных данных содержит целое число L ( L > 0 ) — максимальную длину фрагмента дороги, который может отремонтировать одна компания. Во второй строке входных данных записано целое число N ( N > 0 ) — длина всей дороги. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующий участок дороги нуждается в ремонте, число 0 — что участок не требует ремонта.
Программа должна вывести одно целое число — минимальное количество компаний-подрядчиков, которое необходимо привлечь для ремонта дороги.
В тесте из примера первая компания может отремонтировать участок номер 3, вторая компания — участки с 5 по 7.
Ограничения и система оценивания
Решение, правильно работающее в случае, когда числа L и N не превосходят 10, будет оцениваться в 30 баллов.
Решение, правильно работающее в случае, когда числа L и N не превосходят 1000, будет оцениваться в 60 баллов.
Решение, правильно работающее в случае, когда числа L и N не превосходят 10 5 , будет оцениваться в 100 баллов.
3 8 0 0 1 0 1 0 1 0
2
В игре Cookie Clicker игрок зарабатывает печеньки (cookies), щёлкая мышкой по изображению большой печеньки. Тратя заработанные печеньки, игрок может покупать различные усовершенствования (ферму, фабрику и т. д.), которые также производят дополнительные печеньки.
Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1 + P печенек в секунду, две фабрики — 1 + 2 P печенек, три фабрики — 1 + 3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.
Оригинальная игра никогда не заканчивается, но мы будем считать, что целью игры является набрать хотя бы N печенек. Определите минимальное время, за которое может быть достигнута цель игры.
Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).
Программа должна вывести одно целое число — минимальное время в секундах, за которое игрок может получить не менее N печенек.
В первом тесте: через 50 секунд после начала игры у игрока будет 50 печенек, и он сможет купить фабрику. После этого он будет получать 4 печеньки в секунду, и на производство 100 печенек понадобится еще 25 секунд.
Во втором тесте: игрок сможет набрать 100 печенек за 100 секунд, при этом фабрику покупать нет смысла.
Ограничения и система оценивания
Решение, правильно работающее в случае, когда все входные числа не превосходят 1000, а для получения N печенек за минимальное время нужно приобрести не более одной фабрики, будет оцениваться в 30 баллов.
Решение, правильно работающее в случае, когда все входные числа не превосходят 1000, будет оцениваться в 70 баллов.
Решение, правильно работающее в случае, когда все входные числа не превосходят 10 9 , будет оцениваться в 100 баллов.
50 3 100
75
99 10 100
100