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


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

Ви не зайшли.

#1 2006-01-19 12:12:06

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

III тур - тесты и решения

Тесты: http://www.proveryalka.narod.ru/tests.html
Решения на Паскале: http://www.h0h0l.narod.ru

Временная сложность моих решений:
NewDomino - O(50K)
DSP2          - O(N^3)
Army          - не решил
Lake           - не решил
Message     - O(Length(S1)*Length(S2)) - тупо, но лучше не придумал...

У кого решения лучше - пишите сюда.
Если придумали тесты - тоже пишите (все тесты, которые будут здесь написаны, я добавлю на свой сайт)


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

Поза форумом

 

#2 2006-01-19 13:03:32

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

Re: III тур - тесты и решения

NewDomino - O(K)
DSP            - O(N^2) - точно не помню
Army          - O(K*N^2)
Lake           - O(V^2+V*log V)
Message     - O(Length(S1)*Length(S2))

Если кто знает крутой метод решения Army или Message - расскажите, пожалуйста!!

Поза форумом

 

#3 2006-01-19 13:08:59

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

Re: III тур - тесты и решения

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

NewDomino - O(K)
DSP            - O(N^2) - точно не помню
Army          - O(K*N^2)
Lake           - O(V^2+V*log V)

Круто!!!
можешь скинуть мне решения? mailto:h0h0l@yandex.ru


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

Поза форумом

 

#4 2006-01-19 13:09:53

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

Re: III тур - тесты и решения

2 Батыев Андрей:

Попробуй поискать такие алгоритмы:

алгоритм Рабина-Карпа
алгоритм Кнута-Морриса-Пратта
алгоритм Бойера-Мура
поиск подстрок с помощью конечных автоматов

Відредаговано Anna (2006-01-19 13:10:53)


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

Поза форумом

 

#5 2006-01-19 13:55:20

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: III тур - тесты и решения

NewDomino - O(K)
DSP            - O(N^3)
Army          - O(K*N) - в лутшем случае, на самом галимом моём тесте - 4сек
Lake           - O(V^3), за счёт оптимизаций в лутшем случае O(V^2)
Message     - O(log(min(Length(S1),Length(S2)))*(Length(S1)+Length(S2))

Відредаговано xXx (2006-01-19 14:00:58)


icq - 402174

Поза форумом

 

#6 2006-01-19 14:17:14

Vova
Олімпієць
Звідки: г. Мариуполь
Зареєстрований: 2005-11-19
Повідомлень: 27

Re: III тур - тесты и решения

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

Если кто знает крутой метод решения Army или Message - расскажите, пожалуйста!!

Army
Читаем v<=(номер 1-ого солдата), запоминаем min:=v далее в строю ниже него (op:=v-1) солдат, значит выбрать K солдат можно C(N-op-1, K) способами (C(M,N) - количество способов выбрать из M по N элементов, C(M,N)=m!/(n!(m-n)!))
далее цикл
  for I:=2 to N do begin
    Read(v);
    if v>min then begin
      op:=op+(v-min)-1;
      min:=v;
    end else
      op:=op-1;
    C(N-I-op, K, cnt_i);
    Count:=Count+cnt_i;
  end;

функция C(M, N) оптимизирована под данную задачу;
памяти "кушает" прилично но тест 100000 2 1 2 3 4 ... k ... 100000 работает за 0,078 сек (по мнению Винды)
Вот мой код:

Код:

program Army;

//{$DEFINE test}

const
  MaxCm = 100000;

type
  TArrayOfCmn = array[0..MaxCm] of Int64;

var
  C_val: TArrayOfCmn;
  Cu   : array[0..MaxCm] of Boolean;

procedure Int2String(a: Int64; var S: string);

  function Str100(i: Integer): string;
  begin
    Str100 := Chr(i div 10 + Ord('0')) + Chr(i mod 10 + Ord('0'));
  end;

var
  R:      Integer;
  Is_Neg: Boolean;
begin
  S := '';
  Is_Neg := a<0;
  if Is_Neg then a:=-a;
  repeat
    R:=a mod 100;
    a:=a div 100;
    Insert(Str100(R), S, 1);
  until (a=0) or (Length(S) = 254);
  while (Length(S) > 1) and (S[1] = '0') do Delete(S, 1, 1);
  if Is_Neg then Insert('-', S, 1);
end;

procedure C(const M, N: LongInt; var Res: Int64);
var
  NC: Int64;
  I: LongInt;
begin
  if N>M then
    Res:=0
  else if Cu[M]{(C_val[M]<>nil)and(C_val[M]^[N]<>nil)} then
    Res:=C_val[M]
  else if N=1 then
    Res:=M
  else if N=0 then
    Res:=0
  else if N=M then
    Res:=1
  else begin
    I:=M;
    while (I>N)and(not Cu[i]) do
      Dec(I);
    if I=N then
      NC:=1
    else
      NC:=C_val[i];
    while I<M do begin
      NC:=(NC*(I+1)) div (I+1-N);
      Inc(I);
      C_val[i]:=NC;
      Cu[i]:=True;
    end;
    Res:=NC;
  end;
  Cu[M]:=True;
  C_val[M]:=Res;
end;

procedure ReadData;
var
  min, v, op, I, N, K: LongInt;
  Count, cnt_i: Int64;
  Res: String;
begin
  Read(N, K);
  if K=0 then begin
    WriteLn(N);
    Exit;
  end;
  FillChar(Cu, SizeOf(Cu), 0);
  Read(v);
  op:=v-1;
  min:=v;
  C(N-1-op, K, Count);
  for I:=2 to N do begin
    Read(v);
    if v>min then begin
      op:=op+(v-min)-1;
      min:=v;
    end else
      op:=op-1;
    C(N-I-op, K, cnt_i);
    Count:=Count+cnt_i;
  end;
  Int2String(Count, Res);
  Writeln(Res);
end;

begin
{$IFDEF test}
  Assign(Input, 'Input.dat');
  Assign(Output, 'Output.dat');
  Reset(Input);
  Rewrite(Output);
{$ENDIF}
  ReadData;
{$IFDEF test}
  Close(Output);
  Close(Input);
{$ENDIF}
end.

Поза форумом

 

#7 2006-01-19 14:56:59

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

Re: III тур - тесты и решения

Извините за не точности - только щас откопал код в компе.
DSP2 - таки O(N^3)
LAKE - просто O(V^2), где V - кол-во всех вершин

Значит так:
ARMY

Код:

{$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}
program army;
const maxn=100000;
      maxk=11;
var aa:array[1..maxn]of longint;
    n,k:longint;
    res:array[1..maxn,1..maxk]of comp;


procedure Init;
var i:longint;
begin
 read(n,k);
 inc(k);
 for i:=1 to n do
  read(aa[i]);
end;

procedure Solve;
var i,j,l:longint;
begin
 for i:=1 to n do
  res[i,1]:=1;
 for l:=2 to k do
  for i:=1 to n do
  begin
   res[i,l]:=0;
   for j:=1 to i-1 do
    if aa[j]<aa[i] then
     res[i,l]:=res[i,l]+res[j,l-1];
  end;
end;

procedure WriteResult;
var t:comp;
    i:longint;
begin
 t:=0;
 for i:=1 to n do
  t:=t+res[i,k];
 writeln(t:0:0);
end;

begin
 Init;
 Solve;
 WriteResult;
end.

DSP2

Код:

{$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}
program dsp2;
const maxn=52;
var c:array[1..maxn]of longint;
    res,len,n:integer;

procedure Init;
var i:integer;
begin
 read(len);
 read(n);
 c[1]:=0;
 for i:=2 to n+1 do
  read(c[i]);
 n:=n+2;
 c[n]:=len;
end;

procedure Solve;
var a:array[1..maxn,1..maxn]of longint;
    i,j,l,k:integer;
begin
 for i:=1 to n do
  for j:=1 to n do
   a[i,j]:=0;
 for l:=2 to n-1 do
  for i:=1 to n-l do
  begin
   j:=i+l; a[i,j]:=-1;
   for k:=i+1 to j-1 do
    if(a[i,j]=-1)or(a[i,j]>a[i,k]+a[k,j])then
     a[i,j]:=a[i,k]+a[k,j];
   a[i,j]:=a[i,j]+c[j]-c[i];
  end;
 res:=a[1,n];
end;

procedure WriteResult;
begin
 write(res);
end;

begin
 Init;
 Solve;
 WriteResult;
end.

NEWDOMINO

Код:

{$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}
program newdomino;
type plist=^list;
     list=record
      d:longint;
      next:plist;
     end;
const maxn=50;
      maxl=1000;
var g:array[1..maxn,1..maxn]of shortint;
    num:array[1..maxn]of integer;
    n:integer;
    res:boolean;
    cycle:plist;

procedure Init;
var i,j,a,b:integer;
begin
 for i:=1 to maxn do
 begin
  num[i]:=0;
  for j:=1 to maxn do
   g[i,j]:=0;
 end;
 read(n);
 for i:=1 to n do
 begin
  read(a,b);
  inc(g[a,b]);
  inc(g[b,a]);
  inc(num[a]); inc(num[b]);
 end;
end;

procedure ListAppend(d:longint;p:plist);
var t:plist;
begin
 New(t);
 t^.d:=d;
 t^.next:=p^.next;
 p^.next:=t;
end;

procedure BuildCycle;
var totalnum:longint;
    i,j,first:integer;
    p:plist;
    us:array[1..maxn]of boolean;
begin
 {prepare loop}
 totalnum:=0;
 for i:=1 to maxn do
 begin
  totalnum:=totalnum+num[i];
  us[i]:=false;
 end;
 {making null plug}
 new(cycle);
 cycle^.next:=nil;
 cycle^.d:=-111;
 p:=cycle;
 {first loop}
 for i:=1 to maxn do
  if (num[i]<>0) then
  begin
   first:=i;
   break;
  end;
 repeat
  totalnum:=totalnum-2;
  ListAppend(i,p);
  p:=p^.next;
  for j:=1 to maxn do
   if g[i,j]<>0 then
   begin
    dec(num[i]);
    dec(num[j]);
    dec(g[i,j]);
    dec(g[j,i]);
    i:=j;
    break;
   end;
  us[i]:=true;
 until i=first;
 {main loop}
 while(totalnum>0)do
 begin
  for i:=1 to maxn do
   if (num[i]<>0)and us[i] then
   begin
    first:=i;
    break;
   end;
  {search for position to insert}
  p:=cycle;
  while(p^.next^.d<>first)do
   p:=p^.next;
  {loop for appending}
  repeat
   totalnum:=totalnum-2;
   ListAppend(i,p);
   p:=p^.next;
   for j:=1 to maxn do
    if g[i,j]<>0 then
    begin
     dec(num[i]);
     dec(num[j]);
     dec(g[i,j]);
     dec(g[j,i]);
     i:=j;
     break;
    end;
   us[i]:=true;
  until i=first;
 end;

 {delete plug}
 p:=cycle^.next;
 Dispose(cycle);
 cycle:=p;
end;

procedure Solve;
var p:boolean;
    i,j:integer;
    us:array[1..maxn]of boolean;
begin
 res:=true;
 for i:=1 to maxn do
 begin
  res:=res and (num[i] mod 2=0);
  us[i]:=false;
 end;
 for i:=1 to n do
  if num[i]<>0 then
   break;
 us[i]:=true;
 repeat
  p:=true;
  for i:=1 to n do
   for j:=1 to n do
    if (us[i] xor us[j])and(g[i,j]<>0) then
    begin
     us[i]:=true;
     us[j]:=true;
     p:=false;
    end;
 until p;
 for i:=1 to n do
  res:=res and (us[i] or (num[i]=0));
 if res then
 begin
  BuildCycle;
 end;
end;

procedure WriteResult;
var i,first:integer;
    p:plist;
begin
 if res then
 begin
  first:=cycle^.d;
  write(first,' ');
  p:=cycle^.next;
  dispose(cycle);
  cycle:=p;
  while cycle<>nil do
  begin
   write(cycle^.d,' ',cycle^.d,' ');
   p:=cycle^.next;
   dispose(cycle);
   cycle:=p;
  end;
  writeln(first);
 end
 else
  writeln(-1);
end;

begin
 Init;
 Solve;
 WriteResult;
end.

LAKE

Код:

{$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}
program lake;
const maxn=500;
      maxl=10;
      maxv=20;

type point=record
      x,y:extended;
     end;
     polygon=record
      n:integer;
      v:array[1..maxv]of point;
     end;
     line=record
      a,b,c:extended;
     end;
var polygons:array[1..maxl]of polygon;
    l,n:integer;
    pstart,pend:point;
    g:array[1..maxn,1..maxn]of extended;
    d:array[1..maxn]of extended;
procedure Init;
var i,j:integer;
    x,y,b:extended;
begin
 read(pstart.x,pstart.y);
 read(pend.x,pend.y);
 read(l);
 for i:=1 to l do
 begin
  read(polygons[i].n);
  read(x,y);
  read(polygons[i].v[1].x,polygons[i].v[1].y);
  b:=2*pi/polygons[i].n;
  for j:=2 to polygons[i].n do
  begin
   polygons[i].v[j].x:=(polygons[i].v[1].x-x)*cos(b*(j-1))+
                       (polygons[i].v[1].y-y)*sin(b*(j-1))+x;
   polygons[i].v[j].y:=(polygons[i].v[1].y-y)*cos(b*(j-1))-
                       (polygons[i].v[1].x-x)*sin(b*(j-1))+y;
  end;
 end;
end;

procedure PointToLine(p1,p2:point;var r:line);
begin
 r.a:=p1.y-p2.y;
 r.b:=p2.x-p1.x;
 r.c:=-p1.x*r.a-p1.y*r.b;
end;

function CheckIntersect(ap1,ap2,bp1,bp2:point):boolean;
var l1,l2:line;
    w1,w2:extended;
    res:boolean;
begin
 PointToLine(ap1,ap2,l1);
 PointToLine(bp1,bp2,l2);
 w1:=l1.a*bp1.x+l1.b*bp1.y+l1.c;
 w2:=l1.a*bp2.x+l1.b*bp2.y+l1.c;
 res:=((w1>0)and(w2<0))or((w1<0)and(w2>0));
 w1:=l2.a*ap1.x+l2.b*ap1.y+l2.c;
 w2:=l2.a*ap2.x+l2.b*ap2.y+l2.c;
 res:=res and (((w1>0)and(w2<0))or((w1<0)and(w2>0)));
 CheckIntersect:=not res;
end;

function CheckPolygons(p1,p2:point):boolean;
var i,j:integer;
    res:boolean;
begin
 res:=true;
 for i:=1 to l do
 begin
  for j:=1 to polygons[i].n do
  begin
   res:=res and CheckIntersect(p1,p2,polygons[i].v[j],polygons[i].v[(j mod polygons[i].n)+1]);
   if not res then
    break;
  end;
  if not res then
   break;
 end;
 CheckPolygons:=res;
end;

procedure BuildGraph;
var i,j,ti,tj,s:integer;
begin
 n:=0;
 for i:=1 to l do
  for j:=1 to polygons[i].n do
  begin
   inc(n);
   s:=0;
   for ti:=1 to l do
    for tj:=1 to polygons[ti].n do
    begin
     inc(s);
     if CheckPolygons(polygons[i].v[j],polygons[ti].v[tj]) then
      g[n,s]:=sqrt(sqr(polygons[i].v[j].x-polygons[ti].v[tj].x)+
                   sqr(polygons[i].v[j].y-polygons[ti].v[tj].y))
     else
      g[n,s]:=-1;
     g[s,n]:=g[n,s];
    end;
  end;
 inc(n);
 s:=0;
 for ti:=1 to l do
  for tj:=1 to polygons[ti].n do
  begin
   inc(s);
   if CheckPolygons(pstart,polygons[ti].v[tj]) then
    g[n,s]:=sqrt(sqr(pstart.x-polygons[ti].v[tj].x)+
                 sqr(pstart.y-polygons[ti].v[tj].y))
   else
    g[n,s]:=-1;
   g[s,n]:=g[n,s];
  end;
 inc(n);
 s:=0;
 for ti:=1 to l do
  for tj:=1 to polygons[ti].n do
  begin
   inc(s);
   if CheckPolygons(pend,polygons[ti].v[tj]) then
    g[n,s]:=sqrt(sqr(pend.x-polygons[ti].v[tj].x)+
                 sqr(pend.y-polygons[ti].v[tj].y))
   else
    g[n,s]:=-1;
   g[s,n]:=g[n,s];
  end;
end;

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

procedure Dijkstra;
var i,j,now,k:integer;
    min:extended;
    us:array[1..maxn]of boolean;
begin
 for i:=1 to n do
 begin
  d[i]:=-1; us[i]:=false;
 end;
 d[n-1]:=0;
 now:=n-1;
 for i:=1 to n-1 do
 begin
  us[now]:=true; min:=-1;
  for j:=1 to n do
   if not us[j] then
   begin
    Relax(now,j);
    if ((min<0)or(min>d[j]))and(d[j]>0) then
    begin
     min:=d[j]; k:=j;
    end;
   end;
  now:=k;
 end;
end;

procedure Solve;
begin
 BuildGraph;
 Dijkstra;
end;

procedure WriteResult;
begin
 write(d[n]);
end;

begin
 Init;
 Solve;
 WriteResult;
end.

MESSAGE

Код:

{$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}
program message;
const maxn=20100;
var s:array[1..maxn]of char;
    len:array[1..maxn]of integer;
    res,n,n1:integer;

procedure Init;
var i:integer;
begin
 i:=0;
 while not eoln do
 begin
  inc(i);
  read(s[i]);
 end;
 readln;
 n:=i;
 inc(i); s[i]:=#0;
 while not eoln do
 begin
  inc(i);
  read(s[i]);
 end;
 res:=0;
 n1:=i;
end;

procedure Solve;
var i,j,x:integer;
begin
 for i:=1 to n do
 begin
  len[i]:=0;
  for j:=i+1 to n1 do
  begin
   x:=len[j-1];
   while (s[x+i]<>s[j])and(x>0) do
    x:=len[x+i-1];
   if s[x+i]=s[j] then
    len[j]:=x+1
   else
    len[j]:=0;
   if (len[j]>res)and(j>n) then
    res:=len[j];
  end;
 end;
end;

procedure WriteResult;
begin
 writeln(res);
end;

begin
 Init;
 Solve;
 WriteResult;
end.

Поза форумом

 

#8 2006-01-19 15:53:58

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

Re: III тур - тесты и решения

NewDomino O(N*K)
DSP2          O(N^3)
Army          O(N*K*log(N))
Дерево отрезков.... Уверен, что быстрее решения - нету. У кого за О(N) могу поздравить !!! Просто если K=1 , то эта задача про инверсии, для которой минимум - O(Nlog(N))
Lake           O(V^3)
Батыев Андрей обрати внимание на свои 3 вложенных цикла по V. Сложно такое назвать O(V^2).
Message     O(n)
Кто хочет решить линейно может копать инфу по дереву или же массиву суффиксов, короче все что связано с суффиксами.

Відредаговано Vladislav Simonenko (2006-01-19 15:59:51)

Поза форумом

 

#9 2006-01-19 17:23:17

Rybak
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-04
Повідомлень: 83
Вебсайт

Re: III тур - тесты и решения

Vova написав:

Army
Читаем v<=(номер 1-ого солдата), запоминаем min:=v далее в строю ниже него (op:=v-1) солдат, значит выбрать K солдат можно C(N-op-1, K) способами (C(M,N) - количество способов выбрать из M по N элементов, C(M,N)=m!/(n!(m-n)!))
...

Если я правильно понял условие, то то, что ты здесь написал - неправильно. Пример: 3 2 1 3 2. Твоя прога выводит 1. Правильный ответ - 0.

Поза форумом

 

#10 2006-01-19 18:19:36

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

Re: III тур - тесты и решения

Rybak написав:

Vova написав:

Army
Читаем v<=(номер 1-ого солдата), запоминаем min:=v далее в строю ниже него (op:=v-1) солдат, значит выбрать K солдат можно C(N-op-1, K) способами (C(M,N) - количество способов выбрать из M по N элементов, C(M,N)=m!/(n!(m-n)!))
...

Если я правильно понял условие, то то, что ты здесь написал - неправильно. Пример: 3 2 1 3 2. Твоя прога выводит 1. Правильный ответ - 0.

Согласен. Твоя прога действительно работает неправильно даже на самых простых тестах (проверил еще вчера smile)))

Поза форумом

 

#11 2006-01-19 18:36:53

Vova
Олімпієць
Звідки: г. Мариуполь
Зареєстрований: 2005-11-19
Повідомлень: 27

Re: III тур - тесты и решения

Значит мне не повезло sad
хотел как лучше, а получилось как всегда.

Поза форумом

 

#12 2006-01-19 18:39:12

Vova
Олімпієць
Звідки: г. Мариуполь
Зареєстрований: 2005-11-19
Повідомлень: 27

Re: III тур - тесты и решения

xXx написав:

Message     - O(log(min(Length(S1),Length(S2)))*(Length(S1)+Length(S2))

Объясни как

Поза форумом

 

#13 2006-01-19 19:21:04

Victor Barinov
Олімпієць
Зареєстрований: 2005-12-03
Повідомлень: 21

Re: III тур - тесты и решения

Привет всем!
Лично я решал задачи так:

   NewDomino - O(K) - цикл Эйлера.
   DSP2 - O(n^3) - ДП.
   Army - O(k*n*log(n)) - Использовал сортировку слиянием.
   Lake - O(n^3) - Алгоритм Флойда (Те которые медленее нет смысла использовать, т. к. создать матрицу смежности быстрее чем за O(n^3) я не знаю как).
   Message - O(n*m) - Я ни чего не придумал быстрее. Интересно узнать более эффективные алгоритмы, где можно о них узнать?

Поза форумом

 

#14 2006-01-19 20:07:43

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

Re: III тур - тесты и решения

Victor Barinov написав:

Message - O(n*m) - Я ни чего не придумал быстрее. Интересно узнать более эффективные алгоритмы, где можно о них узнать?

Я уже писал что надо использовать дерево суффиксов. У меня решение за O(N). Могу разместить исходник, но думаю толку не будет. Лучше поискать доку, желательно на английском языке( Suffix Trees ).

Good Luck !!!

Відредаговано Vladislav Simonenko (2006-01-19 20:08:34)

Поза форумом

 

#15 2006-01-19 20:33:27

manuel
Олімпієць
Звідки: Запорожье
Зареєстрований: 2005-12-12
Повідомлень: 56

Re: III тур - тесты и решения

Ура Онлайн Работает на всех тэстах!!!!!!!!!!!!!!!!!!smile


Это всего лишь мое мнение. smile
http://pascal.sources.ru/img/ansi.gif

Поза форумом

 

#16 2006-01-20 01:27:56

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: III тур - тесты и решения

NewDomino

Код:

#define NetOI
#include<stdio.h>
#define AddEdge(a,b,n)\
    if(A[a][b]==0){\
        Adj[a][++*Adj[a]]=b;\
        Adj[b][++*Adj[b]]=a;\
    }\
    A[a][b]+=n;\
    A[b][a]+=n;\
    C[a]=!C[a];\
    C[b]=!C[b]

#define AddVertex(v)\
    if(HVI[v]==-1){\
        HV[VN]=v;\
        HVI[v]=VN++;\
    }\
    v=HVI[v]

char HVI[51];
char HV[50],VN;

bool C[50];

short A[50][50],N;
char R[1002];
short RN=0;
char Adj[50][51];

void Search(char v){
    static char vi;
    char i=1;
    for(;i<=*Adj[v];i++){
        vi=Adj[v][i];
        while(A[v][vi]){
            A[v][vi]--;
            A[vi][v]--;
            N--;
            Search(vi);
            vi=Adj[v][i];
        }
    }
    R[RN++]=v;
}

int main(){
#ifndef NetOI
    *stdin=*fopen("NewDomino.in","r");
#endif
    scanf("%d",&N);
    short i=0,a,b;
    for(;i<=50;i++)
        HVI[i]=-1;
    for(i=0;i<N;i++){
        scanf("%d%d",&a,&b);
        AddVertex(a);
        AddVertex(b);
        AddEdge(a,b,1);
    }
    for(i=0;i<VN;i++)
        if(C[i])
            goto NA;    
    Search(0);
    if(N||R[0]!=R[RN-1]){
NA:
        printf("-1");
    }else
        for(RN-=2;RN>=0;RN--)
            printf("%d %d ",int(HV[R[RN+1]]),int(HV[R[RN]]));
#ifndef NetOI
    fclose(stdin);
#endif
    return 0;
}

DSP2

Код:

#define    NetOI
#include<stdio.h>

#define swap(a,b)    a=(a^=b)^(b^=a)

short N,x[53];
unsigned long R[52][52];

int main(){
#ifndef NetOI
    *stdin=*fopen("DSP2.in","r");
#endif
    scanf("%d%d",x+52,&N);
    short i=1;
    for(N++;i<N;i++)
        scanf("%d",&x[i]);
    x[N]=x[52];
    short j;
    short in,n=N-1,k;
    unsigned long m;
    for(i=1;i<n;i++){
        k=i+1;
        for(j=k+1;j<=n;j++)
            if(x[j]<x[k])
                k=j;
        if(x[k]<x[i])
            swap(x[k],x[i]);
    }
    for(i=1,j=1;i<=N;i++)
        if(x[i]!=x[i-1])
            x[j++]=x[i];
    n=(N=j-1)-1;
    switch(N) {
    case 0:
        printf("%d","0");
        break;
    case 1:
        printf("%d",x[n]);
        break;
    default:
        for(i=N-2;i>=0;i--)
            R[i][i+2]=x[i+2]-x[i];
        for(j=3;j<=N;j++)
            for(i=0;i<=N-j;i++){
                R[i][n=(in=i+j)]=-1;in-=1;
                for(k=i+1;k<=in;k++){
                    m=R[i][k]+R[k][n];
                    if(m<R[i][n])R[i][n]=m;
                }R[i][n]+=x[n]-x[i];
            }
        printf("%lu",R[0][N]);
    }
#ifndef NetOI
    fclose(stdin);
#endif
    return 0;
}

Army

Код:

#define NetOI
#include<stdio.h>

long a[100000],b[100000],n,m;
long long f[2][100000];
char c[100000];

#define f(i)    f[J][i]
#define g(i)    f[K][i]
#define SwapLayers    K=J,J^=1
#define swap(a,b)    a=(a^=b)^(b^=a)
#define sgn(a)    (a<0?-1:1)
#define min(a,b)    (a<b?a:b)
#define rN        13
#define abs(a)    (a<0?-a:a)

short J=1,K=0,y=1;
long long r[rN];

long long F(int x){
    short i=0;
    long x0=x-1;
    long d,min,max;
    if((d=a[x]-a[x0])>0)
        r[0]=g(x0);
    else r[0]=0;
    max=abs(d);
    if(max==1)
        return f(x0)+r[0];
    min=0;
    for(i=1;i<rN;i++){
        if((d=a[x]-a[x0-i])>0)    r[i]=r[i-1]+g(x0-i);
        else {    
            r[i]=r[i-1];d=-d;
        }
        if(d==1)return f(x0-i)+r[i];
        if(d<max){
            max=d;
            min=i;
        }
    }
    i=min;
    x0-=i;
    min=a[x0];
    max=a[x];
    if(min>max)
        swap(min,max);
    long long R=0;
    long j=min+1;
    for(min=y-1;j<max;j++)
        if(b[j]<x0&&b[j]>=min)
            R+=g(b[j]);
    if(a[x0]>a[x])
        R=-R;
    R+=f(x0);
    return r[i]+R;
}

bool CalcC(){
    long l,r,k,i,R=1,p[12];
    c[0]=1;
    for(p[1]=0,i=1;i<n;i++){
        l=1;r=R;
        while(l<=r)
            if(a[p[k=(l+r)/2]]>a[i])r=k-1;
            else l=k+1;
        if(r<11)
            r++;
        if(r>R)
            p[R=r]=i;
        else if(a[i]<a[p[r]])
            p[r]=i;
        c[i]=r;
    }
    if(R<=m)
        return false;
    return true;
}

int main(){
#ifndef NetOI
    *stdin=*fopen("Army.in","r");
#endif
    scanf("%ld%ld",&n,&m);
    long i=0,t;
    for(;i<n;i++){
        scanf("%ld",a+i);
        b[--a[i]]=i;
        f[0][i]=1;
    }
    if(CalcC()){
        long long R;
        for(;y<=m;y++,SwapLayers){
            for(i=min(y+rN,n)-1;i>=y;i--){
                if(c[i]>y){
                    for(R=0,t=y-1;t<i;t++)
                        if(a[t]<a[i])
                            R+=g(t);
                    f(i)=R;
                }else f(i)=0;
            }
            for(i=y+rN;i<n;i++)
                if(c[i]>y)
                    f(i)=F(i);
                else f(i)=0;
        }
        if(c[m]>m)
            R=g(m);
        else R=0;
        for(i=m+1;i<n;i++)
            if(c[i]>m)
                R+=g(i);
        printf("%I64d",R);
    }else printf("0");
#ifndef NetOI
    fclose(stdin);
    return 0;
#endif
}

Lake

Код:

#define NetOI
#include<stdio.h>
#include<math.h>

#define sqr(a)    (a)*(a)
#define S(x0,y0,x1,y1)    sqrt(sqr((x1)-(x0))+sqr((y1)-(y0)))
#define S2(x0,y0,x1,y1)    (sqr((x1)-(x0))+sqr((y1)-(y0)))
#define Eps        1E-16
#define Eps2    1E-8
#define MaxPath    1E9
const long double PI=3.1415926535897932384626433832795;

struct Point{
    double x,y;
};

inline bool CrossLine(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
    double    a0=y1-y0,b0=x0-x1,c0=-(x0*a0+y0*b0),
            a2=y3-y2,b2=x2-x3,c2=-(x2*a2+y2*b2);
#define f0(x,y)    (a0*x+b0*y+c0)
#define f2(x,y)    (a2*x+b2*y+c2)
    return (f0(x2,y2)*f0(x3,y3)<=-Eps && f2(x0,y0)*f2(x1,y1)<=-Eps);
#undef f0
#undef f2
}

class Polygon{
private:
    template<class T>
    static T Abs(T a){
        return (a<0?-a:a);
    }
public:
    double x,y;
    Point p[20];
    double r,R;
    short n;
    void Read(){
        scanf("%d%lf%lf%lf%lf",&n,&x,&y,&p[0].x,&p[0].y);
        short i=1;
        R=S(x,y,p[0].x,p[0].y);
        double A=atan2(p[0].x-x,p[0].y-y),dA=2*PI/n;
        for(;i<n;i++){
            p[i].x=x+cos(A+dA*i)*R;
            p[i].y=y+sin(A+dA*i)*R;
        }
        double tX=(p[1].x+p[0].x)/2-x,tY=(p[1].y+p[0].y)/2-y;
        r=sqrt(tX*tX+tY*tY);
    }
    bool Cross(double x0,double y0,double x1,double y1){
        double a=y1-y0,b=x0-x1,c=-(x0*a+y0*b);
        double C2=a*a+b*b;
        double H=(a*x+b*y+c)/sqrt(C2);
        if(H<0)H=-H;
        double L0=S2(x,y,x0,y0);
        double L1=S2(x,y,x1,y1);
        if(C2<Abs(L1-L0)+Eps2 && L0+Eps2>=R*R && L1+Eps2>=R*R)
            return false;
        if(H+Eps>R)
            return false;
        if(H<r-Eps)
            return true;
        short i=0;
        for(i=1;i<n;i++)
            if(::CrossLine(x0,y0,x1,y1,p[i].x,p[i].y,p[i-1].x,p[i-1].y))
                return true;
        return false;
    }
}P[10];

short N,VN=2;
unsigned char *Adj[202];
unsigned char C[202];
#define AddEdge(v,e)    Adj[v][C[v]++]=e
Point* p[202],CP[2];
double S[202];

bool VerifyLine(double x0,double y0,double x1,double y1){
    short i=0;
    for(;i<N;i++)
        if(P[i].Cross(x0,y0,x1,y1))
            return false;
    return true;
}

inline void Relax(unsigned char i,unsigned char j){
    double L=S[i]+S(p[i]->x,p[i]->y,p[j]->x,p[j]->y);
    if(S[j]>L)S[j]=L;
}

int main(){
#ifndef NetOI
    *stdin=*fopen("Lake.in","r");
#endif
    scanf("%lf%lf%lf%lf%d",&CP[0].x,&CP[0].y,&CP[1].x,&CP[1].y,&N);
    short i,j,k,LN;
    for(i=0;i<N;){
        P[i].Read();
        if(P[i].R>=Eps)
            i++;
        else N--;
    }
    for(i=0;i<202;Adj[i++]=new unsigned char[202])
    p[0]=&CP[0];
    p[1]=&CP[1];
    if(VerifyLine(p[0]->x,p[0]->y,p[1]->x,p[1]->y))
        printf("%.16lf",double(S(p[0]->x,p[0]->y,p[1]->x,p[1]->y)));
    else{
        for(i=0;i<N;i++)
            for(j=0,LN=VN;j<P[i].n;j++,VN++){
                p[VN]=&P[i].p[j];
                k=LN+(j+1)%P[i].n;
                AddEdge(VN,k);
                AddEdge(k,VN);
                for(k=0;k<LN;k++)
                    if(VerifyLine(p[VN]->x,p[VN]->y,p[k]->x,p[k]->y)){
                        AddEdge(VN,k);
                        AddEdge(k,VN);
                    }
            }
        VN--;
        for(S[0]=0,i=1;i<=VN;S[i++]=MaxPath);
        unsigned char Q[202],T;
        for(T=0;T<VN;T++)
            Q[T]=T+1;
        for(i=0;i<C[0];i++)
            Relax(0,Adj[0][i]);
        unsigned char MinI;
        for(;T;Q[MinI]=Q[--T]){
            MinI=0;
            for(i=1;i<T;i++){
                if(S[Q[i]]<S[Q[MinI]])
                    MinI=i;
            }
            i=Q[MinI];
            for(j=0;j<C[i];j++)
                Relax(i,Adj[i][j]);
        }
        if(S[1]<MaxPath)
            printf("%.lf",S[1]);
        else printf("-1");
    }
#ifndef NetOI
    fclose(stdin);
#endif
    for(i=0;i<VN;i++)
        delete Adj[i];
    return 0;
}

Message

Код:

#define NetOI
#include<stdio.h>

short aN=0,bN=0;
unsigned char *a=new unsigned char[10001],*b=new unsigned char[10001];
short SSS=0;
#define q    32768
#define fq(v)    ((v)%q)
#define p    53
short    *L=new short[q],
        *Ta=new short[10000],
        *Tb=new short[10000];
long P;
#define T0(T0,Ai)    fq(fq(long(T0)*p)+Ai)
#define Ti(Ti1,Ai1,Aid1)    fq(fq(p*long(Ti1))+fq(q-fq(long(Ai1)*P))+Aid1)

inline bool F(short d){
    short i,Na=aN-d+1,Nb=bN-d+1;
    for(i=0,P=1;i<d;i++)
        P=fq(P*p);
    Ta[0]=0;
    for(i=0;i<d;i++)
        Ta[0]=T0(Ta[0],a[i]);
    L[Ta[0]]=-1;
    for(Na--,i=0;i<Na;i++)
        L[Ta[i+1]=Ti(Ta[i],a[i],a[i+d])]=-1;
    Tb[0]=0;
    for(i=0;i<d;i++)
        Tb[0]=T0(Tb[0],b[i]);
    L[Tb[0]]=-1;
    for(Nb--,i=0;i<Nb;i++)
        L[Tb[i+1]=Ti(Tb[i],b[i],b[i+d])]=-1;
    short t;
    for(i=0;i<=Na;i++){
        t=Ta[i];
        Ta[i]=L[t];
        L[t]=i;
    }
    short j,k;
    for(j=0;j<=Nb;j++)
        for(i=L[Tb[j]];i>=0;i=Ta[i]){
            for(k=0;a[i+k]==b[j+k]&&k+i<aN&&k+j<bN;k++);
            if(k>=d){
                SSS=k;
                return true;
            }
        }
    return false;
}

int main(){
#ifndef NetOI
    *stdin=*fopen("Message.in","r");
#endif
    gets((char*)a);
    gets((char*)b);
    for(;a[aN];aN++);
    for(;b[bN];bN++);
    short L=1,R=(aN<bN?aN:bN),D;
    do {
        if(F(D=(L+R)/2))
            L=SSS+1;
        else
            R=D-1;
    } while(L<=R);
    printf("%d",SSS);
#ifndef NetOI
    fclose(stdin);
#endif
    delete[] a,b,L,Ta,Tb;
    return 0;
}

Відредаговано xXx (2006-01-20 01:30:21)


icq - 402174

Поза форумом

 

#17 2006-01-20 01:47:29

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: III тур - тесты и решения

Victor Barinov написав:

Привет всем!
Лично я решал задачи так:
   ...
   Lake - O(n^3) - Алгоритм Флойда (Те которые медленее нет смысла использовать, т. к. создать матрицу смежности быстрее чем за O(n^3) я не знаю как).
...

Алгоритм Флойда находит кратчайшие пути между всеми парами вершин... Для решения данной задачи следует использовать алгоритм Дейкстры, сложность которого - O(V*O(ExtMin)+E*O(Add)), где V - кол. вершин, E - кол. рёбер, O(ExtMin) - сложность извлеченя минимального елемента множества, O(Add) - сложность добавления(или изменения значения) елемента множества...


icq - 402174

Поза форумом

 

#18 2006-01-20 12:34:20

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: III тур - тесты и решения

Vladislav Simonenko написав:

...
Дерево отрезков.... Уверен, что быстрее решения - нету. У кого за О(N) могу поздравить !!! Просто если K=1 , то эта задача про инверсии, для которой минимум - O(Nlog(N))
...

Не совсем, если K=1, то задача сводиться к задаче о нахождении числа инверсий в массиве, все елементы которого разлиичные натуральные числа, не превосходящие N... В своём решении я использовал именно этот факт...


icq - 402174

Поза форумом

 

#19 2006-01-20 16:24:04

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

Re: III тур - тесты и решения

А вот мои решения:
Newdomino:

Код:

#include <iostream>

using namespace std;

const int maxN=50;
const int maxK=1000;

struct edge
{
     int w;
    edge *next,*prv,*dup;
};

edge domino[maxN];
edge edgs[maxK*2];
int edgCnt=0;
int stk[maxK+5];
int stkPtr;
int path[maxK+5];
int pathCnt;

inline void AddEdge(int v,int w)
{
    edgs[edgCnt].w=w;
    edgs[edgCnt].next=domino[v].next;
    edgs[edgCnt].prv=&domino[v];
    domino[v].next=&edgs[edgCnt++];
    if(domino[v].next->next)domino[v].next->next->prv=domino[v].next;

    edgs[edgCnt].w=v;
    edgs[edgCnt].next=domino[w].next;
    edgs[edgCnt].prv=&domino[w];
    domino[w].next=&edgs[edgCnt++];
    if(domino[w].next->next)domino[w].next->next->prv=domino[w].next;

    edgs[edgCnt-1].dup=&edgs[edgCnt-2];
    edgs[edgCnt-2].dup=&edgs[edgCnt-1];
}
inline void RemEdge(edge *e)
{
     e->prv->next=e->next;
    if(e->next)e->next->prv=e->prv;
    e=e->dup;
     e->prv->next=e->next;
    if(e->next)e->next->prv=e->prv;
}

inline void GoEuler(int v)
{
    int w;
    while(domino[v].next)
    {
        w=domino[v].next->w;
        RemEdge(domino[v].next);
        stk[stkPtr++]=w;
        v=w;
    }
}

int BuildEuler(int k)
{
     int i;
    for(i=0;i<maxN&&!domino[i].next;i++);
    stk[0]=i;
    stkPtr=1;
    do{
        GoEuler(stk[stkPtr-1]);
        path[pathCnt++]=stk[--stkPtr];
    }while(stkPtr);
    return pathCnt==k+1&&path[0]==path[pathCnt-1];
}

int main()
{
    int i,k,v,w;

    cin>>k;
    for(i=0;i<k;i++)
    {
         cin>>v>>w;
        v--;
        w--;
        AddEdge(v,w);
    }

    if(BuildEuler(k))
    {
         cout<<path[0]+1;
        for(i=1;i<pathCnt-1;i++)
           cout<<" "<<path[i]+1<<" "<<path[i]+1;
        cout<<" "<<path[pathCnt-1]+1<<endl;
    }
    else cout<<-1<<endl;

    return 0;
}

Dsp2

Код:

#include <iostream>
#include <climits>

using namespace std;

const int maxN=50;

int main()
{
    int i,n,l,j;
    int saws[maxN+2];
    int cost[maxN+2][maxN+2]={0};

    cin>>l>>n;
    saws[0]=0;
    saws[n+1]=l;
    for(i=1;i<=n;i++)
       cin>>saws[i];

    for(l=2;l<=n+1;l++)
       for(i=0;i+l<n+2;i++)
       {
            for(j=1,cost[i][i+l]=INT_MAX;j<l;j++)
               if(cost[i][i+l]>cost[i][i+j]+cost[i+j][i+l])
                    cost[i][i+l]=cost[i][i+j]+cost[i+j][i+l];
            cost[i][i+l]+=saws[i+l]-saws[i];
       }

    cout<<cost[0][n+1]<<endl;

    return 0;
}

Army:

Код:

#include <iostream>

using namespace std;

const int maxN=100000;
const int maxK=11;
const int maxNodes=265000;

struct node
{
     unsigned long long count;
    int a,b;
    node *left,*right;
};

int height[maxN];
node nodes[maxNodes];
unsigned long long counts[maxN];
node *tree;
int nCnt=0;

node *buildTree(register int a,register int b)
{
    register int mid;
    node *curr=&nodes[nCnt++];
    curr->a=a;
    curr->b=b;
    if(a<b)
    {
        mid=(a+b)/2;
        curr->left=buildTree(a,mid);
        curr->right=buildTree(mid+1,b);
    }
    return curr;
}

inline void UpdateTree(register node *curr,register int x,register unsigned long long c)
{
    if(c)
          while(curr)
        {
            curr->count+=c;
            if(curr->left&&x<=curr->left->b)curr=curr->left;
            else curr=curr->right;
        }
}

inline unsigned long long FindSegment(register node *curr,register int b)
{
     register unsigned long long res=0;
    while(curr&&curr->count)
    {
         if(curr->left&&b>=curr->left->b)
        {
             res+=curr->left->count;
            curr=curr->right;
        }
        else curr=curr->left;
    }
    return res;
}

int main()
{
    register int n;
    int k;
    register int i;
    register unsigned long long cnt;

    cin>>n>>k;
    for(i=0;i<n;i++)
       cin>>height[i];

    for(i=0;i<n;i++)
       counts[i]=1;

    //building tree
    nCnt=0;
    tree=buildTree(1,n);

    for(;k;k--)
    {
//      rebuilding tree
        for(i=0;i<nCnt;i++)
           tree[i].count=0;
//      main cycle
        for(i=0;i<n;i++)
        {
             UpdateTree(tree,height[i],counts[i]);
            counts[i]=FindSegment(tree,height[i]-1);
        }
    }

    for(i=0,cnt=0;i<n;i++)
       cnt+=counts[i];

    cout<<cnt<<endl;

     return 0;
}

Lake:

Код:

#include <iostream>
#include <cmath>

using namespace std;

const int maxLakes=10;
const int maxLakeV=20;

const double HugeVal=1e100;
const double eps=0.0000001;

const int maxV=2+maxLakes*maxLakeV;
const int IvanV=0;
const int HouseV=1;

struct point
{
     double x,y;
    inline point operator-(const point &p)const
    {
         point ans;
        ans.x=x-p.x;
        ans.y=y-p.y;
        return ans;
    }
    inline point operator+(const point &p)const
    {
         point ans;
        ans.x=x+p.x;
        ans.y=y+p.y;
        return ans;
    }
    inline double operator*(const point &p)const//vector multiple
    {
         return x*p.y-p.x*y;
    }
};
istream &operator>>(istream &is,point &p)
{
    return is>>p.x>>p.y;
}
struct node
{
     int p;
    node *next;
};

double lengths[maxV][maxV];
point points[maxV];
int lakeInd[maxV];
node *lakes[maxLakes];
node nds[maxV+maxLakes];
int nCnt=0;
int lCnt=0;
int pCnt=0;

inline double length(point p1,point p2)
{
     return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

inline void ProcLake(int sides,point center,point first)
{
    const double PiX2=2*M_PI;
    double alpha,r,phi0;//alpha - phi2-phi1
    register int i,j;
    int firstind;
    node *nd;

    alpha=PiX2/sides;
    r=length(center,first);
    nds[nCnt].p=pCnt;
    nds[nCnt].next=0;
    lakes[lCnt]=&nds[nCnt++];
    lakeInd[pCnt]=lCnt;
    points[firstind=pCnt++]=first;
    first=first-center;
    phi0=atan2(first.y,first.x);
    for(i=1;i<sides;i++)
    {
        first.x=r*cos(alpha*i+phi0);
        first.y=r*sin(alpha*i+phi0);
        nds[nCnt].p=pCnt;
        nds[nCnt].next=lakes[lCnt];
        lakes[lCnt]=&nds[nCnt++];
        lakeInd[pCnt]=lCnt;
        points[pCnt++]=first+center;
    }
    nds[nCnt].p=firstind;
       nds[nCnt].next=lakes[lCnt];
    lakes[lCnt]=&nds[nCnt++];
    for(i=firstind;i<pCnt;i++)
       for(j=firstind;j<pCnt;j++)
          lengths[i][j]=HugeVal;
    for(nd=lakes[lCnt];nd->next;nd=nd->next)
       lengths[nd->p][nd->next->p]=lengths[nd->next->p][nd->p]=length(points[nd->p],points[nd->next->p]);
    lCnt++;
}

inline int SideFromVector(const point &ab,const point &ac)
{
     double mult;
    mult=ab*ac;
    if(mult>eps)return 1;
    else if(mult<-eps)return -1;
    else return 0;
}
inline int PointOnLine(const point &a,const point &b,const point &c)
{
    return SideFromVector(b-a,c-a)==0&&
            (a.x-c.x>=-eps&&b.x-c.x<=eps||
             b.x-c.x>=-eps&&a.x-c.x<=eps)&&
            (a.y-c.y>=-eps&&b.y-c.y<=eps||
             b.y-c.y>=-eps&&a.y-c.y<=eps);
}

inline int IntersectLake(point a,point b,int l)
{
    register node *nd;
    register int OnLine=0;
    register point ab=b-a;
    point cd;
    int sign;
    for(nd=lakes[l];nd->next&&OnLine<2;nd=nd->next)
    {
         const point &c=points[nd->p];
        const point &d=points[nd->next->p];
           OnLine+=PointOnLine(a,b,c);
        if(SideFromVector(ab,c-a)*SideFromVector(ab,d-a)<0)
              OnLine+=SideFromVector(cd=d-c,a-c)*SideFromVector(cd,b-c)<=0;
    }
    return OnLine>1;
}

inline int GoodEdge(int v,int w)
{
     register int k;
    for(k=0;k<lCnt;k++)
       if(IntersectLake(points[v],points[w],k))return 0;
    return 1;
}

void BuildAdjMatrix()
{
     register int i,j;
    for(i=0;i<pCnt;i++)
       lengths[i][i]=0.0;
    for(i=0;i<pCnt-1;i++)
       for(j=i+1;j<pCnt;j++)
           if(lakeInd[i]!=lakeInd[j])
           {
                  if(GoodEdge(i,j))
                      lengths[i][j]=lengths[j][i]=length(points[i],points[j]);
                else lengths[i][j]=lengths[j][i]=HugeVal;
           }
}

double GetLengthFromIvanToHome()
{
     double toV[maxV];
    char visited[maxV];
    register int i,shortest;

    for(i=0;i<pCnt;i++)
    {
         visited[i]=0;
        toV[i]=HugeVal;
    }
    toV[IvanV]=0;

    do{
          for(shortest=-1,i=0;i<pCnt;i++)
           if(!visited[i]&&(shortest<0||toV[shortest]>toV[i]))
             shortest=i;
        visited[shortest]=1;
        for(i=0;i<pCnt;i++)
           if(toV[i]>toV[shortest]+lengths[shortest][i])
                toV[i]=toV[shortest]+lengths[shortest][i];
    }while(!visited[HouseV]);
    return toV[HouseV];
}

int main()
{
     register int n,i,sides;
    point center,first;

    cin>>points[0]>>points[1]>>n;
    pCnt=2;
    lakeInd[0]=-1;
    lakeInd[1]=-2;
    for(i=0;i<n;i++)
    {
         cin>>sides>>center>>first;
        ProcLake(sides,center,first);
    }

    BuildAdjMatrix();

    cout<<GetLengthFromIvanToHome()<<endl;

     return 0;
}

Message:

Код:

#include <iostream>
#include <cstring>

using namespace std;

const int maxL=10000;
const int Base=257;
const int Mod=299993;

struct hash_el
{
    hash_el *next;
    char *str;
};

hash_el hashes[maxL];
hash_el *table[Mod];

char strA[maxL+1];
char strB[maxL+1];
int lenA,lenB;

inline int checkPos(char *str,int hash,int len)
{
     int i;
    hash_el *l;
    for(l=table[hash];l;l=l->next)
    {
         for(i=0;i<len&&l->str[i]==str[i];i++);
        if(i==len)return 1;
    }
    return 0;
}
             inline int check(int len)
{
     int i;
    int hash,maxdigpow,found;
    for(i=0;i<Mod;i++)
       table[i]=0;
    for(i=0,hash=0,maxdigpow=1;i<lenA;i++)
    {
        hash=(Base*hash+strA[i])%Mod;
        if(i<len)maxdigpow=(maxdigpow*Base)%Mod;
        else hash=(hash+Mod-maxdigpow*strA[i-len]%Mod)%Mod;
        if(i>=len-1)
        {
             hashes[i].str=strA+i-len+1;
            hashes[i].next=table[hash];
            table[hash]=&hashes[i];
        }
    }
    for(i=0,hash=0,found=0;i<lenB&&!found;i++)
    {
        hash=(Base*hash+strB[i])%Mod;
        if(i>=len)hash=(hash+Mod-maxdigpow*strB[i-len]%Mod)%Mod;
        if(i>=len-1)found=checkPos(strB+i-len+1,hash,len);
    }
    return found;
}

inline int findMaxSubStrLen()
{
     int min,max,mid;
    for(min=0,max=(lenA<lenB?lenA:lenB);min<max;)
    {
        mid=(min+max)/2+1;
        if(check(mid))min=mid;
        else max=mid-1;
    }
    return max;
}

int main()
{
    cin.getline(strA,sizeof strA);
    cin.getline(strB,sizeof strB);

    lenA=strlen(strA);
    lenB=strlen(strB);

    cout<<findMaxSubStrLen()<<endl;

     return 0;
}

"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#20 2006-01-20 18:10:30

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

Re: III тур - тесты и решения

Вот мои решения. newdomino - 1 BD. dsp2 - AC. army - AC. lake - 1 TL. message - 2 WA. Все остальное PASSED.
newdomino:

Код:

{$APPTYPE CONSOLE}
{$B-,R-}
const
 maxn=50;
 maxk=1000;
var
 a:array[1..maxn,1..maxn] of smallint;
 num:array[1..maxn] of smallint;
 st:array[1..maxk+2] of byte;
 numst,numpath:smallint;
 n,k,i,aa,bb,tek:smallint;
 path:array[1..maxk+2] of byte;
procedure Search(ver:byte);
var
 i:byte;
begin
 i:=1;
 while (i<=n)and(a[ver,i]=0)do inc(i);
 if i<=n then
  begin
   dec(a[ver,i]);
   dec(a[i,ver]);
   inc(numst);
   st[numst]:=i;
   Search(i);
  end;
end;
begin
 fillchar(a,sizeof(a),0);
 fillchar(num,sizeof(num),0);
 n:=0;
 read(k);
 for i:=1 to k do
  begin
   read(aa,bb);
   if aa>n then n:=aa;
   if bb>n then n:=bb;
   inc(num[aa]);
   inc(num[bb]);
   inc(a[aa,bb]);
   inc(a[bb,aa]);
  end;
 for i:=1 to n do if odd(num[i]) then
  begin
   writeln(-1);
   halt;
  end;
 tek:=1;
 while num[tek]=0 do inc(tek);
 numst:=0;
 numpath:=0;
 inc(numst);
 st[numst]:=tek;
 while numst>0 do
  begin
   tek:=st[numst];
   Search(tek);
   inc(numpath);
   path[numpath]:=tek;
   dec(numst);
  end;
 write(path[1]);
 for i:=2 to numpath-1 do write(' ',path[i],' ',path[i]);
 writeln(' ',path[numpath]);
end.

dsp2:

Код:

{$APPTYPE CONSOLE}
{$B-,R-}
const
 maxn=50;
 nv=1000000;
var
 a:array[1..maxn+2] of smallint;
 f:array[1..maxn+2,1..maxn+2] of longint;
 l,n,i,j:smallint;
procedure calc(i,j:byte);
var
 k:byte;
 tek:longint;
begin
 if f[i,j]<>nv then exit;
 for k:=i+1 to j-1 do
  begin
   if f[i,k]=nv then calc(i,k);
   if f[k,j]=nv then calc(k,j);
   tek:=f[i,k]+f[k,j]+a[j]-a[i];
   if tek<f[i,j] then f[i,j]:=tek;
  end;
end;
begin
 a[1]:=0;
 read(l,n);
 for i:=1 to n do read(a[i+1]);
 inc(n);
 a[n+1]:=l;
 inc(n);
 for i:=1 to n do
  for j:=1 to n do
   f[i,j]:=nv;
 for i:=1 to n do f[i,i]:=0;
 for i:=1 to n-1 do f[i,i+1]:=0;
 calc(1,n);
 writeln(f[1,n]);
end.

army:

Код:

{$APPTYPE CONSOLE}
{$B-,R-}
{$MAXSTACKSIZE $01000000}
const
 maxn=100000;
 maxtree=300000;
 maxk=11;
type
 treeel=record
  a,b:longint;
  count:int64;
  left,right:longint;
 end;
var
 i,n,h:longint;
 j,k:byte;
 height:array[1..maxn] of longint;
 ans:array[1..maxn] of int64;
 res:int64;
 tree:array[1..maxtree] of treeel;
function BuildTree(a,b:longint):longint;
var
 mid,tekh:longint;
begin
 inc(h);
 tekh:=h;
 tree[tekh].a:=a;
 tree[tekh].b:=b;
 if a<b then
  begin
   mid:=(a+b)div 2;
   tree[tekh].left:=BuildTree(a,mid);
   tree[tekh].right:=BuildTree(mid+1,b);
  end;
 BuildTree:=tekh;
end;
procedure UpdateTree(tek:longint;index:longint;c:int64);
var
 mid:longint;
begin
 if c<>0 then
  while tek<>0 do
   begin
    inc(tree[tek].count,c);
    mid:=(tree[tek].a+tree[tek].b) div 2;
    if index<=mid then tek:=tree[tek].left else tek:=tree[tek].right;
   end;
end;
function Num(tek,h:longint):int64;
var
 ans:int64;
 mid:longint;
begin
 ans:=0;
 while (tek<>0)and(tree[tek].count<>0) do
  begin
   mid:=(tree[tek].a+tree[tek].b) div 2;
   if h>=mid then
    begin
     inc(ans,tree[tree[tek].left].count);
     tek:=tree[tek].right;
    end else tek:=tree[tek].left;
  end;
 Num:=ans;
end;
begin
 read(n,k);
 for i:=1 to n do read(height[i]);
 if k+1>n then
  begin
   writeln(0);
   halt;
  end;
 h:=0;
 fillchar(tree,sizeof(tree),0);
 BuildTree(1,n);
 for i:=1 to n do ans[i]:=1;
 for j:=1 to k do
  begin
   for i:=1 to h do tree[i].count:=0;
   for i:=1 to n do
    begin
     UpdateTree(1,height[i],ans[i]);
     ans[i]:=Num(1,height[i]-1);
    end;
  end;
 res:=0;
 for i:=1 to n do inc(res,ans[i]);
 writeln(res);
end.

lake:

Код:

{$APPTYPE CONSOLE}
{$B-,R-,N+}
const
 maxlake=10;
 maxver=20;
 maxn=maxlake*maxver+2;
 delta=1e-9;
 nv=1e9;
type
 point=record
  x,y:extended;
 end;
 lake=record
  n:byte;
  v:array[1..maxver+2] of point;
 end;
var
 ver:array[1..maxn] of point;
 a:array[1..maxn,1..maxn] of extended;
 f:array[0..maxn] of extended;
 stver,endver,zentr,pp,next:point;
 ang:extended;
 numlake,numver,i,j,k,l,{s,}x,y,n:byte;
 mnog:array[1..maxlake+2] of lake;
 v1,v2,v3:point;
 flag:boolean;
 sign1,sign2:shortint;
 p1,p2,zn:boolean;
 q:array[1..maxn] of byte;
 min,numzero:byte;
function sign(a:extended):shortint;
begin
 if abs(a)<delta then sign:=0 else
 if a>0 then sign:=1 else
 {if a<0 then }sign:=-1;
end;
begin
 for i:=1 to maxn do
  for j:=1 to maxn do
   a[i,j]:=nv;
 n:=0;
 read(stver.x,stver.y,endver.x,endver.y);
 read(numlake);
 for i:=1 to numlake do
  begin
   read(numver);
   mnog[i].n:=numver;
   ang:=2*Pi/numver;
   read(zentr.x,zentr.y,pp.x,pp.y);
   mnog[i].v[1]:=pp;
   inc(n);
   ver[n]:=pp;
   for j:=2 to numver do
    begin
     next.x:=(pp.x-zentr.x)*cos(ang)-(pp.y-zentr.y)*sin(ang)+zentr.x;
     next.y:=(pp.y-zentr.y)*cos(ang)+(pp.x-zentr.x)*sin(ang)+zentr.y;
     pp:=next;
     inc(n);
     ver[n]:=pp;
     mnog[i].v[j]:=pp;
    end;
   mnog[i].v[numver+1]:=mnog[i].v[1];
  end;
 inc(n);
 ver[n]:=stver;
 inc(n);
 ver[n]:=endver;
 k:=0;
 inc(numlake);
 mnog[numlake].n:=1;
 mnog[numlake].v[1]:=stver;
 mnog[numlake].v[2]:=stver;
 inc(numlake);
 mnog[numlake].n:=1;
 mnog[numlake].v[1]:=endver;
 mnog[numlake].v[2]:=endver;
 for i:=1 to numlake do
  begin
   for j:=k+1 to k+mnog[i].n-1 do
    begin
     a[j,j+1]:=sqrt(sqr(ver[j].x-ver[j+1].x)+sqr(ver[j].y-ver[j+1].y));
     a[j+1,j]:=a[j,j+1];
    end;
   a[mnog[i].n+k,1+k]:=sqrt(sqr(ver[mnog[i].n+k].x-ver[1+k].x)+sqr(ver[mnog[i].n+k].y-ver[1+k].y));
   a[1+k,mnog[i].n+k]:=a[mnog[i].n+k,1+k];
   inc(k,mnog[i].n);
  end;
 k:=0;
 for i:=1 to numlake do
  begin
   for j:=k+1 to k+mnog[i].n do
    for l:=k+mnog[i].n+1 to n do
     begin
      flag:=true;
      x:=1;
      {s:=0;}
      if (abs(ver[l].x-ver[j].x)<delta)and(abs(ver[l].y-ver[j].y)<delta) then x:=numlake+1;
      while (x<=numlake)and flag do
       begin
        y:=1;
        while (y<=mnog[x].n)and flag do {if (s+y<>j)and(s+y<>l)and(s+y mod mnog[x].n+1<>j)and(s+y mod mnog[x].n+1<>l) then}
         begin
          numzero:=0;
          v1.x:=ver[l].x-ver[j].x;
          v1.y:=ver[l].y-ver[j].y;
          v2.x:=mnog[x].v[y].x-ver[j].x;
          v2.y:=mnog[x].v[y].y-ver[j].y;
          v3.x:=mnog[x].v[y+1].x-ver[j].x;
          v3.y:=mnog[x].v[y+1].y-ver[j].y;
          sign1:=sign(v1.x*v2.y-v1.y*v2.x);
          sign2:=sign(v1.x*v3.y-v1.y*v3.x);
          inc(numzero,2-abs(sign1)-abs(sign2));
          if sign1<>sign2 then p1:=true else p1:=false;
          v1.x:=mnog[x].v[y+1].x-mnog[x].v[y].x;
          v1.y:=mnog[x].v[y+1].y-mnog[x].v[y].y;
          v2.x:=ver[j].x-mnog[x].v[y].x;
          v2.y:=ver[j].y-mnog[x].v[y].y;
          v3.x:=ver[l].x-mnog[x].v[y].x;
          v3.y:=ver[l].y-mnog[x].v[y].y;
          sign1:=sign(v1.x*v2.y-v1.y*v2.x);
          sign2:=sign(v1.x*v3.y-v1.y*v3.x);
          inc(numzero,2-abs(sign1)-abs(sign2));
          if sign1<>sign2 then p2:=true else p2:=false;
          if (p1 and p2)and(numzero<2) then flag:=false;
          inc(y);
         end;{ else inc(y);}
        {inc(s,mnog[x].n);}
        inc(x);
       end;
      if flag then
       begin
        a[j,l]:=sqrt(sqr(ver[l].x-ver[j].x)+sqr(ver[l].y-ver[j].y));
        a[l,j]:=a[j,l];
       end;
      end;
    inc(k,mnog[i].n);
  end;
 fillchar(q,sizeof(q),0);
 for i:=1 to n do f[i]:=nv;
 q[n-1]:=1;
 f[n-1]:=0;
 flag:=true;
 while flag do
  begin
   min:=0;
   flag:=false;
   for i:=1 to n do if (q[i]=1)and((min=0)or(f[i]<f[min]))then
    begin
     flag:=true;
     min:=i;
    end;
   if min<>0 then q[min]:=2;
   if flag then
    for i:=1 to n do if a[min,i]+f[min]<f[i] then
     begin
      q[i]:=1;
      f[i]:=a[min,i]+f[min];
     end;
  end;
 writeln(f[n]);
end.

message:

Код:

{$APPTYPE CONSOLE}
{$B-,R-,H+}
const
 maxl=10000;
 base=257;
 modul=299993;
type
 tlist=record
  pol:smallint;
  next:longint;
 end;
var
 s1,s2,s:string;
 len1,len2:smallint;
 hash:array[1..modul] of record
  first,last:smallint;
 end;
 h:smallint;
 table:array[1..maxl] of tlist;
function CheckStr(i,j,k:smallint):boolean;
var
 l:smallint;
begin
 l:=0;
 while (l<k)and(s1[i+l]=s2[j+l])do inc(l);
 if l=k then CheckStr:=true else CheckStr:=false;
end;
function CheckSeq(k:smallint):boolean;
var
 i:smallint;
 tekhash,maxdigpow:longint;
 teklist:smallint;
begin
 fillchar(hash,sizeof(hash),0);
 h:=0;
 tekhash:=0;
 maxdigpow:=1;
 for i:=1 to len1 do
  begin
   tekhash:=(base*tekhash+Ord(s1[i])) mod modul;
   if i<=k then maxdigpow:=(maxdigpow*base) mod modul else
    tekhash:=(tekhash+modul-(maxdigpow*Ord(s1[i-k]))mod modul)mod modul;
   if i>=k then
    begin
     if hash[tekhash].first<>0 then
      begin
       teklist:=hash[tekhash].last;
       inc(h);
       table[teklist].next:=h;
       teklist:=table[teklist].next;
       table[teklist].pol:=i-k+1;
       table[teklist].next:=0;
       hash[tekhash].last:=teklist;
      end else
      begin
       inc(h);
       hash[tekhash].first:=h;
       teklist:=hash[tekhash].first;
       table[teklist].pol:=i-k+1;
       table[teklist].next:=0;
       hash[tekhash].last:=teklist;
      end;
    end;
  end;
 tekhash:=0;
 maxdigpow:=1;
 for i:=1 to len2 do
  begin
   tekhash:=(base*tekhash+Ord(s2[i])) mod modul;
   if i<=k then maxdigpow:=(maxdigpow*base) mod modul else
    tekhash:=(tekhash+modul-(maxdigpow*Ord(s2[i-k]))mod modul)mod modul;
   if (i>=k)and(hash[tekhash].first<>0)then
    begin
     teklist:=hash[tekhash].first;
     repeat
      if CheckStr(table[teklist].pol,i-k+1,k) then
       begin
        CheckSeq:=true;
        exit;
       end;
      teklist:=table[teklist].next;
     until teklist=0;
    end;
  end;
 CheckSeq:=false;
end;
function GetMaxSubseqLength:smallint;
var
 l,r,tek:smallint;
begin
 l:=1;
 r:=len1;
 if not CheckSeq(l) then
  begin
   GetMaxSubseqLength:=0;
   exit;
  end;
 if CheckSeq(r) then
  begin
   GetMaxSubseqLength:=r;
   exit;
  end;
 while l<>r do
  begin
   tek:=(l+r) div 2+1;
   if CheckSeq(tek) then l:=tek else r:=tek-1;
  end;
 GetMaxSubseqLength:=l;
end;
begin
 readln(s1);
 readln(s2);
 if length(s1)>length(s2) then
  begin
   s:=s1;
   s1:=s2;
   s2:=s;
  end;
 len1:=length(s1);
 len2:=length(s2);
 writeln(GetMaxSubseqLength);
end.

Відредаговано partisan (2006-01-20 18:13:35)

Поза форумом

 

#21 2006-01-20 23:54:55

Victor Barinov
Олімпієць
Зареєстрований: 2005-12-03
Повідомлень: 21

Re: III тур - тесты и решения

xXx написав:

Не совсем, если K=1, то задача сводиться к задаче о нахождении числа инверсий в массиве, все елементы которого разлиичные натуральные числа, не превосходящие N... В своём решении я использовал именно этот факт...

Расскажи пожайлуста свое решение, с оценкой сложности алгоритма

И еще... В GNU printf("I64d", R) - выводит, почему-то, не то, что надо. Напиши cout << R и пройдешь все тесты!

Відредаговано Victor Barinov (2006-01-21 00:37:05)

Поза форумом

 

#22 2006-01-23 12:38:45

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: III тур - тесты и решения

Victor Barinov написав:

xXx написав:

Не совсем, если K=1, то задача сводиться к задаче о нахождении числа инверсий в массиве, все елементы которого разлиичные натуральные числа, не превосходящие N... В своём решении я использовал именно этот факт...

Расскажи пожайлуста свое решение, с оценкой сложности алгоритма

И еще... В GNU printf("I64d", R) - выводит, почему-то, не то, что надо. Напиши cout << R и пройдешь все тесты!

Если быть точным, то сложность - O(K*rN^2+(N-rN)*(rN+O(GetIndex)*min(abs(Ai-Aj)))), где rN - произвольная натуральная константа...(я использовал 13), O(GetIndex) - сложность получения индекса елемента по значению(1), i = rN, rN+1, ... , N-1, j = i-rN, i-rN+1, ... , i-1...
Также сложность можно представить как O(N*rN*dA)) dA ~ не помню как считать sad, но если сгенерить массив случайных, натуральных, различных, не превосходящих N чисел, то dA ~ Summa(g(i))/N, g(i)=min(abs(A[i]-A[j]), j-i>0 and j-i<=rN...
теоретически на самом плохом тесте можно добиться сложности O(N^2)... (dA = N/rN)
По памяти - O(N)
Алгоритм:
Предположим у нас есть функция f(i,k,min), которая даёт решение для элементов, индекс которых не меньше i, значения не меньше min, тогда f(1,K,1) - решение задачи...
f(i,k,min) = f(i+1,k-1,A[i])+f(i+1,k,min)
итерируя, можно получить формулу
f(i,k,min) = f(i+1,k-1,A[i])+f(i+2,k-1,A[i+1])+f(i+3,k-1,A[i+2])+...
Предоложим мы нашли f(j,k,1), f(i+1,k-1,1), f(i+2,k-1,1), ... , j>i,
тогда f(i,k,1)=f(i+1,k-1,A[i]+...+f(j,k-1,A[i])+f(j,k,1)+sgn(A[i]-A[j])*f(j,k,A[i])
найти f(j,k,A[i]) можно за O(abs(A[i]-A[j])*O(GetIndex)) перебирая индексы элементов, и если индекс превосходит j, то добавляем решение для этого елемента при k-1 к уже найденному решению f(j,k,A[i]).Получить индекс мы можем за O(1), для этого следует хранить индексы элементов в отельном массиве...
----------------------
Не знаю как можно это решение объяснить понятно...sad
Идея тут одна - использовать дополнительный массив индексов, по которому можно быстро определить sgn((A[i]-A[j])*(i-j)), для любого A[i],A[j],i,j...

Відредаговано xXx (2006-01-23 14:40:13)


icq - 402174

Поза форумом

 

#23 2006-01-23 21:35:58

Raziel Redstone
Олімпієць
Звідки: Hell
Зареєстрований: 2005-11-19
Повідомлень: 55

Re: III тур - тесты и решения

Лучше б ты просто прокомментировал свою прогу. wink Хотя, учитывая твой стиль программирования, боюсь, здесь и это бесполезно. sad

Поза форумом

 

#24 2006-01-24 14:31:03

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: III тур - тесты и решения

Поиграл с rN, очень не плохо получаеться при rN = 100


icq - 402174

Поза форумом

 

#25 2006-01-25 01:42:34

ХОБОТ
Новий користувач
Звідки: Китай
Зареєстрований: 2006-01-21
Повідомлень: 2
Вебсайт

Re: III тур - тесты и решения

ROBOT написав:

Тесты: http://www.proveryalka.narod.ru/tests.html
Решения на Паскале: http://www.h0h0l.narod.ru

Временная сложность моих решений:
NewDomino - O(50K)
DSP2          - O(N^3)
Army          - не решил
Lake           - не решил
Message     - O(Length(S1)*Length(S2)) - тупо, но лучше не придумал...

У кого решения лучше - пишите сюда.
Если придумали тесты - тоже пишите (все тесты, которые будут здесь написаны, я добавлю на свой сайт)

а мои решения на www.sosiska.ru!


У меня есть Kylix 7,Free Paskal for Linux,Linux Fedora 4
Про меня на сайте www.sosiska.ru
ICQ: 174743442

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt