Большое Путешествие (Малыш и Карлсон) (25 баллов)
Задачу добавил: elena
Успешно сдано решений: 7
Карлсон решил выполнить свое обещание и показать Малышу не только свой домик на крыше, но и Стокгольм с "высоты птичьего полета". Но в таком большом путешествии Карлсону потребуется периодически восстанавливать силы: Малыш для него - довольно нелегкая ноша. Для восстановления сил было запасено варенье и печенье. Чтобы подкрепиться, Карлсон должен либо брать продукты с собой и поедать их, делая остановку на какой-нибудь крыше, либо возвращаться в свой домик. Вернуться в домик он может как с Малышом, так и без него: Малыш может подождать его на одной из крыш. Однако Малыш не может там оставаться долго: маленький мальчик на крыше непременно привлечет чье-нибудь внимание, и большое путешествие закончится совсем не так, как планировали друзья. Существует еще одно ограничение: Малыш должен непременно вернуться к ужину, иначе его начнут искать.
Ваша задача - по заданному маршруту путешествия выяснить, может ли Малыш оказаться дома вовремя.
Примечания
1. Для перемещения 1 кг дополнительного груза на 1 единицу расстояния Карлсону требуется съесть либо p граммов печенья, либо q граммов варенья. Однако, во-первых, Карлсон не может перемещать груз более тяжелый, чем G килограммов. Во-вторых, минимальная порция печенья или варенья, которую он съедает "за один присест" - PMin граммов и QMin граммов соответственно.
В третьих, максимальная порция, которую он может съесть, когда совсем голоден (все "топливо" израсходовано), составляет K граммов (печенья или варенья, или и того и другого вместе).
2. Карлсон летает с постоянной скоростью V единица расстояния/секунда - как с дополнительным грузом, так и без него. К своему домику он возвращается всегда "напрямую"
3. Печенье можно возить с собой в невесомом пакете, варенье же приходится везти в банке массой B граммов, и вмещает она A граммов варенья
4. Съеденные печенье и варенье дополнительным грузом не являются
Формат входного файла input.txt
Первая строка - целые числа M, G, p, q, PMin, QMin, K, B, A через пробел
M (10<=M<=50) - масса Малыша в килограммах,
G (0<=G<=100) - максимальный груз, который может перемещать Карлсон,
p (10<=p<=1000) - масса (в граммах) печенья, которое требуется для перемещения 1 кг дополнительного груза на 1 единицу расстояния,
q (10<=q<=1000) - масса (в граммах) варенья, которое требуется для перемещения 1 кг дополнительного груза на 1 единицу расстояния,
PMin (10<=PMin<=10000) - минимальная порция печенья, которую Карлсон съедает "в один присест",
QMin (10<=QMin<=10000) - минимальная порция печенья, которую Карлсон съедает "в один присест",
K (10<=K<=20000) - максимальное количество печенья и/или варенья, которое может съесть Карлсон за один раз, когда он совсем голоден
B - масса пустой банки в граммах
Вторая строка - целые числа V, W, T, ZP, ZQ, N через пробел
V (1<=V<=10) - скорость Карлсона (единица расстояния/секунда)
W (0<=W<=1000) - максимально возможное время в секундах, которое Малыш может провести на крыше в ожидании Карлсона
T (0<=T<=30000) - время (в секундах), через которое после начала путешествия Малыш должен оказаться в домике Карлсона, чтобы успеть к ужину
ZP (0<=ZP<=100) - масса (в килограммах) запасенного в домике Карлсона перед Большим Путешествием печенья
ZQ (0<=ZQ<=100) - масса (в килограммах) запасенного в домике Карлсона перед Большим Путешествием варенья
N (0<=N<=20) - количество остановок (крыш домов, на которые друзья будут приземляться) на маршруте, запланированном Карлсоном
Следующие N строк содержат по два целых числа Xi и Yi (0<=Xi, Yi<=10000) через пробел - координаты остановок
Примечание.
Домик Карлсона расположен в точке с координатами (0,0). Маршрут начинается в этой точке, последовательно проходит через все остановки (в порядке их перечисления во входном файле). После последней остановки друзья должны вернуться в домик.
Формат выходного файла output.txt
Первая строка - слово YES, если Малыш может успеть к ужину, и слово NO, если успеть к ужину не получается
Пример входного файла
25 30 1000 1000 1000 1000 20000 10
10 1000 30000 100 100 1
10 10
Пример выходного файла
YES