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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2007-11-29 00:02:10

Skiminok
Новий користувач
Звідки: Киев, Украина
Зареєстрований: 2006-01-19
Повідомлень: 144
Вебсайт

Задачи, коды, тесты... Начинаем разбор!

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

Задача 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 smile )
Его доказательство, как и множество комментариев, найти в Инете совершенно несложно, поэтому не буду вдаваться в разглагольствования. Скажу только, что споры по поводу того, какой из методов будет быстрее, не угасли среди моих знакомых до сих пор. Я лично придерживаюсь первого, ибо даже на глазок операций с длинными числами при работе с матрицами более чем хватает… Несмотря на то, что оценка сложности простого вычисления 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 и порисовать немножко иллюстраций, которые потом можно было бы выложить на некоем имеджхостинге и таким образом усилить наглядность… но примерно прикинув собственные чертёжные и дизайнерские способности, я понял, что для нормального иллюстрирования начинать эту затею следовало бы эдак недельку назад… Так что не взыщите – рассказываю как есть smile
(Альтернативным вариантом для иллюстрирования была в итоге выбрана следующая номенклатура: всё дело рассматривается на параллелепипеде размерами 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)    Точки лежат на одной грани, но на противоположных рёбрах: одна пара координат совпадает и равна вы догадались чему smile , одна различна, а разность третьей пары равняется соответствующему ребру параллелепипеда. Пример: (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 вершин графа, банальными геометрическими формулами посчитать длины (веса) его рёбер и свести задачу к классической: кратчайший путь в графе со взвешенными рёбрами? Существует масса алгоритмов: волновой (он же поиск в ширину), Дейкстры, Флойда-Уоршелла (хотя последний тут лучше не применять smile ), пишутся они значительно быстрее и не надо париться с никакой математикой. Кода только больше получится. Проблема в том, что оценка сложности каждого из вышеуказанных алгоритмов не меньше O(N^2). Конечно, время работы T(100) считается смехотворным, но всё-таки это ведь NetOI. Тут особенно ярко понимаешь смысл фразы «Промедление смерти подобно». Много человек писало и сдало именно графовый алгоритм, они уверены, что тайм-лимит «авторское время*1.5» он пройдёт без каких-либо проблем. Не хочу спорить. Попросту не знаю. Всё зависит от метода, который применял автор (а тут я на 99% уверен, что присутствовали именно формулы и случаи). В любом случае, метод в рамках общего разбора я таки привёл.
Известны и другие решения. Все они в какой-то мере преобразовывают первую идею, только рассматривают больше частных случаев и иногда применяют всяческие симметрии и повороты фигур и точек. Самое страшное из виденных мною солюшенов занимало 125 строчек и делилось в итоге на 15 веток вариантов. Позвольте оставить его без комментариев… Хотя это не так критично. Сложность-то всё равно О(1), а главное – результат.
И на этой ноте мы покидаем наш любимый параллелограмм… smile
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.

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


Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом системному программисту. Он исправит ошибки в трансляторе.
http://wwp.icq.com/scripts/online.dll?icq=282667777&amp;img=5ICQ 282667777

Поза форумом

 

#2 2007-11-29 00:04:37

MAXXX
Новий користувач
Звідки: м. Київ
Зареєстрований: 2006-10-17
Повідомлень: 132

Re: Задачи, коды, тесты... Начинаем разбор!

Как мы договорились с Александром Полозовым aka Skiminok, напишу мои мысли по поводу CrossGroup  и Liquidation, один из вариантов решения NewTower. Скажу сразу – они не претендуют на оптимальность, как и коды на минимальный размер, красивость и т.п. Но вроде они правильные smile
CROSSGROUP
Сначала по поводу Кроссгрупа…Согласен в общем то с товарищем necro :                       

necro написав:

Задача чиста папкова - риспект за нийо.

Начну с пояснения теста из условия, он вроде вызвал довольно много вопросов…Сначала первые 4 человек садятся в…  кхм…  пусть это будет бобслей…  так вот, садятся в бобслей и едут около 11.6 км, потом высаживаются и бегут до финиша. А бобслей возвращается, подбирает вторую группу из 4 человек, которые все время до встречи бежали своим ходом, и едет с этой самой группой до финиша. Что интересно, по странному стечению обстоятельств финишируют одновременно обе группы – вторая на бобслее и первая своим ходом
     А теперь пару мыслей…Нетрудно понять, что оптимальным будет такой способ движения:   бобслей берет первую группу из 4 человек, отвозит в определенное место, там высаживает, оттуда они бегут к финишу. В это время все остальные бегут к финишу ногами. Бобслей разворачивается и встречается с группой, бегущей сзади. Оттуда опять берет 4 человека и везет их, пока не встречается с первой группой, которую он высадил в прошлый раз. Там высаживает всех из бобслея и все заново…Т.е. бобслей курсирует между двумя группами людей,   бегущими к  финишу с одинаковой скоростью… И когда он подбирает последнюю группу – он должен высадить уже на финише, куда    одновременно с этим приедут другие группы. Нетрудно доказать, что это оптимальный способ, но я этим заниматься не буду - олимпиада по информатике, а не физике или математике . А пока давайте поверим, что все прибывают к финишу одновременно для красоты – флэш-мобик такой smile
     Если принять этот факт – то можно сделать следующие выводы – время, за которое бобслей уедет от первой группы и вернется к ней – всегда одинаково. Также понятно, что чтобы все финишировали одновременно, надо чтобы каждый из спортсменов прошел одинаковое расстояние. (тогда он и проедет такое же расстояние, как и другие, а значит  - общее время его путешествия равно времени путешествия остальных и все придут к финишу одновременно).
Последнюю группу спортсменов бобслей должен везти прямо к финишу, т.е.он должен их подобрать за такое расстояние до финиша, на какое он провез и всех остальных участников.
     Теперь более точно: Пусть х – расстояние, которое проехал на бобслее каждый из спортсменов.
     Тогда x/v+(z-x)/u=t, где t – ответ, искомое время.
     До первой высадки бобслей двигался х/v минут, за это время остальные прошли расстояние (х/v)*u=x1.
     Потом до встречи бобслея и группы идущих сзади прошло время, равное (x-x1)/(u+v) ,
     а точка встречи имеет координаты  x1+((x-x1) /(u+v))*u=x2.
     Если вы поняли все до этого места , то теперь совсем просто smile :
     место k-той встречи бобслея и идущей сзади группы – точка с абсциссой k*х2.
     Тогда пусть Хл – точка последней встречи бобслея и спортсменов.
     Она же равна z-x=Хр.
     Приравниваем Хл и Хр, выражаем из уравнения t.
     Вот и все big_smile Если мне не верите и хотите проверить правильность формул – милости прошу smile  А вобще формулка такая:
                 T=Z/v*((2*k+1)*v+u)/((2*k+1)*u+v) ,
     где k – количество встреч бобслея и задней группы людей (не считая первого в точке 0.) Для примера из условия k=1.
Отдельно надо рассматривать еще 2 случая
1). U>=V. Тогда никто не садится в бобслей - все бегут.
Т=Z/U.
2). N<=4. Тогда все сразу садятся в бобслей и едут 
Т=Z/V.
Вот и все вроде). Код иллюстрирует все сказанное.  Единственное чего я в упор не понимаю  - почему в проверке на задачу ТЛ – секунда yikes

Код:

Var n,k,u,v,z:Longint;
    t:Real;
begin
 Read(n,v,u,z);
 If u>=v then Writeln((z/u):0:5) else
 If n<=4 then Writeln((z/v):0:5) else
 begin
  If n mod 4=0 then k:=(n div 4)-1 else k:=n div 4;
  t:=z/v;t:=t*((2*k+1)*v+u);
  t:=t/((2*k+1)*u+v);Writeln(t:0:5);
 end;
end.

LIQUIDATION
Вся Асседо очень велика.
День и ночь гуляла вся ББС
На веселом похороне Намцога!

     Не буду упоминать, чем закончилась эта грустная история- ведь Намцог всегда на линии пули)
Теперь про Ликвидейшн…ИМХО самая трудная в реализации задача и по недочетам в алгоритме может срезаться много участников…
Собственно, первое что приходит в голову (если туда хоть что-нибудь приходит ) – просто проверить, в каких террористов Намцог попасть не может, потому что пуля задевает дом или его стену…Ну а собственно реализаций этого алгоритма есть 2
     1). Проверяем, пересечет ли диагональ квадрата – дома прямая Намцог – террорист.
Надо отдельно рассматривать, в какой четвертьплоскости террорист относительно полковника – в зависимости от этого если террорист прячется за домом, прямая Намцог – террорист, пересекает одну из 4 диагоналей. Если террорист не левее и не ниже Намцога, то, если террорист прячется за домом  - путь пули пересекает диагональ из верхнего левого в нижний правый угол дома квадрата. Для других четвертьплоскостей соответственно:
                                         В.п.-н.л. |Н.л.-в.п.
                                          В.л.-н.п  |Н.л.-в.п.    
     2). Для диагонали каждого дома (как для каждого дома находить диагональ см.выше) определил для ее 2 концов полярный угол относительно Намцога. Также определим полярный угол для каждого террориста. Тогда проверка того, что террорист прячется за домом очень проста: Если полярный угол террориста находится между полярными углами двух концов диагонали и расстояние до террориста больше чем расстояние до ближайшего из углов квадрата – значит террорист укрыт рассматриваемым домом.
     3). Есть еще 3 алгоритм, который имеет меньшую оценку сложности, но из-за константы работает медленнее. А именно: сортируем диагонали по полярному углу, для каждого террориста делаем бинарный  (двоичный) поиск по упорядоченному массиву, пытаясь найти дом, за которым этот террорист может укрыться. Если мы нашли такой дом – террорист спасен .
Оценка сложности первых 2 алгоритмов в худшем случае – О(Т*N) ,  3-его алгоритма -   О(N*log N+T*log N) , где  T – количество террористов, N – количество домов.
      Теперь про одно небольшое ускорение:
Для каждого террориста запишем первого террориста раньше его ( в массиве терров) , про которого мы не знаем точно, что он защищен домом. Аналогично определим следующего такого после данного.
Когда мы узнали, что данный террорист защищен – говорим, что
след(предыд(текущий)) = след(текущий) и
предыд(след(текущий)) = (предыд(текущий))
Тогда при проходе по массиву террористов мы можем не рассматривать террористов, который укрытии домами, а переход к следующему террористу очень прост – текущий<-след(текущий) .
5). И последнее…не знаю почему, но алгоритм с применением полярного угла работает почти в 5 раз быстрее алгоритма с пересечением отрезков…   
Алгоритм с применением полярного угла

Код:

Const Pi=3.1415926535;
Type TGangster=record
      a,d:Real;
      end;
Type THouse=record
     s,f,d:Real;
     end;
Type TData=record
     l,n:integer;
     end;
Var a:array[1..500] of TGangster;
    b:array[1..500] of THouse;
    c:array[0..501] of TData;
    x,y,p2,q2,p,q,p1,q1:Longint;
    n,m,i,j,k:Integer;
