Codeforces Round 775 (Div. 2, по задачам Открытой олимпиады школьников по программированию) |
---|
Закончено |
Вы играете в одну очень популярную компьютерную игру. Очередной уровень состоит из $$$n$$$ подряд идущих локаций, пронумерованных от $$$1$$$ до $$$n$$$, каждая из которых содержит либо землю, либо воду. Известно, что первая и последняя локации содержат землю, и ваша задача — попасть с первой локации на последнюю, при этом если вы попадете на локацию с водой, то вы погибнете, так что вы можете перемещаться только между локациями с землей.
Вы можете бесплатно совершать прыжки между соседними локациями, а также не более одного раза совершить прыжок с любой локации с землей $$$i$$$ на любую локацию с землей $$$i + x$$$, затратив на это $$$x$$$ монет ($$$x \geq 0$$$).
Ваша задача — вывести минимальное количество монет, необходимое для того, чтобы переместиться с первой локации на последнюю.
Обратите внимание, что это всегда возможно, так как и первая, и последняя локация являются локациями с землей.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \leq n \leq 100$$$) — количество локаций.
Во второй строке набора задана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), где $$$a_i = 1$$$ обозначает, что $$$i$$$-я локация является локацией с землей, а $$$a_i = 0$$$ обозначает, что $$$i$$$-я локация является локацией с водой. Гарантируется, что $$$a_1 = 1$$$ и $$$a_n = 1$$$.
Для каждого набора входных данных выведите единственное целое число — ответ на задачу.
3 2 1 1 5 1 0 1 0 1 4 1 0 1 1
0 4 2
В первом наборе входных данных достаточно сделать один бесплатный прыжок с первой локации на вторую, которая также последняя, поэтому ответ $$$0$$$.
Во втором наборе единственный способ добраться с первой локации до последней — перепрыгнуть между ними сразу, что будет стоить $$$4$$$ монеты.
В третьем наборе можно за $$$2$$$ монеты прыгнуть с первой локации на третью, а затем бесплатно прыгнуть на четвертую, поэтому ответ $$$2$$$. Можно показать, что это оптимальный способ.
Название |
---|