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


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

Ви не зайшли.

#1 2005-11-19 18:46:13

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Решения задач на Паскале

Большинство решений было написано на С. Для любителей публикую свои на Паскале. Вроде все правильно smile

Поза форумом

 

#2 2005-11-19 18:48:45

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

Re: Решения задач на Паскале

Джулгаков Дмитрий написав:

Большинство решений было написано на С. Для любителей публикую свои на Паскале. Вроде все правильно smile

А какая разница на чем ты пишеш лучше бы идеи расказал свои это более полезно


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

Поза форумом

 

#3 2005-11-19 18:49:42

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: Решения задач на Паскале

Bear: O(n):

Код:

var
  M, K, i : longint;
begin
  Read(M, K);
  if K mod 2 = 0 then
    for i := 0 to K div 2 do
      Write(i*2*m, ' ')
  else
    for i := 0 to K div 2 do
      Write((i*2+1)*m, ' ');
end.

Решение очевидно smile

Відредаговано Джулгаков Дмитрий (2005-11-19 20:44:00)

Поза форумом

 

#4 2005-11-19 18:51:09

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: Решения задач на Паскале

Piece: o(1)

Идея:
1. Находим уравнение прямой.
2. Находим уравнение перпендикуляра к прямой.
3. Считаем пересекается ли окружность и прямая.
4. Решая квадратное уравнение находим длину отрезочка внутри окружности

Код:

var
  R, RX, RY, X1, X2, Y1, Y2, t : Longint;
  k, b, d : Extended;
begin
  Read(R, RX, RY, X1, Y1, X2, Y2);
  X1 := X1-RX;
  Y1 := Y1-RY;
  X2 := X2-RX;
  Y2 := Y2-RY;
  if Abs(Y1-Y2) > Abs(X1-X2) then
  begin
    t := X1;
    X1 := Y1;
    Y1 := t;
    t := X2;
    X2 := Y2;
    Y2 := t;
  end;
  k := (y1-y2)/(x1-x2);
  b := y1-k*x1;
  d := Sqr(k*b)-(sqr(b)-sqr(r))*(sqr(k)+1);
  if d < 0 then
    Write(-1)
  else if Abs(D) < 1e-15 then
    Write(0)
  else
    Write(2*sqrt( d/(sqr(Extended(k))+1) ));
end.

Blamblam: o(n)

Идея:
Проводим окружность с центром в центре стола и радиусом с диагональю карты и считаем точки пересечения + случай с горизонтальным расположнеием

Код:

var
  N, i : Integer;
  a, b, x, y, r : longint;
  t, co : extended;
  b1, b2 : Boolean;
begin
  Read(N);
  for i := 1 to N do
  begin
    Read(x,y,a,b);
    if (x <= a) and (y <= b) or (x <= b) and (y <= a) then
      Write('1')
    else
    begin
      r := x*x+y*y;

      if r >= a*a then
      begin
        t := sqrt(r-a*a);
        t := b-t;
        if t < 0 then
          b1 := False
        else
        begin
          co := sqrt(r)/a;
          t := t*co;
          b1 := (t >= x) or (t >= y);
        end;
      end
      else
        b1 := True;

      if r >= b*b then
      begin
        t := sqrt(r-b*b);
        t := a-t;
        if t < 0 then
          b2 := False
        else
        begin
          co := sqrt(r)/b;
          t := t*co;
          b2 := (t >= x) or (t >= y);
        end;
      end
      else
        b2 := True;

      if b1 or b2 then
        Write('1')
      else
        Write('0');
    end;
  end;
end.

Newpatience: o(n)

Идея:
Описаный в других постах алгоритм за линейное время с прямой индексацией

Код:

const
  maxN = 65535;
var
  N, KK, KSum, i, j, P, Prev, nnew : longint;
  Side : Byte;
  K : array [1..2] of Integer;
  A : array [1..2, 1..maxN] of Word;
  D : array [1..2, 1..maxN] of Byte;
  First : array [1..10000] of Word;
  t : longint;
begin
  Read(N);
  FillChar(D, SizeOf(D), 0);
  for i := 1 to N do
    Read(First[i]);
  for i := 1 to N do
  begin
    Read(t);
    Inc(D[2, t]);
    Inc(D[1, First[i]]);
    if D[1, First[i]] = 2 then
      A[2, First[i]] := t
    else
      A[1, First[i]] := t;
    if D[2, t] = 2 then
      A[1, t] := First[i]
    else
      A[2, t] := First[i];
  end;

  KSum := 0;
  for i := 1 to N do
  begin
    if D[1, First[i]] <> 2 then
      Continue;
    K[1] := 0;
    K[2] := 0;
    KK := 1;
    P := A[1, first[i]];
    D[1, First[i]] := 3;
    K[1] := 1;
    Side := 2;
    Prev := 0;

    while D[1, P] < 3 do
    begin
      if D[Side, P] = 2 then
      begin
        D[Side, P] := 3;
        if Prev=A[1, P] then
          nnew := A[2, P]
        else
          nnew := A[1, P];
        Prev := P;
        P := nnew;
        Side := 3-Side;
        KK := 3-KK;
        Inc(K[KK]);
      end
      else
      begin
        Prev := P;
        P := A[3-Side, P];
        Inc(K[KK]);
      end;
    end;

    if K[1] > K[2] then
      KSum := KSum+K[2]
    else
      KSum := KSum+K[1];
  end;
  Write(KSum);
end.

Circuit: o(n)

Идея:
1. Главное - доказательство, что разрезов 1 или 2.
2. А само решение элементарно smile

Код:

var
  K, k2, k4, v, t, i, ans : Longint;
  A : array [1..20000] of Boolean;
begin
  Read(k);
  k2 := k div 2;
  k4 := k div 4;
  v := -k4;
  for i := 1 to k2 do
  begin
    Read(t);
    A[i] := t = 1;
    if t = 1 then
      Inc(v);
  end;
  if v = 0 then
    ans := 0
  else
    for i := 1 to k2 do
    begin
      Read(t);
      if (t=1) <> A[i] then
        if t = 1 then
          Inc(v)
        else
          Dec(v);
      if v = 0 then
      begin
        ans := i;
        Break;
      end;
    end;
  if (ans = 0) or (ans = k2) then
    Write('1 ', k2, ' ', k2+1)
  else
    Write('2 ', ans, ' ', ans+1, ' ', ans+k2, ' ', ans+k2+1);
end.

Відредаговано Джулгаков Дмитрий (2005-11-19 20:48:29)

Поза форумом

 

#5 2005-11-19 18:56:33

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

Re: Решения задач на Паскале

Кстати под чем это компилить твое если так да и еще на авто тестилке по памяти какие ограничения (по незнанию спрашиваю)?


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

Поза форумом

 

#6 2005-11-19 19:12:34

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: Решения задач на Паскале

necro написав:

Кстати под чем это компилить твое если так да и еще на авто тестилке по памяти какие ограничения (по незнанию спрашиваю)?

Компилить все можно и под BP. Только NewPatience нужно под FP. А по поводу памяти, по-моему, всегда было так: сколько система позволяет - все твое. Т.е под BP - 640К. А под FP - много...

Поза форумом

 

#7 2005-11-19 19:31:13

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

Re: Решения задач на Паскале

Джулгаков Дмитрий написав:

necro написав:

Кстати под чем это компилить твое если так да и еще на авто тестилке по памяти какие ограничения (по незнанию спрашиваю)?

Компилить все можно и под BP. Только NewPatience нужно под FP. А по поводу памяти, по-моему, всегда было так: сколько система позволяет - все твое. Т.е под BP - 640К. А под FP - много...

То есть никогда не было ограничений. Блин и тестилка компилит под фрипаскаль?


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

Поза форумом

 

#8 2005-11-19 20:21:21

Батыев Андрей
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 70

Re: Решения задач на Паскале

Люди!!!!! Блин, неужели есть гении которые способны понять алгоритм по 1-5 кб коду?
И ваще лучше выкладывать и спорить над АЛГОРИТМАМИ чем над ИСХОДНИКАМИ!
Тогда не будет проблем с языком, компилятором и проч.!

Поза форумом

 

#9 2005-11-19 20:25:55

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Решения задач на Паскале

А вы знаете,что на главной странице уже появилась ссылка на результаты первого тура?
Правда она нерабочая... :-(


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#10 2005-11-19 20:36:42

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: Решения задач на Паскале

necro написав:

Джулгаков Дмитрий написав:

necro написав:

Кстати под чем это компилить твое если так да и еще на авто тестилке по памяти какие ограничения (по незнанию спрашиваю)?

Компилить все можно и под BP. Только NewPatience нужно под FP. А по поводу памяти, по-моему, всегда было так: сколько система позволяет - все твое. Т.е под BP - 640К. А под FP - много...

То есть никогда не было ограничений. Блин и тестилка компилит под фрипаскаль?

Да. В правилах написано, что все проги на Паскале компилятся на FP

Поза форумом

 

#11 2005-11-19 20:41:17

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: Решения задач на Паскале

jack_spektor написав:

А вы знаете,что на главной странице уже появилась ссылка на результаты первого тура?
Правда она нерабочая... :-(

Н-да, прикольно. У всех ?? балов smile

Поза форумом

 

#12 2005-11-19 20:57:17

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Решения задач на Паскале

Джулгаков Дмитрий написав:

jack_spektor написав:

А вы знаете,что на главной странице уже появилась ссылка на результаты первого тура?
Правда она нерабочая... :-(

Н-да, прикольно. У всех ?? балов smile

Был какой то глюк, и мне показало,что у меня 30 баллов.
Потом всё исчезло...


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#13 2005-11-23 10:29:17

ROBOT
Олімпієць
Звідки: Ялта
Зареєстрований: 2005-10-26
Повідомлень: 158

Re: Решения задач на Паскале

Джулгаков Дмитрий написав:

Bear: O(n):

Код:

var
  M, K, i : longint;
begin
  Read(M, K);
  if K mod 2 = 0 then
    for i := 0 to K div 2 do
      Write(i*2*m, ' ')
  else
    for i := 0 to K div 2 do
      Write((i*2+1)*m, ' ');
end.

Решение очевидно smile

я немного сжал:

Код:

Var i,j,k:longint;
begin
  read(j,k);
  for i:=0 to (k div 2) do
    write(j*(2*i+(k mod 2)),' ');
end.

ничего, что в конце вывода лишний пробел?

Відредаговано ROBOT (2005-11-23 10:31:47)


I have Delphi 7, BP 7.0, FP 1.0.4, Windows XP
Мои решения олимпиад на  Паскале: http://h0h0l.narod.ru/
Моя проверялка: http://www.proveryalka.narod.ru/
ICQ: 266367671

Поза форумом

 

#14 2005-11-23 10:45:06

ROBOT
Олімпієць
Звідки: Ялта
Зареєстрований: 2005-10-26
Повідомлень: 158

Re: Решения задач на Паскале

Джулгаков Дмитрий написав:

Piece: o(1)


Circuit: o(n)

Идея:
1. Главное - доказательство, что разрезов 1 или 2.
2. А само решение элементарно smile

Код:

var
  K, k2, k4, v, t, i, ans : Longint;
  A : array [1..20000] of Boolean;
begin
  Read(k);
  k2 := k div 2;
  k4 := k div 4;
  v := -k4;
  for i := 1 to k2 do
  begin
    Read(t);
    A[i] := t = 1;
    if t = 1 then
      Inc(v);
  end;
  if v = 0 then
    ans := 0
  else
    for i := 1 to k2 do
    begin
      Read(t);
      if (t=1) <> A[i] then
        if t = 1 then
          Inc(v)
        else
          Dec(v);
      if v = 0 then
      begin
        ans := i;
        Break;
      end;
    end;
  if (ans = 0) or (ans = k2) then
    Write('1 ', k2, ' ', k2+1)
  else
    Write('2 ', ans, ' ', ans+1, ' ', ans+k2, ' ', ans+k2+1);
end.

здесь у меня тоже покороче:

Код:

var
  curs,i,k,st:integer;
  b:array[0..40004] of byte;
begin
  read(k);
  for i:=1 to k do read(b[i]);
  st:=1;
  curs:=0;
  for i:=1 to k div 2 do inc(curs,b[i]);
  while curs<>k div 4 do
    begin
      dec(curs,b[st]);
      inc(curs,b[st+(k div 2)]);
      inc(st);
    end;
  if st=1 then
    write('1 ',k div 2,' ',(k div 2)+1)
  else
    write('2 ',st-1,' ',st,' ',st+(k div 2)-1,' ',st+(k div 2));
end.

I have Delphi 7, BP 7.0, FP 1.0.4, Windows XP
Мои решения олимпиад на  Паскале: http://h0h0l.narod.ru/
Моя проверялка: http://www.proveryalka.narod.ru/
ICQ: 266367671

Поза форумом

 

#15 2005-11-23 10:53:17

ROBOT
Олімпієць
Звідки: Ялта
Зареєстрований: 2005-10-26
Повідомлень: 158

Re: Решения задач на Паскале

Батыев Андрей написав:

Люди!!!!! Блин, неужели есть гении которые способны понять алгоритм по 1-5 кб коду?
И ваще лучше выкладывать и спорить над АЛГОРИТМАМИ чем над ИСХОДНИКАМИ!
Тогда не будет проблем с языком, компилятором и проч.!

АЛГАРИТМЫ трудно объяснить слловами
Легче нарисовать на бумажке рисунок
Кстати как можно разрезать цепь МЕЖДУ звеньями?


I have Delphi 7, BP 7.0, FP 1.0.4, Windows XP
Мои решения олимпиад на  Паскале: http://h0h0l.narod.ru/
Моя проверялка: http://www.proveryalka.narod.ru/
ICQ: 266367671

Поза форумом

 

#16 2005-11-23 18:32:17

CHERTIK
Олімпієць
Зареєстрований: 2005-10-29
Повідомлень: 3

Re: Решения задач на Паскале

Я его уже по полочкам разложил.А два теста не прохадит (Time Out). Что не так?
program Bear1;
var
m,k,i:longint;
procedure run;
begin
read(m,k);
if k mod 2=0 then
begin
  i:=0;
  write(0,' ');
  repeat
   inc(i,2);
   write(i*m,' ');
  until i=k;
end
else
begin
   i:=1;
  write(m,' ');
  repeat
   inc(i,2);
   write(i*m,' ');
  until i=k;
end
end;
begin
run
end.

Поза форумом

 

#17 2005-11-23 19:04:01

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

Re: Решения задач на Паскале

Проверь. что будет,  если К у тебя 1. Я правда в решение не вчитывалась, но, по-моему, оно заглючит.
Мой вариант решения:

var M,K,i : integer;
begin
readln(M,K);
if K mod 2 = 0 then i := 0
else i := 1;
while i <= K do
begin
   write(i*M,' ');
   inc(i,2);
end;
writeln;
end.

Відредаговано Anna (2005-11-23 19:09:28)


Хорошо смеется тот, кто смеется последним...

Поза форумом

 

#18 2005-11-23 19:16:30

Батыев Андрей
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 70

Re: Решения задач на Паскале

Попробуйте понять, почему мой Bear прошел все тесты smile

program bear;
var r,m,k,i:longint;
begin
read(m,k);
if k mod 2=1 then
  i:=1
else
  i:=0;
while i<k do
begin
  write(i*m,' ');
  i:=i+2;
end;
write(i*m);
end.

Відредаговано Батыев Андрей (2005-11-23 19:17:45)

Поза форумом

 

#19 2005-11-23 19:20:00

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

Re: Решения задач на Паскале

Ну, у меня, фактически, то же самое, и я тоже 20 балов за это получила. А зачем тебе там р? smile


Хорошо смеется тот, кто смеется последним...

Поза форумом

 

#20 2005-11-23 20:23:22

Батыев Андрей
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 70

Re: Решения задач на Паскале

Сорри, глюк! Ре там не нужно!

Поза форумом

 

#21 2005-11-23 22:10:44

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: Решения задач на Паскале

Задача Bear.
Маленький медвежонок идет по дороге, вдоль которой на расстоянии М одно от другого растут деревья.Останавливаясь под каждым деревом, медвежонок забывает, откуда пришел, и, двигаясь через некоторое время дальше, случайно выбирает то или иное направление движения. На каком расстоянии от "стартового" дерева может быть медвежонок после К этапов?
Технические условия Программа считывает с клавиатуры числа M и К через пробел (1<=М,К<=10000). Программа выводит на экран в одной строке через пробелы расстояния, на которых может находиться медвежонок (от меньшего до большего).
Пример
Ввод 2 6
Вывод 0 4 8 12


Сперва будем считать М=1. Тогда заметим, что все пройденные мишкой расстояния будут имет одинаковую четность, равную четности числа К (так как при каждом переходе четность меняется). Кроме того, он всегда может попасть в точку с координатой 0 (при четном К) или 1 (при нечетном) а также всегда может попасть в точку с координатой К. Также, можно заметить, что мишка может попасть во все координаты между ними, равные К по четности (несколько раз ходим взад-вперед, а потом а раз прямо, a<=К), поэтому ответом будут: все числа от 0 до К, равные К по четности. При М>1, умножаем все числа в ответе на М.
Сложность алгоритма: O(K)

Задача Piece.
Имеется окружность радиуса R с координатами центра x,y и прямая, заданная координатами двух своих точек.Какой длины отрезок прямой лежит внутри окружности?
Технические условия Программа читает с клавиатуры строку из 7-ми чисел: радиус окружности, координаты x y центра и координаты 2-х точек прямой. Все числа целые, по абсолютной величине не превосходят 10000. Результат вывести на экран, не округляя. Если окружность и прямая не пересекаются, вывести -1, если касаются - вывести 0.
Пример
Ввод 5 0 0 4 1 4 2
Вывод 6.0000000000000000E+0000

Сперва делаем движение на вектор (-x;-y), чтобы точка (x;y) перешла в точку (0;0).
Далее, находим расстояние от центра окружности до нашей прямой. На мой взгляд, самый оптимальный способ – это подсчет высоты в треугольнике OAB как
H= 2*S(OAB)/AB, где 2*S(OAB) подчитывается, как модуль псевдоскалярного произведения векторов OA и OB  ( (a;b)*(c;d) = a*d-b*c). Зная расстояние, легко перейти к длинне секущей:
Если     H>R – пересечения нет
H=R – касание
H<R – пересечение, длинна секущей из т. Пифагора: L2 = 2(R2 – H2)
Не забываем делать “допуск” для условия касания, вместо
H=R пишем
Abs(H-R)<=0.00001
Сложность алгоритма: O(1)
Задача Circuit.
    Дана цепочка, состоящая из k=4n звеньев. Причем 2n звеньев - золотые и 2n звеньев - серебряные. Два разбойника желают справедливо разделить серебро и золото данной цепочки. Составьте программу,которая находит минимальное количество разрезов цепочки,так, чтобы как серебро так и золото можно было бы разделить между двумя разбойниками.
Технические условия Программа читает с клавиатуры количество звеньев k,а далее - k чисел 0 либо 1 (0 - серебряное звено, 1 - золотое).Все числа вводятся одной строкой через пробелы. Программа выводит на экран количество разрезов и номера звеньев, между которыми они были сделаны. Первый разрез должен быть как можно ближе к началу цепи. N<10000
Пример
Ввод 8 0 1 0 0 1 1 0 1
Вывод 2 1 2 5 6


Создадим массив a[i], i=0..k по такому правилу a[0]=0, a[i]= разность золотых и серебряных звеньев цепи среди первых n (создается в один проход) , легко видеть, что цепь можно разделить правильно одним разрезом тогда и только тогда когда a[2n]=0. Проверяем этот случай.
Докажем что в ином случае можно обойтись двумя разрезами и найдем их. Рассмотрим ф-цию f(x) =a[x+2*n-1]-a[x-1]. Она равна разности числа золотых и серебрянных звеньев в отрезке цепи длинной 2n с x по x+2n-1. Если f(x)=0, то этот отрезок даем одному разбойнику, остаток – другому. Все довольны. Докажем, что у ф-ции f всегда есть корень. Заметим, что она всегда принимает четные значения. F(1) = -f(2n) (так как соответствующие куски дают в сумме всю цепь, а количества звеньев в них меняются местами). Также заметим f(x+1) отличается от f(x) не более чем на 2. Значит функчия имеет корень. Так как если f(1)<>0 то f(1) и f(2n) имеют разный знак. Значит, найдется такое t, что  f(t) и f(t+1) имеют разный знак (иначе везде был бы один и тот же знак) но тогда f(t) f(t+1) отличаются как минимум на 4 что невозможно. Значит f(x) имеет корень, находим наименьший из корней перебором и выводим соответствующее ему разрезание цепи. Также заметим, что карни ф-ции f(x) дают нам все возможные «хорошие» разрезания цепи двумя разрезами т.к. в таком случае всегда будет кусок длинны 2n а это значит, что наш ответ будет удовлетворять условию «Первый разрез должен быть как можно ближе к началу цепи.»
Сложность алгоритма: O(K)


Задача Newpatience.
Многие в свободное время увлекаются разложением пасьянсов. Предлагаем вам еще один, правда, карты для него нужно изготовить самостоятельно. Итак, на N карточках нанесите натуральные числа по одному числу на каждой стороне карточки так, что каждое из чисел наносилось ровно 2 раза. Карточки разложите на столе в ряд. Все готово. Можно начинать. В процессе игры карточки можно переворачивать другой стороной. Пасьянс сходится тогда, когда перевернув некоторые карточки, вы получите возможность видеть все N чисел одновременно. Сойдется ли пасьянс, а если да, то какое наименьшее количество карточек необходимо для этого перевернуть?
Технические условия Программа читает с клавиатуры число N (N<10000), а далее 2 группы по N чисел-сначала числа на одной из сторон каждой из N карточек (игрок их видит в начале игры), а затем числа,нанесеннные на эти же карточки,но на противоположную сторону. Все числа вводятся одной строкой через пробелы. Вы выводите на экран одно число: -1, если пасьянс не "сошелся", либо минимальное количество перевернутых другой стороной карточек, если игра завершилась успехом. Пример
Ввод 5 3 2 5 3 2 5 4 1 1 4
Вывод 2


Назовем циклом последовательность из a карточек такой, что у любых двух соседних (а также у 1 и а) карточек есть общее число. Решим задачу для цикла: найдем общее число карточек 1 и 2, повернем карточку 1 этим числом вверх для всех 1<x<=a повернем карточку х вверх тем числом, какое снизу у карточки х-1. В итоге получаем сошедшийся пасьянс. Количество ходов при этом (t) определяется однозначно. Можно заметить, что при этом существует еще всего один способ собрать пасьянс: повернуть все карточки наоборот. Количество ходов при этом: a-t. Поэтому нужно выбрать минимум из этих двух чисел. Это и будет минимальное число ходов, чтобы собрать цикл. Теперь разбиваем наш набор на циклы (последовательность карточек в цикле не обязательно совпадает с последовательностью карточек на столе) и считаем число ходов, необходимое чтобы собрать каждый из них. Сумма ходов и будет ответом. Попутно мы доказали, что любой пасьянс сходится.
Сложность алгоритма: O(N)


ICQ 233-416-344

Поза форумом

 

#22 2005-11-24 22:16:58

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

Re: Решения задач на Паскале

Ваня, задачу Circuit можно решить намного проще.

Поза форумом

 

#23 2005-11-24 23:02:10

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: Решения задач на Паскале

Нет! Решение Circuit у меня простое А длинное доказательство достаточности двух разрезов.


ICQ 233-416-344

Поза форумом

 

#24 2005-11-25 15:49:31

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

Re: Решения задач на Паскале

Я могу доказать быстрее smile. Правда устно, сейчас попытаюсь обосновать это математически. Вообщем то, что разреза 2 до меня почему-то дошло через 1-2 мин после прочтения условия.

Поза форумом

 

#25 2005-11-25 17:28:48

CHERTIK
Олімпієць
Зареєстрований: 2005-10-29
Повідомлень: 3

Re: Решения задач на Паскале

Упс. Глюк. Спасибо. В попыхах и не заметил.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt