eolymp
bolt
Try our new interface for solving problems
Məsələlər

Праздничные дни

Праздничные дни

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Жители Флатландии очень любят праздники. Они считают, что любая более-менее важная памятная дата заслуживает того, чтобы ее отметить. Поэтому во Флатландии очень много государственных праздников. Настолько много, что там нет даже обычных выходных (как суббота и воскресенье в России) — жителям вполне хватает государственных праздников.

У каждого праздника есть день, когда он должен отмечаться. При этом день многих праздников определяется по очень сложным правилам; например, День защиты Флатландских волков отмечается в последнее полнолуние года, Международный День СУНЦов — в 42-й день летних каникул, а День Флатландского метеоролога — на следующий день после первого дождливого летнего четверга. (Правда, флатландские метеорологи настолько суровы, что могут предсказать, на какой день придется их профессиональный праздник, за год до него.)

Естественно, что при такой сложной и запутанной системе праздников нередко случается так, что несколько праздников выпадают на один и тот же день. Но флатландцы — очень систематичные люди, и они не могут отмечать несколько праздников в один и тот же день, поэтому в таких случаях праздники надо переносить.

Естественно, просто так переносить праздники нельзя. Перенос праздника допускается только при условии, что все дни между правильной датой праздника и тем днем, на который этот праздник переносится, также будут праздничными. Строго говоря, праздник с дня i можно отмечать в день j при одном из двух следующих условий:

  • или i=j,

  • или i≠j, но при этом в день i, а также во все дни между i и j невключительно отмечаются какие-то другие праздники (обратите внимание, что может быть как i < j, так и i > j).

Таким образом, весь год будет состоять из чередующихся блоков рабочих и выходных дней, и перенос праздника допустим только при условии, что он попадает в тот же блок.

Флатландцы — последовательные люди, и придерживаются принципа "работать — так работать, отдыхать — так отдыхать". Поэтому они не любят частых смен выходных и рабочих дней. Поэтому праздники должны быть перенесены так, чтобы средняя длина блоков выходных дней была наибольшей.

Сегодня во Флатландии, как и во всем мире, наступает Новый год. Через несколько часов президент Флатландии выступит с обращением перед гражданами. По традиции, он должен озвучить календарь выходных и рабочих дней на наступающий год. Это расписание должен был подготовить Министр Флатландии по Праздникам, но, к сожалению, вчера отмечался День Министров Флатландии, и потому Министр не успел подготовить календарь — и не успеет, поскольку компьютером пользоваться он не умеет, а вручную составление календаря отнимает много времени.

Поэтому подготовить календарь поручено вам. Напишите программу, которая, зная, на какой день сколько праздников приходится, перенесет их в соответствии с правилами. Учтите, что нельзя праздники отмечать раньше первого дня года, и нельзя их отмечать позже последнего дня.

Giriş verilənləri

На первой строке входного файла находится одно число n — количество дней во Флатландском году (1n4000). На второй строке находятся n неотрицательных целых чисел, i-ое из которых указывает, сколько праздников приходится на i-ый день года.

Гарантируется, что сумма всех чисел во второй строке входного файла не превосходит n.

Çıxış verilənləri

Выведите в выходной файл n символов: для каждого дня года выведите, должен он быть выходным или рабочим. Выводите символ 'X' (латинская заглавная буква X) для рабочего дня и символ '*' (звездочка) для выходного.

Nümunə

Giriş verilənləri #1
1
0
Çıxış verilənləri #1
X
Müəllif Петр Калинин, ЛКШ. Зима - 2011
Mənbə Зимняя школа, Харьков 2011, День 5