Страница: << 1 2 Отображать по:
#1087
Лифты
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.

В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.

Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.

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

В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа Ki — количества этажей, на которых останавливается i-й лифт, за которым следует Ki натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤Ki≤1000, K1+K2+…+KL≤100000. Количество этажей в небоскребе не превосходит 1000000.

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

В выходной файл выведите одно число — минимальную стоимость подъема сейфа.

Группы тестов:

  • Группа 0 : Тесты из условия (тесты 1-3). 0 баллов.
  • Группа 1 : Количество этажей в доме не превосходит 100 (тесты 4-6). 30 баллов.
  • Группа 2 : Количество этажей в доме не превосходит 1000 (тесты 7-11). 30 баллов.
  • Группа 3 : K1+K2+…+KL≤1000 (тесты 12-32). 20 баллов.
  • Группа 4 : Дополнительных ограничений нет (тесты 33-50). 20 баллов.
Баллы за группу тестов выставляются только при корректной работе программы на всех тестах группы.

Примеры
Входные данные
10 1 1 1 1 1
2 3 7
Выходные данные
7
Входные данные
10 1 1 3 2 1
2 3 7
Выходные данные
9
Входные данные
20 100 0 1 1 2
2 5 7
2 8 17
Выходные данные
804
#1745
Ездящий город
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с «Бегущим городом» назвать их «Ездящий город».

Участник соревнований получает маршрутный лист, где указано, какие контрольные пункты и в каком порядке он должен посетить (в каждом пункте участник должен отметиться). При этом участник должен отмечаться в пунктах строго в указанном порядке. Какие-то пункты может потребоваться посетить несколько раз.

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

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

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

Сначала вводится число \(N\) — общее количество контрольных пунктов (2≤\(N\)≤10000).

Далее вводится количество автобусных маршрутов \(K\) (1≤\(K\)≤50000). Далее идет \(K\) описаний автобусных маршрутов.

Каждый маршрут описывается четырьмя числами \(A_i\), \(B_i\), \(C_i\), \(D_i\), которые означают, что каждые \(C_i\) минут (т.е. в моменты времени 0, \(C_i\), 2*\(C_i\), …) автобус выходит от контрольного пункта \(A_i\) и через \(D_i\) минут прибывает к контрольному пункту \(B_i\). Все \(C_i\) и \(D_i\) — натуральные и не превышают 10000.

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

Далее вводится число \(M\) — количество контрольных пунктов в маршрутном листе участника (2≤\(M\)≤50). Далее вводятся \(M\) чисел \(P_1\), \(P_2\), …, \(P_M\) — номера контрольных пунктов, которые нужно посетить (числа в этом списке могут повторяться). В момент времени 0 участник находится в пункте \(P_1\). Временем прохождения маршрута считается момент времени, когда участник окажется в пункте \(P_M\).

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

Выведите одно число — минимальное время, за которое участник может пройти маршрут. Если существующие автобусные рейсы не позволяют пройти маршрут, выведите одно число –1 (минус один).

Примеры
Входные данные
2 2
2 1 3 1
1 2 5 4
3
1 2 1
Выходные данные
7
Входные данные
3 4
2 1 30 10
1 2 50 40
2 3 45 10
3 1 55 10
3
1 2 1
Выходные данные
65
Входные данные
2 2
1 2 3 1
1 2 5 4
3
1 2 1
Выходные данные
-1
#1969
  
Темы: [Куча]
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Вам необходимо нанять работников для строительного проекта. Заявление о приёме на работу подали 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 можно было сохранить в одной переменной. Дополнительные подробности представлены на страницах с технической информацией.

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

Ваша программа должна читать из стандартного потока ввода следующие данные:

  • Первая строка входного файла содержит два целых числа N и W, разделённые пробелом.
  • Следующие N строк описывают кандидатов, по одному кандидату на каждую строку. k-я строка из них описывает кандидата с номером k и содержит два целых числа Sk и Qk, разделённых пробелом.
Выходные данные

Ваша программа должна вывести в стандартный поток вывода следующие данные:

Первая строка должна содержать одно целое число 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 долларов соответственно.

Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест