На тропическом острове в разгар туристического сезона особой популярностью пользуется квас. Раньше весь квас импортировался из России, но с увеличением популярности этого напитка встал вопрос о производстве кваса прямо на месте. На острове расположено N курортных городов, все города расположены на побережье. Вдоль побережья проходит единственная на острове кольцевая дорога, соединяющая все города. Движение по дороге возможно в любом направлении. Для каждого города известно, сколько бочек кваса требуется ему ежедневно.
Планируется построить всего один завод в каком-нибудь городе, и развозить продукцию по остальным городам. Перевозка одной бочки в соседний город стоит один тугрик (местная валюта).
Ваша задача состоит в том, чтобы определить, в каком из городов следует построить завод, чтобы минимизировать транспортные расходы.
Первая строка входных данных содержит число N – количество городов ( N ≤ 10) и еще N чисел – количество кваса, требуемое ежедневно 1-м, 2-м, …, N -м городом (города нумеруются подряд вдоль кольцевой дороги).
Выведите одно число – номер города, в котором следует построить завод. Если подходящих городов окажется несколько – выведите номер любого из них.
Примеры
Пояснение для второго примера(см. рисунок):
На острове 6 городов, потребность каждого города указана в кружочках, номер города рядом с кружочком.
Если построить завод во 2-м городе (он выделен серым), то потребуется заплатить 4 + 1 (стоимость перевозки в 1-й и 3-й города) + 5*2 + 3*2 (в 4-й и 6-й) + 1*3 (в 5-й см. рисунок).
Во 2-й вообще ничего не везем. Это будет 24 тугрика. Легко проверить, что если построить завод в других городах, сумма будет больше. Например, если построить в 4-м городе, то сумма составит 1 + 1 + 3*2 + 4*2 + 4*3 = 28 тугриков.
3 5 3 10
3
6 4 4 1 5 1 3
2
В Шахматной Стране всегда пользовались популярностью различные спортивные соревнования: ферзебол, рокировочная борьба, эндшпилевые бега. Но наибольшую популярность в этом году получила спортивная игра «обмен королей».
Суть её заключается в следующем. Двух королей (белого и чёрного) ставят на прямоугольное шахматное поле, некоторые клетки которого отмечены как недостижимые. По правилам игры короли делают ходы по очереди (сначала белый, а затем чёрный), не наступая на недостижимые клетки. Игра считается успешно законченной, если черный и белый короли поменялись местами. В соревновании побеждает та пара королей, которая смогла поменяться местами за минимальное количество ходов.
Напомним, что в шахматах король имеет право переместиться из своей клетки в любую из 8 соседних по вертикали, диагонали или горизонтали, при условии, что она не является соседней для другого короля.
Напишите программу, которая по информации о доске найдет минимальное количество ходов, необходимое для успешного окончания игры.
В первой строке входных данных даны целые числа N и M (1 ≤ N, M ≤ 8) — размеры доски по вертикали и по горизонтали, соответственно. В следующих N строках даны M символов — состояние доски в начале игры. Символ «.» обозначает пустую клетку, символ «*» — недостижимую клетку, символ «W» — белого короля, «B» — черного короля. Гарантируется, что символы «W» и «B» встречаются на поле ровно по одному разу, и короли не находятся в соседних клетках изначально.
В выходной файл необходимо вывести минимальное количество ходов, которое потребуется для того, чтобы белый король поменялся местами с чёрным. В случае, если поменять королей местами невозможно, требуется вывести «Impossible» без кавычек.
4 3
*.*
W.B
...
*.*
8
2 3
W..
..B
Impossible
Последовательность ходов, необходимая для обмена королей в первом тесте, приведена на рисунке:
Настал декабрь, и вместе с ним пришло время готовиться к Новому Году. На острове рыцарей и лжецов этот праздник традиционно отмечается очень масштабно. Праздничный стол, новогодняя ёлка, конфетти и бенгальские огни — все готово к началу торжества.
Как вы знаете, на острове рыцарей и лжецов живут только два вида жителей — рыцари и лжецы. Рыцари никогда не лгут, так как этого им не позволяют их высокие моральные принципы. Лжецы же, наоборот, всегда говорят только неправду.
Важнейшей частью празднования Нового года является хоровод вокруг елки. Все приглашенные жители острова берутся за руки и движутся по кругу под музыку. Поскольку население острова весьма консервативно, то в этом году жители хотят выстроиться в круг в том же порядке, что и в прошлом. Однако данных о том, как был устроен хоровод, не сохранилось. Известно только, что каждый житель острова запомнил, кем были его соседи по хороводу (рыцарями или лжецами).
Опросив каждого человека, приглашенного на празднование, вы узнали, кем были их соседи по их словам (при этом лжецы говорят неправду про каждого соседа). Осталось только придумать какое-нибудь расположение жителей острова в круг так, чтобы их показания не противоречили друг другу.
Напишите программу, которая по списку жителей и их показаний определит, существует ли такое расположение или же выстроиться в хоровод как в прошлом году не получится.
В первой строке входных данных дано целое число n (2 ≤ n ≤ 105) — количество жителей на острове лжецов.
В следующих n строках даны целые числа li и ri (0 ≤ li, ri ≤ 1) — данные о соседях i-го человека. Если li = 0, то i-й житель утверждает, что его сосед по хороводу в направлении против часовой стрелки был лжецом, а если li = 1, то рыцарем. Аналогично, число ri содержит информацию о соседе по часовой стрелке.
Требуется вывести «Yes», если существует способ выстроить людей по указанным правилам, или «No», если нет.
5
1 1
0 1
1 1
0 0
1 0
Yes
2
0 0
1 1
No
Тесты к этой задаче состоят из четырёх групп.
В первом примере, можно выстроить жителей в порядке (2, 1, 3, 5, 4) по часовой стрелке. Показания всех людей будут сходиться в этом случае, например, когда четвертый житель будет рыцарем, а все остальные четыре человека — лжецами.
Во втором примере, очевидно, нельзя получить никакого решения, так как выстроить двух человек в хоровод можно лишь одним способом. Рассмотрим два случая: если первый человек — рыцарь, то, по его словам, второй человек — лжец, однако, из лживости его слов следует, что первый человек не рыцарь. С другой стороны, если первый человек — лжец, то из его показаний следует, что второй человек — рыцарь, но второй человек говорит, что первый — тоже рыцарь. Таким образом, поскольку в обоих случаях мы получили противоречие, не существует способа построить хоровод из имеющегося набора жителей.