--->
71 задач
<---
Источники
Дана лекционная аудитория, в которой несколько профессоров хотят прочесть свои лекции. Для составления расписания профессора подали заявки, вида [\(s_i, f_i\)) – время начала и конца лекции. Лекция считается открытым полуинтервалом, то есть какая-то лекция может начаться в момент окончания другой, без перерыва. Составьте расписание занятий так, чтобы выполнить максимальное количество заявок.
В первой строке вводится натуральное число \(N\), не более 1000 – общее количество заявок. Затем вводится \(N\) строк с описаниями заявок - по два числа в каждом \(s_i\) и \(f_i\).
Гарантируется, что \(s_i < f_i\). Время начала и окончания лекции – натуральное число, не превышает 1440 (в минутах с начала суток :) )
Выведите одно число – максимальное количество заявок, которые можно выполнить.
Во втором примере можно выполнить вторую и третью заявки.
1 5 10
1
3 1 5 2 3 3 4
2
В некоей воинской части есть сапожник. Рабочий день сапожника длится \(N\) минут. Заведующий складом оценивает работу сапожника по количеству починенной обуви, независимо от того, насколько сложный ремонт требовался в каждом случае. Дано \(k\) сапог, нуждающихся в починке. Определите какое максимальное количество из них сапожник сможет починить за один рабочий день.
В первой строке вводятся число \(N\) (натуральное, не превышает 1000), и число \(k\) (натуральное, не превышает 500). Затем идет \(k\) чисел – количество минут, которые требуются чтобы починить \(i\)-й сапог (времена – натуральные числа, не превосходят 100).
Выведите единственное число – максимальное количество сапог, которые можно починить за один рабочий день.
В первом примере можно починить либо первый и второй, либо второй и третий сапоги.
10 3 6 2 8
2
3 2 10 20
0
100 4 2 6 7 8
4
Андрей едет из пункта A в пункт B на автомобиле. Расстояние между этими пунктами равно \(N\) километров. Известно, что с полным баком автомобиль способен проехать k километров. Дана карта, на которой отмечены координаты бензоколонок, относительно пункта A. Определите минимальное число заправок, которые придется сделать Андрею чтобы успешно достичь пункта B. Известно, что при выезде из пункта A бак был полон.
В первой строке вводятся числа \(N\) и \(k\) (натуральные, не превосходят 1000). В следующей строке вводится количество бензоколонок \(S\), потом следует \(S\) натуральных чисел, не превосходящих \(N\) – расстояния от пункта A до каждой заправки. Заправки упорядочены по удаленности от пункта A.
Если при данных условиях пункта B достичь невозможно, то вывести число -1. Если решение существует, то вывести минимальное количество остановок на дозаправку, которое нужно чтобы достичь пункта B.
100 20 1 50
-1
100 50 1 50
1
100 100 3 10 20 80
0
В некотором королевстве есть \(N\) провинций. Король пожелал объединить все их под своей самодержавной властью. Естественно, чтобы никто не догадался об этих планах, он будет это делать поэтапно, а именно: раз в год он будет объединять какие-то две провинции в одну. Чтобы жителям обеих провинций не было обидно, новому территориальному образованию будет присвоено новое название, которое будет отличаться от обоих старых названий. Естественно, это потребует выпуска новых паспортов для жителей обеих провинций.
Очевидно, что если в первой провинции \(p_i\) жителей, а во второй – \(p_j\) жителей, то для них надо выпустить \(p_i + p_j\) новых паспортов.
На следующий год король объединяет еще какие-то две провинции. И так далее, до тех пор пока вся территория королевства не будет объединена в одну большую «провинцию». Определите, какое наименьшее количество новых паспортов придется выпустить, если король будет объединять провинции оптимально с этой точки зрения.
В первой строке вводится число \(N\) (натуральное, не превышает \(10^5\)) – количество провинций. Затем вводится \(N\) чисел – количество жителей каждой провинции (натуральное, не превосходит \(10^9\)). Гарантируется, что изначально в королевстве хотя бы две провинции.
Выведите единственное число – количество новых паспортов, которые придется выпустить.
2 2 6
8
3 6 2 4
18
Толик придумал новую технологию программирования. Он хочет уговорить друзей использовать ее. Однако все не так просто. \(i\)-й друг согласится использовать технологию Толика, если авторитет Толика будет не меньше \(a_i\) (авторитет выражается целым числом). Как только \(i\)-й друг начнет ее использовать, к авторитету Толика прибавится число \(b_i\) (попадаются люди, у которых \(b_i\) < 0). Помогите Толику наставить на путь истинный как можно больше своих друзей.
На первой строке содержатся два целых числа: Количество друзей у Толика \(n\) и первоначальный авторитет Толика \(a_0\) (\(-10^9 \le a_0 \le 10^9\)). Следующие \(n\) строк содержат пары целых чисел \(a_i\) и \(b_i\) (\(-10^9 \le a_i, b_i \le 10^9\)).
На первой строке выведите число \(m\) \(-\) максимальное число друзей, которых может увлечь Толик. На второй строке выведите \(m\) чисел \(-\) номера друзей в том порядке, в котором их нужно агитировать.
Подзадача 1 (50 баллов) \(1 \le n \le 10^3\)
Подзадача 2 (50 баллов) \(1 \le n \le 10^5\)
Пример
ввод:
5 1 1 3 6 -5 6 -4 2 2 2 -1
Вывод:4 1 4 3 5