Школьник Вася очень любит читать книжки по программированию и математике. Недавно он прочёл в энциклопедии статью, в которой рассказывалось о методе медианного сглаживания и его многочисленных применениях в науке и технике. Идея метода Васе очень понравилась, и он решил опробовать его на практике.
При использовании простейшего варианта медианного сглаживания по последовательности чисел a 1 , a 2 , ..., a n строится новая последовательность чисел b 1 , b 2 , ..., b n по следующему алгоритму:
- b 1 = a 1 , b n = a n , то есть первое и последнее число новой последовательности совпадают с соответствующими числами исходной последовательности.
- При i = 2, ..., n - 1 значение b i полагается равным медиане трёх значений a i - 1 , a i и a i + 1 .
Напомним, что медианой набора из трех чисел называется число, которое окажется на втором месте, если три числа выписать в порядке неубывания. Например, медианой набора 5, 1, 2 является число 2, а медианой набора 1, 0, 1 — число 1.
Чтобы не усложнять себе задачу, Вася решил применять метод только к последовательностям, состоящим из нулей и единиц.
Проделав нехитрую процедуру один раз, Вася посмотрел на получившуюся последовательность и подумал: что будет, если снова применить к ней алгоритм, а потом применить его к следующему результату и так далее? Рассмотрев пару примеров, Вася обнаружил, что через несколько применений медианного сглаживания последовательность может перестать изменяться. Будем говорить, что последовательность стабильна , если она не изменяется при применении к ней медианного сглаживания.
Васе стало интересно, всегда ли последовательность рано или поздно становится стабильной. Он просит вас написать программу, которая по заданной последовательности нулей и единиц определит, становится ли она когда-нибудь стабильной, и если да, то сколько раз для этого нужно применить к ней метод медианного сглаживания.
В первой строке входных данных находится одно целое число n ( 3 ≤ n ≤ 500 000 ) — число элементов в рассматриваемой последовательности.
В следующей строке находится исходная последовательность чисел a 1 , a 2 , ..., a n , состоящая только из нулей и единиц.
В случае, если последовательность никогда не станет стабильной, выведите одно число - 1 .
В противном случае в первой строке выведите одно число — минимальное число раз, которое нужно применить алгоритм медианного сглаживания, прежде чем последовательность станет стабильной. Во второй строке выведите n чисел через пробел — саму итоговую последовательность.
Во втором примере стабилизация наступает через два шага:
, а последовательность
00000
, как нетрудно заметить, является стабильной.
4 0 0 1 1
0 0 0 1 1
5 0 1 0 1 0
2 0 0 0 0 0
Как вам, может быть, известно, на одном хлебобулочном заводе, который специализируется на производстве багетов, всем заправляет вовсе не гендиректор, а его жена, хотя официально она даже не является сотрудницей завода. Однажды об этом узнал и сам гендиректор. Он страшно разозлися и решил показать жене, кто на заводе хозяин. Для этого он предложил ей сыграть в управленческую игру.
Иерархия сотрудников завода описывается следующими простыми правилами:
- Всего на заводе n + 1 сотрудник. У каждого из них, кроме гендиректора, есть непосредственный начальник — один из других сотрудников. У гендиректора начальника нет.
- Все сотрудники завода так или иначе подчинены гендиректору, то есть любой сотрудник является либо гендиректором, либо непосредственным подчинённым гендиректора, либо непосредственным подчинённым непосредственного подчинённого гендиректора и так далее.
Гендиректор и его жена ходят по очереди, начинает гендиректор. За один ход необходимо выбрать одного произвольного сотрудника, чьим непосредственным начальником ещё не является гендиректор, и исправить эту оплошность, то есть назначить гендиректора непосредственным начальником выбранного сотрудника. Тот, кто не может сделать ход, проигрывает.
Определите, кто из супругов выиграет при правильной игре и сможет называть себя настоящим хозяином завода.
В первой строке находится число n ( 1 ≤ n ≤ 200 000 ) — количество сотрудников на хлебобулочном заводе, не считая директора .
Во второй строке следуют числа d 1 , d 2 , ..., d n ( 0 ≤ d i < i ), где d i означает номер сотрудника, который является непосредственным начальником сотрудника под номером i . Сам гендиректор имеет номер 0 .
Если при правильной игре выигрывает гендиректор, то выведите « Husband » (без кавычек). Если, как бы ни старался гендиректор, победу в игре одержит его жена, то выведите « Wife » (без кавычек).
Во первом примере все сотрудники уже являются непосредственными подчинёнными гендиректора, поэтому в игре нельзя сделать ни одного хода.
2 0 0
Wife
6 0 1 2 1 4 5
Husband
Условие пока не опубликовано...
6 1 police p m
molice
11 6 abacabadaba a b b c a d e g f a b b
cdcbcdcfcdc
Лесничий Хогвартса Хагрид собирается заняться разведением драконов, для этого он намерен закупить партию драконьих яиц. С этой целью он отправился в волшебный зоомагазин в Косом переулке.
Хагриду известно, что магическая сила новорождённого дракона зависит от веса яйца дракона в фунтах, а именно, она равняется сумме квадратов цифр в десятичной записи веса. Заметим, что в волшебном мире вес яйца дракона всегда выражается целым положительным числом фунтов.
Естественно, Хагрид желает завести себе драконов как можно большей суммарной силы, но его мотоцикл не сможет поднять груз весом более l фунтов. Ассортимент в волшебном зоомагазине поистине волшебный, поэтому можно считать, что для любого целого положительного веса x , Хагрид может купить в магазине произвольное количество яиц драконов с таким весом.
Напишите программу, которая определит максимальную возможную суммарную волшебную силу драконов, родившихся из яиц, которые Хагрид сможет увезти на своём мотоцикле.
В единственной строке входных данных находится целое число l ( 1 ≤ l ≤ 10 12 ) — максимальный вес груза, который может поднять мотоцикл Хагрида.
Выведите единственное целое число — максимальную возможную суммарную волшебную силу драконов, которых Хагрид будет разводить рядом с Хогвартсом, при условии, что он съездит за яйцами только один раз и увезёт всю покупку на своём мотоцикле.
В первом примере выгоднее всего купить одно яйцо весом 6 фунтов.
Во втором примере выгоднее всего купить два яйца весом 9 фунтов каждое.
6
36
18
162
Команда пушистых спасателей сидела без дела в своём дупле, когда неожиданно поступил сигнал бедствия. В считанные мгновения все были на своих местах, и дирижабль бурундучков-спасателей отправился в путь.
Будем считать, что действие происходит на декартовой плоскости. База спасателей расположена в точке ( x 1 , y 1 ) , а сигнал бедствия поступил из точки ( x 2 , y 2 ) .
Благодаря инженерному искусству Гаечки, летательный аппарат спасателей может произвольное количество раз в любые моменты времени мгновенно изменить свою текущую скорость и направление движения. Единственное ограничение — величина скорости дирижабля относительно воздуха не может превосходить
метров в секунду.
Разумеется, как настоящий спасатель, Гаечка хочет лететь так, чтобы оказаться на месте происшествия как можно быстрее. Дело осложняется тем, что в небе дует ветер, который влияет на перемещение дирижабля. Согласно прогнозу погоды, в ближайшие
t
секунд скорость ветра будет характеризоваться вектором
(
v
x
,
v
y
)
, а по прошествии
t
секунд скорость ветра станет равна
(
w
x
,
w
y
)
. Данные вектора определяют как направление ветра, так и его скорость. Формально, если дирижабль находится в точке
(
x
,
y
)
, его собственная скорость относительно воздуха равна нулю и при этом дует ветер
(
u
x
,
u
y
)
, то для любого неотрицательного вещественного числа
, через
секунд дирижабль окажется в точке с координатами
.
Гаечка занята управлением дирижаблем, поэтому она попросила Чипа вычислить, как скоро они смогут быть на месте, с чем он легко справился. Однако Дейл убеждён, что Чип не справился вычислить ответ и назвал случайное значение, лишь бы не ударить в грязь лицом перед Гаечкой. Чтобы пристыдить Чипа, Дейл попросил вас посчитать правильный ответ.
Гарантируется, что скорость ветра в любой момент времени строго меньше максимально возможной скорости дирижабля относительно воздуха.
В первой строке ввода записаны четыре целых числа x 1 , y 1 , x 2 , y 2 ( | x 1 |, | y 1 |, | x 2 |, | y 2 | ≤ 10 000 ) — координаты дупла спасателей и точки, из которой поступил сигнал бедствия.
Во второй строке записаны два целых числа
и
t
(
0 <
v
,
t
≤ 1000
), задающих соответственно максимальную скорость дирижабля бурундуков и момент времени, в который произойдёт перемена ветра, согласно прогнозу погоды.
Далее, по одной в строке записаны две пары целых чисел
(
v
x
,
v
y
)
и
(
w
x
,
w
y
)
, описывающие ветер в первые
t
секунд и ветер, который будет дуть всё остальное время, соответственно. Гарантируется, что
и
.
Выведите единственное число — минимальное время, через которое спасатели смогут оказаться в точке ( x 2 , y 2 ) . Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6 .
А именно: пусть ваш ответ равен
a
, а ответ жюри —
b
. Проверяющая программа будет считать ваш ответ правильным, если
.
0 0 5 5 3 2 -1 -1 -1 0
3.729935587093555327