TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

camci.pas    1,596 b      izvorni kod rešenja
camci2.pas    1,858 b      izvorni kod rešenja
camci.tests.rar    153,133 b      test primeri

zadatak: Čamci

Stanovnici jednog malog sela bave se ribarenjem i programiranjem. Nakon završenog ribolova, ribari svoje čamce ostavljaju duž jedne obale uskog kanala. Svaki ribar ima jedan čamac i sopstveni stubić negde duž kanala koji mu služi za privezivanje čamca, pri čemu sme da priveže svoj čamac isključivo za svoj stubić. Čamci moraju biti ostavljeni tako da svaki čamac bude tačno uz svoj stubić, što znači da stubić mora biti negde neposredno pored čamca, tj. između dva kraja čamca (dozvoljeno je i da stubić bude neposredno pored nekog kraja čamca). Pošto je kanal uzan, najviše jedan čamac se može nalaziti na svakom poprečnom preseku kanala, odnosno svi čamci moraju biti privezani neposredno do obale. Čamci se mogu dodirivati svojim krajevima.

Zbog ovakvog vezivanja čamaca nije obavezno moguće da čamci svih ribara budu vezani istovremeno. Zato su ribari zamolili svoje prijatelje programere da im izračunaju koliko najviše čamaca može istovremeno biti vezano. Međutim, programerima je ovo bio pretežak zadatak, pa su i oni počeli da se bave ribarenjem, a zadatak su prepustili vama.

dozvoljena vezivanja          nedozvoljena vezivanja

Ulaz:

Ulazni podaci učitavaju se iz tekstualnog fajla camci.in. U prvom redu zapisan je samo broj ribara n (1 ≤ n ≤ 10000). U svakom od narednih n redova zapisani su prirodni brojevi li i pi (1 ≤ li, pi ≤ 100000) razdvojeni jednim razmakom, koji redom označavaju dužinu čamca i položaj (koordinatu) stubića i-tog ribara. Nijedna dva stubića nemaju istu koordinatu.

Izlaz:

U izlazni tekstualni fajl camci.out treba upisati samo jedan broj - koliko najviše čamaca može biti privezano istovremeno.

Primer:

camci.in      camci.out
7
5 9
2 17
6 10	
3 11
2 16
4 13
5 6
        
5

Objašnjenje:

Najviše je moguće da 5 čamaca bude istovremeno vezano, na primer čamci 1, 2, 4, 5 i 7.

rešenje


Zadatak je moguće rešiti na više načina od kojih je najefikasniji sledeći gramzivi algoritam:

Tokom algoritma održavamo skup privezanih čamaca S. Jedan po jedan čamac pokušavamo da ubacimo u taj skup idući sa leva na desno po koordinatama stubića. Na početku skup S sadrži samo najlevlji čamac privezan maksimalno u levo. Neka su l i r koordinate levog i desnog kraja poslednjeg ubačenog čamca, i neka trenutno posmatramo čamac opisan parom (li, pi). Ako je pir, tada ubacujemo i-ti čamac u skup S i privezujemo ga tako da ga postavimo što je moguće više levo. Ako je pi < r, tada proveravamo da li važi li < r - l i ako jeste izbacujemo poslednji čamac iz S, i umesto njega u S ubacujemo i-ti čamac, takođe što je moguće više levo, a ako ne važi, i-ti čamac preskačemo.

Indukcijom se može pokazati da za svako i (1 ≤ in) važi sledeće tvrđenje: Nakon i koraka ovog algoritma u skupu S nalazi se najveći podskup skupa koji čine prvih i čamaca, koji se mogu istovremeno privezati, i to onaj podskup za koji važi da je desni kraj najdesnijeg čamca iz tog podskupa maksimalno levo.

Iz ovog tvrđenja je jasno da se nakon n koraka ovog algoritma dobija traženo rešenje.

Pseudokod

Sortirati niz parova (l[i], p[i]) tako da bude rastući po p[i]

m = 1
r = p1
for i = 2 to n
	if p[i] ≥ r
		l = r
		r = max(p[i], r + l[i])
		inc(m)
	else
		r = min(r, max(p[i], l + l[i])

m je traženi maksimalan broj čamaca

Vremenska složenost ovog algoritma je O(n lg n) u čemu dominira vreme potrebno za sortiranje.

Zadatak je takođe moguće rešiti dinamičkim programiranjem na nekoliko načina.

Kao i u prethodnom rešenju, najpre sortirajmo parove (li, pi) da budu rastući po pi. Za km posmatrajmo sve skupove koji sadrže tačno k ispravno privezanih čamaca izabranih od prvih m čamaca. Uočimo sve koordinate desnih krajeva najdesnijih čamaca iz tih skupova. Sa S(m, k) označimo najlevlju od svih tih koordinata. Ako ne postoji ni jedan takav skup, onda neka je S(m, k) = ∞.

Da bismo izračunali S(m, k) moramo da razmotrimo nekoliko mogućnosti. Ako isključimo mogućnost da m-ti čamac bude privezan, tada je S(m, k) = S(m-1, k). Da bi m-ti čamac uopšte bio privezan potrebno je da se njegov stubić ne nalazi pored nekog drugog čamca, tj. mora da važi S(m-1, k-1) ≤ pm. Ako to važi, m-ti čamac privezujemo što je moguće više levo. Ako je S(m-1, k-1) < pm - lm tada on neće dodirivati prethodni čamac i važiće S(m, k) = pm. Suprotno, ako je S(m-1, k-1) ≥ pm - lm tada će on dodirivati prethodni čamac i važiće S(m, k) = S(m-1, k-1) + lm. Konačno možemo da zapišemo formulu:

        S(m, k) = min(S(m-1, k), R)

gde je R =

              ako je     pm     <     S(m-1, k-1)         
S(m-1, k-1) + lm ako je pm - lm S(m-1, k-1) pm
pm ako je S(m-1, k-1) < pm - lm

Početne vrednosti su S(m, 0) = -∞, jer ne postoji najlevlja tačka ako nema ni jednog čamca.

Željeno rešenje (najveći broj čamaca koji se mogu istovremeno privezati) je najveće k za koje S(n, k) nije ∞ (jer S(n, k) = ∞ znači da istovremeno vezivanje k čamaca nije moguće).

Sada je lako napisati program koji izračunava S(m, k) za sve m i k (kmn). Iako je S dvodimenzionalno, možemo koristiti samo jednodimenzionalan niz za S jer je za izračunavanje S(m, k) dovoljno znati samo vrednosti iz m-1-og reda (jer da bismo dobili S(m, k) koristimo samo S(m-1, k-1) i S(m-1, k)).

Pseudokod

Sortirati niz parova (l[i], p[i]) tako da bude rastući po p[i]

S[0] = -inf
S[1] = inf
m = 0

for i = 1 to n
	for j = m+1 downto 1
		if S[j-1] ≤ p[i]
			r = max(p[i], S[j-1] + l[i])
		else
			r = inf
		S[j] = min(S[j], r)
	if S[m+1] < inf
		inc(m)
	S[m+1] = inf

m je traženi maksimalan broj čamaca

Vremenska složenost ovog algoritma je O(n2).

Ostala rešenja dinamičkim programiranjem se dobijaju ako se koristi činjenica da su koordinate stubića i dužine čamaca celi brojevi unutar relativno malog intervala.

fajl: camci.pas
const
  fin = 'camci.in';
  fout = 'camci.out';
  maxN = 10000;

type
  TBoat = record
            p, l : Longint;
          end;

var
  n, m : Integer;
  c : array[1..maxN] of TBoat;



procedure ReadInput;
var
  f : Text;
  i : Integer;
begin
  Assign(f, fin);
  Reset(f);
  Readln(f, n);
  for i := 1 to n do
    Readln(f, c[i].l, c[i].p);
  Close(f);
end;


procedure Sort;
var
  tmp : TBoat;

  procedure QuickSort(l, r : Integer);
  var
    i, j : Integer;
    p : Longint;
  begin
    i := l;
    j := r;
    p := c[(l + r) div 2].p;
    repeat
      while c[i].p < p do inc(i);
      while p < c[j].p do dec(j);
      if i <= j then
      begin
        tmp := c[i];
        c[i] := c[j];
        c[j] := tmp;
        inc(i);
        dec(j);
      end;
    until i > j;
    if l < j then QuickSort(l, j);
    if i < r then QuickSort(i, r);
  end;

begin
  QuickSort(1, n);
end;


function Max(a, b : Longint) : Longint;
begin
  if a > b then
    Max := a
  else
    Max := b
end;


procedure Solve;
var
  i : Integer;
  l, r, t : Longint;
begin
  Sort;

  m := 1;
  r := c[1].p;

  for i := 2 to n do
    if c[i].p >= r then
    begin
      l := r;
      r := Max(c[i].p, r + c[i].l);
      inc(m);
    end else
    begin
      t := Max(c[i].p, l + c[i].l);
      if t < r then
        r := t;
    end;
end;


procedure WriteOutput;
var
  f : Text;
begin
  Assign(f, fout);
  Rewrite(f);
  Writeln(f, m);
  Close(f);
end;




begin
  ReadInput;
  Solve;
  WriteOutput;
end.
fajl: camci2.pas
const
  fin = 'camci.in';
  fout = 'camci.out';
  maxN = 10000;
  inf = 999999999;

type
  TBoat = record
            p, l : Longint;
          end;

var
  n, m : Integer;
  c : array[1..maxN] of TBoat;



procedure ReadInput;
var
  f : Text;
  i : Integer;
begin
  Assign(f, fin);
  Reset(f);
  Readln(f, n);
  for i := 1 to n do
    Readln(f, c[i].l, c[i].p);
  Close(f);
end;


procedure Sort;
var
  tmp : TBoat;

  procedure QuickSort(l, r : Integer);
  var
    i, j : Integer;
    p : Longint;
  begin
    i := l;
    j := r;
    p := c[(l + r) div 2].p;
    repeat
      while c[i].p < p do inc(i);
      while p < c[j].p do dec(j);
      if i <= j then
      begin
        tmp := c[i];
        c[i] := c[j];
        c[j] := tmp;
        inc(i);
        dec(j);
      end;
    until i > j;
    if l < j then QuickSort(l, j);
    if i < r then QuickSort(i, r);
  end;

begin
  QuickSort(1, n);
end;


function Min(a, b : Longint) : Longint;
begin
  if a < b then
    Min := a
  else
    Min := b
end;


function Max(a, b : Longint) : Longint;
begin
  if a > b then
    Max := a
  else
    Max := b
end;


procedure Solve;
var
  i, j, k : Integer;
  s : array[0..MaxN+1] of Longint;
  r : Longint;
begin
  Sort;

  s[0] := -inf;
  s[1] := inf;
  m := 0;

  for i := 1 to n do
  begin
    for j := m+1 downto 1 do
    begin
      if s[j-1] <= c[i].p then
        r := Max(c[i].p, s[j-1] + c[i].l)
      else
        r := inf;

      s[j] := Min(s[j], r);
    end;

    if s[m+1] < inf then
    begin
      inc(m);
      s[m+1] := inf;
    end;
  end;
end;


procedure WriteOutput;
var
  f : Text;
begin
  Assign(f, fout);
  Rewrite(f);
  Writeln(f, m);
  Close(f);
end;




begin
  ReadInput;
  Solve;
  WriteOutput;
end.