|
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: Knjižica
|
Kići i Ćiki su već dugo najbolji drugari. Nažalost,
Kići je izgubio pamćenje i Ćiki je odlučio da mu
spremi specijalno iznenađenje kako bi mu pomogao da se seti
svega. On je sve njihove zajedničke uspomene zapisivao u jednu
zelenu sveskicu, i sada on želi da od toga napravi jednu od
onih knjižica gde je čitaocu povremeno ponuđeno da
izabere kako će se priča nastaviti. Na kraju svakog dela
priče, čitalac bira da li će nastaviti onako kako bi
Kići nastavio ili onako kako bi Ćiki nastavio, s tim
što se sa nekih delova ne može nastaviti dalje (na njima se
priča završava), a na pojedinim delovima postoji samo jedna
mogućnost da se nastavi priča (nekad je to Ćikijeva a
nekad Kićijeva ideja). U toku jednog čitanja ne možemo
dva puta da se nađemo na istom delu i do svakog dela priče
se može stići na jedinstven način. Svaki deo priče se
nalazi na po jednoj stranici.
Delovi ove priče su numerisani brojevima od 1 do n (gde je
n broj delova priče) ali pošto je Ćiki perfekcionista
on želi da ih renumeriše (opet brojevima od 1 do n).
Ćiki je uvek voleo male stvari, a Kići velike, pa zato
Ćiki želi da: ako sa dela priče koji je na stranici a
prelazimo na deo priče koji je na stranici b važi:
- Ako smo izabrali ono što bi Kići uradio, onda je b > a, i redni broj svake
stranice do koje ćemo kasnije u toku čitanja priče moći da dođemo je veći od a
- Ako smo izabrali ono što bi Ćiki uradio, onda je b < a, i
redni broj svake stranice do koje ćemo kasnije u toku čitanja priče moći da dođemo je manji od a
Pomozite Ćikiju da složi stranice kako bi što pre mogao
da da knjižicu Kićiju (Ćiki je sjajan programer, ali je
trenutno previše tužan da bi razmišljao o ovom problemu).
Ulaz.
(Ulazni podaci se nalaze u datoteci knjizica.in)
U prvom redu nalaze se tri broja n, k i c
(1 ≤ n ≤ 250.000, 1 ≤ k, c ≤
n). Zatim se u narednih k redova nalaze po dva broja, a i
b, koji označavaju da sa dela priče obeleženog brojem
a ako poslušamo Kićija prelazimo na deo obeležen
brojem b. Slično se u narednih c redova nalaze po dva
broja, a i b, koji označavaju da sa dela priče
obeleženog brojem a ako poslušamo Ćikija prelazimo na
deo obeležen brojem b. Pre renumerisanja početak priče
je na delu obeleženom brojem 1 (obratite pažnju da posle
renumeracije ne mora biti).
Izlaz.
(Izlazne podatke upisati u datoteku knjizica.out) Treba da se sastoji od n redova - u i-tom
redu nalazi se broj stranice na kojoj će se deo priče
obeležen brojem i nalaziti posle renumeracije. Ako postoji
više rešenja, štampati bilo koje.
Primer 1.
knjizica.in
|
|
knjizica.out
|
7 3 3
3 6
1 3
5 7
1 2
3 5
2 4
|
|
3
2
6
1
4
7
5
|
|
|
fajl: knjizica.cpp
|
#include <stdio.h>
#include <stdlib.h>
const int maxN = 500000;
int levi[maxN + 1];
int desni[maxN + 1];
int strana[maxN + 1];
int brojac;
void numerisi(int deo) {
if (deo == -1) return;
numerisi(levi[deo]);
brojac++;
strana[deo] = brojac;
numerisi(desni[deo]);
}
int main(){
int n, k, c, a, b;
freopen("knjizica.in", "r", stdin);
scanf("%d %d %d",&n, &k, &c);
for (int i = 1; i <= n; i++) {
levi[i] = -1;
desni[i] = -1;
}
for (int i = 1; i <= k; i++) {
scanf("%d %d", &a, &b);
desni[a] = b;
}
for (int i = 1; i <= c; i++) {
scanf("%d %d", &a, &b);
levi[a] = b;
}
brojac = 0;
numerisi(1);
freopen("knjizica.out", "w", stdout);
for (int i = 1; i <= n; i++)
printf("%d\n", strana[i]);
return 0;
}
|
|
|