|
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: Loto
|
U zemlji Srećiji zavladala je nova pošast – nagradna igra na sreću Loto. Pravila ove igre su sledeća: iz bubnja koji sadrži n kuglica numerisanih brojevima od 0 do n-1 sve kuglice se izvlače nekim redosledom i pobednik je onaj koji pogodi tačan redosled kuglica. Bubanj je oblika horizontalno postavljene kružne ploče na kojoj se nalaze kuglice Iznos nagrade koja se dodeljuje pobedniku računa se kao zbir brojeva oblika ai*10000n-i, gde ai označava broj kuglice koja je izašla i-ta po redu.
Prošlo je već mnogo vremena od kada je Loto startovao a još se nije pojavio nijedan srećni dobitnik, i to je nagnalo ljude da počnu da sumnjaju u verodostojnost igre. Međutim, dok se ostali samo žale kako je sve to namešteno, profesor Đurić, stari vuk igara na sreću, je izračunao da je iznos eventualnog dobitka veći nego što bi ga koštala uplata svih mogućih kombinacija, pa je odlučio da na taj način zaradi. Nestrpljivo iščekujući dan kada će konačno biti dodeljena premija, možete zamisliti naše zaprepašćenje kada su u naše prostorije banuli predstavnici organizatora ove igre i rekli nam da je sve zaista namešteno (1:0 za narod), i da nas mole, pošto na sledećem izvlačenju svakako moraju da dodele premiju (1:0 za profesora Đurića), da im pomognemo da iznos nagrade bude što manji.
Loto se namešta na sledeći način: ispod bubnja, paralelno sa njegovom ravni, nalazi se jak magnet u obliku šipke, koji se može postaviti u proizvoljan položaj. U tačno određenom momentu magnet se aktivira što uzrokuje da se sve kuglice momentalno prilepe za njega (kuglica na magnet doleće pod pravim uglom) i u tom redosledu izađu iz bubnja.
Naše zaprepašćenje još uvek traje, a pošto nismo sigurni ni koliko je sve to moralno, odlučili smo da problem predamo vama – odredite kombinaciju koja će organizatore koštati što manje.
Ulaz:
U prvoj liniji ulaznog fajla loto.in se nalazi prirodan broj n (1 ≤ n ≤ 3000), broj kuglica. U narednih n linija se nalaze celi brojevi xi, yi razdvojeni prazninom (-15000 ≤ xi, yi ≤ 15000), koordinate kuglice i u momentu uključivanja magneta. Kuglice su opisane redom, počev od kuglice sa oznakom 0, do kuglice sa oznakom n-1.
Izlaz:
U n linija izlaznog fajla loto.out upisati brojeve kuglica u redosledu u kom izlaze pri najpovoljnijem položaju magneta, tako da se u i-tom redu nalazi broj kuglice koja izlazi i-ta po redu.
Primer:
loto.in
|
|
loto.out
|
5
1 3
0 4
4 4
0 0
4 0
|
|
1
0
2
3
4
|
Objašnjenje
Minimalnu vrednost glavnog dobitka postići ćemo ako magnet postavimo kao na slici. Glavni dobitak u tom slučaju iznosi: 1∙100004 + 0∙100003 + 2∙100002 + 3∙10000 + 4
|
|
fajl: loto.pas
|
const
fin = 'loto.in';
fout = 'loto.out';
MaxN = 3000;
type
TVector = record
x, y : Longint;
id : Integer;
end;
var
n : Integer;
p : array[0..MaxN] of TVector;
min : array[1..MaxN] of Integer;
function Compare(const a, b : TVector) : Longint;
begin
if a.x <> b.x then
Compare := a.x - b.x
else
Compare := a.y - b.y;
end;
function Prod(const a, b : TVector) : Shortint;
var
p : Longint;
begin
p := a.x*b.y - a.y*b.x;
if p < 0 then
Prod := -1
else
if p > 0 then
Prod := 1
else
if (a.x*b.x > 0) or (a.y*b.y > 0) then
Prod := 0
else
Prod := 2;
end;
function Sub(const a, b : TVector) : TVector;
var
c : TVector;
begin
c.x := a.x - b.x;
c.y := a.y - b.y;
Sub := c;
end;
function Perp(const a : TVector) : TVector;
var
c : TVector;
begin
c.x := -a.y;
c.y := a.x;
Perp := c;
end;
var
m, t : TVector;
procedure Sort(l, r : Integer);
var
i, j : Integer;
begin
i := l;
j := r;
m := p[(l + r) div 2];
repeat
while Compare(p[i], m) < 0 do Inc(i);
while Compare(p[j], m) > 0 do Dec(j);
if i <= j then
begin
t := p[i];
p[i] := p[j];
p[j] := t;
inc(i);
dec(j);
end;
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r);
end;
procedure Solve;
var
k, i, j : Integer;
m, mc : Integer;
c : array[0..MaxN+1] of Integer;
cn, d : Integer;
boundL, boundH : TVector;
t1, t2 : TVector;
valid : Boolean;
begin
Sort(1, n);
for k := n downto 2 do
begin
// nalazenje konveksnog omotaca (tacke su vec sortirane)
cn := 1;
c[1] := 1;
d := 1;
for i := 2 to 2*k-1 do
begin
j := k - Abs(k - i);
while (cn > d) and (Prod(Sub(p[c[cn]], p[c[cn-1]]), Sub(p[j], p[c[cn]])) <= 0) do
Dec(cn);
Inc(cn);
c[cn] := j;
if i = k then d := cn;
end;
dec(cn);
c[0] := c[cn];
// nalazenje dozvoljene tacke na konveksnom omotacu sa najmanjom oznakom
m := 0;
p[0].id := n + 1;
for i := 1 to cn do
begin
if (k = n) then
valid := true
else
begin
t1 := Perp(Sub(p[c[i]], p[c[i-1]]));
t2 := Perp(Sub(p[c[i+1]], p[c[i]]));
if Prod(boundL, t1) < 0 then
valid := Prod(boundL, t2) = 1
else
valid := Prod(t1, boundH) > 0;
end;
if valid and (p[c[i]].id < p[m].id) then
begin
m := c[i];
mc := i;
end;
end;
min[n-k+1] := p[m].id;
// suzavamo dozvoljeni interval pravaca
t1 := Perp(Sub(p[c[mc]], p[c[mc-1]]));
t2 := Perp(Sub(p[c[mc+1]], p[c[mc]]));
if (k = n) or (Prod(t2, boundH) > 0) then boundH := t2;
if (k = n) or (Prod(t1, boundL) < 0) then boundL := t1;
// izbacivanje tacke m iz daljeg razmatranja (tacke ostaju sortirane)
for i := m to k-1 do
p[i] := p[i+1];
end;
min[n] := p[1].id;
end;
procedure ReadInput;
var
f : Text;
i : Integer;
begin
Assign(f, fin);
Reset(f);
Readln(f, n);
for i := 1 to n do
begin
Readln(f, p[i].x, p[i].y);
p[i].id := i - 1;
end;
Close(f);
end;
procedure WriteOutput;
var
f : Text;
i : Integer;
begin
Assign(f, fout);
Rewrite(f);
for i := 1 to n do
Writeln(f, min[i]);
Close(f);
end;
begin
ReadInput;
Solve;
WriteOutput;
end.
|
|
|