[es] - [Zadatak] Kutije

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*

Profil

^{16.07.2005. u 15:29 - pre 236 meseci}

Zadatak je sa saveznog 2002 valjda ... (ima ga na www.z-trening.com)

Dato je n kutija (n<=10000), i za svaku je dat prechnik osnove i visina. Kutija A se moze
staviti u kutiju B samo ako joj ni visina ni prechnik nisu veci od prechnika i visine kutije
B. Date kutije treba smestiti tako da na kraju ostane minimalan broj vidljivih kutija.

Primer: Dato je 5 kutija: jedna sa precnikom 20 i visinom 30, druga sa precnikom 30 i
visinom 20, treca sa precnikom 40 i visinom 40, cetvrta sa precnikom 10 i visinom 30 i
peta sa precnikom 15 i visinom 15. Tada je moguce smestiti cetvrtu kutiju u prvu, a
zatim prvu u trecu, kao i petu kutiju u drugu. Tako ostaju dve vidljive kutije: druga i
treca. Medutim, nikako nije moguce smestiti sve kutije u jednu, pa je 2 ovde rešenje.

Ulaz:
5
20 30
30 20
40 40
10 30
15 15

Izlaz:
2

E sad, ja sam tu svashta probao, ali mi je sve sporo ... neka ideja? cassey :)

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: [Zadatak] Kutije

^{16.07.2005. u 20:05 - pre 236 meseci}

Sladak zadatak. Sad tacno nemam vremena da razmislim ali koliko se secam radi se tipa: sortiras po npr. visini (a naravno menjas i pozicije osnova) i onda u tom novodobijenom nizu osnova trazis najduzi rastuci podniz (ili opadajuci zavisno kako sortiras visine). Pa navedeni primer:

= precnik

= visina

Posle sortiranja

i sad u drugom nizu trazis duzinu najduzes rastuceg podniza sto jelte

.

Ja mislim da je dokaz trivijalan...

Slozenost ti je u

(za najduzi rastuci podniz ces raditi onaj algoritam u

koji ti samo daje duzinu najduzeg rastuceg podniza a ne onaj u

koji i rekonstruise sam niz)

Math is like love. A simple idea but it can get complicated.

Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr

Profil

Re: [Zadatak] Kutije

^{16.07.2005. u 20:49 - pre 236 meseci}

Citat:

Posle sortiranja

i sad u drugom nizu trazis duzinu najduzes rastuceg podniza sto jelte

Ovdje je naduzi rastuci podniz 3 (15,20,40 ili 15,30,40).

Moje misljenje je da bi ovaj problem se mogao svrstati u Greedy algoritam.
Prvo stabilni sort po precnici pa visini (zbog mogucnosti istih precnica).

Nadalje, implementiraj prolazak kroz taj niz kutija, tako da uzmes prvu najvecu kutiju pa u nju stavljas svaku sljedecu koja moze uci po visini u tu prijasnju.
Kad tako izbacis nekoliko kutija ponovi postupak za preostale.
Koliko si puta ponavljao postupak, toliko imas sve ukupno kutija - rijesenje!

90% sam siguran da bi ti ovaj GREEDY mogao upaliti !

Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*

Profil

Re: [Zadatak] Kutije

^{17.07.2005. u 00:48 - pre 236 meseci}

Ovaj, cassey ... mislim da tvoje reshenje ne radi bash najsrecnije (tachnije, ne radi nikako :)

A iskreno mislim da bi greedy ovde proshao za svega par primera ...

Slazem se da je lep/sladak zadatak :)

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: [Zadatak] Kutije

^{17.07.2005. u 01:22 - pre 236 meseci}

Greedy nece da prodje ni za 2-3 test primera to je sigurno. I ako neko ima test primere neka pogleda i videce da nije ni priblizno dobro (a ni pametno) kucati greedy... Ovo, da ja sam pogresio ali sam siguran da je nesto bilo na tu foru... Evo moj kod pa provalite jer ja nemam trenutno vremnena...

Code:

program Kutije;
const
    MaxN = 10000;
var
  q, d, h: array [1.. MaxN] of LongInt;
    n, Sol, br: LongInt;
  f, g: Text;

  procedure InPut;
  var
      i: LongInt;
  begin
      {Assign (f, 'zad5.dat');
    Reset (f);}
    Read (n);
    for i := 1 to n do
        Read (d [i], h [i]);
    {Close (f);}
  end;

  procedure Quick_Sort (l, r: LongInt);
  var
      q, p, tmp, k, i, j: LongInt;
  begin
    if l < r then begin
          k := (l + r) DIV 2;
        i := l; j := r;
      p := d [k];
      q := h [k];
        repeat
        while (i < r) and (d [i] > p) or
            ((d [i] = p) and (h [i] > q)) do Inc (i);
        while (j > l) and (d [j] < p) or
            ((d [j] = p) and (h [j] < q)) do Dec (j);
            if i <= j then begin
                tmp := d [i]; d [i] := d [j]; d [j] := tmp;
                tmp := h [i]; h [i] := h [j]; h [j] := tmp;
              Inc (i); Dec (j);
            end;
        until i > j;
        Quick_Sort (l, j);
        Quick_Sort (i, r);
    end;
  end;

  function Find (p, k, x: LongInt): LongInt;
  var
      tmp: LongInt;
    begin
      if (k - p > 1) then begin
        tmp := (p + k) DIV 2;
      if (q [tmp] > x) then
          Find := Find (p, tmp, x)
      else
          Find := Find (tmp, k, x);
    end
    else
        if (x <= q [p]) then Find := p
      else Find := k;
  end;

  procedure Solve;
  var
    i, j: LongInt;
  begin
      Quick_Sort (1, n);

    q [1] := h [1];
    br := 1;
    for i := 2 to n do begin
        if h [i] >  q [br] then
          j := br + 1
      else
          j := Find (1, br, h [i]);
      q [j] := h [i];
      if j > br then br := j;
    end;
    Sol := br;
  end;

  procedure OutPut;
  begin
      {Assign (g, 'zad5.res');
    ReWrite (g);}
    WriteLn (Sol);
    {Close (g);}
  end;

begin
    InPut;
  Solve;
  OutPut;
end.

Math is like love. A simple idea but it can get complicated.

Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*

Profil

Re: [Zadatak] Kutije

^{17.07.2005. u 11:14 - pre 236 meseci}

Ok, hvala ti!

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*

Profil

Re: [Zadatak] Kutije

^{18.07.2005. u 00:10 - pre 236 meseci}

Uhmm... pa manje vishe sam ukapirao reshenje ... u svakom sluchaju, ne verujem da bi se ovoga sam setio ... mada, ja sam najduzi podniz radio drugachije od ideja koja se ovde primenjuje, tako da je moguce to razlog ... :)
Lep zadatak, u svakom sluchaju ...

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: [Zadatak] Kutije

^{18.07.2005. u 00:21 - pre 236 meseci}

Pa da bi zadatak resio u

moras da trazis NRP (najduzi rastuci podniz) na ovaj nacin, koji ne rekonstrusise sam NRP... Neznam kako bi to drugacije uradio?! (slazemo se da je rekonstrukcija u

koja ti ovde nije potrebna)...

Math is like love. A simple idea but it can get complicated.

Odgovor na temu