|
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: Atomi
|
Pošto je Draganče uspešno rešio sve zadatke koje mu je
profesor Đurić zadao, matematika i programiranje su mu
postali dosadni. Zato je odlučio da se malo za promenu posvetio
hemiji. Pošto je svu potrebnu teoriju brzo savladao, rešio je da
isproba kako sve to radi u praksi, pa je kupio spravu koja može
da sastavlja jedinjenja po želji korisnika. Unutar sprave se
nalazi traka koja je izdeljena na redom numerisana polja od 1 do
N, i korisnik može da postavi atom na neko polje ili da ga
ukloni. Na jednom polju trake može da se nalazi samo jedan atom.
Ukoliko se dva atoma nalaze na susednim poljima, oni su spojeni.
Međutim, ono što sprava nema je provera stabilnosti jedinjenja.
Naravno, Dragančetu to ne stvara problem, jer sve što mu je
potrebno da bi izračunao stabilnost je da zna koliko je dugačak
najduži lanac na nekom delu trake (lanac čine uzastopno povezani
atomi). Kako broj atoma može biti veoma velik, a Draganče ne
želi da provede ceo dan u brojanju atoma, zamolio je vas da mu
pomognete u određivanju dužine najdužeg lanca na delu trake
koji ga interesuje.
Ulaz:
(Ulazni podaci se nalaze u datoteci atomi.in) U prvom redu ulazne datoteke se nalaze dva broja,
N i M. Broj
N predstavlja dužinu trake, a M ukupan broj operacija. U
narednih M linija nalaze se opisi operacija koje Draganče
vrši, a operacije mogu biti:
- 0 i - (1 ≤ i ≤ N) uklanja atom sa polja i (ukoliko je polje već prazno, ništa se ne dešava)
- 1 i - (1 ≤ i ≤ N) postavlja atom na polje i (ukoliko se atom već nalazi na tom polju, ništa se ne dešava)
- 2 a b - (1 ≤ a ≤ b ≤ N) Draganče se pita kolika je dužina najdužeg lanca ako
se posmatraju samo atomi koji se nalaze na intervalu [a,b].
Izlaz:
(Izlazne podatke upisati u datoteku atomi.out) Za svako pitanje
(upit tipa "2 a b") u nov red datoteke treba ispisati odgovor.
Ograničenja:
- 1 ≤ N ≤ 1000000
- 1 ≤ M ≤ 500000
- vremensko ograničenje za izvršavanje programa je 1 s
- memorijsko ograničenje za izvršavanje programa je 32 MB
Primer 1:
atomi.in
|
|
atomi.out
|
8 5
1 3
1 5
2 3 5
1 4
2 1 8
|
|
1
3
|
Objašnjenje:
Posle druge operacije, traka izgleda ovako:
00X0X000
pa je odgovor 1.
Posle četvrte operacije traka izgleda ovako:
00XXX000
pa je odgovor 3.
Primer 2:
atomi.in
|
|
atomi.out
|
8 8
1 1
1 2
1 3
1 4
2 2 5
0 2
1 7
2 1 3
|
|
3
1
|
Objašnjenje:
Posle četvrte operacije traka izgleda ovako:
XXXX0000
ali pošto nas u petom pitanju zanima samo interval od polja 2 do polja 5,
odgovor je 3.
Posle sedme operacije traka izgleda ovako :
X0XX00X0
pa je odgovor na osmo pitanje 1.
Napomena:
U 60% test primera će važiti M ≤ 1000.
|
|
rešenje
|
1. O(M * N) - 60 poena
Najjednostavnije rešenje je da se u nizu pamti gde postoji atom a gde ne. Postavljanje
i uklanjanje se vrši u O(1), dok je za odgovaranje na pitanje potrebno proći
kroz ceo interval, što u najgorem slučaju može biti O(N).
2. O(M * sqrt(N)) - 80 poena
Celu traku ćemo izdeliti na segmente, tako da je dužina svakog segmenta sqrt(N)
(ukoliko traka nije dovoljno dugačka, proširićemo je sa najviše sqrt(N)
- 1 polja). Dakle, imamo sqrt(N) segmenata i svaki je dužine sqrt(N).
Za svaki segment ćemo pamtiti tri informacije : koliko je dugačak lanac koji
sadrži prvo polje segmenta, koliko je dugačak lanac koji sadrži poslednje polje
segmenta (naravno, ukoliko se na tim mestima ne nalazi atom, dužina lanca je
0), i koliko je dugačak najduži lanac na celom intervalu. Neka Draganče zeli
najduži lanac na intervalu [A,B]. Ukoliko A i B pripadaju
istom segmentu, odgovor ćemo naći tako što ćemo proći kroz ceo interval. Zbog
dužine segmenta, možemo imati najviše sqrt(N) iteracija. Pretpostavimo
sada da A i B pripadaju segmentima S1 i S2. Na
intervalu [A,poslednje_polje(S1)] ćemo naći najduži lanac, kao i
dužinu lanca koji sadrži poslednje polje intervala S1 (nazvaćemo tu dužinu
L), tako što ćemo proći kroz sva polja intervala. Dalje se nećemo
kretati kroz svako polje, već ćemo samo posmatrati segmente u celini. Na dužinu
L možemo nadovezati vrednost levo[S1+1]. Ukoliko je ceo segment S1+1
pokriven atomima, možemo nastaviti da nadovezujemo levo[S1+2], itd. U
momentu kada dođemo do toga da segment S1 + k nije ceo pokriven atomima,
L dobija vrednost desno[S1 + k], i nastavljamo dalje na isti način.
Ovo kretanje po segmentima prekidamo kada dođemo do S2. Tada na dužinu L
nadovežemo lanac koji sadrži polje prvo_polje(S2) i nalazi se u
intervalu [prvo_polje(S2), B]. Takođe, na intervalu [prvo_polje(S2),B],
nađemo i dužinu najdužeg lanca. Te dve stvari nalazimo tako što prođemo kroz
svaki element intervala. Rešenje ce biti najveća dužina od svih posmatranih.
Prilikom postavljanja i uklanjanja atoma, da bi ažurirali informacije na
segmentu, potrebno je da prođemo kroz svaki element tog segmenta, pa je
složenost te dve operacije O(sqrt(N)). Kod odgovaranja na pitanje, u
najgorem slučaju možemo posetiti sve elemente segmenta kome pripada A
(njih ima sqrt(N)), sve segmente između segmenata kome pripadaju A
i B (njih ima sqrt(N)-2), i sve elemente segmenta kome pripada B
(njih ima sqrt(N)), pa je ukupna složenost O(sqrt(N)).
3. O(M * log N) - 100 poena
Prvo, proširićemo traku tako da broj elemenata bude stepen broja 2. Konstruisaćemo
kompletno binarno stablo koje ima N listova (samim tim i dubinu log N).
Svakom čvoru stabla ćemo pridružiti određen interval, i to na sledeći način :
korenu stabla pridružujemo interval [1,N], njegovom levom sinu [1,N/2],
a desnom [N/2 + 1, N], itd. Prema tome, listovima će odgovarati
tačno jedan element, tj interval oblika [k,k]. Dalje, u svakom čvoru
ćemo pamtiti još 4 informacije : koliko je dugačak lanac koji sadrži prvi
element intervala koji odgovara tom čvoru, koliko je dugačak lanac koji sadrži
poslednji element, kolika je dužina najdužeg lanca na tom intervalu, i da li je
ceo interval pokriven atomima. Ažuriranje informacija posle
uklanjanja/postavljanja atoma se vrši na sledeći način : u stablu nađemo list
koji odgovara polju čije stanje menjamo (to možemo uraditi tako što ćemo se, počevši
od korena, uvek kretati ka onom čvoru u čiji interval upada traženo polje). Ukoliko
u to polje stavljamo atom, svim informacijama dodeljujemo vrednost 1, a ukoliko
skidamo atom svim informacijama dodeljujemo vrednost 0. Kada promenimo
informacije lista, to će uticati samo na njegove pretke (zbog načina na koji
smo čvorovima dodeljivali intervale), pa ćemo samo njih posetiti, i to od dole
ka gore (tj od lista ka korenu). Kako je dubina stabla log N, posetićemo
tačno log N čvorova na putu od lista ka korenu. Neka se trenutno
nalazimo u čvoru C, njegov levi sin je L a desni D.
Informacije koje pamtimo u C računamo uz pomoć informacija iz L i
D :
Ako je L.ceo_popunjen onda C.levo = L.levo + D.levo
u suprotnom C.levo = L.levo;
ako je D.ceo_popunjen onda C.desno = D.desno + L.desno
u suprotnom C.desno = D.desno;
C.najveci = max (L.najveci, D.najveci, L.desno + D.levo);
C.ceo_popunjen ako je L.ceo_popunjen i D.ceo_popunjen;
Prilikom traženja najdužeg lanca na datom intervalu konstruisaćemo pomoćno
binarno stablo, koje ce po strukturi biti isto kao već opisano stablo. Traženje
odgovora počinjemo od korena. Ukoliko je traženi interval upravo [1,N],
odgovor već imamo kao informaciju koren.najveći. U suprotnom, rekurzivno
tražimo koji čvorovi su odgovorni za traženi interval u levom i desnom
podstablu. Pokazaćemo šta se radi u levom podstablu (desno podstablo se obrađuje
na isti način): ukoliko smo došli do čvora kome je pridružen interval [p,q],
i važi A ≤ p i q ≤ B, onda informacije iz tog čvora
prepisujemo u novo stablo. U suprotnom, ako važi p ≥ B ili A
≥ q, svim informacijam u čvoru u novom stablu dodeljujemo vrednost 0. Inače,
rekurzivno se spuštamo u levo i desno podstablo, i ponavljamo isti postupak. Po
završetku obrađivanja levog i desnog podstabla, informacije računamo na isti način
kao što smo radili i u prvobitnom stablu (naravno, ovde ne koristimo
informacije prvobitnog stabla, već novog, pomocnog stabla). Na kraju, odgovor
na pitanje koliko je dugačak najduži lanac na intervalu [A,B] će se
nalaziti u informaciji "najveći" u korenu pomoćnog stabla. Složenost
uklanjanja i postavljanja je O(log N). Prilikom traženja najdužeg lanca,
interval [A,B] moze da se pokrije sa najviše log N čvorova, pa
je i složenost O(log N). Prema tome, ukupna složenost je O(M * log N).
|
|
fajl: mn.cpp
|
/*
ZADATAK: atomi
JEZIK: c++
*/
// Atomi, SIO 2007
// Autor zadatka : Rajko Nenadov
/*
resenje nosi 10 poena
vremenska slozenost : O(M * N)
prostorna slozenost : O(N)
*/
#include <iostream>
#include <cstdio>
using namespace std;
const long MaxN = 1000005;
long n, m;
bool postoji[MaxN];
FILE *fin, *fout;
int main(){
fin=fopen("atomi.in","r");
fout=fopen("atomi.out","w");
memset(postoji,0,sizeof(postoji));
fscanf(fin,"%ld %ld",&n,&m);
long op,x,a,b;
for (long k=0; k<m; k++){
fscanf(fin,"%ld",&op);
if (op == 0){
fscanf(fin,"%ld",&x);
postoji[x]=false;
}
else if (op == 1){
fscanf(fin,"%ld",&x);
postoji[x]=true;
}
else{
fscanf(fin,"%ld %ld",&a,&b);
long brojac=0, best=0;
for (long i=a; i<=b; i++){
if (postoji[i]) brojac++;
else{
best=max(best,brojac);
brojac=0;
}
}
best=max(best,brojac);
fprintf(fout,"%ld\n",best);
}
}
fclose(fin); fclose(fout);
return 0;
}
|
|
fajl: msqrtn.cpp
|
/*
ZADATAK: atomi
JEZIK: c++
*/
// Atomi, SIO 2007
// Autor zadatka : Rajko Nenadov
/*
resenje nosi : 70 poena
vremenska slozenost : O(M * sqrt(N))
prostorna slozenost : O(N)
*/
#include <iostream>
#include <cstdio>
using namespace std;
const long MaxN = 1000005;
const long SqrtMaxN = 1005;
long n, m;
bool postoji[MaxN];
long levo[SqrtMaxN], desno[SqrtMaxN], najveci[SqrtMaxN];
long korak;
FILE *fin, *fout;
void update(long x){
long mesto=x/korak;
long nl=0;
for (long i=mesto*korak; postoji[i] && i<(mesto+1)*korak; i++) nl++;
levo[mesto]=nl;
long nd=0;
for (long i=(mesto+1)*korak - 1; postoji[i] && i>=mesto*korak; i--) nd++;
desno[mesto]=nd;
najveci[mesto]=0;
long naj=0;
for (long i=mesto*korak; i<(mesto+1)*korak; i++){
if (postoji[i]) naj++;
else{
najveci[mesto]>?=naj;
naj=0;
}
}
najveci[mesto]>?=naj;
}
void dodaj(long x){
postoji[x]=true;
update(x);
}
void izbaci(long x){
postoji[x]=false;
update(x);
}
long prebroj(long a, long b){
long reta = 0;
long m1 = a/korak, m2= b/korak;
if (m1 == m2){
long brojac = 0;
for (long i=a; i<=b; i++){
if (postoji[i]) brojac++;
else{
reta>?=brojac;
brojac=0;
}
}
reta>?=brojac;
}
else{
long brojac = 0;
for (long i=a; i<(m1 + 1)*korak; i++){
if (postoji[i]) brojac++;
else{
reta>?=brojac;
brojac=0;
}
}
for (long i=m1+1; i<m2; i++){
reta>?=najveci[i];
brojac+=levo[i];
reta>?=brojac;
if (levo[i]!=korak) brojac=desno[i];
}
for (long i=m2*korak; i<=b; i++){
if (postoji[i]) brojac++;
else{
reta>?=brojac;
brojac=0;
}
}
reta>?=brojac;
}
return reta;
}
int main(){
fin=fopen("atomi.in","r");
fout=fopen("atomi.out","w");
memset(postoji,0,sizeof(postoji));
fscanf(fin,"%ld %ld",&n,&m);
while (korak * korak < n) korak++;
long op,x,a,b;
for (long k=0; k<m; k++){
fscanf(fin,"%ld",&op);
if (op == 0){
fscanf(fin,"%ld",&x);
izbaci(x);
}
else if (op == 1){
fscanf(fin,"%ld",&x);
dodaj(x);
}
else{
fscanf(fin,"%ld %ld",&a,&b);
fprintf(fout,"%ld\n",prebroj(a,b));
}
}
fclose(fin); fclose(fout);
return 0;
}
|
|
fajl: mlogn.cpp
|
/*
ZADATAK: atomi
JEZIK: c++
*/
// Atomi, SIO 2007
// Autor zadatka : Rajko Nenadov
/*
resenje nosi : 100 poena
vremenska slozenost : O(M * log N)
prostorna slozenost : O(N)
*/
#include <iostream>
#include <cstdio>
using namespace std;
const long MaxN = 1048576; // 2^20
const long MaxTree = MaxN * 2 + 1;
struct Cvor{
long levo, desno, najveci;
bool ceo;
};
Cvor tree[MaxTree], aux_tree[MaxTree];
long n, upper_n;
long m;
FILE *fin, *fout;
void make_tree(){
for (long i=0; i<MaxTree; i++){
tree[i].levo = 0; tree[i].desno = 0; tree[i].najveci = 0;
tree[i].ceo = false;
}
}
void update(long x){
while (x>=1){
long L1 = tree[2*x].levo, D1 = tree[2*x].desno, N1 = tree[2*x].najveci;
bool C1 = tree[2*x].ceo;
long L2 = tree[2*x + 1].levo, D2 = tree[2*x + 1].desno, N2 = tree[2*x + 1].najveci;
bool C2 = tree[2*x + 1].ceo;
if (C1) tree[x].levo = L1 + L2;
else tree[x].levo = L1;
if (C2) tree[x].desno = D2 + D1;
else tree[x].desno = D2;
tree[x].najveci = max(max(N1,N2), D1 + L2);
tree[x].ceo = C1 && C2;
x/=2;
}
}
void dodaj(long x){
tree[x].levo = 1; tree[x].desno = 1; tree[x].najveci = 1;
tree[x].ceo = true;
update(x/2);
}
void izbaci(long x){
tree[x].levo = 0; tree[x].desno = 0; tree[x].najveci = 0;
tree[x].ceo = false;
update(x/2);
}
void query(long ind, long p, long q, long a, long b){
if (a<=p && q<=b){
aux_tree[ind] = tree[ind];
}
else if (a>q ||p>b){
aux_tree[ind].levo = 0; aux_tree[ind].desno = 0; aux_tree[ind].najveci = 0;
aux_tree[ind].ceo = false;
}
else{
query(ind*2, p, (p+q)/2, a, b);
query(ind*2 + 1, (p+q)/2 + 1, q, a, b);
long L1 = aux_tree[2*ind].levo, D1 = aux_tree[2*ind].desno, N1 = aux_tree[2*ind].najveci;
bool C1 = aux_tree[2*ind].ceo;
long L2 = aux_tree[2*ind + 1].levo, D2 = aux_tree[2*ind + 1].desno, N2 = aux_tree[2*ind + 1].najveci;
bool C2 = aux_tree[2*ind + 1].ceo;
if (C1) aux_tree[ind].levo = L1 + L2;
else aux_tree[ind].levo = L1;
if (C2) aux_tree[ind].desno = D2 + D1;
else aux_tree[ind].desno = D2;
aux_tree[ind].najveci = max(max(N1,N2), D1 + L2);
aux_tree[ind].ceo = C1 && C2;
}
}
int main(){
fin=fopen("atomi.in","r");
fout=fopen("atomi.out","w");
fscanf(fin,"%ld %ld",&n,&m);
upper_n = 1;
while (upper_n<n) upper_n*=2;
make_tree();
long op,x,a,b;
for (long k=0; k<m; k++){
fscanf(fin,"%ld",&op);
if (op == 0){
fscanf(fin,"%ld",&x);
izbaci(upper_n+x-1);
}
else if (op == 1){
fscanf(fin,"%ld",&x);
dodaj(upper_n+x-1);
}
else{
fscanf(fin,"%ld %ld",&a,&b);
query(1,1,upper_n,a,b);
fprintf(fout,"%ld\n",aux_tree[1].najveci);
}
}
fclose(fin); fclose(fout);
return 0;
}
|
|
|