| Codeforces Round 592 (Div. 2) |
|---|
| Закончено |
Николай живет в двухэтажном доме. На каждом этаже расположено по $$$n$$$ комнат. Комнаты на каждом этаже расположены в ряд и пронумерованы слева направо целыми числами, начиная с единицы. Таким образом, каждая комната характеризуется номером этажа, на котором она находится, а также своим порядковым номером на этаже (это целое число от $$$1$$$ до $$$n$$$).
Если Николай находится в какой-то комнате, он может перейти из нее в любую из двух соседних комнат на том же этаже (если таковые есть). Комнаты, с порядковыми номерами $$$i$$$ и $$$i+1$$$ на любом из этажей являются соседними, для всех $$$1 \leq i \leq n - 1$$$. Также известно, что между некоторыми парами комнат, которые расположены на разных этажах, но имеют одинаковые порядковые номера, есть лестницы. Если между комнатой с номером $$$x$$$ на первом этаже и комнатой с номером $$$x$$$ на втором этаже есть лестница, то Николай может перейти по лестнице из одной комнаты в другую.
На картинке показан пример дома для случая $$$n = 4$$$. Лестницы есть между комнатой номер $$$2$$$ на первом этаже и комнатой номер $$$2$$$ на втором этаже, а также между комнатой номер $$$4$$$ на первом этаже и комнатой номер $$$4$$$ на втором этаже. Стрелками указаны направления, по которым Николай может перемещаться между комнатами. Эта картинка соответствует строке «0101» во входных данных. Николай хочет обойти комнаты в своем доме. Для этого он может выбрать любую комнату для начала обхода. Далее Николай будет переходить между комнатами, учитывая описанные выше правила. Если Николай уже был в какой-то комнате, то повторно возвращаться в эту комнату он не будет.
Определите максимальное количество комнат, которые Николай может обойти, если:
- начать свой путь он может в любой комнате на любом этаже,
- и не будет переходить в те комнаты, в которых он уже был.
В первой строке следует целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных в тесте. Затем следуют сами наборы входных данных. Каждый набор состоит из двух строк.
В первой строке следует целое число $$$n$$$ $$$(1 \le n \le 1\,000)$$$ — количество комнат на каждом из двух этажей в доме Николая.
Во второй строке следует строка длины $$$n$$$, состоящая из нулей и единиц. Если $$$i$$$-й символ строки равен '1', то между комнатой номер $$$i$$$ на первом этаже и комнатой номер $$$i$$$ на втором этаже есть лестница. Если $$$i$$$-й символ строки равен '0', то между комнатой номер $$$i$$$ на первом этаже и комнатой номер $$$i$$$ на втором этаже нет лестницы.
Во взломах разрешается использовать только один набор входных данных, то есть $$$t = 1$$$ должно быть выполнено.
Для каждого теста выведите максимальное количество комнат, которые Николай может обойти, если начать свой путь он может в произвольной комнате и не будет переходить в те комнаты, в которых он уже был.
4 5 00100 8 00000000 5 11111 3 110
6 8 10 6
В первом наборе входных данных примера Николай может начать обход на первом этаже в первой комнате. Затем он может перейти во вторую комнату на первом этаже, а затем в третью комнату на первом этаже. После этого он может подняться по лестнице на второй этаж в третью комнату. Затем он может перейти в четвертую комнату на втором этаже, а после этого в пятую комнату на втором этаже. Таким образом, он посетит $$$6$$$ комнат.
Во втором наборе входных данных нет ни одной лестницы, поэтому Николай может лишь обойти все комнаты на каком-то из этажей, начав либо в первой комнате на любом из этажей, либо в восьмой комнате на любом из этажей.
В третьем наборе входных данных Николай может обойти все комнаты в доме. Если он начнет обход в первой комнате на первом этаже, его путь может выглядеть следующим образом: первый этаж, первая комната $$$\rightarrow$$$ второй этаж, первая комната $$$\rightarrow$$$ второй этаж, вторая комната $$$\rightarrow$$$ первый этаж, вторая комната $$$\rightarrow$$$ первый этаж, третья комната $$$\rightarrow$$$ второй этаж, третья комната $$$\rightarrow$$$ второй этаж, четвертая комната $$$\rightarrow$$$ первый этаж, четвертая комната $$$\rightarrow$$$ первый этаж, пятая комната $$$\rightarrow$$$ второй этаж, пятая комната.
В четвертом наборе входных данных Николай также может обойти все комнаты. Один из возможных вариантов: второй этаж, третья комната $$$\rightarrow$$$ второй этаж, вторая комната $$$\rightarrow$$$ второй этаж, первая комната $$$\rightarrow$$$ первый этаж, первая комната $$$\rightarrow$$$ первый этаж, вторая комната $$$\rightarrow$$$ первый этаж, третья комната.
