Codeforces Round 828 (Div. 3) |
---|
Закончено |
Вы попали на необычный перекресток со странным светофором. У этого светофора есть три возможных цвета: красный (r), желтый (y), зеленый (g). Известно, что светофор повторяет свои цвета каждые $$$n$$$ секунд и в $$$i$$$-ю секунду горит цвет $$$s_i$$$.
Таким образом, порядок цветов задаётся строкой. Например, если $$$s=$$$«rggry», то светофор горит так: красный-зеленый-зеленый-красный-желтый-красный-зеленый-зеленый-красный-желтый- ... и так далее.
Более формально, вам дана строка $$$s_1, s_2, \ldots, s_n$$$ длины $$$n$$$. В первую секунду горит цвет $$$s_1$$$, во вторую $$$s_2$$$, ..., в $$$n$$$-ю секунду горит цвет $$$s_n$$$, в $$$n + 1$$$-ю секунду горит цвет $$$s_1$$$ и так далее.
Вам нужно перейти дорогу, и это можно сделать только тогда, когда на светофоре горит зеленый цвет.
Вам известно, какой сейчас цвет на светофоре, но вы не знаете текущей момент времени. Вам нужно найти минимальное время, в течение которого вы точно (наверняка) сможете перейти дорогу.
Можно считать, что дорогу мы проходим моментально.
Например, в случае $$$s=$$$«rggry» и текущего света r возможны два варианта: либо зеленый свет наступит через через $$$1$$$ секунду, либо через $$$3$$$. Таким образом, ответ равен $$$3$$$ — именно через столько секунд мы гарантированно сможем перейти дорогу, если текущий цвет r.
В первой строке входных данных дано единственное целое число $$$t$$$ $$$(1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Далее следуют описания наборов входных данных.
В первой строке каждого набора входных данных содержится целое число $$$n$$$ и символ $$$c$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$c$$$ является одним из допустимых цветов светофора r, y или g)— длина строки $$$s$$$ и текущий цвет светофора.
Во второй строке каждого набора входных данных содержится строка $$$s$$$ длины $$$n$$$, состоящая из символов r, y и g.
Гарантируется, что символ g встречается в строке $$$s$$$ и что символ $$$c$$$ встречается в строке $$$s$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных теста не превосходит $$$2\cdot10^5$$$.
Для каждого набора входных данных выведите минимальное количество секунд, в течение которого можно гарантировано перейти дорогу.
65 rrggry1 gg3 rrrg5 yyrrgy7 rrgrgyrg9 yrrrgyyygy
3 0 2 4 1 4
Первый набор входных данных разобран в условии.
Во втором наборе входных данных уже сейчас горит зеленый цвет, поэтому можно перейти дорогу сразу же.
В третьем наборе входных данных если изначально горел красный цвет на второй секунде, то ждать зеленого цвета пришлось бы одну секунду, а если бы горел красный цвет на первой секунде, то уже две.
В четвертом наборе входных данных дольше всего ждать зеленый цвет мы будем с пятой секунды.
Название |
---|