--->
71 задач
<---
Источники
Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами \(A\), \(B\) и \(C\) (\(A \lt B \lt C\)) сидят три кузнечика, которые играют в чехарду по следующим правилам:
1. На одной плитке может находиться только один кузнечик.
2. За один ход один из двух крайних кузнечиков (то есть с плитки \(A\) или с плитки \(C\)) может перепрыгнуть через среднего кузнечика (плитка \(B\)) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между \(B\) и \(C\) или \(A\) и \(B\) соответственно). Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.
Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).
Даны три числа: \(A\), \(B\), \(C\). Определите, какое наибольшее число ходов может продолжаться игра.
Программа получает на вход три целых числа \(A\), \(B\) и \(C\) (\(1\le A \lt B \lt C\leq 1000\)), записанных в отдельных строках.
Выведите одно число — наибольшее количество ходов, которое может продолжаться игра.
1 4 6
2
Джек нашел \(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 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.
5 1 2 3 1 2 1 4 2 5 1
< > > ? >
Всем известно, что основной целью любого крупного правительственного проекта во Флатландии является освоение бюджетных средств (разумеется, по назначению). В настоящее время во Флатландии ведется работа над m национальным проектами, i-й проект может освоить \(s_i\) миллионов Флатландских тугриков в день.
Правительство Флатландии планирует выделить \(n\) грантов для финансирования проектов, каждый по p миллионов Флатландских тугриков. Деньги i-го из грантов будут доступны для освоения, начиная с дня \(r_i\). Когда очередной грант становится доступен для освоения, его можно отдать некоторому проекту. Этот проект осваивает деньги гранта в течение \(\lceil\frac{p}{s_i}\rceil\) дней. Проект не может одновременно осваивать деньги нескольких грантов.
Премьер-министр Флатландии господин Тупиков хочет выяснить, за какое время удастся освоить все деньги, выделенные в рамках грантов. Помогите ему выяснить самый ранний день, когда можно полностью освоить все деньги грантов.
Первая строка входного файла "budget.in" содержит числа m, n и p (1 ≤ m ≤ 100, 1 ≤ n ≤ 100, 1 ≤ p ≤ \(10^9\)). Вторая строка содержит m целых чисел: \(s_1\), \(s_2\), . . . , \(s_m\) (1 ≤ \(s_i\) ≤ \(10^9\)). Третья строка содержит n целых чисел: \(r_1\),\(r_2\),...,\(r_n\) (1 ≤ ri ≤ \(10^9\)).
Первая строка выходного файла "budget.out" должна содержать одно целое число — минимальный день, к которому можно полностью освоить все деньги грантов.
Одна из возможных оптимальных схем освоения устроена следующим образом: грант 1 отдается первому проекту, который осваивает его в течение 11 дней. Остальные гранты отдаются второму проекту, грант 2 осваивается в течение дней 3–7, грант 3 в течение дней 8–12 и грант 4 в течение дней 13–17. Заметим, что грант 4 появляется в день 12, но назначается только в день 13.
2 4 22 2 5 1 3 8 12
17
На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая \(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 2 1 3 2 1 2 4 3
3 1 3
Для хранения двух агрессивных жидкостей \(A\) и \(B\) используется емкость с многослойной перегородкой, которая изготавливается из имеющихся \(N\) листов. Для каждого листа \(i\) (\(i\) = 1, ..., \(N\)) известно время его растворения жидкостью \(A\) - \(a_i\) и жидкостью \(B\) - \(b_i\). Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа. Требуется спроектировать такую перегородку, время растворения которой было бы максимальным.
В первой строке входного файла записано число \(N\) (1 ≤ \(N\) ≤ 256). В каждой из последующих N строк содержатся два положительных вещественных числа \(a_i\) и \(b_i\), разделенные пробелом.
В первую строку выходного файла записать время растворения перегородки с точностью до 3 цифр после десятичной точки. В следующую строку файла записать номера листов в порядке их расположения от жидкости A к жидкости B, разделяя числа пробелами.
4 1 2 1 2 0.5 1.5 7 3.5
6.00000000 4 2 1 3