Страница: << 1 2 3 4 5 6 7 >> Отображать по:

#111878

Взвешивание камней

Темы: [Алгоритмы сортировки] [Жадный алгоритм] [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Жаутыковские олимпиады, 2011, Задача D ]

Джек нашел \(N\) камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий 2 и так далее, самый тяжелый получил номер \(N\).

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

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

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

Первая строка содержит целое число \(N\) (1 \(\le\) \(N\) \(\le\) 100000).

Каждая из следующих \(N\) строк содержит по два целых числа: \(R\) (1 \(\le\) \(R\) \(\le\) \(N\)) и \(S\) (1 \(\le\) \(S\) \(\le\) 2). \(R\) номер камня, который будет положен на чашу \(S\). Все \(R\) будут различны.

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

Выведите \(N\) строк по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

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

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

<
>
>
?
>

#112038

Межрегиональная олимпиада

Темы: [Жадный алгоритм]

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

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая \(i\)-я задача (1 ≤ \(i\) ≤ \(n\)) становится доступной участникам в свой момент времени \(s_i\). При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть \(t_i\) минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение \(i\)-й задачи участник получает \(c_i\) баллов.

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

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

Формат входного файла

Первая строка входного файла содержит одно целое число \(n\) (1 ≤ \(n\) ≤ \(10^5\)) количество задач на олимпиаде.

Последующие \(n\) строк содержат описания задач, по три числа на каждой строке: \(s_i\) момент появления \(i\)-й задачи в минутах, \(t_i\) время, отведенное на ее решение в минутах, и \(c_i\) сколько баллов получит участник за решение этой задачи (1 ≤ \(s_i\), \(t_i\), \(c_i\) ≤ \(10^9\)).

Формат выходного файла

Первая строка выходного файл должна содержать одно число – максимальное количество баллов, которое сможет получить Артур на олимпиаде.

Вторая строка должна содержать одно целое число \(m\) - количество задач, которые надо решить при оптимальном выборе.

Третья строка должна содержать \(m\) разделенных пробелом целых чисел - номера этих задач в порядке их решения. Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.

Если оптимальных ответов несколько, необходимо вывести любой из них.

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

В первом примере Артур успевает решить все задачи и получить три балла.

Во втором примере Артуру выгоднее решать последнюю задачу и получить за нее три балла, чем решать только первые две и получить два балла.

Система оценивания

Частичные правильные решения для тестов, в которых все \(c_i\) одинаковы и \(n\) ≤ 1000, оцениваются из 30 баллов.

Частичные правильные решения для тестов, в которых все \(c_i\) одинаковы, оцениваются из 50 баллов.

Частичные правильные решения для тестов, в которых \(n\) ≤ 1000, оцениваются из 50 баллов.

Примеры

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

2
1 1 1
2 2 2

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

3
2
1 2

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

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

3
1
3

#112559

Up and Down

Темы: [Динамическое программирование по подстрокам] [Жадный алгоритм]

Источники: [ Личные олимпиады, Интернет-олимпиады, Google Code Jam, Up and Down ]

Дана последовательность попарно различных чисел A = [ A ₁ , A ₂ , ..., A _N ] , требуется переставить числа так, чтобы было верно A ₁ < A ₂ < ... < A _m > A _{m

+ 1} > ... > A _N (где m лежит между 1 и N включительно) Переставлять можно только пары соседних чисел, требуется минимизировать количество обменов.

1 ≤ A _i ≤ 10 ⁹ 1 ≤ N ≤ 1000 A _i попарно различны.

В задаче есть две группы тестов:

1. 1 ≤ N ≤ 10 - оценивается в 35 баллов

2. 1 ≤ N ≤ 1000 - оценивается в 65 баллов

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

В первой строке число N . Вторая строка содержит N чисел: A ₁ , ..., A _N .

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

Выведите одно число - минимальное количество обменов

Примеры
Входные данные
3 1 2 3
Выходные данные
0
Входные данные
5 1 8 10 3 7
Выходные данные
1

#112829

Ремонт дороги

Темы: [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2014, Задача C ]

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Длина автомобильной дороги составляет 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 ⁵ , будет оцениваться в 100 баллов.

Примеры
Входные данные
3 8 0 0 1 0 1 0 1 0
Выходные данные
2

#112830

Cookie Clicker

Темы: [Жадный алгоритм]

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

В игре 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 ⁹ , будет оцениваться в 100 баллов.

Примеры
Входные данные
50 3 100
Выходные данные
75
Входные данные
99 10 100
Выходные данные
100

Страница: << 1 2 3 4 5 6 7 >> Отображать по:

Выбрано
:
Отменить
|
Добавить в контест