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

Вася идет из школы домой вдоль проспекта, по которому ходят трамваи. Мама считает, что ему после школы полезно дышать свежим воздухом, поэтому настаивает, чтобы не менее K метров он прошел пешком. Вася при этом хочет попасть домой как можно быстрее (обязательно выполнив требование мамы).

Вдоль проспекта расположено N трамвайных остановок, которые находятся в точках a1, a2, ..., aN (все координаты задаются в метрах). Школа находится около 1-й остановки, а дом — около остановки номер N. Мальчик идет пешком со скоростью v метров в минуту. Трамвай едет со скоростью w метров в минуту (временем стоянки трамвая на остановках пренебрежем). В нулевой момент времени и далее с интервалом T минут от первой остановки в сторону Васиного дома отправляются трамваи. Вася выходит из школы также в момент времени 0. Сесть в трамвай и выйти из него можно только на остановке. При этом, если Вася приходит на остановку раньше трамвая, на который хочет сесть, то ему придется подождать, пока тот не подъедет. Вася идет пешком и едет на трамвае только в направлении от школы к дому.

Напишите программу, которая определит, когда Вася сможет оказаться дома.

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

Сначала вводится число N — количество остановок (1 ≤ N ≤ 2000). Далее заданы координаты остановок a1, a2, ..., aN (0 ≤ a1 < a2 < ... < aN ≤ 109). Далее вводится интервал движения трамваев T (1 ≤ T ≤ 2000). Затем расстояние, не меньше которого Вася должен пройти пешком K (0 ≤ K ≤ 2000). Затем заданы скорости Васи v и трамвая w (1 ≤ v ≤ w ≤ 10 000). Все вводимые числа целые. K не превышает длины пути от школы до дома.

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

В первую строку выведите не менее чем с пятью знаками после десятичной точки одно число — минимальное время, когда Вася сможет оказаться дома, пройдя пешком не менее K метров. Далее нужно вывести информацию о пути Васи. Занумеруем промежутки между соседними остановками числами от 1 до N - 1 (то есть промежуток между первой и второй остановками имеет номер 1, между второй и третьей — 2 и так далее). Следующая строка должна содержать количество промежутков, пройденных Васей пешком. Далее выведите номера этих промежутков в возрастающем порядке.

Примеры
Входные данные
3
0 10 30
5
10
1 5
Выходные данные
16.000000
1
1
Входные данные
4
0 3 8 11
1
6
1 3
Выходные данные
7.666667
2
1
3
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в K реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё N - 1 реальностей. Для удобства они были занумерованы числами от 1 до N, при этом его собственная реальность имеет номер 1, а посетить ему необходимо реальности с номерами 2, 3, ..., K + 1.

Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени 0). Исследование показало, что реальность с номером i ответвилась от реальности с номером Pi в момент времени Ti. Из каждой реальности с номером i архимаг может переместиться

  • в любую ответвившуюся от неё, то есть в любую j, такую что Pj = i;
  • в Pi, если i — не Начальная реальность.
Другими словами, возможны лишь переходы вида i <-> Pi. На каждый такой переход в любую сторону архимаг затрачивает Ti - TPi > 0 условных единиц энергии.

Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером 1, посетить все реальности с номерами от 2 до K + 1 (в любом порядке) и затем вновь вернуться в 1. Любую реальность при этом разрешается посещать сколько угодно раз.

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

Сначала вводятся два целых числа N и K (0 ≤ K < N ≤ 100 000): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт N пар целых чисел, i-я пара — это Pi и Ti (1 ≤ Pi ≤ N, 0 ≤ Ti ≤ 106; для Начальной реальности Pi = Ti = 0).

Гарантируется, что ответвившаяся реальность появилась строго позже породившей (Ti > TPi), и что маг может при желании добраться до любой из N реальностей.

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

 

Выведите единственное число E — минимальную возможную энергию, которая потребуется архимагу для путешествия.

Примеры
Входные данные
5 2
4 2
4 6
1 9
0 0
1 7
Выходные данные
30
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В этой задаче Вася готовится к олимпиаде. Учитель дал ему N (1 ≤ N ≤ 100) задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi.

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

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

Сначала вводятся два целых числа N, A (1 ≤ N ≤ 100, 0 ≤ A ≤ 100) — количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1 ≤ ai ≤ 100, 1 ≤ bi ≤ 100) — соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения.

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

Выведите одно число — максимальное количество задач, которое Вася может решить.

Примечание

В первом тесте Вася сможет решить все задачи, выбрав, например, порядок 2, 1, 3. Во втором тесте ему необходимо сначала разобраться с 1 и 3 задачами, после чего он осилит 2.

Примеры
Входные данные
3 2
3 1
2 1
1 1
Выходные данные
3
Входные данные
4 1
1 10
21 5
1 10
100 100
Выходные данные
3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

В наличии имеется N (1 ≤ N ≤ 100 000) маек и M (1 ≤ M ≤ 100 000) штанов, про каждый элемент известен его цвет (целое число от 1 до 10 000 000). Помогите Глебу выбрать одну майку и одни штаны так, чтобы разница в их цвете была как можно меньше.

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

Сначала вводится информация о майках: в первой строке целое число N (1 ≤ N ≤ 100 000) и во второй N целых чисел от 1 до 10 000 000 — цвета имеющихся в наличии маек. Гарантируется, что номера цветов идут в возрастающем порядке (в частности, цвета никаких двух маек не совпадают).

Далее в том же формате идёт описание штанов: их количество M (1 ≤ M ≤ 100 000) и в следующей строке M целых чисел от 1 до 10 000 000 в возрастающем порядке — цвета штанов.

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

Выведите пару неотрицательных чисел — цвет майки и цвет штанов, которые следует выбрать Глебу. Если вариантов выбора несколько, выведите любой из них.

Примеры
Входные данные
2
3 4
3
1 2 3
Выходные данные
3 3
Входные данные
2
4 5
3
1 2 3
Выходные данные
4 3
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Ваша задача – по данным о расположении рисунка и прямоугольной дырки определить, испортил ли Вася рисунок старшего брата, другими словами, есть ли на вырезанном Васей прямоугольнике хотя бы маленький фрагмент рисунка Пети.

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

Вам даны 8 целых чисел - x1, y1, x2, y2, x3, y3, x4, y4, где (x1, y1) - координаты левого нижнего угла рисунка Пети, (x2, y2) - координаты правого верхнего угла рисунка. Аналогично, (x3, y3) - координаты левого нижнего угла вырезанного Васей прямоугольника, (x4, y4) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (x1 < x2, y1 < y2 и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит 104.

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

Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Примеры
Входные данные
1 1 2 2 3 3 4 4
Выходные данные
NO
Входные данные
1 1 3 3 2 2 4 4
Выходные данные
YES
Входные данные
1 1 4 4 2 2 3 3
Выходные данные
YES

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