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


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

Ви не зайшли.

#1 2005-12-21 09:57:27

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

Делимся результатами тура по Online проверке

Итак у меня:
WOOD - 40
DSP - 34 - перестарался где-то smile
BUILDING - 40
PRIMENUM -38 - ну очень обидно sad
COUNTRY - 40

За первый тур 88 / 100
За второй тур 192 / 200
Всего              280 / 300

По-моему, неплохо, хотя глюки очень тупые...

Поза форумом

 

#2 2005-12-21 09:59:01

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

Re: Делимся результатами тура по Online проверке

Публикую заодно решения задач, в которых у меня полный бал:
WOOD:

Код:

var
  N, Top, topl, topr, i, l, r : Integer;
  A : array [1..500] of record
    x,y,l : extended;
  end;
  TL, ML, SML, NL, MH, Len, ro, dl, dr : extended;
  isl : Boolean;
begin
  Read(N);

  top := 1;
  TL := 0;
  for i := 1 to N do
  begin
    Read(A[i].X, A[i].Y);
    if i <> 1 then
    begin
      if A[i].Y > A[i-1].Y then
        top := i;
      A[i-1].l := sqrt(sqr(A[i].x-A[i-1].x)+sqr(A[i].y-A[i-1].y));
      TL := TL+A[i-1].l;
    end;
  end;
  Read(ro);
  Len := sqrt(sqr(A[1].x-A[N].x)+sqr(A[1].y-A[N].y));
  TL := (TL+Len)*ro;
  topl := top;
  while (topl > 1) and (A[topl-1].Y = A[topl].Y) do
    Dec(topl);
  topr := top;
  while (topr < N) and (A[topr-1].Y = A[topr].Y) do
    Inc(topr);
  l := 1;
  r := n;
  ML := Len;
  while (l < topl) and (r > topr) do
  begin
    SML := ML;
    dl := A[l+1].Y-A[l].Y;
    dr := A[r-1].Y-A[r].Y;
    if A[l+1].Y <= A[r-1].Y then
    begin
      MH := A[l+1].Y;
      isl := True;
      ML := ML+A[l].l;
      NL := ML+A[r-1].l*(MH-A[r].Y)/dr;
    end
    else
    begin
      isl := False;
      MH := A[r-1].Y;
      ML := ML+A[r-1].l;
      NL := ML+A[l].l*(MH-A[l].Y)/dl;
    end;
    if NL >= TL then
    begin
      MH := ( dr*dl*(TL-SML) + dr*A[l].Y*A[l].l + dl*A[r].Y*A[r-1].l )/
            (dr*A[l].l + dl*A[r-1].l);
      Break;
    end;
    if isl  then
      Inc(l)
    else
      Dec(r);
  end;
  WriteLn(MH);
end.

BUILDING:

Код:

var
  M, N, i, j, l, t, C, max : Integer;
  A : array [1..100, 1..100] of Integer;
begin
  Read(M, N);
  for i := 1 to M do
  begin
    C := 0;
    for j := 1 to N do
    begin
      Read(t);
      if t = 0 then
        C := 0
      else
        Inc(C);
      A[i, j] := C;
    end;
  end;
  max := 0;
  for j := 1 to N do
  begin
    for i := 1 to M do
      if (A[i, j] <> 0) then
        if ((i = 1) or (A[i, j] > A[i-1, j])) then
        begin
          l := i;
          t := maxint;
          C := 0;
          while (l <= M) and (A[l, j] <> 0) do
          begin
            Inc(C);
            if A[l, j] < t then
              t := A[l, j];
            if c*t > max then
              max := c*t;
            Inc(l);
          end;
        end;
  end;
  WriteLn(max);
end.

COUNTRY:

Код:

var
  M : array [1..50000] of Byte;
  N, K, t, i, j : longint;
  A : array [1..3] of longint;
  C : array [1..3, 1..3] of longint;
begin
  Read(N);
  FillChar(C, sizeof(C), 0);
  FillChar(A, Sizeof(A), 0);
  for i := 1 to N do
  begin
    Read(M[i]);
    Inc(A[M[i]]);
  end;
  for i := 1 to A[1] do
    if M[i] <> 1 then
      Inc(C[1, M[i]]);
  for i := A[1]+1 to N-A[2] do
    if M[i] <> 3 then
      Inc(C[3, M[i]]);
  for i := N-A[2]+1 to N do
    if M[i] <> 2 then
      Inc(C[2, M[i]]);
  K := 0;

  t := C[1, 2];
  if C[2, 3] < t then
    t := C[2, 3];
  if C[3, 1] < t then
    t := C[3, 1];
  K := K+t;
  C[1, 2] := C[1, 2]-t;
  C[2, 3] := C[2, 3]-t;
  C[3, 1] := C[3, 1]-t;

  t := C[1, 3];
  if C[3, 2] < t then
    t := C[3, 2];
  if C[2, 1] < t then
    t := C[2, 1];
  K := K+t;
  C[1, 3] := C[1, 3]-t;
  C[3, 2] := C[3, 2]-t;
  C[2, 1] := C[2, 1]-t;

  for i := 1 to 3 do
    for j := i+1 to 3 do
    begin
      t := C[i, j];
      if C[j, i] < t then
        t := C[j, i];
      K := K+t;
      C[i, j] := C[i, j]-t;
      C[j, i] := C[j, i]-t;
    end;

  WriteLn(K);
end.

Поза форумом

 

#3 2005-12-21 10:26:12

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

Re: Делимся результатами тура по Online проверке

Короче в мене 200/200. Ось розвязки
Building. Ну дуже жалко що розвязки O(N^3) проходять

Код:

const con=200;
type t=word;
var a:array[1..con] of T;
    stek:array[1..con] of T;
    max,c,n,m,i,j,size:T;
    q1,q2:array[1..con] of T;

 procedure read_data;
  begin
    read(n,m);
    for i:=1 to n do
    begin
     for j:=1 to m do begin read(c); a[j]:=(a[j]+1)*c; end;
     {lower bound}
     size:=0;
     for j:=m downto 1 do
      begin
        while (size<>0) and (a[j]<a[stek[size]]) do begin q1[stek[size]]:=j+1; dec(size); end;
        inc(size);stek[size]:=j;
      end;
     for j:=1 to size do q1[stek[j]]:=1;
     {upper bound}
     size:=0;
     for j:=1 to m do
      begin
        while (size<>0) and (a[j]<a[stek[size]]) do begin q2[stek[size]]:=j-1; dec(size); end;
        inc(size);stek[size]:=j;
      end;
     for j:=1 to size do q2[stek[j]]:=m;
     {compute answer}
     for j:=1 to m do if max<(q2[j]-q1[j]+1)*a[j] then max:=(q2[j]-q1[j]+1)*a[j];
    end;
  end;

 procedure write_data;
  begin
    writeln(max);
  end;

begin
{  assign(input,'building.in'); reset(input);
  assign(output,'building.out'); rewrite(output);}
  read_data;
  write_data;
{  close(input);close(output);}
end.

Country. Смішно стає, коли дивишся деякі розвязки учасників. Все набагато легше:)

Код:

var a:array[1..50000] of byte;
    b,c:array[1..3] of word;
    i,n,ans:word;

 procedure read_data;
  begin
    read(n);
    for i:=1 to n do begin read(a[i]); inc(b[a[i]]); end;
  end;

 procedure algor;
 function max(q,w:word):word; begin if q>w then max:=q else max:=w; end;
  begin
    for i:=1 to n do
     case a[i] of
      1:if i>b[1] then inc(c[a[i]]);
      3:if (i<=b[1]) or (i>b[1]+b[3]) then inc(c[a[i]]);
      2:if i<=b[1]+b[3] then inc(c[a[i]]);
     end;
    ans:=max(max(c[1],c[2]),c[3]);
  end;

 procedure write_data;
  begin
    writeln(ans);
  end;

begin
{  assign(input,'country.in'); reset(input);
  assign(output,'country.out'); rewrite(output);}
  read_data;
  algor;
  write_data;
 { close(input);close(output);}
end.

Dsp.

Код:

const con=200;
var a:array[1..con,1..con] of longint;
    tem,k,n,m,q,w,i,j:longint;

 procedure read_data;
  begin
    read(n,m,q,w);
  end;

 procedure algor;
 function min(q,w:longint):longint; begin if q<w then min:=q else min:=w; end;
  begin
    {suppose that first side >= then second}
    if n<m then begin tem:=n;n:=m;m:=tem; end;
    if q<w then begin tem:=q;q:=w;w:=tem; end;
    a[q][w]:=1;a[w][q]:=1;
    for i:=q to n do
     for j:=1 to min(i,m) do
      begin
        for k:=1 to i div 2 do
         if (a[i][j]<a[k][j]+a[i-k][j]) then a[i][j]:=a[k][j]+a[i-k][j];
        for k:=1 to j div 2 do
         if (a[i][j]<a[i][k]+a[i][j-k]) then a[i][j]:=a[i][k]+a[i][j-k];
       a[j][i]:=a[i][j];
      end;
  end;

 procedure write_data;
  begin
    writeln(a[n][m]);
  end;

begin
{  assign(input,'dsp.in'); reset(input);
  assign(output,'dsp.out'); rewrite(output);}
  read_data;
  algor;
  write_data;
  {close(input);close(output);}
end.

Primenum. Мабуть найтупіший мій розвязок на цій олімпіаді:)

Код:

var now,kil,g,x,y,z,q,w,e,a,b,c,n:longint;
    d:array[1..10000] of longint;
    res:extended;

 procedure read_data;
  begin
    read(a,b,c,n);
  end;

 procedure algor;

procedure sort(l,r: longint);
var i,j: longint;
begin
  i:=l;
  j:=r;
  x:=d[(l+r) div 2];
  repeat
    while d[i]<x do inc(i);
    while x<d[j] do dec(j);
    if not(i>j) then begin y:=d[i]; d[i]:=d[j]; d[j]:=y; inc(i); j:=j-1; end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

  function pow(l:extended;r:longint):extended;
   begin
     res:=1;
     for g:=1 to r do
      res:=res*l;
     pow:=res;
   end;

  begin
    now:=1; for q:=0 to 40 do begin if now*(a+0.0)>maxlongint then break; now:=now*a; end;
    now:=1; for w:=0 to 40 do begin if now*(b+0.0)>maxlongint then break; now:=now*b; end;
    now:=1; for e:=0 to 40 do begin if now*(c+0.0)>maxlongint then break; now:=now*c; end;
    for x:=0 to q do
     for y:=0 to w do
     if pow(a,x)*pow(b,y)<maxlongint+1.0 then
      for z:=0 to e do
       if pow(a,x)*pow(b,y)*pow(c,z)<maxlongint+1.0 then
       begin
         inc(kil);
         d[kil]:=trunc(pow(a,x)*pow(b,y)*pow(c,z));
       end;
    sort(1,kil);
  end;

 procedure write_data;
  begin
    writeln(d[n]);
  end;

begin
{  assign(input,'primenum.in'); reset(input);
  assign(output,'primenum.out'); rewrite(output);}
  read_data;
  algor;
  write_data;
 { close(input);close(output);}
end.

взагалі сішникам була шара:

Код:

#include <set>
#include <iostream>
using namespace std;
const long MAX=(1<<30)+((1<<30)-1);
set<long> mas;
int main() {
    mas.insert(1);
    long a,b,c,n;
    cin>>a>>b>>c>>n;    
    for(int i=1;i<n;i++) {
        long num=*mas.begin();
        mas.erase(mas.begin());
        if (num*(a+.0)<=MAX) mas.insert((long) (num*a));
        if (num*(b+.0)<=MAX) mas.insert((long) (num*b));
        if (num*(c+.0)<=MAX) mas.insert((long) (num*c));
    }
    cout<<*mas.begin();
    return 0;
}

І накінець Wood

Код:

const con=500;
      _eps=1e-8;
type typ=extended; rec=record x,y:typ; end;
var a:array[0..con-1] of rec;
    count,n,i,j:longint;
    maxh,b1,b2,mid,S,x,r:typ;

 procedure read_data;
  begin
    read(n);
    for i:=0 to n-1 do
    begin
     read(a[i].x,a[i].y);
     if a[i].y>maxh then maxh:=a[i].y;
    end;
    read(r);
  end;

 procedure algor;
 function eq(q,w:typ):boolean; begin eq:=abs(q-w)<_eps; end;
 function more(q,w:typ):boolean; begin more:=q-w>_eps; end;
 function lesseq(q,w:typ):boolean; begin lesseq:=q-w<_eps; end;
 function min(q,w:typ):typ; begin if q<w then min:=q else min:=w; end;
 function max(q,w:typ):typ; begin if q>w then max:=q else max:=w; end;
 function dist(x1,y1,x2,y2:typ):typ;
  begin dist:=sqrt(sqr(x1-x2)+sqr(y1-y2)); end;
 function calc(y:typ):typ;
 var res:typ;
  begin
    res:=0;count:=0;
    for i:=0 to n-1 do
     begin
       j:=(i+1) mod n;
       if more(y,min(a[i].y,a[j].y)) and lesseq(y,max(a[i].y,a[j].y)) then
        begin
          x:=(y-a[i].y)*(a[j].x-a[i].x)/(a[j].y-a[i].y)+a[i].x;
          if count=0 then res:=res+dist(a[i].x,a[i].y,x,y) else
                          res:=res+dist(x,y,a[j].x,a[j].y);
          inc(count);
        end else
       if count<>1 then res:=res+dist(a[i].x,a[i].y,a[j].x,a[j].y);
     end;
     calc:=res;
  end;
  begin
    for i:=0 to n-1 do
     S:=S+dist(a[i].x,a[i].y,a[(i+1) mod n].x,a[(i+1) mod n].y);
     b1:=0;
     b2:=maxh;
    while (b2-b1>1e-6) do
     begin
       mid:=(b1+b2)/2;
       if calc(mid)>S*r then b2:=mid else b1:=mid;
     end;
  end;

 procedure write_data;
  begin
    writeln(mid:0:2);
  end;

begin
{  assign(input,'wood.in'); reset(input);
  assign(output,'wood.out'); rewrite(output);}
  read_data;
  algor;
  write_data;
 { close(input);close(output);}
end.

Поза форумом

 

#4 2005-12-21 16:03:44

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

Re: Делимся результатами тура по Online проверке

А мне очень жалко что проходит ДСП за (m+n)*m*n


ICQ 233-416-344

Поза форумом

 

#5 2005-12-21 18:01:24

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

Re: Делимся результатами тура по Online проверке

Ivan написав:

А мне очень жалко что проходит ДСП за (m+n)*m*n

За сколько у тебя проходит?

Поза форумом

 

#6 2005-12-21 19:19:37

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

Re: Делимся результатами тура по Online проверке

Офигеть... В первом туре жюри все твердило: "ваше решение не проходит, так как работате на 0.001 с больше, чем надо".

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

В итоге: у нас пятеро человек набрали полный балл, но тем не менее в списке они стоят под разными номерами, а не под 1... Это как понимать?!

Остается надеятся только на одно: что в онлайн-туре жюри будет более внимательно к получаемым решениям, раз уж задалось такой целью в первом... Хотя, так можно думать только потому что надежда умирает последней... =)

Відредаговано Raziel Redstone (2005-12-21 19:20:59)

Поза форумом

 

#7 2005-12-21 19:32:14

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

Re: Делимся результатами тура по Online проверке

40 баллов :-)
я лажу не гоню :-)


ICQ 233-416-344

Поза форумом

 

#8 2005-12-21 20:16:49

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

Re: Делимся результатами тура по Online проверке

Ivan! Ты все время говоришь, что знаешь решение DSP за меньшее чем O(m*n*(m+n)) время. Так выложи, поясни и докажи!


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

Поза форумом

 

#9 2005-12-21 21:18:26

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

Re: Делимся результатами тура по Online проверке

netoi.ho.com.ua я же, вроде тебе об этом уже говорил


ICQ 233-416-344

Поза форумом

 

#10 2005-12-21 22:25:08

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

Re: Делимся результатами тура по Online проверке

reiten написав:

Ivan! Ты все время говоришь, что знаешь решение DSP за меньшее чем O(m*n*(m+n)) время. Так выложи, поясни и докажи!

Мое решение: первый разрез не любой, а всегда отрезаем горизонтальные или вертикальные полосы ширины A или B.

Код:

#include <iostream>
using namespace std;

void Order(long &a, long &b, bool a_smaller_b = true)
{ if (a > b == a_smaller_b) {long t = a; a = b; b = t;}}


long w, h, a, b;
long ans[256][256];

long dvd_a[256], dvd_b[256];


int main()
{ 
  long i, j;

  cin >> w >> h >> a >> b;
  Order(a, b);

  for (i = 0; i < 256; ++i) {
    dvd_a[i] = i / a;
    dvd_b[i] = i / b;
  }

  memset(ans, 0, sizeof(ans));
  
  for (i = 1; i <= h; ++i) 
    for (j = 1; j <= w; ++j) {
      ans[i][j] = max(ans[i][j - 1], ans[i - 1][j]);

      if (j >= a) {
        ans[i][j] = max(ans[i][j], ans[i][j - a] + dvd_b[i]);
        if (j >= b)
          ans[i][j] = max(ans[i][j], ans[i][j - b] + dvd_a[i]);
      }

      if (i >= a) {
        ans[i][j] = max(ans[i][j], ans[i - a][j] + dvd_b[j]);
        if (i >= b)
          ans[i][j] = max(ans[i][j], ans[i - b][j] + dvd_a[j]);
      }
    }
  
  cout << ans[h][w] << endl;
  return 0;
}

Я доказал так:

1. Если M = A то ответ - N div B. Аналогично - случаи когда M = B, N = A или N = B.
В принципе это очевидно, но я повозился с точным доказательством. Могу написать.

2. По индукции: для любых M, N, A и В правильное решение всегда можно начать с отрезания полосы ширины А или полосы ширины B, либо горизонтальной, либо вертикальной (т.е. один из 4 вариантов всегда окажется правильным). Доказательство нетривиально, но и не слишком сложно. Расписывать полностью - сильно громоздко выйдет, но я попробую smile.

Предположим, что в правильном решении первый разрез НЕ отрезает полосу ширины A или B, и такого результата нельзя получить отрезая A или B. Будем считать что он, этот первый разрез - вертикальный, т.е. длины N.

Итак, имеем два прямоугольника: UxN и VxN, U + V = M. Для каждого из них выполняется доказуемое утверждение, т.е. для них правильный первый разрез отрезает полосу ширины либо А либо В. Если хоть один из этих разрезов - вертикальный, то его можно выполнять первым (если он не у края - горизонтальная симметрия действий в его прямоугольнике). Остался один вариант - оба горизонтальные. Тогда если оба - А или оба - В, то их можно выполнить одним, первым разрезом (опять, если один сверху, а другой снизу, вертикальная симметрия в любом из 2х прямоугольников). Значит остался (самый сложный) вариант - один из них - А, другой - В, оба горизонтальные.

Вот здесь я и остановлюсь. Дальше идея в том, что мы последовательно (вглубь, отрезая полосы) изучаем структуру каждого из двух прямоугольников, и обязательно приходим к тому, что всегда найдется либо вертикальный, либо общий горизонтальный разрез. Для этого понадобится утверждение №1, т.к. оно дает нам возможность говорить, что если, скажем, в левом прямоугольнике сделан сверху горизонтальный разрез ширины А, то эту (верхнюю) полосу можно смело (без ухудшения решения) считать разрезанной на вертикальные полосы ширины В, и не иначе. Именно из этой однозначной структуры у нас получится совмещать разрезы в один сквозной.

Очень может быть что доказательство излишне громоздкое, но я довел его до конца полностью, без всяких "интуитивно понятно что" и т.п., так что если кому сильно захочется проверить - давайте.

Відредаговано Rybak (2005-12-21 22:35:49)

Поза форумом

 

#11 2005-12-21 23:15:04

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

Re: Делимся результатами тура по Online проверке

Я лично получил 21 балл за тупое решение 2-ой задачи:
Просто писал результат (x*y)div(a*b)


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

Поза форумом

 

#12 2005-12-21 23:20:10

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

Re: Делимся результатами тура по Online проверке

Думаешь 21 это круто?
Баллы вполне соответствуют "умности" решения.


ICQ 233-416-344

Поза форумом

 

#13 2005-12-21 23:23:26

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

Re: Делимся результатами тура по Online проверке

Rybak написав:

без всяких "интуитивно понятно что" и т.п.

Ну если ты это про меня :-) то суть в чем: зачем доказывать если можно просто напросто проверить?


ICQ 233-416-344

Поза форумом

 

#14 2005-12-22 01:36:18

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

Re: Делимся результатами тура по Online проверке

Ivan написав:

Rybak написав:

без всяких "интуитивно понятно что" и т.п.

Ну если ты это про меня :-) то суть в чем: зачем доказывать если можно просто напросто проверить?

Нет, совсем не про тебя. Я просто имел ввиду что в моем тексте я опускаю куски доказательства, но могу привести его полностью, без "интуитивно понятно" и "можно доказать что".

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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt