Решение задачи Прыгающая лягушка с Codeforces
Без пояснения   Просмотров: 201
Слева от строки s=s1s2…sn, состоящей из n символов, находится лягушка (точнее, изначально лягушка находится в клетке 0). Каждый символ строки s — это или 'L', или 'R'. Это значит, что если лягушка находится в i-й клетке и i-й символ — это 'L', то она может прыгать только влево. Если лягушка стоит в i-й клетке и i-й символ — это 'R', то она может прыгать только вправо. Из клетки 0 лягушка может прыгать только вправо.
Заметим, что лягушка может прыгать в одну и ту же клетку дважды и может совершить столько прыжков, сколько ей потребуется.
Лягушка хочет достичь n+1-й клетки. Лягушка выбирает некоторое целое положительное значение d перед самым первым прыжком (и потом не может изменить его) и прыгает не более, чем на d клеток за раз. То есть, если i-й символ — 'L', то лягушка может прыгнуть в любую клетку из отрезка [max(0,i−d);i−1], а если i-й символ — 'R', то лягушка может прыгнуть в любую клетку из отрезка [i+1;min(n+1;i+d)].
Лягушка не хочет прыгать слишком далеко, поэтому ваша задача — найти минимальное возможное значение d, при котором лягушка сможет достичь клетки n+1 из клетки 0, если будет прыгать не более, чем на d клеток за раз. Гарантируется, что всегда возможно достичь n+1 из 0.
Вам нужно ответить на t независимых наборов входных данных.
Заметим, что лягушка может прыгать в одну и ту же клетку дважды и может совершить столько прыжков, сколько ей потребуется.
Лягушка хочет достичь n+1-й клетки. Лягушка выбирает некоторое целое положительное значение d перед самым первым прыжком (и потом не может изменить его) и прыгает не более, чем на d клеток за раз. То есть, если i-й символ — 'L', то лягушка может прыгнуть в любую клетку из отрезка [max(0,i−d);i−1], а если i-й символ — 'R', то лягушка может прыгнуть в любую клетку из отрезка [i+1;min(n+1;i+d)].
Лягушка не хочет прыгать слишком далеко, поэтому ваша задача — найти минимальное возможное значение d, при котором лягушка сможет достичь клетки n+1 из клетки 0, если будет прыгать не более, чем на d клеток за раз. Гарантируется, что всегда возможно достичь n+1 из 0.
Вам нужно ответить на t независимых наборов входных данных.