|
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.
|
logo by Igor Antolović
|
|
|
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 pi ≥ r, 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 ≤ i ≤ n) 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 k ≤ m 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 (k ≤ m ≤ n). 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.
|
|
|