B. Лавочки
Задачу добавил: alef
Успешно сдано решений: 465
Кеша считает, что этим летом ему повезло. Во-первых, он устроился на стажировку в компанию, в которую хотел, во-вторых, от офиса компании всего несколько минут ходьбы до пляжа. Так что вместо перерыва на обед Кеша может устроить перерыв на плавание.
Кеша берет с собой на пляж не очень много вещей, которые оставляет на одной из n лавочек, расположенных вдоль берега. Кеша плавает вдоль берега, и ему намного спокойнее плавать, когда в любой момент он может видеть лавочку и свои вещи на ней.
Для каждой лавочки #j известны расстояния справа rj и слева lj (по линии, вдоль которой плавает Кеша), на которых Кеша ещё видит лавочку. Если он отплывёт вправо дальше, чем на rj, или влево дальше, чем на lj, то другие сооружения на пляже помешают ему наблюдать, что происходит возле лавочки с его вещами.
Кеша будет плавать следующим образом. Он войдёт в воду строго напротив лавочки, на которой оставил вещи, после чего поплывёт вправо или влево на расстояние, с которого ему ещё будет видно лавочку. Как только он достигнет этой точки, он повернёт и поплывёт в противоположную сторону — вновь до точки, из которой ему ещё видно лавочку. В этой точке он снова сменит направление движения...
Кеша будет плавать между крайними точками, из которых ему ещё видно лавочку, и изменять направление своего движения он будет только в этих точках. Завершать плавание Кеша будет в точке, расположенной строго напротив лавочки.
Он хочет проплыть расстояние, как можно более близкое к m, но не меньшее него. Ваша задача — определить, какое расстояние проплывет Кеша, номер лавочки, на которой ему следует оставить свои вещи, а также направление, в котором он поплывёт, когда войдёт в воду.
В первой строке содержатся целые числа n и m (1 ≤ n ≤ 105, 1 ≤ m ≤ 109) — количество лавочек на пляже и расстояние, которое хочет проплыть Кеша.
В каждой из следующих строк содержится пара чисел lj и rj (0 ≤ lj, rj ≤ 109) — расстояние, на которое Кеша может отплыть от лавочки #j влево и вправо соответственно.
Гарантируется, что задача всегда имеет решение (что хотя бы одно среди всех значений lj и rj отлично от нуля).
Выведите расстояние, которое фактически проплывёт Кеша, номер лавочки, на которой ему следует оставить вещи, а также символ L, если Кеше сначала следует поплыть влево, или символ R, если Кеше сначала следует поплыть вправо.
Разделяйте выводимые данные пробелами или переводами строк. Если существует более одного ответа, выведите любой.
Подзадача 1 (до 20 баллов).
1 ≤ n ≤ 100, lj = rj для всех лавочек.
Баллы начисляются за каждый пройденный тест, по запросу сообщаются результаты проверки на каждом тесте.
Подзадача 2 (до 80 баллов).
Входные данные могут принимать любые допустимые значения.
Баллы начисляются в случае прохождения всех тестов группы.
По запросу сообщается номер первого непройденного теста в группе.
3 100
7 7
17 17
11 11
102
2 L
5 100
3 8
7 12
4 4
10 6
11 2
100
2 R
5 117
3 8
7 12
4 4
10 6
11 2
120
3 L
Поясним приведённые примеры.
Будем называть полным кругом перемещение Кеши сначала в одну сторону от лавочки (в зависимости от выбранного направления), затем до конца в другую сторону, и, наконец, возвращение в точку напротив лавочки. Т.е., например, если Кеша сначала плывёт влево, то описанное перемещение происходит следующим образом lj + lj + rj + rj.
В первом примере Кеше выгоднее всего выбирать вторую лавочку; направление же может быть любым.
Если Кеша оставит вещи на первой лавочке, то ему придётся сделать четыре полных круга (т.е. проплыть 112 единиц длины), прежде чем он сможет выйти из воды. Если Кеша оставит вещи на второй лавочке, то ему нужно будет проплыть один полный круг, после чего проплыть в выбранном направлении и вернуться в точку напротив лавочки. Расстояние при этом составит 102. Наконец, если Кеша оставит вещи на третьей лавочке, то ему придётся проплыть два полных круга, а затем проплыть в выбранном направлении и вернуться в точку напротив лавочки. Расстояние составит 110 единиц длины.
Обратите внимание, что второй и третий примеры не отвечают ограничениям подзадачи 1.
Во втором примере Кеша может оставить вещи не только на второй, но и на пятой лавочке: в обоих случаях он сможет выбрать направление движения так, чтобы проплыть в точности желаемое расстояние.
В третьем примере Кеше придётся превысить желаемое расстояние, однако нет разницы, в каком направлении он поплывёт сначала: самой подходящей лавочкой является третья, а для неё расстояния слева и справа, с которых Кеша ещё может наблюдать за вещами, одинаковы.