Соревнования лучников проходит по следующим правилам. Есть \(N\) мишеней, расположенных в линию и пронумерованных от \(1\) до \(N\) включительно в соответствии с их местом на линии (самая левая мишень имеет номер 1, а самая правая мишень имеет
номер \(N\)). Также есть \(2*N\) лучников. В произвольный момент во время турнира в каждую из мишеней стреляют два лучника. Каждый тур соревнований проходит по такой процедуре:
Турнир состоит из \(R\) туров, количество туров не меньше, чем количество лучников (то есть \(R \ge 2*N)\).
Вы – единственный лучник, который прибыл на турнир точно вовремя. Остальные \(2*N - 1\) лучников прибыли раньше и уже расположились в линию. Вам теперь нужно «вставиться» в линию где-то среди них. Вы знаете, что после того как вы займете свою позицию, два самых левых лучника начнут турнир на мишени с номером \(1\), два следующих на мишени с номером \(2\), и так далее. Два самых правых лучника начнут турнир на мишени с номером \(N\).
Все \(2*N\) лучников на турнире (включая вас) имеют ранг, установленный в соответствии с их навыками, при этом меньший ранг соответствует более высоким навыкам. Нет двух лучников одинаковым рангом. Также, когда бы ни соревновались два лучника, всегда победит лучник с меньшим рангом.
Зная, как сильны в стрельбе ваши соперники, вы хотите разместиться так, чтобы закончить турнир на мишени с наименьшим возможным номером. Если есть несколько способов сделать это, выберите тот, который начинается на мишени с наибольшим номером.
Напишите программу, которая по заданным рангам всех лучников, включая вас, а также по расположению ваших соперников на линии, определяет, на какой мишени вы должны начать турнир, чтобы достичь описанных выше целей.
Ваша программа должна читать со стандартного потока ввода такие данные:
Ваша программа должна записать в стандартный поток вывода одну строку, в которой будет содержаться одно целое число между \(1\) и \(N\) включительно, являющееся номером мишени, на которой вы начнете турнир.
В тесте из условия вы второй наихудший лучник. Если вы начнете на мишени с номером 1, то вы попадете на мишень с номером 4 и останетесь там до конца. Если вы начнете на мишени с номером 2 или 4, вы просто останетесь там до конца турнира. Если вы начнете на мишени с номером 3, то победите наихудшего лучника, переместитесь на мишень с номером 2 и там останетесь.
В тесте (ниже) вы второй наилучший лучник. Наилучший лучник уже расположен на мишени с номером 1, и останется там до окончания турнира. Таким образом, вне зависимости от того, где вы начнете турнир, вы будете всегда передвигаться со своей мишени,
проходя через все мишени с номерами от 4 до 1 снова и снова. Для того чтобы окончить турнир на мишени с номером 1 после девяти переходов, вы должны начать на мишени с номером 2.
| Пример ввода | Пример вывода |
|---|---|
| 4 9 2 1 5 8 3 4 7 6 |
2 |
Для набора тестов общей стоимостью \(60\) баллов \(N\) не будет превышать \(5\,000\).
Также, для некоторых из этих тестов, суммарной стоимостью \(20\) баллов, \(N\) не будет превышать \(200\).
4 8 7 4 2 6 5 8 1 3
3
Вам необходимо нанять работников для строительного проекта. Заявление о приёме на работу подали 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 долларов соответственно.