Вам необходимо нанять работников для строительного проекта. Заявление о приёме на работу подали N кандидатов, пронумерованных от 1 до N включительно. Каждый кандидат с номером k требует, чтобы в случае приёма его на работу ему платили не менее чем Sk долларов. Также для каждого кандидата с номером k известен его уровень квалификации Qk. Положение о строительной деятельности требует, чтобы вы платили работникам пропорционально их уровню квалификации относительно друг друга. Например, если вы нанимаете двух работников A и B таких что QA = 3 * QB, то вы обязаны платить работнику A ровно в три раза больше, чем вы платите работнику B. Вам разрешается платить работникам нецелое число денег. Более того, разрешается даже платить количество денег, которое не может быть записано с помощью конечного числа десятичных цифр, такое как треть или шестую долю доллара.
В вашем распоряжении есть W долларов, и вы хотите нанять как можно больше рабочих. Вы решаете кого нанимать и сколько им платить, но вы должны удовлетворить как требованиям работников о минимальном жаловании, так и требованиям положения о строительной деятельности. Естественно, что вам требуется уложиться в бюджет, равный W долларам.
Для данного строительного проекта уровень квалификации работников не имеет значения. Вы заинтересованы только в том, чтобы нанять как можно больше работников независимо от их уровня квалификации. Однако, если есть несколько способов достичь цели, то вы хотите выбрать такой, чтобы общая сумма денег, которую вы заплатите работникам, была как можно меньше. Если и этого можно достичь несколькими способами, то нет никакого различия между этими способами, и вас удовлетворит любой из них.
Напишите программу, которая по заданным требованиям к жалованию и уровням квалификации кандидатов, а также количеству денег, которое у вас есть, определяет, каких кандидатов вам требуется нанять. Вы должны нанять как можно больше из них и при этом потратить как можно меньше денег, соблюдая требования положения о строительной деятельности, описанные выше.
Ограничения
1 ≤ N ≤ 500 000 Число кандидатов.
1 ≤ Sk ≤ 20 000 Минимальное требование к жалованию кандидата номер k.
1 ≤ Qk £ 20 000Уровень квалификации кандидата номер k.
1 ≤ W ≤ 10 000 000 000Сумма денег, доступная вам.
Важное замечание
Максимальное значение W не может быть представлено 32-битным типом данных. Вам необходимо использовать 64-битный тип данных, такой как long long в C/C++ или int64 в Pascal, чтобы значение W можно было сохранить в одной переменной. Дополнительные подробности представлены на страницах с технической информацией.
Ваша программа должна читать из стандартного потока ввода следующие данные:
Ваша программа должна вывести в стандартный поток вывода следующие данные:
Первая строка должна содержать одно целое число H – количество работников, которых вы принимаете на работу.
Следующие H строк должны содержать список номеров кандидатов в произвольном порядке, которых вы выбрали для найма на работу (различные целые числа от 1 до N), по одному в каждой строке.
Система оценки
Для каждого из тестов, используемых для проверки решения этой задачи, вы получаете полный балл, если ваш выбор кандидатов помогает достигнуть всех ваших целей при удовлетворении всем заданным ограничениям. Если вы выведете корректно первую строку (то есть, корректное значение H), но при этом оставшаяся часть файла не будет соответствовать вышеописанным условиям, то вы получите 50% баллов за этот тест. Это правило также действует даже в случае, если оставшаяся часть файла отформатирована неправильно, но первая строка выведена правильно.
Для набора тестов общей стоимостью 50 баллов значение N не будет превосходить 5 000.
ПРИМЕРЫ
| Пример ввода | Пример вывода |
| 4 100 5 1000 10 100 8 10 20 1 | 2 2 3
|
Единственная комбинация, при которой вы можете позволить себе нанять двух рабочих и удовлетворить всем требованиям – это выбрать рабочих с номерами 2 и 3. Вы можете заплатить им 80 и 8 долларов, соответственно, таким образом, уложившись в бюджет 100 долларов.
| Пример ввода | Пример вывода |
| 3 4 1 2 1 3 1 3 | 3 1 2 3 |
В этом примере вы можете позволить себе нанять всех трёх рабочих. Вы платите 1 доллар рабочему с номером 1 и по 1.50 доллара рабочим с номерами 2 и 3, и таким образом, укладываетесь в ваш бюджет, равный 4 долларам.
| Пример ввода | Пример вывода |
| 3 40 10 1 10 2 10 3 | 2 2 3 |
В этом примере вы не можете позволить себе нанять всех трёх рабочих, так как это стоило бы вам 60 долларов, но вы можете позволить себе нанять любых двух из них. Вы выбираете рабочих с номерами 2 и 3, потому что в этом случае получается наименьшая сумма денег по сравнению с другими комбинациями из двух рабочих. Вы можете заплатить 10 долларов рабочему с номером 2 и 15 долларов рабочему с номером 3, общая сумма будет равна 25 долларам. Если бы вы наняли рабочих с номерами 1 и 2, то вам пришлось бы заплатить им хотя бы 10 и 20 долларов соответственно. Если бы вы выбрали рабочих с номерами 1 и 3, то вам пришлось бы заплатить им хотя бы 10 и 30 долларов соответственно.
В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые \(c\) цифр телефонов совпадают, а \((c+1)\)-я цифра различается, то стоимость сообщения составляет \((10-c)\) кредитов (\(0\le c\le9\)). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.
Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.
Напишите программу, определяющую цепочку доставки, для которой суммарная стоимость отправленных сообщений минимальна.
Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число \(n_i\) (\(1\le n_i\le100\,000\)) — количество друзей Поликарпа в соответствующем городе, после которой следуют \(n_i\) строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех \(n_i\) не превосходит 100 000. Все номера телефонов во входных данных различны.
В первой строке выходного файла выведите минимальную возможную стоимость передачи информации \(w\) и количество задействованных в цепочке телефонных номеров \(k\). Далее выведите \(k\) номеров телефонов, описывающих саму цепочку, в порядке следования от Поликарпа к профессору де Коде́ру. Первый номер в цепочке должен совпадать с номером телефона Поликарпа, а последний — с номером телефона профессора де Коде́ра. Если решений несколько, выведите любое.
Система оценивания
2099013166 7043239909 1 0258442145 1 0000000000 1 0000000001 1 0000000002 1 0147571204
22 5 2099013166 0000000000 0000000001 0000000002 7043239909
4261802325 7967612531 1 8176476745 1 3084033164 1 1737248630 1 9447552231 1 2848478213
40 5 4261802325 3084033164 1737248630 9447552231 7967612531
У Олега есть матрица целых чисел \(N \times M\). Его очень часто просят узнать сумму всех элементов матрицы в прямоугольнике с левым верхним углом (\(x_1\), \(y_1\)) и правым нижним (\(x_2\), \(y_2\)). Помогите ему в этом.
В первой строке находится числа \(N, M\) размеры матрицы (\(1 \leq N, M \leq 1000\)) и K - количество запросов (\(1 \leq K \leq 100000\)). Каждая из следующих \(N\) строк содержит по \(M\) чисел --- элементы соответствующей строки матрицы (по модулю не превосходят 1000). Последующие K строк содержат по \(4\) целых числа, разделенных пробелом - \(x_1\) \(y_1\) \(x_2\) \(y_2\) --- запрос на сумму элементов матрице в прямоугольнике (\(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M\))
Для каждого запроса на отдельной строке выведите его результат - сумму всех чисел в элементов матрице в прямоугольнике \((x_1,y_1)\), \((x_2,y_2)\)
3 3 2 1 2 3 4 5 6 7 8 9 2 2 3 3 1 1 2 3
28 21
Вам даны пары чисел \((a_i, b_i)\), Вам необходимо построить декартово дерево, такое что \(i\)-ая вершина имеет ключи \((a_i, b_i)\), вершины с ключом \(a_i\) образуют бинарное дерево поиска, а вершины с ключом \(b_i\) образуют кучу на минимум.
В первой строке записано число \(N\) — количество пар. Далее следует \(N\) (\(1 \le N \le 50\,000\)) пар \((a_i, b_i)\). Для всех пар \(\lvert a_i\rvert, \lvert b_i \rvert \le 30\,000\). \(a_i \ne a_j\) и \(b_i \neq b_j\) для всех \(i \ne j\).
Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите \(N\) строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номер предка, номер левого сына и номер правого сына. Если у вершины отсутствует предок или какой-либо из сыновей, то выводите на его месте число 0.
Если подходящих деревьев несколько, выведите любое.
7 5 4 2 2 3 9 0 5 1 3 6 6 4 11
YES 2 3 6 0 5 1 1 0 7 5 0 0 2 4 0 1 0 0 3 0 0
Реализуйте структуру данных, которая поддерживает множество \(S\) целых чисел, с котором разрешается производить следующие операции:
Исходно множество \(S\) пусто. Первая строка входного файла содержит \(n\) — количество операций (\(1 \le n \le 300\,000\)). Следующие \(n\) строк содержат операции. Каждая операция имеет вид либо «+ \(i\)», либо «? \(i\)». Операция «? \(i\)» задает запрос \(next(i)\).
Если операция «+ \(i\)» идет во входном файле в начале или после другой операции «+», то она задает операцию \(add(i)\). Если же она идет после запроса «?», и результат этого запроса был \(y\), то выполняется операция \(add((i + y) \bmod 10^9)\).
Во всех запросах и операциях добавления параметры лежат в интервале от \(0\) до \(10^9\).
Для каждого запроса выведите одно число — ответ на запрос.
6 + 1 + 3 + 3 ? 2 + 1 ? 4
3 4