|
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ć
|
Sponzori
|
|
|
zadatak: Ostrva
|
Kapetan Mika ima zadatak da napravi mapu arhipelaga koji se sastoji od n ostrva. Na
raspolaganju ima mali brod i hrabru posadu. On se odlučio za sledeću taktiku: za svaka
dva različita ostrva A i B , on će se pravolinijski uputiti od ostrva
A do ostrva B, izbrojaće koliko se ostalih ostrva nalazi sa desne strane putanje broda i pribeležiće
to. Ostrvo se nalazi sa desne strane putanje ako pripada desnoj poluravni (polumoru)
određenoj pravom AB. Smer je, naravno, bitan - ako je neko ostrvo sa desne strane putanje
od A do B, onda je ono sa leve strane putanje od B do A.
Napomenimo da ne postoje tri kolinearna ostrva, tj. pri pomenutim pravolinijskim
putanjama između dva ostrva brod nikad neće naleteti na neko treće ostrvo. Takođe
napomenimo da nije poznato kako kapetanove beleške pomažu pri pravljenju mape.
Posle svih putovanja, kapetan Mika se zagledao u svoje beleške i pokušao na osnovu njih
da odgovori na k pitanja tipa: "kada sam putovao od ostrva A do ostrva B,
da li mi je ostrvo C bilo sa desne strane?", ali nije uspeo. Možete li mu pomoći?
Ulaz.
(Ulazni podaci se učitavaju iz datoteke ostrva.in.)
U prvom redu ulazne datoteke
nalazi se jedan prirodan broj n - broj ostrva u arhipelagu. Zatim se u narednih n redova
(3 ≤ n ≤ 200) nalaze po n celih brojeva - opis matrice a koja predstavlja Mikine beleške.
aij označava broj ostrva sa desne strane pri putovanju od ostrva i do ostrva j (ostrva su
numerisana brojevima od 1 do n ). Elementi na glavnoj dijagonali matrice a će uvek biti 0.
U narednom redu ulazne datoteke nalazi se broj k - broj Mikinih upita (1 ≤ k ≤ 105). Najzad,
u sledećih k redova se nalaze po 3 cela broja A , B i C (1 ≤ A, B, C ≤ n ,
A ≠B ≠ C ≠ A) koji
predstavljaju pitanje: da li je ostrvo C sa desne strane putanje od ostrva A do ostrva B .
Izlaz.
(Izlazni podaci se ispisuju u datoteku ostrva.out.)
Za svaki od k upita je potrebno
odgovoriti sa ’DA’ ili ’NE’ (bez navodnika), zavisno od toga da li je odgovarajuće ostrvo sa
prave strane. Na pitanja odgovarati u datom redosledu, pri čemu svaki odgovor treba biti
ispisan u posebnom redu.
Primer 1.
ostrva.in
|
|
ostrva.out
|
3
0 1 0
0 0 1
1 0 0
2
1 2 3
1 3 2
|
|
DA
NE
|
Objašnjenje.
Kako se sa desne strane puta od ostrva 1 do ostrva 2 nalazi jedno ostrvo
(a12 = 1) i kako imamo samo 3 ostrva, to ostrvo mora biti ostrvo 3, pa je odgovor na prvo
pitanje potvrdan. Slično, ostrvo 2 se ne može nalaziti sa desne strane puta od ostrva 1
do ostrva 3.
|
|
fajl: ostrva.cpp
|
#include <cstdlib>
#include <cstdio>
#include <memory.h>
const int MaxN = 210;
int n, k;
int a[MaxN][MaxN];
bool sol[MaxN][MaxN][MaxN];
bool mark[MaxN];
int main()
{
freopen("ostrva.in", "r", stdin);
freopen("ostrva.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
}
memset(mark, false, sizeof(mark));
for (int count = 1; count <= n - 2; count++)
{
// nalazenje tacke na konveksnom omotacu
int x = 0;
for (int i = 1; i < n; i++)
{
if (mark[i]) continue;
for (int j = i + 1; j <= n; j++)
if (!mark[j] && a[i][j] == 0)
{
x = i;
break;
}
if (x != 0) break;
}
mark[x] = true;
// racunanje odgovora na sve upite koji sadrze tacku x (i,j,x)
// i izbacivanje tacke x (updateovanje matrice a)
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
if (!mark[i] && !mark[j])
{
bool b = (a[x][i] > a[x][j]);
sol[x][i][j] = sol[i][j][x] = sol[j][x][i] = b;
sol[x][j][i] = sol[j][i][x] = sol[i][x][j] = !b;
if (b)
a[i][j]--;
else
a[j][i]--;
}
}
scanf("%d", &k);
for (int i = 1; i <= k; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%s\n", (sol[a][b][c] ? "DA" : "NE"));
}
return 0;
}
|
|
fajl: ostrva.pas
|
const
MaxN = 210;
VAR
inFile, outFile : text;
n, k, i, j, count, x, y, z : longint;
val : boolean;
a : array[0..MaxN, 0..MaxN] of longint;
sol: array[0..MaxN, 0..MaxN, 0..MaxN] of boolean;
mark : array[0..MaxN] of boolean;
BEGIN
assign(inFile, 'ostrva.in');
assign(outFile, 'ostrva.out');
reset(inFile); rewrite(outFile);
readln(inFile, n);
for i := 1 to n do
for j := 1 to n do
read(inFile, a[i][j]);
fillchar(mark, sizeof(mark), false);
for count := 1 to n - 2 do begin
// nalazenje tacke na konveksnom omotacu
x := 0;
for i := 1 to n - 1 do begin
if (mark[i]) then continue;
for j := i + 1 to n do
if ((NOT mark[j]) AND (a[i][j] = 0)) then begin
x := i;
break;
end;
if (x <> 0) then break;
end;
mark[x] := true;
// racunanje odgovora na sve upite koji sadrze tacku x (i,j,x)
// i izbacivanje tacke x (updateovanje matrice a)
for i := 1 to n - 1 do
for j := i + 1 to n do
if ((NOT mark[i]) AND (NOT mark[j])) then begin
val := (a[x][i] > a[x][j]);
sol[x][i][j] := val; sol[i][j][x] := val; sol[j][x][i] := val;
sol[x][j][i] := NOT val; sol[j][i][x] := NOT val; sol[i][x][j] := NOT val;
if (val) then
a[i][j] := a[i][j] - 1
else
a[j][i] := a[j][i] - 1;
end;
end;
readln(inFile, k);
for i := 1 to k do begin
read(inFile, x, y, z);
if (sol[x][y][z]) then
writeln(outFile, 'DA')
else
writeln(outFile, 'NE');
end;
close(inFile);
close(outFile);
END.
|
|
|