Форум Всеукраїнської інтернет-олімпіади NetOI

По предварительной договорённости с Андреем Максаем aka MAXXX было решено для всех интересующихся попробовать устроить как можно более полный разбор задач второго тура – только по нашим собственным представлениям. Сразу скажу – мы не авторы, с многоуважаемым жюри никакими ниточками не связаны , а просто весёлые люди. По той же договорённости на мою долю достались Street, MiniLine и NewTower, Андрюше же, соответственно, CrossGroup и Liquidation. Что же, если кого заинтересовало это пустословное вступление, может начинать читать

Задача Street
Пункт раз. Основная идея. До неё несложно было догадаться, как по мне.
Рассмотрим дом, состоящий из некоторого количества (скажем, K) этажей и попытаемся высчитать количество способов раскраски для него (я обозначу это некоторой функцией F(K)). Для этого посмотрим на самый верхний этаж, имеющий номер К. Если он покрашен в белый цвет, тогда (K-1)-й спокойно можно красить как в красный, так и в белый цвет – ограничений нет. Таким образом, зафиксировав цвет верхнего этажа как белый, мы видим, что количество раскрасок в таком случае равняется количеству раскрасок для K-1 этажа – F(K-1).
А если верхний этаж – красный? В таком случае предпоследний, (К-1)-й этаж уже нельзя делать того же цвета – будет большая бяка, у мэра эстетствующие наклонности взыграют! Итак, (К-1)-й этаж мы в принудительном порядке делаем белым, а дальше уже проблем вроде бы и нет и оставшиеся этажи можно красить как угодно. Количество таких раскрасок равно F(K-2).
Таким образом, F(K)=F(K-1)+F(K-2). По-моему, эта формула большинству читателей знакома, не так ли? Знаменитый ряд чисел Фибоначчи, в котором, каждое является суммой дух предыдущих, выглядит так:
1 1 2 3 5 8 13 21 34 55 89 144 ………
В данном случае подсчёт начинается с третьего числа (ибо F(1)=2), и строчка, записанная нерадивым программистом, выглядит как «23581321345589144…» Дело остаётся за малым: узнать числа Фибоначчи.
Несложные подсчёты показывают, что при необходимости определить 10000000-ю цифру в строке потребуется вычислить огромное количество чисел Фибоначчи, причем последнее из них будет состоять более чем из 2000 разрядов. Без длинной арифметики не обойтись. Другой вопрос, как это делать. Существует 2 общепринятых метода вычисления ряда. Первый заключается в обычном подсчёте «одно за другим» и требует для своей реализации при умном подходе всего лишь 2 массива для представления длинных чисел. Если нет желания менять местами индексы (хотя это несложно – взгляните ниже на код программы), можно использовать 3 массива. Второй же способ – метод матриц – построен на весьма занимательном факте:
( 1  1 )  *  (  F(k)   )   =   ( F(k+1) )
( 1  0 )      ( F(k-1) )        (   F(k)   )
,который преобразовывается в
( 1  1 )^(K-1)  *  ( 1 )   =   (  F(k)   )
( 1  0 )                ( 0 )        ( F(k-1) )


(прошу прощения за ОЧЕНЬ извращённую попытку нарисовать матрицы в условиях форума NetOI )
Его доказательство, как и множество комментариев, найти в Инете совершенно несложно, поэтому не буду вдаваться в разглагольствования. Скажу только, что споры по поводу того, какой из методов будет быстрее, не угасли среди моих знакомых до сих пор. Я лично придерживаюсь первого, ибо даже на глазок операций с длинными числами при работе с матрицами более чем хватает… Несмотря на то, что оценка сложности простого вычисления O(K), а матричного – O(log K).
И ещё немного оптимизаций. Можно потрудиться и заранее вычислить некоторые «базисные точки». Например, найти в домашних условиях число Фибоначчи, содержащее в себе 5000000-ю цифру вышеуказанной строки, забить его в константы и в зависимости от значения входящего К разделять решение на две ветки. Сложность алгоритма сокращается почти вдвое. Идя ещё дальше, можно найти… четыре(!) числа Фибоначчи через равные промежутки и использовать их в качестве базисных. Главное в таком подходе – не довести ситуацию до абсурда. «Золотое правило механики» получается: выигрывая в скорости программы, мы теряем в её объёме, а главное – в гарантии качества написания. Ибо код даже для одной отправной точки получается… кгм… некрасивый и поначалу 100% глючный.
На этом с числами Фибоначчи всё. В постскриптуме – мой код решения на Паскале.
P.S.

 program Street;

{$APPTYPE CONSOLE}
const
  Osn=10000;

type
  TLong=array [0..512] of integer;

var
  a:array [0..1] of TLong;
  K,quan,last:longint;
  qf,_0,_1:byte;
  zp,nzp,t,i:integer;
  s:string;

begin
  fillchar(a,sizeof(a),0);
  Readln(k);
  if k=1
    then begin Writeln(2); halt end
    else if k=2 then begin Writeln(3); halt end;
  a[0][0]:=1; a[0][1]:=2;
  a[1][0]:=1; a[1][1]:=3;
  _0:=0; _1:=1;
  quan:=2;
  repeat
    if a[_0][0]>a[_1][0] then t:=a[_0][0] else t:=a[_1][0];
    zp:=0;
    for i := 1 to t do
    begin
      nzp:=(a[_0][i]+a[_1][i]+zp) div osn;
      a[_0][i]:=(a[_0][i]+a[_1][i]+zp) mod osn;
      zp:=nzp;
    end;
    a[_0][t+1]:=zp;
    if a[_0][t+1]>0 then a[_0][0]:=t+1 else a[_0][0]:=t;
    if a[_0][a[_0][0]]<10 then qf:=1 else if a[_0][a[_0][0]]<100 then qf:=2 else if a[_0][a[_0][0]]<1000 then qf:=3 else qf:=4;
    last:=(a[_0][0]-1)*4+qf;
    inc(quan,last);
    t:=_0; _0:=_1; _1:=t;
  until quan>=K;
  dec(K,quan-last);
  if k<=qf
    then begin
      i:=a[_1][0];
      str(a[_1][i],s);
      writeln(s[k])
    end
    else begin
      dec(k,qf);
      i:=a[_1][0]-(((k-1) div 4)+1);
      str(a[_1][i],s);
      while length(s)<4 do s:='0'+s;
      if k mod 4=0 then i:=4 else i:=k mod 4;
      writeln(s[i]);
    end;
end.

Задача MiniLine
Разбор именно этой задачи в условиях форума выполнить будет сложнее всего. В голову даже приходила идея открыть M$ Paint и порисовать немножко иллюстраций, которые потом можно было бы выложить на некоем имеджхостинге и таким образом усилить наглядность… но примерно прикинув собственные чертёжные и дизайнерские способности, я понял, что для нормального иллюстрирования начинать эту затею следовало бы эдак недельку назад… Так что не взыщите – рассказываю как есть
(Альтернативным вариантом для иллюстрирования была в итоге выбрана следующая номенклатура: всё дело рассматривается на параллелепипеде размерами X*Y*Z=10*8*6, и по ходу разговора я постоянно буду на нём приводить в пример какие-нибудь точки.)
Для начала рассмотрим все варианты взаимного расположения точек на рёбрах параллелепипеда. В зависимости от их принадлежности некоторым рёбрам/граням можно выделить 5 основных случаев:
1)    Точки лежат на одном ребре: у них две координаты совпадают и равны либо 0, либо X, Y или Z. Примеры: (5; 0; 0) и (7; 0; 0), (10; 4;0) и (10; 7; 0), (0; 8; 2) и (0; 8; 3).
2)    Точки лежат на двух соседних рёбрах: у них совпадает и равна 0, X, Y или Z только одна координата. Примеры: (5; 0; 0) и (10; 1; 0), (10; 8; 5) и (3; 8; 6) и т.д.
3)    Точки лежат на одной грани, но на противоположных рёбрах: одна пара координат совпадает и равна вы догадались чему , одна различна, а разность третьей пары равняется соответствующему ребру параллелепипеда. Пример: (0; 8; 2) и (10; 8; 4).
4)    Точки лежат на параллельных рёбрах, но на разных гранях: разность двух пар координат равна соответствующему ребру. Пример: (6; 0; 0) и (9; 8; 6).
5)    Точки лежат на скрещивающихся рёбрах: разность одной пары координат точно равна ребру. Можно и двух, и трёх пар (в последнем случае точки попадают в вершины). Пример: (10; 0; 1) и (8; 8; 6).
Рассмотрим их все и выведем некоторые закономерности. В первом случае путь очевиден – прямо по ребру. Во втором тоже кратчайший вариант однозначен - любые другие ответвления приведут к тому, что некоторые рёбра нам придётся пройти полностью, в то время как при очевидном пути из двух отрезков мы эти рёбра преодолеваем лишь частично. Таким образом, можно не рассматривать всяческие повороты и симметрии параллелепипеда, а сразу дать общую формулу для случаев 1 и 2: |x1-x2|+|y1-y2|+|z1-z2|.
Теперь переходи к остальной тройке. В отличие от уже рассмотренных, их отличает присутствие одного признака: есть хоть одна пара координат, разность между которыми равна соответствующему ребру. Это важно. Потому что тогда и только тогда у нас появляется выбор, с какой стороны преодолевать это ребро (говоря точнее, по которому из рёбер параллелограмма, имеющих таковую длину, двигаться). И кратчайший путь, получается, зависит только от суммы оставшихся маленьких отрезочков по остальным двум осям, по которым приходится идти. Вариантов всего два: куда повернуть в самом начале. Потому по иксу сумма этих отрезочков равна, в одном случае, x1+x2, в другом (X-x1)+(X-x2)=2*X-x1-x2. По игреку и зету значения аналогичны. И общая формула для любого движения, подчиняющегося случаям 3, 4, 5, выглядит так: min(x1+x2,2*X-x1-x2)+min(y1+y2,2*Y-y1-y2)+min(z1+z2,2*Z-z1-z2).
Заметим, что, если разность одной или двух пар координат равна соответствующим рёбрам, а остальные пары совпадают (частные подслучаи пунктов 1 и 2 – точки в вершинах), то вторая формула вырождается в первую. Можете проверить.
Окончательный код программы дан ниже. Сложность решения – O(1).
Существует ещё один, кардинально другой подход к решению MiniLine. Он основан на теории графов. Действительно, что мешает представить 8 вершин параллелепипеда и 2 целевые точки как 10 вершин графа, банальными геометрическими формулами посчитать длины (веса) его рёбер и свести задачу к классической: кратчайший путь в графе со взвешенными рёбрами? Существует масса алгоритмов: волновой (он же поиск в ширину), Дейкстры, Флойда-Уоршелла (хотя последний тут лучше не применять ), пишутся они значительно быстрее и не надо париться с никакой математикой. Кода только больше получится. Проблема в том, что оценка сложности каждого из вышеуказанных алгоритмов не меньше O(N^2). Конечно, время работы T(100) считается смехотворным, но всё-таки это ведь NetOI. Тут особенно ярко понимаешь смысл фразы «Промедление смерти подобно». Много человек писало и сдало именно графовый алгоритм, они уверены, что тайм-лимит «авторское время*1.5» он пройдёт без каких-либо проблем. Не хочу спорить. Попросту не знаю. Всё зависит от метода, который применял автор (а тут я на 99% уверен, что присутствовали именно формулы и случаи). В любом случае, метод в рамках общего разбора я таки привёл.
Известны и другие решения. Все они в какой-то мере преобразовывают первую идею, только рассматривают больше частных случаев и иногда применяют всяческие симметрии и повороты фигур и точек. Самое страшное из виденных мною солюшенов занимало 125 строчек и делилось в итоге на 15 веток вариантов. Позвольте оставить его без комментариев… Хотя это не так критично. Сложность-то всё равно О(1), а главное – результат.
И на этой ноте мы покидаем наш любимый параллелограмм…
P.S.

 program MiniLine;

{$APPTYPE CONSOLE}
var X,Y,Z,x1,y1,z1,x2,y2,z2:integer;

function min(a,b:integer): Integer;
begin
  if a<b
    then min:=a
    else min:=b;
end;

begin
  Readln(X,Y,Z,x1,y1,z1,x2,y2,z2);
  if (abs(x2-x1)=X) or (abs(y2-y1)=Y) or (abs(z2-z1)=Z)
    then Writeln(min(x1+x2,2*X-x1-x2)+min(y1+y2,2*Y-y1-y2)+min(z1+z2,2*Z-z1-z2))
    else Writeln(abs(x2-x1)+abs(y2-y1)+abs(z2-z1));
end.

Задача NewTower
На мой очень скромный взгляд, модификация «Ханойских башен» - самая яркая задачка этого тура. Тут вам и мозги, и немного аккуратного кодинга, и чуточку знания знаменитостей. А главное – она подразумевает огромное разнообразие решений, которые в итоге все приводят, разумеется, к одному результату. Но давайте обо всём по порядку. Сначала выкладываю свой метод, оформлять его буду пошагово – краткими отдельными утверждениями.
Шаг 1. Очевидно, что набор дисков вида 111000101100 перекладывается за то же время, что и набор 000111010011. Какая разница, означает ли ноль жёлтый диск или наоборот? Поэтому для ускорения рассказа условимся всегда иметь в виду только последовательности, начинающиеся на 1. Если же во входных данных первой цифрой стоит 0 – инвертируем их.
Шаг 2. Всю башенку можно представить как подряд идущие группы ноликов и единичек, то есть 11100110000100 это:
первая группа из 3 единичек;
вторая группа из 2 ноликов;
третья группа из 2 единичек;
четвёртая группа из 4 ноликов;
пятая группа из 1 единички;
шестая группа из 2 ноликов.
Назовём эти количества соответственно a1, a2, a3, …, ak.
Шаг 3. Сейчас мне придётся дать некоторое утверждение, которое объясняться будет только лишь в конце рассказа. Поэтому поверьте мне на слово: всё решение делится на 2 кардинально отличающихся случая. Когда a2=1 и когда a2<>1. (Для любителей Си: a2==1 и a2!=1). Позже будет ясно, почему.
Шаг 4. Рассматриваем второй случай (a2<>1). Имеем дело с такой ситуацией:
Все операции с группами дисков можно фактически разделить на два класса: перенос и подкладывание. Перенос – это когда группу из K дисков нам надо перенести на целевой стержень, используя вспомогательный, и никаких препятствий нам к этому нет. То бишь вспомогательный стержень изначально свободен, и на целевом или совсем пусто, или лежат только диски больших радиусов. Буду обозначать такое действие как функцию K(N), где N – количество переносимых дисков, а значение функции K(N) – количество требуемых для этого ходов.
Остаётся ещё подкладывание. Оно тоже наглядно определяется. На целевом диске уже что-то лежит, и нам надо подложить группу дисков большего радиуса под низ. Вспомогательный стержень свободен. Такую операцию будем обозначать Под(M,K) (читается «подложить M дисков под К»).
Думаю, ни у кого нет сомнений, что тогда ответ задачи будет выглядеть следующим образом:
K(a1)+K(a2)+Под(а3, а1)+Под(а4, а2)+Под(а5, а1+а3)+Под(а6, а2+а4)+Под(а7, а1+а3+а5)+…
На всякий случай всё же прокомментирую формулу. Первую группу дисков переносим на свой диск без проблем за K(a1). Вторую потом, независимо от них, за К(а2). После подкладываем группу из а3 единичек под уже лежащие на их стержне а1. Затем то же с ноликами. И по такой схеме до конца. Дело за малым: вычислить значения функций К и Под.
Шаг 5. Функция К представляет собой просто-напросто задачу «Ханойские башни» в своей оригинальной формулировке. И потому получаем первую формулу:
K(N)=2^N-1
Шаг 6. Для того чтобы найти значение функции Под(M, K), приходится копнуть глубже, а именно в понимание того, как именно происходит это самое подкладывание. Итак, представим себе ситуацию следующего образца: М дисков лежат на стартовом стержне, К меньших радиусов – на целевом, полосатый свободен, о четвёртом пока можно забыть – он на этом этапе смысловой нагрузки не несёт. Видим, что пирамидку из М+К дисков строить приходится постепенно: сначала К+1 получим в нужном порядке, потом К+2 и так далее до финиша. Это достигается следующим алгоритмом:
один диск со стартового стержня сносим на полосатый;
на него перекидываем К, получаем пирамидку высотой К+1;
один диск со стартового стержня сносим на целевой;
на него перекидываем К+1 с полосатого, получаем пирамидку высотой К+2;
один диск со стартового стержня сносим на полосатый;
на него перекидываем К+2…
…и так далее.
Таким образом, пирамида постоянно кочует с полосатого стержня на цветной и обратно, с каждым разом увеличиваясь в размерах. Так как радиусы К стержней меньше, чем радиусы остальных дисков этого цвета, то переносы пирамидки будут происходить без проблем за К(текущая_высота_пирамидки) операций. Весь вопрос только в том, где в итоге окажется нужная пирамида из M+K дисков: на целевом стержне или на полосатом? Это зависит от чётности числа М. Если М чётно, мы придём на целевой стержень, если нечётно – на полосатый. Таким образом, чтобы обеспечить минимальность суммарного количества ходов, в случае нечётного М первым ходом сносить на полосатый стержень надо не диск со стартового, а весь набор из К штук – с цветного. Потому что если мы начнём работать по обычному алгоритму, то в конце концов переносить на цветной стержень придется М+К дисков, а не К. А это несоизмеримо длиннее.
Имеем для чётного М:
Под(М, К) = 1 + К(К) + 1 + К(К+1) + 1 + К(К+2) + … + 1 + К(М+К-1) = 1 + (2^K-1) + 1 + (2^(K+1)-1) + 1 + (2^(K+2)-1) + … + 1 +(2^(M+K-1)-1) = 2^K + 2^(K+1) + 2^(K+2) + … + 2^(M+K-1) = (2^K + 2^(K+1) + 2^(K+2) + … + 2^(M+K-1)) + (2^1 + 2^2 + 2^3 + … + 2^(K-1)) - (2^1 + 2^2 + 2^3 + … + 2^(K-1)) (2^1 + 2^2 + 2^3 + … + 2^(K-1)) = 2^(M+K) – 2^K
Для нечётного М имеем то же самое плюс (2^K - 1), то есть тогда Под(М, К) = 2^(M+K) -1.
А эти значения уже очень несложно высчитать. Желательно это вообще делать руками, а в окончательной программе забить в массив констант. Вот первые его рядки и строчки:
Под(M, K)
    M   1   2    3    4

K         3    6   15  30
1         7   12  31  60
2        15  24  63 120
3        31  48 127  …
4        63  96 255
5       127  …  …

Шаг 7. А теперь вспомним про первый странный случай. Его уникальность на самом деле в том, что один диск можно перенести на свой стержень за одно действие в любой момент, и для этого не надо ему освобождать полосатый стержень. Таким образом, можно вообразить, что этого первого нолика вообще нет, совместить первую и вторую группы единиц и заняться их перекладыванием за K(a1+a3). А в середине, когда потребуется, за 1 операцию скинуть в нужное место единственный нолик. После этого всё опять вернётся на круги своя – к стандартному алгоритму.
Сложность программы – O(N).
Код ниже.

 program NewTower;

{$APPTYPE CONSOLE}
const
k:array [1..30] of longint=(1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,
                            2097151,4194303,8388607,16777215,33554431,67108863,134217727,268435455,536870911,1073741823);
pod: array [1..29] of array [1..29] of longint=(
(3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,
  16777215,33554431,67108863,134217727,268435455,536870911,1073741823),
(6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,196608,393216,786432,1572864,3145728,6291456,12582912,
  25165824,50331648,100663296,201326592,402653184,805306368,1610612736),
(15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,
  33554431,67108863,134217727,268435455,536870911,1073741823,0,0),
(30,60,120,240,480,960,1920,3840,7680,15360,30720,61440,122880,245760,491520,983040,1966080,3932160,7864320,15728640,
  31457280,62914560,125829120,251658240,503316480,1006632960,2013265920,0,0),
(63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,
  33554431,67108863,134217727,268435455,536870911,1073741823,0,0,0,0),
(126,252,504,1008,2016,4032,8064,16128,32256,64512,129024,258048,516096,1032192,2064384,4128768,8257536,16515072,33030144,
  66060288,132120576,264241152,528482304,1056964608,2113929216,0,0,0,0),
(255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,
  67108863,134217727,268435455,536870911,1073741823,0,0,0,0,0,0),
(510,1020,2040,4080,8160,16320,32640,65280,130560,261120,522240,1044480,2088960,4177920,8355840,16711680,33423360,66846720,
  133693440,267386880,534773760,1069547520,2139095040,0,0,0,0,0,0),
(1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863,
  134217727,268435455,536870911,1073741823,0,0,0,0,0,0,0,0),
(2046,4092,8184,16368,32736,65472,130944,261888,523776,1047552,2095104,4190208,8380416,16760832,33521664,67043328,134086656,
  268173312,536346624,1072693248,2145386496,0,0,0,0,0,0,0,0),
(4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863,134217727,
  268435455,536870911,1073741823,0,0,0,0,0,0,0,0,0,0),
(8190,16380,32760,65520,131040,262080,524160,1048320,2096640,4193280,8386560,16773120,33546240,67092480,134184960,268369920,
  536739840,1073479680,2146959360,0,0,0,0,0,0,0,0,0,0),
(16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863,134217727,268435455,
  536870911,1073741823,0,0,0,0,0,0,0,0,0,0,0,0),
(32766,65532,131064,262128,524256,1048512,2097024,4194048,8388096,16776192,33552384,67104768,134209536,268419072,536838144,
  1073676288,2147352576,0,0,0,0,0,0,0,0,0,0,0,0),
(65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863,134217727,268435455,536870911,
  1073741823,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(131070,262140,524280,1048560,2097120,4194240,8388480,16776960,33553920,67107840,134215680,268431360,536862720,1073725440,
  2147450880,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863,134217727,268435455,536870911,1073741823,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(524286,1048572,2097144,4194288,8388576,16777152,33554304,67108608,134217216,268434432,536868864,1073737728,2147475456,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(1048575,2097151,4194303,8388607,16777215,33554431,67108863,134217727,268435455,536870911,1073741823,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(2097150,4194300,8388600,16777200,33554400,67108800,134217600,268435200,536870400,1073740800,2147481600,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(4194303,8388607,16777215,33554431,67108863,134217727,268435455,536870911,1073741823,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(8388606,16777212,33554424,67108848,134217696,268435392,536870784,1073741568,2147483136,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(16777215,33554431,67108863,134217727,268435455,536870911,1073741823,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(33554430,67108860,134217720,268435440,536870880,1073741760,2147483520,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(67108863,134217727,268435455,536870911,1073741823,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(134217730,268435460,536870920,1073741840,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(268435455,536870911,1073741823,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(536870910,1073741820,2147483640,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(1073741823,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0));

var
  N,i,a,p,fg,ftotal,stotal,q:byte;
  ans:longint;

begin
  ftotal:=0;
  a:=2;
  Read(N,fg);
  repeat
    inc(ftotal);
    if ftotal<N then read(a);
  until (a<>fg) or (ftotal=N);
  if ftotal=N then begin writeln(k[ftotal]); halt end;
  stotal:=1;
  if ftotal+1=N then begin writeln(k[ftotal]+1); halt end;
  read(a);
  i:=ftotal+1;
  if a=fg
    then begin
      repeat
        inc(ftotal);
        inc(i);
        if i<N then read(a);
      until (a<>fg) or (i=N);
      ans:=k[ftotal]+1;
    end
    else begin
      repeat
        inc(stotal);
        inc(i);
        if i<N then read(a);
      until (a=fg) or (i=N);
      ans:=k[ftotal]+k[stotal];
    end;
  if i=N then begin writeln(ans); halt end;
  p:=1-a;
  q:=0;
  Repeat
    if a<>p
      then begin
        if a=fg
          then begin
            if q<>0 then inc(ans,pod[q][stotal-q]);
            inc(ftotal);
          end
          else begin
            if q<>0 then inc(ans,pod[q][ftotal-q]);
            inc(stotal);
          end;
        q:=1;
      end
      else begin
        inc(q);
        if a=fg
          then inc(ftotal)
          else inc(stotal);
      end;
    inc(i);
    if i<N then begin p:=a; read(a) end;
  Until i=N;
  if a=fg
    then inc(ans,pod[q][ftotal-q])
    else inc(ans,pod[q][stotal-q]);
  Writeln(ans);
end.

Все спасибо за внимание Передаю слово своему коллеге и соратнику: слушаем варианты решения оставшихся задач.