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


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

Ви не зайшли.

Сторінок: 1

 

#1 2006-02-05 12:24:37

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

Обсуждаем решения

Итак 4-й тур прошел!

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

SUBNET:
Задача очень оригинальная, мне понравилась. Как оказалось, основная проблема - это понять условие smile Самое хорошее решение: запускаем Дейкстру из сервера. Потом возвращаемся из всех К вершин рекурсией назад помечая дуги, по которым идет хотя бы один оптимальный путь для каждой из К вершин. Потом смотрим какие дуги оказались помечены для всех К компьютеров. Получаем, что в графе есть некоторые помеченые дуги, причем можно доказать, что эти дуги образуют дерево. Высота этого дерева и будет ответом. Такое решение набирало 100 балов (например, так сделал Батыев Андрей).

Я реализовал более тупое решение, которое впрочем набрало 95 балов smile Запускаем из каждой из К вершин по Дейкстре. Потом рекурсивно идем и сервера обходом в глубину и для каждой вершины в этом обходе проверяем равняется ли длина оптимального пути ко всем К вершинам из нее плюс длина пути к этой вершине длине оптимального пути для каждой из К вершин (во завернул!)

Короче говоря, вот мое решение (95 балов - 1 TimeLimit)

Код:

type
  TArr = array [1..1000] of Longint;
var
  N, M, K, i, j, l, x,y,z : integer;
  F : array [1..1000] of Integer;
  V : array [1..20000] of record
    e,l,next : Integer;
  end;
  B : array [1..100] of Integer;
  D : array [0..100] of TArr;
  Q : array [1..1000] of Boolean;
  ans : Integer;

procedure pr(st : Integer; var M : TArr);
var
  i,j,min,w,t : Integer;
begin
  FillChar(Q, SizeOf(Q), 0);
  for i := 1 to N do
    M[i] := maxlongint;
  M[st] := 0;
  for j := 1 to N do
  begin
    min := -1;
    for i := 1 to N do
      if not Q[i] and ((min = -1) or (M[min] > M[i])) then
        min := i;
    if min = -1 then
      Break;
    Q[min] := True;
    w := F[min];
    while w <> 0 do
    begin
      if not Q[V[w].e] then
      begin
        t := M[min]+V[w].l;
        if t < M[V[w].e] then
          M[V[w].e] := t;
      end;
      w := V[w].next;
    end;
  end;
end;

procedure Rec(ver, step, len : longint);
var
  w, i, j, vv : Integer;
  ok : Boolean;
begin
  if len > ans then
    ans := len;
  Q[ver] := True;
  w := F[ver];
  while w <> 0 do
  begin
    vv := V[w].e;
    if not Q[vv] then
    begin
      ok := True;
      for i := 1 to K do
        if D[i][1] <> D[i][vv]+len+V[w].l then
        begin
          ok := False;
          Break;
        end;
      if ok then
        rec(vv, step+1, len+V[w].l);
    end;
    w := V[w].next;
  end;
  Q[ver] := False;
end;

begin
  Read(N,M,K);
  for i := 1 to K do
    Read(B[i]);
  for i := 1 to M do
  begin
    Read(x,y,z);
    V[i*2-1].e := y;
    V[i*2-1].l := z;
    V[i*2-1].next := F[x];
    F[x] := i*2-1;
    V[i*2].e := x;
    V[i*2].l := z;
    V[i*2].next := F[y];
    F[y] := i*2;
  end;
  Pr(1, D[0]);
  for i := 1 to K do
    Pr(B[i], D[i]);
  FillChar(Q, SizeOf(Q), 0);
  ans := -1;
  Rec(1, 0, 0);
  WriteLn(ans);
end.

NEWSUBNET:
Как оказалось, это вообще "фонарь"! Правильное решение - найти максимальное расстояние между двумя передающими компьютерами и разделить его пополам!!! Я естественно до этого не додумался и послал полный перебор, который набрал 1 балл!!! Правильное решение до смешного простое:

Код:

var
  N, i, j, max, t : Integer;
  A : array [1..1000] of record x,y : Integer; end;
begin
  Read(N);
  for i := 1 to N do
    Read(A[i].x, A[i].y);
  max := 0;
  for i := 1 to N do
    for j := i+1 to N do
    begin
      t := Abs(A[i].x-A[j].x)+Abs(A[i].y-A[j].y);
      if t > max then max := t;
    end;
  WriteLn((max+1) div 2);
end.

JUMP
Без комментариев! Физика, математика и много технического программирования. Я ей не очень занимался и набрал всего 13 балов. Лучший результат у Шамова Александра - 48 баллов (за исключением Жюри, конечно). Решение даже не публикую изза его отсутствия.

SPACE
Лобовое решение, в котором нужно не пропустить несколько тонких моментов с организацией очереди. Думаю, что написать рабочее решение не составит труда. У меня небольшой глюк, изза которого я получил всего 84.

FOUR
Чесно говоря, мне эта задача страшно понравилась! Первое, что приходит в голову - жадный алгоритм. Но он тут не работает!!! Насколько я знаю, все кто написал его ("пожадничал" так сказать) получили не больше 55 балов. Я сделал динамику, хотя объяснить как она работает до сих пор не могу smile Но результат за задачу 100 баллов:

Код:

var
  N,t,i,K,j,x,v,m : Integer;
  A : array [1..100] of Integer;
  G, GG : array [0..1000] of Word;
  maxG, maxGG : Integer;
  procedure check(x, v : Integer);
  begin
    if G[x] > v then
    begin
      G[x] := v;
      if x > maxG then
        maxG := x;
    end;
  end;
begin
  Read(N);
  FillChar(A, SizeOf(A), 0);
  for i := 1 to N do
  begin
    Read(t);
    Inc(A[t]);
  end;
  N := 0;
  FillChar(GG, SizeOf(GG), $FF);
  maxGG := 0;
  GG[0] := 0;
  for i := 1 to 100 do
    if A[i] <> 0 then
    begin
      FillChar(G, SizeOf(G), $FF);
      maxG := 0;
      t := (4-A[i] mod 4)mod 4;
      m := A[i] mod 4;
      for j := 0 to maxGG do
      if GG[j] <> $FFFF then
      begin
        Check(j+t, GG[j]);
        x := j-m;
        v := GG[j]+m;
        if x >= 0 then
        for k := A[i] div 4 downto 0 do
        begin
          Check(x,v);
          Dec(x,4);
          Inc(v, 4);
          if x < 0 then
            Break;
        end;
      end;
      GG := G;
      maxGG := maxG;
    end;
  WriteLn(GG[0]);
end.

Итого у меня 293 балла. Вроде прохожу на Всеукраинскую.

В целом олимпиада очень понравилась, жюри потрудилось на славу! Так держать!

Поза форумом

 

#2 2006-02-05 15:57:02

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

Re: Обсуждаем решения

А теперь прикол: решение задачи NewSubnet неправильное :-)

К нему есть контрпример :-)

ICQ 233-416-344

Поза форумом

 

#3 2006-02-05 16:09:35

Трегубенко Антон
Новий користувач
Зареєстрований: 2005-12-23
Повідомлень: 7

Re: Обсуждаем решения

До журі:
Розвязок задачі NewSubnet , який шукає найдовший шлях між двома точками, ділить навпіл і виводить як результат проходить всі тести. Але наприклад у тесті 4 1 4 1 5 7 1 9 6 замість відповіді 5 (по цьому алгоритму) мусить бути відповідь 6. Тобто тести правильні, просто неправильний розвязок проходить як і правильний всі тести.

Поза форумом

 

#4 2006-02-05 16:47:45

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

Re: Обсуждаем решения

Тут я вижу меня вспомнили...

И так SUBNET

Код:

program subnet;
const maxn=1000;
      maxk=100;
      infinity=1000000000;
var g:array[1..maxn,1..maxn]of longint;
    d:array[1..maxn]of longint;
    sel:array[1..maxk]of longint;
    us:array[1..maxn]of boolean;
    sel_us:array[1..maxk,1..maxn]of boolean;
    n,m,k,res:longint;


procedure Init;
var i,p,q,l:longint;
begin
 read(n,m,k);
 for i:=1 to k do
 begin
  read(sel[i]);
  for p:=1 to n do
   sel_us[i,p]:=false;
 end;
 for p:=1 to n do
 begin
  for q:=1 to n do
   g[p,q]:=infinity;
  d[p]:=infinity;
  us[p]:=false;
 end;
 d[1]:=0;
 for i:=1 to m do
 begin
  read(p,q,l);
  g[p,q]:=l;
  g[q,p]:=l;
 end;
end;

procedure Relax(u,v:longint);
begin
 if d[v]>d[u]+g[u,v] then
  d[v]:=d[u]+g[u,v];
end;

procedure recurse_ways(t,p:longint);
var i:longint;
begin
 if not sel_us[t,p] then
 begin
  sel_us[t,p]:=true;
  for i:=1 to n do
   if d[i]+g[i,p]=d[p] then
    recurse_ways(t,i);
 end;
end;

procedure ScanForResult;
var i,j:longint;
    p:boolean;
begin
 res:=0;
 for i:=1 to n do
 begin
  p:=true;
  for j:=1 to k do
  begin
   p:=p and sel_us[j,i];
   if not p then
    break;
  end;
  if p and (res<d[i]) then
   res:=d[i];
 end;
end;

procedure Solve;
var now,i,j,t,min:longint;
begin
 now:=1;
 for i:=1 to n-1 do
 begin
  us[now]:=true; min:=infinity;
  for j:=1 to n do
   if not us[j] then
   begin
    Relax(now,j);
    if min>d[j] then
    begin
     t:=j;
     min:=d[j];
    end;
   end;
  now:=t;
 end;
 for i:=1 to k do
  recurse_ways(i,sel[i]);
 ScanForResult;
end;

procedure WriteResult;
begin
 writeln(res);
end;

begin
 Init;
 Solve;
 WriteResult;
end.

Поза форумом

 

#5 2006-02-05 18:33:27

Журі NetOI-2005 - Пасіхов
Адміністратор
Зареєстрований: 2005-10-01
Повідомлень: 74

Re: Обсуждаем решения

Трегубенко Антон написав:

До журі:
Розвязок задачі NewSubnet , який шукає найдовший шлях між двома точками, ділить навпіл і виводить як результат проходить всі тести. Але наприклад у тесті 4 1 4 1 5 7 1 9 6 замість відповіді 5 (по цьому алгоритму) мусить бути відповідь 6. Тобто тести правильні, просто неправильний розвязок проходить як і правильний всі тести.

Ваш пример некорректен. Возможно, вы что-то пропустили?
Ведь в задаче.....
Технічні умови: Програма читає з клавіатури цілі числа N, M, K, далі - K натуральних чисел, далі - M груп по три натуральних числа -номери з'єднаних комп'ютерів та довжина каналу між ними, що не перевищує 1000. Всі числа розділено пропусками. Мережу збудовано так, що пакети з будь-якого комп'ютера можуть дістатися до сервера.

(2<=N<=1000, 1<=M<=10000, 1<=K<=100)
N - кількість комп'ютерівв мережі,
M - кількість відрізків кабелю, що з'єднують комп'ютери попарно,
К -кількість комп'ютерів, що надсилають сигнали на сервер (введені К натуральних чисел - їх номери).


Програма виводить на екран найбільшу довжину каналів, якими, за згаданих  умов, проходять пакети від всіх К комп'ютерів на сервер.

Приведите правильный тест в защиту ваших аргументов.

Поза форумом

 

#6 2006-02-05 19:14:44

Vladislav Simonenko
Олімпієць
Зареєстрований: 2005-10-05
Повідомлень: 20

Re: Обсуждаем решения

По-моєму ви поплутали Subnet з NewSubNet sad
Вобще, контрприклад вірний. sad

Поза форумом

 

#7 2006-02-05 21:09:23

Журі NetOI-2005 - Пасіхов
Адміністратор
Зареєстрований: 2005-10-01
Повідомлень: 74

Re: Обсуждаем решения

Vladislav Simonenko написав:

По-моєму ви поплутали Subnet з NewSubNet sad
Вобще, контрприклад вірний. sad

Дійсно, і задачі переплутав ( три доби неперервної роботи) :-(, і контрприклад правильний. Публікую авторський розв'язок

program NewSubNet;
{Pupkin}
const
     S=2000;
     MaxN=1000;

type
    koor = record
         x, y : integer
    end;

var
   koords         : array[1..MaxN] of koor;
   i, j, k, N     : integer;
   bestr, maxl, r : integer;
   best           : koor;
   x,y,xpy,xmy,x0y0,x0y1,x1y0,x1y1,x0y0g,x0y1g,x1y0g,x1y1g,rp,rn,maxr : integer;


begin
    Read(N);
    for k:=1 to N do Read(koords[k].x,koords[k].y);

     x0y0 := S+S+1; x1y1 := 0; x0y1 := S+S+1; x1y0 := -S-1;
     for k := 1 to N do begin
    xpy := koords[k].x + koords[k].y;
    xmy := koords[k].x - koords[k].y;
    if xpy < x0y0 then x0y0 := xpy;
    if xpy > x1y1 then x1y1 := xpy;
    if xmy < x0y1 then x0y1 := xmy;
    if xmy > x1y0 then x1y0 := xmy;
     end;
     rp := x1y1 - x0y0; rn := x1y0 - x0y1;
     if rp > rn then r := rp else r := rn;
     maxr := (r div 2) + 1;

     x0y0g := x0y0+maxr; x1y1g := x1y1-maxr; x0y1g := x0y1+maxr; x1y0g := x1y0-maxr;

     bestr := S;
     for i:=x1y1g to x0y0g do begin
    j:=x1y0g;
    x := (i+j+1) div 2; y := i-x;
    while x-y < x0y1g do begin
              maxl := 0;
              for k:=1 to N do begin
                  r := abs(koords[k].x-x)+abs(koords[k].y-y);
                  if r > maxl then maxl := r;
              end;
              if maxl < bestr then begin
                 bestr := maxl;
                 best.x := x;
                 best.y := y;
              end;
              inc(x); dec(y);
    end
     end;
     Write({best.x,' ',best.y,' '}bestr);
end.

--------------
Він  проходить цей тест. На жаль, жодна з 100 - бальних робіт учасників його не пройшла. Автору задачі  не вдалося придумати таку "евристику", яку придумало досить немало учасників, тому й не було такого теста....Але всі тести, що використовувалися при перевірці, правильні.

Запропонований тест включено до набору тестів, проведена повторна перевірка. Результати можна побачити на сторінці 4-го туру. Розполділ місць не змінився, хоча ситуація, що склалася, не прикрашає журі.

Поза форумом

 

#8 2006-02-05 22:28:04

Alexey
Новий користувач
Зареєстрований: 2006-02-05
Повідомлень: 5

Re: Обсуждаем решения

Может быть справедливо было бы для задачи NewSubNet добавить несколько тестов, подобных предложеному Трегубенко Антоном. Ведь в других задачах неправильный алгоритм не давал и 60% баллов.

Поза форумом

 

#9 2006-02-05 22:34:04

Трегубенко Антон
Новий користувач
Зареєстрований: 2005-12-23
Повідомлень: 7

Re: Обсуждаем решения

Дуже дякую за включення тесту. Завдяки цьому я опинився на 3-ому місці 4-ого туру олімпіади.

Журі NetOI-2005 - Пасіхов написав:

На жаль, жодна з 100 - бальних робіт учасників його не пройшла.

У мене залишилося 100 балів. Як ви помітите - у інших балли знизилися. Я теж вважаю що справедливим було б додати більше подібних тестів.
Мені жаль, що у Симоненка Владислава (100-5) баллів за другу задачу, бо якщо б він отримав менше 50 баллів за неправильний розвязок, то я би опинився на другому місці після Джулгакова sad.

Все одно дякую за включення цього тесту.

Відредаговано Трегубенко Антон (2006-02-05 22:36:29)

Поза форумом

 

#10 2006-02-05 22:46:37

Nicky Nick
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-25
Повідомлень: 48
Вебсайт

Re: Обсуждаем решения

Поддерживаю Трегубенко Антона и Ivana по поводу newsubnet:
тест: 3 1 1 9 1 5 9

ответ: 6 (пакеты встречаются в точке (5;3))

другой алгоритм, если я не ошибаюсь, дает ответ 8

Відредаговано Nicky Nick (2006-02-05 22:48:16)

Поза форумом

 

#11 2006-02-05 23:40:32

Vladislav Simonenko
Олімпієць
Зареєстрований: 2005-10-05
Повідомлень: 20

Re: Обсуждаем решения

Дійсно , тест цікавий. Вобще, я писав спочатку розв’язок за O(n^2), він точно вірний, але потім випадково прийшла ідея перевірити дану евристику, виявилося, що вона така сама квадратна , але константа при О набагато менша. Ну згенерував 40 тестів випадковим, і виявилося що відповіді повністю співпадають !!! Такий тест реально складно було знайти(особисто для мене) ... Ну я й зробив помилку ...  Але от це :

У мене залишилося 100 балів. Як ви помітите - у інших балли знизилися. Я теж вважаю що справедливим було б додати більше подібних тестів.
Мені жаль, що у Симоненка Владислава (100-5) баллів за другу задачу, бо якщо б він отримав менше 50 баллів за неправильний розвязок, то я би опинився на другому місці після Джулгакова sad.

Все одно дякую за включення цього тесту.

lol... Ну якщо так думати , то і Джулгакову треба було б ще побільше тестів дати на першу задачу, подібних до тесту який у нього вона не пройшла. Було б у нього не (100-5) балів , а менше 50 баллів. Ти був би не другий... А перший перед Джулгаковим...  Робота журі не заключається у здійснені плану 1062 задачі Тімуса:)

Відредаговано Vladislav Simonenko (2006-02-05 23:42:39)

Поза форумом

 

#12 2006-02-05 23:47:08

Alexey
Новий користувач
Зареєстрований: 2006-02-05
Повідомлень: 5

Re: Обсуждаем решения

Просьба к жюри:
Так как до сих пор судейство NetOI отличалось своей справедливостью и прозрачностью, было бы справдливо кардинально пересмотреть набор тестов (распределение баллов) по задаче NewSubNet так, чтобы правильное (но неэффективное) решение не набирало на 90 (!) баллов меньше, чем не правильное (случайно совпавшее с ответом).

Поза форумом

 

#13 2006-02-06 07:55:35

Журі NetOI-2005 - Пасіхов
Адміністратор
Зареєстрований: 2005-10-01
Повідомлень: 74

Re: Обсуждаем решения

Alexey написав:

Просьба к жюри:
Так как до сих пор судейство NetOI отличалось своей справедливостью и прозрачностью, было бы справдливо кардинально пересмотреть набор тестов (распределение баллов) по задаче NewSubNet так, чтобы правильное (но неэффективное) решение не набирало на 90 (!) баллов меньше, чем не правильное (случайно совпавшее с ответом).

Есть предложение закрыть тему.
1. Я благодарен за комплимент в адрес работы жюри.
2. К сожалению, ситуация с данной задачей жюри не украшает. (подобная эвристика в упор не приходила на ум, хотя лежит на поверхности  sad
3. 300 (!) случайных тестов, згегирированих мною,  она прошла без проблем, т.е. получить случайный тест, ее "заганяющий", мне не удалось.
4. Мы добавили предложеный  тест в набор, произвели перепроверку.
5. Тон дискуссии мне не нравится.
6. Олимпиада закончена. Поздравляем победителей.

Поза форумом

 

#14 2006-02-06 09:34:37

Alexey
Новий користувач
Зареєстрований: 2006-02-05
Повідомлень: 5

Re: Обсуждаем решения

Журі NetOI-2005 - Пасіхов написав:

5. Тон дискуссии мне не нравится.

Не понял упрёка. Я старался быть корректным. Просто пытался отстоять свою точку зрения. Но если проявил но отношению к кому-то некорректность, прошу извинть.

Поза форумом

 

#15 2006-02-06 10:53:07

Трегубенко Антон
Новий користувач
Зареєстрований: 2005-12-23
Повідомлень: 7

Re: Обсуждаем решения

До Vladislav Simonenko

У мене складність алгоритму O(n) . 100 балів. Доведено математично правильність алгоритму.

Поза форумом

 

#16 2006-02-06 11:24:54

Журі NetOI-2005 - Пасіхов
Адміністратор
Зареєстрований: 2005-10-01
Повідомлень: 74

Re: Обсуждаем решения

Alexey написав:

Журі NetOI-2005 - Пасіхов написав:

5. Тон дискуссии мне не нравится.

Не понял упрёка. Я старался быть корректным. Просто пытался отстоять свою точку зрения. Но если проявил но отношению к кому-то некорректность, прошу извинть.

Почему вы решили что упрек в ваш адрес? Отнюдь. Мне не нравится выяснения отношений между участниками в смысле "кто больший гуру". Но и это не упрек. Мне просто не нравится. Да и расстроен слегка. Эвристика-то очевидная....("Хорошо быть умным, как моя жена потом"...есть такая старинная еврейская поговорка...)

Поза форумом

 

#17 2006-02-06 11:27:21

Журі NetOI-2005 - Пасіхов
Адміністратор
Зареєстрований: 2005-10-01
Повідомлень: 74

Re: Обсуждаем решения

Трегубенко Антон написав:

До Vladislav Simonenko

У мене складність алгоритму O(n) . 100 балів. Доведено математично правильність алгоритму.

Журі буде вдечне, якщо ви опублікуєте свлї міркування.Наш розв'язок опубліковано. Кращого не маємо.

Поза форумом

 

#18 2006-02-06 11:30:41

Vladislav Simonenko
Олімпієць
Зареєстрований: 2005-10-05
Повідомлень: 20

Re: Обсуждаем решения

Трегубенко Антон написав:

До Vladislav Simonenko

У мене складність алгоритму O(n) . 100 балів. Доведено математично правильність алгоритму.

Я ж не проти. Я не писав що такого алгоритму не існує smile , просто написав як я робив цю задачу. Короче, ладно, мабуть дискусію треба завершувати... Поздоровляю , тепер вже напевно зустрінемось на всеукрі... Удачі !!!

Поза форумом

 

#19 2006-02-06 15:41:05

Alexey
Новий користувач
Зареєстрований: 2006-02-05
Повідомлень: 5

Re: Обсуждаем решения

Журі NetOI-2005 - Пасіхов написав:

Да и расстроен слегка. Эвристика-то очевидная....("Хорошо быть умным, как моя жена потом"...есть такая старинная еврейская поговорка...)

Не ошибается тот, кто ничего не делает...
Олимпиада в целом очень качественно подготовлена (есть с чем сравнить), интересная и нужная. Так что расстраиваться нет причин :-)

Поза форумом

 

#20 2006-02-07 19:47:10

Трегубенко Антон
Новий користувач
Зареєстрований: 2005-12-23
Повідомлень: 7

Re: Обсуждаем решения

Журі NetOI-2005 - Пасіхов написав:

Трегубенко Антон написав:

До Vladislav Simonenko

У мене складність алгоритму O(n) . 100 балів. Доведено математично правильність алгоритму.

Журі буде вдечне, якщо ви опублікуєте свлї міркування.Наш розв'язок опубліковано. Кращого не маємо.

Мій алгоритм схожий на ваш першою половиною. Ідея розвязання - якщо пакети дійдуть до точки А(х0;у0) за час Т , то ГМТ точок віддалених від А не більше ніж на Т (по вузлам, як біжать пакети) буде ромбом.

Код:

program NewSubNet;

Const MaxN = 2000;

type MTPoint = record
      x:integer;
      y:integer;
     end;

var n,i:integer;
    Points:array[1..MaxN] of MTPoint;
    LeftTopPoint,RightTopPoint,LeftBottomPoint,RightBottomPoint:integer;
    Distance1,Distance2:integer;
    T:integer;

function Max(a,b:integer):integer;
 begin
  Max:=(a+b+abs(a-b)) div 2;
 end;

begin
  read(n);
  for i:=1 to n do
   read(Points[i].x,Points[i].y);

  {Найменший ромб з діагоналями паралельними осям координат, який покриває всі точки}

  {Знаходимо ліву верхню, праву верхню, ліву нижню і праву нижню точки}
  LeftTopPoint:=1;
  RightTopPoint:=1;
  LeftBottomPoint:=1;
  RightBottomPoint:=1;
  for i:=2 to n do
   begin
    if Points[i].x + Points[i].y < Points[LeftTopPoint].x + Points[LeftTopPoint].y then
     LeftTopPoint:=i;
    if Points[i].x + Points[i].y > Points[RightBottomPoint].x + Points[RightBottomPoint].y then
     RightBottomPoint:=i;
    if Points[i].x - Points[i].y < Points[LeftBottomPoint].x + Points[LeftBottomPoint].y then
     LeftBottomPoint:=i;
    if Points[i].x - Points[i].y > Points[RightTopPoint].x + Points[RightTopPoint].y then
     RightTopPoint:=i;
   end;

  {Подвоєна відстань між лівою верхньою та правою нижньою точками. Відстань рахується по довжині частини прямої у=0 (або х=0, всеодно), яка лежить між прямими у=х+с, які проходять через данні точки}
  Distance1:=(Points[RightBottomPoint].x + Points[RightBottomPoint].y) - (Points[LeftTopPoint].x + Points[LeftTopPoint].y);
  {Подвоєна відстань між лівою нижньою та правою верхньою точками}
  Distance2:=(Points[RightTopPoint].x - Points[RightTopPoint].y) - (Points[LeftBottomPoint].x - Points[LeftBottomPoint].y);

  {Шукане Т буде більше за ці відстані. С геометричної точки зору це буде половина діагоналі шуканого ромба}

  {Перевіряємо довжини на парність, та місце положення центу (бо якщо довжини рівні і парні, то центр може лежати в нецілій точці)}

  if (Distance1 <> Distance2) or (Distance1 mod 2 = 1) or (Distance2 mod 2 = 1) then
   T:=Max(Distance1,Distance2) div 2 + Max(Distance1,Distance2) mod 2
  else
   begin
    {Одна відстань рівна іншій і до того ж парна}
    if (Points[LeftTopPoint].x + Points[LeftTopPoint].y + Points[RightTopPoint].x + Points[RightTopPoint].y) mod 2 = 0 then
     begin
      {Центр ромба з діагоналлю Distance1 лежить у цілій точці}
      T:=Distance1 div 2;
     end
    else
     begin
      {Центр ромба з діагоналлю Distance1 лежить у нецілій точці}
      T:=Distance1 div 2 + 1;
     end;
   end;

  write(T);


end.

Вибачаюся, цей розвязок я писав заново тому допустив помилку:

Код:

if (Distance1 <> Distance2) or (Distance1 mod 2 = 1) or (Distance2 mod 2 = 1) then
   T:=Max(Distance1,Distance2) div 2 + 1

а треба:

Код:

if (Distance1 <> Distance2) or (Distance1 mod 2 = 1) or (Distance2 mod 2 = 1) then
   T:=Max(Distance1,Distance2) div 2 + Max(Distance1,Distance2) mod 2

Відредаговано Трегубенко Антон (2006-02-08 09:21:29)

Поза форумом

 

#21 2006-02-07 19:54:22

Трегубенко Антон
Новий користувач
Зареєстрований: 2005-12-23
Повідомлень: 7

Re: Обсуждаем решения

Мені ця задача дуже сподобалась з математичної точки зору. В ній головне - знайти вірний алгоритм, а сам текст программи досить невеликий.

Дякую за увагу. Бажаю всім успіхів.

Поза форумом

 

#22 2006-02-07 20:00:37

Журі NetOI-2005 - Пасіхов
Адміністратор
Зареєстрований: 2005-10-01
Повідомлень: 74

Re: Обсуждаем решения

Трегубенко Антон:

Щиро дякую.

Поза форумом

 

 

Сторінок: 1

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

Powered by Likt
© Copyright 2002–2009 Likt