begin
 Read(x,y,n);
 For i:=1 to n do
  begin
   Read(p,q);
   p:=p-x;q:=q-y;
   if p=0 then
    begin if q>0 then a[i].a:=Pi/2.0 else a[i].a:=3.0*Pi/2.0; end
   else
   if q=0 then
    begin if p>0 then a[i].a:=0 else a[i].a:=Pi; end
   else
    begin
     a[i].a:=arctan(abs(q)/abs(p));
     if (p<0) and (q>0) then a[i].a:=Pi-a[i].a else
     if (p<0) and (q<0) then a[i].a:=a[i].a+Pi else
     if (p>0) and (q<0) then a[i].a:=2*Pi-a[i].a;
    end;
   a[i].d:=Sqr(p)+Sqr(q);
  end;
 Read(m);
 For i:=1 to m do
  begin
   Read(p,q);
   p:=p-x;q:=q-y;
   if (p>=0) and (q>=0) then
   begin p2:=p;q2:=q+1;p1:=p+1;q1:=q;b[i].d:=Sqr(p)+Sqr(q); end else
   if (p<0) and (q>=0) then
   begin p2:=p;q2:=q;p1:=p+1;q1:=q+1;b[i].d:=Sqr(p+1)+Sqr(q); end else
   if (p<0) and (q<0) then
   begin p2:=p+1;q2:=q;q1:=q+1;p1:=p;b[i].d:=Sqr(p+1)+Sqr(q+1); end else
   if (p>=0) and (q<0) then
   begin p2:=p+1;q2:=q+1;q1:=q;p1:=p;b[i].d:=Sqr(p)+Sqr(q+1); end;
   if p1=0 then
    begin if q1>0 then b[i].s:=Pi/2.0 else b[i].s:=3.0*Pi/2.0; end
   else
   if q1=0 then
    begin if p1>0 then b[i].s:=0 else b[i].s:=Pi; end
   else
    begin
     b[i].s:=arctan(abs(q1)/abs(p1));
     if (p1<0) and (q1>0) then b[i].s:=Pi-b[i].s else
     if (p1<0) and (q1<0) then b[i].s:=b[i].s+Pi else
     if (p1>0) and (q1<0) then b[i].s:=2*Pi-b[i].s;
    end;
    if p2=0 then
    begin if q2>0 then b[i].f:=Pi/2.0 else b[i].f:=3.0*Pi/2.0; end
   else
   if q2=0 then
    begin if p2>0 then b[i].f:=0 else b[i].f:=Pi;
    if (q=-1) then b[i].f:=2*Pi; end
   else
    begin
     b[i].f:=arctan(abs(q2)/abs(p2));
     if (p2<0) and (q2>0) then b[i].f:=Pi-b[i].f else
     if (p2<0) and (q2<0) then b[i].f:=b[i].f+Pi else
     if (p2>0) and (q2<0) then b[i].f:=2*Pi-b[i].f;
    end;
  end;
 For i:=0 to n+1 do
  begin
   c[i].l:=i-1;
   c[i].n:=i+1;
  end;
 j:=1;k:=n;
 While (j<=m) and (k>0) do
  begin
   i:=c[0].n;
   While (i<=n) and (k>0) do
    begin
     if (a[i].a-b[j].s>=0) and (b[j].f-a[i].a>=0) and (a[i].d-b[j].d>1e-7) then
      begin Dec(k);c[c[i].n].l:=c[i].l;c[c[i].l].n:=c[i].n; end else
     if (a[i].a=0) then
     if (abs(b[j].f-2*Pi)<1e-7) then
     if (a[i].d-b[j].d>1e-7) then
      begin Dec(k);c[c[i].n].l:=c[i].l;c[c[i].l].n:=c[i].n; end;
     i:=c[i].n;
    end;
   Inc(j);
  end;
 Writeln(n-k);
end.

Алгоритм с применением пересечений отрезков

Код:

Var a:array[1..500,1..5] of Longint;
    b:array[1..500,1..8] of Longint;
    c:array[0..501,1..2] of Integer;
    n,m,i,j,k,x,y,l:Integer;
    rx,ry:Real;
    k1x,k2x,k3x,k1y,k2y,k3y:Longint;
    t:boolean;
Function Intersect:boolean;
begin
 t:=true;
 k1x:=b[j,1];k1y:=b[j,2];
 k2x:=b[j,3];k2y:=b[j,4];
 k3x:=a[i,1];k3y:=a[i,2];
 if not((rx<=k1x) and (rx>=k2x)) and
 not((rx>=k1x) and (rx<=k2x)) then t:=false;
 if not((ry<=k1y) and (ry>=k2y)) and
 not((ry>=k1y) and (ry<=k2y)) then t:=false;
 if not((rx<=k3x) and (rx>=x)) and
 not((rx>=k3x) and (rx<=x)) then t:=false;
 if not((ry<=k3y) and (ry>=y)) and
 not((ry>=k3y) and (ry<=y)) then t:=false;
 Intersect:=t;
end;
begin
 Read(x,y,n);
 For i:=1 to n do
  begin
   Read(a[i,1],a[i,2]);
   a[i,3]:=a[i,2]-y;
   a[i,4]:=x-a[i,1];
   a[i,5]:=a[i,1]*y-x*a[i,2];
  end;
 Read(m);
 For i:=1 to m do
  begin
   Read(k,l);
   if (k>=x) and (l>=y) then
    begin
     b[i,1]:=k+1;
     b[i,2]:=l;
     b[i,3]:=k;
     b[i,4]:=l+1;
     b[i,5]:=Sqr(x-k)+Sqr(y-l);
    end else
   if (k<x) and (l>=y) then
    begin
     b[i,1]:=k+1;
     b[i,2]:=l+1;
     b[i,3]:=k;
     b[i,4]:=l;
     b[i,5]:=Sqr(k+1-x)+Sqr(l-x);
    end
   else
   if (k<x) and (l<y) then
    begin
     b[i,1]:=k+1;
     b[i,2]:=l;
     b[i,3]:=k;
     b[i,4]:=l+1;
     b[i,5]:=Sqr(k+1-x)+Sqr(l+1-y);
    end
   else
   if (k>=x) and (l<y) then
    begin
     b[i,1]:=k+1;
     b[i,2]:=l+1;
     b[i,3]:=k;
     b[i,4]:=l;
     b[i,5]:=Sqr(k-x)+Sqr(l+1-y);
    end;
   b[i,6]:=b[i,4]-b[i,2];
   b[i,7]:=b[i,1]-b[i,3];
   b[i,8]:=b[i,3]*b[i,2]-b[i,1]*b[i,4];
  end;
 For i:=0 to n+1 do
  begin
   c[i,1]:=i-1;
   c[i,2]:=i+1;
  end;
 k:=n;
 j:=1;
 While (j<=m) and (k>0) do
  begin
   i:=c[0,2];
   While (i<=n) do
    begin
     If a[i,4]*b[j,6]<>a[i,3]*b[j,7] then begin
     ry:=(b[j,8]*a[i,3]-a[i,5]*b[j,6])/(a[i,4]*b[j,6]-a[i,3]*b[j,7] );
     rx:=(b[j,8]*a[i,4]-a[i,5]*b[j,7])/(a[i,3]*b[j,7]-a[i,4]*b[j,6]);
     if Intersect then begin
      Dec(k);c[c[i,1],2]:=c[i,2];
     c[c[i,2],1]:=c[i,1];
     end;end;i:=c[i,2];
    end;
   Inc(j);
  end;
 Writeln(n-k);
end.

NEWTOWER
     Есть еще один алгоритм решения этой задачи, который отличается от описанного выше..
Понятно , что когда мы сносим с начального стержня новый диск, мы его ставим на некоторый пустой стержень, значит все синие и желтые кольца, которые мы снесли до этого – на 2 других стержнях. Есть только 3 варианта из взаимного расположния:
     1). Синие на синем, Желтые на желтом, полосатый пустой
     2).Синие на синем, желтый пустой, Желтые на полосатом
     3).синий пустой, Желтые на желтом, Синие на полосатом
     Для каждого из 3 случаев мы снесли еще 1 диск и перед сносом следующего опять получился 1 из 3 случаев. Т.е.если для каждого из 3 вариантов с С+1 синим дисками и Ж желтыми дисками (при условии, ч то мы снесли синий диск) мы может получить каждый из 3 случаев с помощью 3 вариантов для С синих и Ж желтых дисков… Пример:
      Если у нас на синем стержне С+1 диск, а на желтом Ж, то мы могли получить такую конфигурацию из 3 случаев: (для краткости будем записывать просто количество дисков на каждом из стержней)
      1)    С_Ж_0 –> 0_Ж_С –> 1_Ж_С –> С+1_Ж_0
      2)    С_0_Ж –>С_Ж_0 –> 0_Ж_С –> 1_Ж_С –> С+1_Ж_0
      3)    0_Ж_С –> 1_Ж_С –> С+1_Ж_С
      т.е. для каждой из 3 конфигураций для С и Ж дисков мы может е определить ее через конфигурацию из меньшего количества дисков..Т.е. решение заключается в следующем :
      Для  каждой из 3 возможных конфигураций определить, за какое минимальное число шагов ее можно достигнуть. Делаем мы это зная конфигурации послу предыдущего шага.
По коду все достаточно прозрачно.. 

Код:

Const p:array[0..30] of qword=(
0,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);
Var i,n,c,x,y:byte;
    h1,h2,h3,v1,v2,v3:qword;
Function min(a,b,c:qword):qword;
begin
 if (a<=b) and (a<=c) then min:=a else
 if (b<=c) and (b<=a) then min:=b else min:=c;
end;
begin
 Read(n);v1:=0;v2:=0;v3:=0;x:=0;y:=0;
 For i:=1 to n do begin
 Read(c);h1:=v1;h2:=v2;h3:=v3;
 If c=0 then begin
  If x=0 then begin
    v1:=min(h1+1,h2+p[y]+1,h3+p[y]+1);
    v2:=min(h1+p[y]+1,h2+1,h3+1);
    v3:=min(h1+p[y]+1,h2+1,h3+1);
   end
  else
   begin
    v1:=min(h1+p[y]+p[x]+1+p[x]+p[y],h2+1+p[x]+p[y],h3+p[x]+1+p[x]+p[y]);
    v2:=min(h1+p[y]+1+p[x],h2+p[x]+1+p[x],h3+1+p[x]);
    v3:=min(h1+p[y]+p[x]+1+p[x],h2+1+p[x],h3+p[x]+1+p[x]);
   end;
  Inc(x);
 end
 else
  begin
   If (y=0) then
    begin
     v1:=min(h1+1,h2+p[x]+1,h3+1);
     v2:=min(h1+p[x]+1,h2+1,h3+p[x]+1);
     v3:=min(h1+1,h2+p[x]+1,h3+1);
    end
   else
    begin
     v1:=min(h1+p[y]+1+p[y],h2+p[x]+1+p[y],h3+1+p[y]);
     v2:=min(h1+1+p[y]+p[x],h2+p[x]+p[y]+1+p[y]+p[x],h3+p[y]+1+p[y]+p[x]);
     v3:=min(h1+1+p[y],h2+p[x]+p[y]+1+p[y],h3+p[y]+1+p[y]);
    end;
   Inc(y);
  end;
 end;
 Writeln(min(v1+p[y],v2+p[x],v3));
end.

Интересно все-таки, эту ли задачу предложил Даниил Нейтер? Думаю, или эту, или первую…
Ну что, дорогие читатели? Мы здорово помучали друг друга big_smile , ждите следующего выпуска, задавайте вопросы если что непонятно..

Відредаговано MAXXX (2007-11-29 00:11:18)


ICQ 426287475

Поза форумом

 

#3 2007-11-29 00:14:50

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Задачи, коды, тесты... Начинаем разбор!

Ну конечно формулы выводить это дело прикольное но вот чтобы долго не думать я использовал более менее стандартые и общие подходы а именно : МиниЛайн - ФлойдуУоршал, Кросгруп - бинпоиск


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#4 2007-11-29 00:15:54

spiker
Новий користувач
Зареєстрований: 2007-10-24
Повідомлень: 24

Re: Задачи, коды, тесты... Начинаем разбор!

Киньте пару тестів до кожної задачі

Поза форумом

 

#5 2007-11-29 00:20:02

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

necro написав:

Ну конечно формулы выводить это дело прикольное но вот чтобы долго не думать я использовал более менее стандартые и общие подходы а именно : МиниЛайн - ФлойдуУоршал, Кросгруп - бинпоиск

Ну, в Кросгрупі формула була простішою, тому я вивів, а про Мінілайн абсолютно згоден! smile


Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#6 2007-11-29 00:30:16

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

spiker написав:

Киньте пару тестів до кожної задачі

Прошу. Тести, на яких я тестував свої розв'язки. Не усі, звісно ж.

Street:

Код:

19      -> 3
100     -> 0
1497    -> 6
9999999 -> 5

Miniline:

Код:

9785 8245 9978 9785 0 6847 9785 0 3245 -> 3602
9785 8245 9978 0 0 8475 9785 8245 4911 -> 24600
9785 8245 9978 9785 2178 0 0 1822 0    -> 13785

CrossGroup:

Код:

3 27 6 97  -> 3.593
12 26 6 97 -> 8.887
21 6 8 96  -> 12.000

Відредаговано Phoenix_Ukraine (2007-11-29 00:45:39)


Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#7 2007-11-29 00:32:32

spiker
Новий користувач
Зареєстрований: 2007-10-24
Повідомлень: 24

Re: Задачи, коды, тесты... Начинаем разбор!

Думаю, що мій розв'язок до задачі NewTower самий лаконічний.

Код:

  
Код

 program tower;
{$APPTYPE CONSOLE}
var f:array[0..30] of longint; res,n,we,i,prev1,prev2,kil1,kil2,prev:longint; a:array[0..30] of byte;
b,c:array[0..30] of longint;
procedure parne(kilo:longint; var prevs:longint);
var i:longint;
begin
        for i:=1 to kilo do
        res:=res+1+f[prevs-1+i];
        prevs:=prevs+kilo;
end;
procedure neparne(kilo:longint; var prevs:longint);
var i:longint;
begin
        res:=res+f[prevs];
        for i:=1 to kilo do
        res:=res+1+f[prevs-1+i];
        prevs:=prevs+kilo;
end;
begin
f[0]:=0; f[1]:=1; f[2]:=3; f[3]:=7; f[4]:=15; f[5]:=31; f[6]:=63; f[7]:=127; f[8]:=255; f[9]:=511; f[10]:=1023;
        f[11]:=2047; f[12]:=4095; f[13]:=8191; f[14]:=16383; f[15]:=32767; f[16]:=65535; f[17]:=131071;
        f[18]:=262143; f[19]:=524287; f[20]:=1048575; f[21]:=2097151; f[22]:=4194303; f[23]:=8388607;
        f[24]:=16777215; f[25]:=33554431; f[26]:=67108863; f[27]:=134217727; f[28]:=268435455; f[29]:=536870911;
        f[30]:=1073741823;
        read(n);
        we:=0;
        prev1:=-1;
        prev2:=-1;
        for i:=1 to n do
        begin
                read(a[i]);
                if (i=1) and (a[i]=0) then we:=1;
                a[i]:=(a[i]+we) mod 2;

                if a[i]=1 then
                begin
                        if prev1<>(i-1) then
                        kil1:=kil1+1;
                        b[kil1]:=b[kil1]+1;
                        prev1:=i;
                end else
                begin
                        if prev2<>(i-1) then
                        kil2:=kil2+1;
                        c[kil2]:=c[kil2]+1;
                        prev2:=i;
                end;
        end;
        prev:=0;
        for i:=1 to kil1 do
        begin
                if (i=2) and (c[1]=1) then parne(b[i],prev) else
                if b[i] mod 2 = 1 then neparne(b[i],prev) else
                parne(b[i],prev);
        end;
        prev:=0;
        for i:=1 to kil2 do
        begin
                if c[i] mod 2 = 1 then neparne(c[i],prev) else
                parne(c[i],prev);
        end;
        write(res);
end.

Відредаговано spiker (2007-11-29 00:40:41)

Поза форумом

 

#8 2007-11-29 00:35:38

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

Сховай у теґи code, будь ласка! Заодно і усмішки зникнуть із тексту програми. big_smile

Відредаговано Phoenix_Ukraine (2007-11-29 00:38:43)


Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#9 2007-11-29 00:38:40

spiker
Новий користувач
Зареєстрований: 2007-10-24
Повідомлень: 24

Re: Задачи, коды, тесты... Начинаем разбор!

Як це зробити

Поза форумом

 

#10 2007-11-29 00:39:50

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

Перед початком коду напиши [ code ] (без пропусків!), а після закінчення - [ /code ] (також без пропусків!).


Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#11 2007-11-29 00:40:07

spiker
Новий користувач
Зареєстрований: 2007-10-24
Повідомлень: 24

Re: Задачи, коды, тесты... Начинаем разбор!

To Phoenix_Ukraine:
До задачі СrossGroup
тест №2: 12 26 6 97 відповідь 8.474
тест №3: 21 6 8 96 - 12.000
thanks

Поза форумом

 

#12 2007-11-29 00:43:25

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

Ось моє. Правда, писав після роз'яснення...

Код:

program NewTower;
  const zzz=2;
        mnax=30;
        twos:array[0..mnax] of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,
                                        262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,
                                        134217728,268435456,536870912,1073741824);
  var n,i,j,cur,y_num,b_num,a,b:longint;
      yb,ys,sb:array[0..mnax] of longint;
begin
  if (zzz=1) then begin
    assign(input,'v.in');reset(input);
    assign(output,'v.out');rewrite(output);
  end;
  fillchar(yb,sizeof(yb),0);
  fillchar(ys,sizeof(ys),0);
  fillchar(sb,sizeof(sb),0);
  y_num:=0;
  b_num:=0;
  
  read(n);
  for i:=1 to n do begin
    read(cur);
    if (cur=0) then begin
      inc(y_num);
      
      { yellow-blue }
      a:=yb[i-1]+twos[y_num]-1;
      if (sb[i-1]<>-1) then
        b:=sb[i-1]+twos[y_num-1]
      else
        b:=maxlongint;
      
      if (a<b) then
        yb[i]:=a
      else
        yb[i]:=b;
      
      { stripe-blue }
      a:=yb[i-1]+twos[y_num-1];
      if (sb[i-1]<>-1) then
        b:=sb[i-1]+twos[y_num]-1
      else
        b:=maxlongint;
      
      if (a<b) then
        sb[i]:=a
      else
        sb[i]:=b;
      
      { yellow-stripe }
      if (y_num<>1) then
        ys[i]:=-1
      else
        ys[i]:=ys[i-1]+1;      
    end
    else begin
      inc(b_num);
      
      { yellow-blue }
      a:=yb[i-1]+twos[b_num]-1;
      if (ys[i-1]<>-1) then
        b:=ys[i-1]+twos[b_num-1]
      else
        b:=maxlongint;
      
      if (a<b) then
        yb[i]:=a
      else
        yb[i]:=b;
        
      { yellow-stripe }
      a:=yb[i-1]+twos[b_num-1];
      if (ys[i-1]<>-1) then
        b:=ys[i-1]+twos[b_num]-1
      else
        b:=maxlongint;
      
      if (a<b) then
        ys[i]:=a
      else
        ys[i]:=b;
      
      { stripe-blue }
      if (b_num=1) then
        sb[i]:=sb[i-1]+1
      else
        sb[i]:=-1;
    end;
  end;
  writeln(yb[n]);
end.

Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#13 2007-11-29 00:44:46

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

spiker написав:

To Phoenix_Ukraine:
До задачі СrossGroup
тест №2: 12 26 6 97 відповідь 8.474
тест №3: 21 6 8 96 - 12.000
thanks

Із 12-кою згоден, хибнодрук, вже спатки, мабуть, час. А в другому так виходило...


Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#14 2007-11-29 01:01:52

rat
Новий користувач
Зареєстрований: 2007-11-22
Повідомлень: 3

Re: Задачи, коды, тесты... Начинаем разбор!

Еще один лаконичный вариант NewTower-a (набрал всего лишь 34 очка)

Код:

program newtower;

function Power2(Exp: Byte): LongWord;
begin
  Power2 := 2 shl Exp;
end;

var
  LastIndex: array [0..1] of SmallInt;
  CurIndex: array [0..1] of Byte;
  i, N: Byte;
  CurColor, LastColor: SmallInt;
  fEnd: Boolean;
  Res: Longword; // Максимальный ответ: 1073741823. Максимальный Лонгворд: 4294967295
begin

  LastColor := -1;
  LastIndex[0] := 0;
  LastIndex[1] := 0;
  CurIndex[0] := 0;
  CurIndex[1] := 0;
  Res := 0;
  fEnd := False;

  read(N);
  for i := 1 to N + 1 do begin
    fEnd := i = N + 1;
    if fEnd then
      CurColor := -1
    else
      read(CurColor);
    if (LastColor <> CurColor) then begin
      if LastColor <> -1 then begin
        Inc(Res, Power2(CurIndex[LastColor]-1) - 1);
        if LastIndex[LastColor]-1 >= 0 then
          if CurIndex[LastColor] mod 2 = LastIndex[LastColor] mod 2 then
            Dec(Res, Power2(LastIndex[LastColor]-1) - 1);
        if (LastIndex[LastColor] = 1)
        and (LastIndex[1 - LastColor] = 1) then
          // Три первых диска чередуются
          Dec(Res);
        LastIndex[LastColor] := CurIndex[LastColor];
      end;
      LastColor := CurColor;
    end;
    Inc(CurIndex[CurColor]);
  end;
  writeln(Res);

end.

Идея в следующем:
1. Число перекладываний для одного цвета определяется по известной формуле: 2^N-1

2. Для последовательности 1110000 необходимо просто сложить числа перекладываний для группы 111 и группы 0000, т.е. R=2^3-1 + 2^4-1. Отсюда делаем вывод, что при изменении цвета, а также при окончании выборки необходимо просуммировать число перекладываний для предстоящей группы дисков с общим результатом.

3. Далее анализируем различные варианты с несколькими чередованиями, и приходим к выводу, что вариантов всего два:
3.1) случаи 3.1а и 3.1б, либо оба четные, либо оба нечетные
3.1а) группа заканчивается на четный номер своего цвета, и предыдущая группа этого же цвета закончилась на четный номер, пример (с конца): С4 С3 Ж2 Ж1 С2 С1, в данном случае С4 - 4 четная, С2 - 2 четная
3.1б) группа заканчивается на нечетный номер своего цвета, и предыдущая группа этого же цвета закончилась на нечетный номер, пример (с конца): С5 С4 Ж2 Ж1 С3 С2 С1, в данном случае С5 - 5 нечетная, С3 - 3 нечетная,
3.2) четность несоблюдается, т.е. одно число четное, другое число нечетное
Так вот, для варианта 3.2 формула не меняется, а для варианта 3.1 формула принимает вид: R=R + 2^L-1 - 2^P-1
Где
L - последний номер текущего цвета текущей группы,
P - последний номер текущего цвета предыдущей группы
Почему уменьшается число перекладываний для варианта 3.1? Потому что часть работы уже сделана хорошо, и переделывать её не нужно, т.е. диски уже частично лежат на нужном стержне.
Почему не уменьшается число для варианта 3.2? Потому, что все разложенные диски текущего цвета нужно переложить на полосатый, чтобы закончить перекладывание. А чтобы переложить диски на полосатый мы опять потратим 2^P-1

4. При чередовании первых трех дисков общее число перекладываний уменьшается на 1, исходя из наблюдений.

Все.

Відредаговано rat (2007-11-29 22:12:02)

Поза форумом

 

#15 2007-11-29 15:23:15

Silicious Man
Новий користувач
Звідки: Донецк
Зареєстрований: 2007-11-11
Повідомлень: 79

Re: Задачи, коды, тесты... Начинаем разбор!

Комментарий по задаче street.
На самом деле есть возможность определить длину n-ного числа Фибоначчи, если прологорифмировать по осн. 10 обе части формулы для нахождения n-ного числа Фибоначчи (отбросив от неё маленький довесок).
Можно используя этот метод определить номер числа Фибоначчи, в котором находится интересующая нас цифра и номер этой цифры.
Итак, вот ф-ция, возвращающая длину числа Фибоначчи:

int fibn ( int n )
{
    n++;
    if ( n == 1 )
        return 1;

    double n2 = (double)n;
    double temp = (n2 * logp - log5);
    int ans = (int)temp + 1;
    return ans;
}
, где
    phi = (sqrt ((double)5) + 1) / 2; // золотое сечение
    logp = log10 (phi);
    log5 = (log10 ((double)5)) / 2;


А вычислял само число я вышеописанным методом с матрицами + быстрое умножение длинных чисел с помощью быстрого преобразования Фурье

Відредаговано Silicious Man (2007-11-29 15:26:28)


—————————————————————————————————
Life is a beautiful place where dreams and reality live in peace.

Поза форумом

 

#16 2007-11-29 15:30:15

Skiminok
Новий користувач
Звідки: Киев, Украина
Зареєстрований: 2006-01-19
Повідомлень: 144
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

Silicious Man написав:

Комментарий по задаче street.
На самом деле есть возможность определить длину n-ного числа Фибоначчи, если прологорифмировать по осн. 10 обе части формулы для нахождения n-ного числа Фибоначчи (отбросив от неё маленький довесок).
Можно используя этот метод определить номер числа Фибоначчи, в котором находится интересующая нас цифра и номер этой цифры.
...
А вычислял само число я вышеописанным методом с матрицами + быстрое умножение длинных чисел с помощью быстрого преобразования Фурье

Как выяснилось, при данных условиях это не критично: линейный алгоритм подсчёта по основной формуле проходит все тесты, и никакого тайм-лимита.


Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом системному программисту. Он исправит ошибки в трансляторе.
http://wwp.icq.com/scripts/online.dll?icq=282667777&amp;img=5ICQ 282667777

Поза форумом

 

#17 2007-11-29 17:27:04

Gnelik
Новий користувач
Зареєстрований: 2005-11-06
Повідомлень: 3

Re: Задачи, коды, тесты... Начинаем разбор!

Короткое решение Street на питоне.

Код:

def f1(n):  
  a,b = long(0),long(1)
  d=long(10)
  w=0
  l=1
  s=0
  while s<n:
        a,b=b,a+b
        k = (a+b)/d
        w+=1
        if k!=0:
          d*=10
          l+=1
        s+=l
        #print a+b
  print str(a+b)[-(s-n+1)]
a = int(raw_input())
f1(a)

Відредаговано Gnelik (2007-11-30 07:04:28)

Поза форумом

 

#18 2007-11-29 17:31:40

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

Gnelik, краса! smile

ПиСи. Сам хочу вивчити Пітон...


Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#19 2007-11-29 18:12:55

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: Задачи, коды, тесты... Начинаем разбор!

Решение представленное выше на Питоне не проходит ни 1 теста.

Вот мое решение NewTower.

Код:

var b,a,i,j,n:integer;
tek:integer;
k:longint;
s:array[0..3] of integer;
mas:array[0..30] of integer;
Begin
 for i:=0 to 30 do mas[i]:=2;
 for i:=0 to 3 do s[i]:=0;
 k:=0; tek:=0; a:=0; b:=0; i:=0; j:=0; n:=0;
 read(n); a:=0; i:=1;
 for i:=1 to n do read(mas[i]);
 tek:=mas[1]; i:=1; if mas[2]=mas[1] then if tek=1 then tek:=0 else tek:=1;
 while i<=n do begin
 b:=j;
 a:=0; j:=i; while (j<=n) and (mas[j]<>tek) do begin inc(j); inc(a); end;
 dec(j);  if j=b then if tek=1 then tek:=0 else tek:=1;
 if a mod 2=0 then k:=k+trunc(exp((s[mas[j]]+a)*ln(2)))-trunc(exp(s[mas[j]]*ln(2))) else
 k:=k+trunc(exp((s[mas[j]]+a)*ln(2)))-1;
 inc(s[mas[j]],a);
 i:=j+1; if j<>b then tek:=mas[j];
 end;
 i:=2; j:=mas[1]; while mas[i]=j do inc(i);
 dec(i); if (i<=n-2) and (n>=3) and (mas[i+1]<>mas[i+2])  then begin
 j:=i+2; tek:=1; while mas[j]=mas[i] do begin inc(tek); inc(j); end;
 if not odd(tek) then dec(k,trunc(exp(i*ln(2))-1));
 end;
 writeln(k);
end.

Ну вот еще ликвидейшн:

Код:

var x2,y2,x3,y3,x1,y1,x,y,d,i,j,n,m,k:integer;
xp1,yp1,xp2,yp2,a,b,a1,a2,c,b1,b2,c1,c2:real;
mas:array[1..2,1..500] of integer;
Begin
 read(x,y); read(n); for i:=1 to n do read(mas[1,i],mas[2,i]); k:=n;
 read(m); for i:=1 to m do begin
 read(x1,y1);
 x2:=x1+1; y2:=y1+1;
 a1:=y2-y1; b1:=x1-x2;
 c1:=x1*(y1-y2)+y1*(x2-x1);
 y1:=y1+1; y2:=y2-1;
 a2:=y2-y1; b2:=x1-x2;
 c2:=x1*(y1-y2)+y1*(x2-x1);
 for j:=1 to n do begin
 if mas[1,j]<>-20 then begin
 a:=-mas[2,j]+y; b:=-x+mas[1,j];
 c:=mas[1,j]*(-y+mas[2,j])+mas[2,j]*(x-mas[1,j]);
 if ((-a*b1+a1*b)<>0) then begin
 yp1:=(a*c1-a1*c)/(-a*b1+a1*b);
 xp1:=(-c1-b1*yp1)/a1;
 end else begin xp1:=-1; yp1:=-1; end;
 if ((-a*b2+a2*b)<>0) then begin
 yp2:=(a*c2-a2*c)/(-a*b2+a2*b);
 xp2:=(-c2-b2*yp2)/a2;
 end else begin xp2:=-1; yp2:=-1; end;
 if (((xp1>=x1) and (xp1<=x2) and (yp1<=y1) and (yp1>=y2)) or ((xp2>=x1) and (xp2<=x2) and (yp2<=y1) and (yp2>=y2)))
{ or (((a1=a) and (b1=b) and (c1=c)) or ((a2=a)and(b2=b)and(c2=c)))}
 then begin
 if (((x1>=x) or (x2>=x)) and ((x1<=mas[1,j]) or (x2<=mas[1,j]))) or (((x1<=x) or (x2<=x)) and ((x1>=mas[1,j]) or
 (x2>=mas[1,j]))) then if (((y1>=y) or (y2>=y)) and ((y1<=mas[2,j]) or (y2<=mas[2,j]))) or
 (((y1<=y) or (y2<=y)) and ((y1>=mas[2,j]) or (y2>=mas[2,j])))
 then begin
 dec(k);
 mas[1,j]:=-20; mas[2,j]:=-20;
 end;
 end;
 end;
 end;
 end;
 writeln(n-k);
end.

Відредаговано kadr (2007-11-29 18:22:36)

Поза форумом

 

#20 2007-11-30 01:21:29

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Задачи, коды, тесты... Начинаем разбор!

2 kadr : Может это все конечно и правильно но это же уродство а не проги. Както не в тему просто бросил решения свои ничем не примечательные которые уже постились разборщиками


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#21 2007-11-30 01:26:33

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Задачи, коды, тесты... Начинаем разбор!

Here is mine Liquidante : Belissima ))

Код:

{$APPTYPE CONSOLE}
{$O-}
const
   max = 1600;
type
   point = record
              x, y : longint;
           end;
   lines = array [1..max, 1..2] of point;
var
   a, b : lines;
   t : array [1..max] of point;
   p, s : point;
   res, btop, atop, i, n, m : longint;
procedure putline(var a : lines; var top : longint; p1x, p1y, p2x, p2y : longint);
begin
   inc(top);
   a[top, 1].x := p1x; a[top, 1].y := p1y;
   a[top, 2].x := p2x; a[top, 2].y := p2y;
end;
function mult(var a, b, c : point) : longint;
var
   p1, p2 : point;
begin
   p1.x := a.x - c.x; p1.y := a.y - c.y;
   p2.x := b.x - c.x; p2.y := b.y - c.y;
   mult := p1.x * p2.y - p1.y * p2.x;
end;
function intersect(var a, b, c, d : point) : boolean;
begin
   intersect := (mult(a, c, d) * mult(b, c, d) <= 0) and
                (mult(c, b, a) * mult(d, b, a) <= 0);
end;
function killed(var a : lines; var top : longint; p1, p2 : point) : boolean;
var
   i : integer;
begin
   i := 1;
   while (i <= top) and not(intersect(p1, p2, a[i, 1], a[i, 2])) do inc(i);
   killed := i > top;
end;
begin
   read(s.x, s.y);
   read(n);
   for i := 1 to n do read(t[i].x, t[i].y);

   atop := 0; btop := 0;
   read(m);
   for i := 1 to m do begin
      read(p.x, p.y);

      putline(a, atop, p.x, p.y, p.x + 1, p.y);
      putline(a, atop, p.x, p.y, p.x, p.y + 1);
      putline(a, atop, p.x + 1, p.y, p.x + 1, p.y + 1);
      putline(a, atop, p.x, p.y + 1, p.x + 1, p.y + 1);

      putline(b, btop, p.x, p.y, p.x + 1, p.y + 1);
      putline(b, btop, p.x + 1, p.y, p.x, p.y + 1);
   end;

   res := n;
   for i := 1 to n do dec(res, ord(killed(a, atop, s, t[i]) or
                                   killed(b, btop, s, t[i])));

   writeln(res);
end.

PS : читай подпись ))

Відредаговано necro (2007-11-30 01:29:29)


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#22 2007-11-30 01:33:03

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Задачи, коды, тесты... Начинаем разбор!

Еще в принципе не постились решения более стандартные : минилайн через ФлойдаУоршала

Код:

{$APPTYPE CONSOLE}
{$R-,O-}
const
   max = 16;
   oo = 2000000000;
type
   point = record
              x, y, z : longint;
           end;
var
   a : array [1..max] of point;
   d : array [1..max, 1..max] of longint;
   p : point;
   top, i, j, k : longint;
procedure put(x, y, z : longint);
begin
   inc(top);
   a[top].x := x; a[top].y := y; a[top].z := z;
end;
function eq(a, b : longint; ch : char) : boolean;
begin
   case ch of
      'x' : eq := (a = b) and ((a = 0) or (a = p.x));
      'y' : eq := (a = b) and ((a = 0) or (a = p.y));
      'z' : eq := (a = b) and ((a = 0) or (a = p.z));
   end;
end;
begin
   top := 2;
   readln(p.x, p.y, p.z,
          a[1].x, a[1].y, a[1].z,
          a[2].x, a[2].y, a[2].z);

   put(0, 0, 0); put(p.x, p.y, p.z);
   put(p.x, 0, 0); put(p.x, p.y, 0);
   put(0, p.y, 0); put(0, p.y, p.z);
   put(0, 0, p.z); put(p.x, 0, p.z);

   for i := 1 to top do
      for j := 1 to top do d[i, j] := oo;

   for i := 1 to top do d[i, i] := 0;

   for i := 1 to top do
      for j := i + 1 to top do
         if (eq(a[i].x, a[j].x, 'x') and eq(a[i].y, a[j].y, 'y')) or
            (eq(a[i].y, a[j].y, 'y') and eq(a[i].z, a[j].z, 'z')) or
            (eq(a[i].x, a[j].x, 'x') and eq(a[i].z, a[j].z, 'z')) then begin
            d[i, j] := abs(a[i].x - a[j].x) +
                       abs(a[i].y - a[j].y) +
                       abs(a[i].z - a[j].z);
            d[j, i] := d[i, j];
         end;

   for k := 1 to top do
      for i := 1 to top do
         for j := 1 to top do
            if (d[i, k] <> oo) and (d[k, j] <> oo) then
               if d[i, j] > d[i, k] + d[k, j] then
                  d[i, j] := d[i, k] + d[k, j];

   writeln(d[1, 2]);
end.

и Кросгруп через бинпоиск :

Код:

{$APPTYPE CONSOLE}
{$O-}
const
   eps = 1e-5;
var
   l, r, t : real;
   n, v, u, z : longint;
function can(n : longint; v, u, z, t : real) : boolean;
var
   l, t1, t2 : real;
begin
   l := (t - z / u) / (1 / v - 1 / u);
   if (l > z) or (l < 0) then can := false
   else begin
      if n <= 4 then begin can := ((z / v) <= t); exit; end;
      t1 := l / v;
      t2 := (l - u * l / v) / (u + v);
      can := can(n - 4, v, u, z - u * (t1 + t2), t - (t1 + t2));
   end;
end;
begin
   readln(n, v, u, z);

   if (u >= v) then begin writeln(z / u :0:3); halt; end;

   l := 0;
   r := z / u;
   t := (l + r) / 2;

   while abs(r - l) > eps do begin
      t := (l + r) / 2;
      if can(n, v, u, z, t) then r := t
                            else l := t;
   end;

   writeln(t:0:3);
end.

Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#23 2007-11-30 07:05:20

Gnelik
Новий користувач
Зареєстрований: 2005-11-06
Повідомлень: 3

Re: Задачи, коды, тесты... Начинаем разбор!

kadr написав:

Решение представленное выше на Питоне не проходит ни 1 теста.

Уже проходит, не ту версию выложил...

Поза форумом

 

#24 2007-11-30 09:01:44

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Задачи, коды, тесты... Начинаем разбор!

necro написав:

Here is mine Liquidante : Belissima ))
...
PS : читай подпись ))

Абсолютно підтримую обидві тези! smile

У мене Флойд-Уоршалл трохи більше коду зайняв, але все гут.


Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#25 2007-11-30 16:40:00

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Re: Задачи, коды, тесты... Начинаем разбор!

newtower

Код:

{$APPTYPE CONSOLE}
{$B-,R-,O+}
const
 maxn=30;
var
 tw:array[0..maxn] of longint;
 n,i,j:smallint;
 a:array[1..maxn] of byte;
 ans:longint;
 col:array[0..1] of smallint;
begin
 read(n);
 for i:=1 to n do
  read(a[i]);
 tw[0]:=1;
 for i:=1 to n do
  tw[i]:=2*tw[i-1];
 ans:=0;
 col[0]:=0;
 col[1]:=0;
 if a[1]=1 then
  for i:=1 to n do
   a[i]:=1-a[i];
 i:=1;
 while (i<=n)and(a[i]=0)do inc(i);
 inc(i);
 if (i<=n)and(a[i]=0) then
  inc(col[1]) else
  dec(i);
 while (i<=n)and(a[i]=0)do inc(i);
 col[0]:=i-1-col[1];
 inc(ans,tw[col[0]]-1+tw[col[1]]-1);
 while i<=n do
  begin
   j:=0;
   while (i+j<=n)and(a[i+j]=a[i])do inc(j);
   if odd(j)then
    inc(ans,tw[col[a[i]]]-1);
   inc(ans,tw[j+col[a[i]]]-tw[col[a[i]]]);
   inc(col[a[i]],j);
   inc(i,j);
  end;
 writeln(ans);
end.

В miniline писал Дейкстру. Способ заполнения координат:

Код:

for i:=0 to 1 do
 for j:=0 to 1 do
  for k:=0 to 1 do
   begin
    inc(n);
    a[n].x:=x*i;
    a[n].y:=y*j;
    a[n].z:=z*k;
   end;

Відредаговано partisan (2007-12-01 15:39:18)

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt