← Back to topics
Topic

Okruzno Takmicenje

r
renovator
263/300 :|
Nije bas kako sam ocekivao , ali sta je tu je ( gaus-100 , zecovi - 100 , filmovi - 63 ) , dakle A-grupa :)

Zeleo bih da cujem i vase rezultate.
t
trobok
je l' moze neko da okaci zadatke
r
renovator
za A grupu (prekucao sam , pa ako ima gresaka , ne zamerite mi ) :
gaus : dati brojevi A i B ( 1<=A<=B<=2^30 ) . Izracunati koliko ima brojeva u intervalu [A,B] ciji je zbir cifara paran broj.

zecovi
Na poljani se nalazi n zeceva i n zecica.Svi oni stoje duz jedne linije tako da svi zecevi gledaju desno niz liniju a sve zecice levo niz liniju.Oni bi zeleli da se podele u parove tako da u svakom paru bude jedna zecica i jedan zec koji mogu medjusobno da se vide.Zec vidi zecicu ako je ona bilo gde desno od njega, a zecica vidi zeca ako je on bilo gde levo od nje.Od vas se trazi da izbrojite na koliko nacina oni to mogu uraditi tako da se svaki zec odnostno zecica nadje u tacno jednom paru.Posto taj broj moze biti veoma veliki , nadjite samo koliki ostatak daje taj broj pri deljenju sa 10007.
ogranicenje : n<=100000.

filmovi
Kako se mali Dragance iz treceg zadatka nije proslavio u matematici i programiranju , roditelji su mu smanjili dzeparac.Zato je on resio da iskoristi svoju veliku kolekciju DVD filmova i odlucio da prodaje filmove po niskim cenama.Svaki film se nalazi na jednom DVD-u, a na Dragancetovom hard disku moze stati najvise k filmova.Procedura rezanja je sledeca: ukoliko se trazeni film nalazi na hard disku, Dragance odmah pocinje sa rezanjem; u suprotnom on mora da nadje odgovarajuci DVD i presnimi ga na hard disk.Ako na disku nema slobodnog prostora, on mora da obrise neki film.Trazenje DVD-a i presnimavanje iziskuje puno vremena, i zato Dragance zeli da smanji taj broj.Na pocetku je njegov disk prazan.

On je napravio spisak porucenih filmova i zna tacno redosled n kupaca koji dolaze da nasnime omiljeni film. Dragance je uspeo da minimizira broj prebacivanja filmova ha HDD.Da li i vi mozete da izracunate koliko ce najmanje puta Dragance ipak morati da presnimi neki film na hard disk?

ogranicenja : 1<=n<=10000 , 1<=k<=500 , memorija 64kB,vrem.og. 1s
p
privatni_detektiv
Administrator je okacio zadatke GAUS i FILMOVI 19. 03. 2007 koje mogu da vide samo MODERATORI.
Sta ocekujes da narod misli o broju tvojih poena na ovom takmicenju,kada si ti moderator?
t
trobok
hmm ne znam sta da kazem, ne verujem da je admin napravio takvu omasku i dozvolio nekom od aktivnih takmicara da vide zadatak pre takmicenja

u svakom slucaju relja bi onda imao sigurno 100 poena na zadatku filmovi,
r
renovator
Ono sto je admin okacio su neki test primeri koje ja , verujte mi , nisam ni gledao jer zaista nisam video
poentu u tome kada ne znam textove zadataka..

Textova zadataka NEMA , i mozete biti sigurni da ni na koji nacin nisam bio u prednosti u odnosu
na ostale takmicare..Na kraju krajeva, kada se okace kodovi , mozete skinuti moje i videti da se ne baziraju na ispisivanju resenja iz test primera ( u slucaju da su isti testovi koriscenji i na takmicenju )..
Nadam se da mi verujete.

Pozdrav,
Relja
t
trobok
a sad o zadacima

prvi je prilicno lak, ali treba biti malo oprezan, pa da se ne zaletis i zakljucis da je pola brojeva parno pola ne :)

mislim da bih znao i drugi da resim, za treci nisam bas siguran
kad razmislim jos malo videcu
r
renovator
treci :
1. ideja : dovedem A do prvog veceg broja tako da je A%10==0 ( i usput dodam koliko ima sa parnim ciframa ) .Zatim dovedem B do prvog manjeg tako da je B%10==0( i usput radim isto ) i onda bi resenje trebalo biti (B-A)/2;naravno, mozda treba paziti na par stvari..ali to je u sustini to..

2. ideja : memoizacija . imamo najvise 10x2x2 stanja...ko hoce nek razmislja.to je ideja koju sam ja iskucao na takmicenju.

cetvrti:
c = 0; res = 1;
for i = 0->s.length()-1 do
if(res==0) break;
if(s[i]=='>')++c;
else res = (res*c)%10007 , c=c-1;

peti:
za vreme takmicenja nisam bas bio nacisto sa ovim zadatkom..Imao sam neku ideju koja je, eto prosla za 63 poena, ali necu je izlagati posto nije skroz tacna..

Inace, mora malo da se opravdam :) ...Radio sam takmicenje sa malo visom temperaturom zato sto sam debil :(.
r
renovator
ljudi, zasto se ne javljate !?
nestrpljiv sam da cujem rezultate :)
t
trobok
ako te bas tako zanimaju
evo iz bg-a

http://www.rg.edu.yu/Takmicenja/OkrMat2007RezA.pdf
http://www.rg.edu.yu/Takmicenja/OkrMat2007RezB.pdf
b
boba5551
[quote author=GHOUST GHOUST link=topic=10263.msg11766#msg11766 date=1175348964]
Administrator je okacio zadatke GAUS i FILMOVI 19. 03. 2007 koje mogu da vide samo MODERATORI.
Sta ocekujes da narod misli o broju tvojih poena na ovom takmicenju,kada si ti moderator?

[/q]

Textovi zadataka nisu bili okaceni!!! Pretpostavljam da je tvoj rezultat los cim osudjujes druge bez osnove...
s
sanja
evo ja cu da se javim
231 poen (70+100+61) :)
Textovi zadataka, test primeri i neki rezultati na [url]http://www.dms.org.yu/takmicenja%202007.htm[/url]
t
trobok
dobro slobo ne moras tako burno da reagujes, decko je samo izrazio svoju sumnju, razjasnili smo da nema razloga da je bude, tako da no frx, dosta o tome

btw relja hvala za prekucavanje zadatak
zaboravio sam da napisem u prethodnim postovima
b
boba5551
[quote author=Bojan Trobok link=topic=10263.msg11775#msg11775 date=1175379357]
dobro slobo ne moras tako burno da reagujes, decko je samo izrazio svoju sumnju, razjasnili smo da nema razloga da je bude, tako da no frx, dosta o tome
[/q]

Reagovanje nije bilo burno, ali je prozivka bila neosonovana. Admin se trudi da pomogne, a ne da "vara".
p
pyost
166 :-\ Uspeo sam da dobijem samo 40 na Gausu :D
s
stratincica
119(100+10+9)...retard nisam uradila drugi(tj cetvrti)...
r
rajkon
E stvarno Iva, bash si retard ;D








salim se, naravno :)
a
adminModerator
Tekstovima zadataka niko nije imao pristupa... posto nisu ni bili okaceni...

Elem.. evo i z-resenja za okruzno takmicenje (kao alternatica officialnim resenjima):

filmovi


#include <iostream>
#include <map>
#include <vector>
#include <queue>

using namespace std;

int main(){

int n, k, c, t=0, s=0, i, mm;
cin >> k >> n;
vector<int> a(k), b(k+1), in(k+1), on;
map<int, int> h; queue<int> q[10002];

for (i=0;i<k;a[i]=h[c]?h[c]:(h[c]=++t), q[a[i]].push(i), i++) cin >> c;

for (i=0;i<k;q[a[i]].pop(),i++) {
if (!in[a[i]] &amp;&amp; s >= n) {
vector<int>::iterator it = on.begin(), id;
for (int max=0;it!=on.end(); max>?=mm, ++it) {
mm = q[*it].empty()?10004:q[*it].front();
id = (mm>max)?it:id;
}
in[*id] = 0;
on.erase(id);
}
if (!in[a[i]]) {
on.push_back(a[i]);
s+= in[a[i]]=1;
}

};
cout << s << endl;

}


biracki spisak


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(){
int n, sol=0; cin >> n;
vector<string> A(n), srtdA;

getline(cin, A[0]);
for (int i=0;i<n;i++) getline(cin, A[i]);

srtdA = A; sort(srtdA.begin(), srtdA.end());

for (int i=0;i<n;i++) sol += srtdA[i] != A[i];

cout << sol;
}


zecovi

#include <iostream>

using namespace std;

int main(){
int z=1, c=1, n; char w;
cin >> n >> w;
for (int i=0;i<2*n;i++,z++,cin>>w) c = c*(w=='>'?1:(--z)--) % 10007;
cout << c << endl;
}


gaus


#include <iostream>

using namespace std;

int e(int n) {return (n==0)?1:((e(n/10)+n%10)%2);}
int q(int n) {return n/2+(n%2)*e(n/10);}

int main(){
int n, m;
cout << q(m+1)-q(n);
}


vlada

#include <iostream>

int t[100], h, N;
int r(int s,int n) {return (n==N)?(s>h):(r(s+t[n],n+1)+r(s,n+1));}

int main(){
std::cin >> N;
for (int i=0;i<N;h+=t[i],t[i]*=2,i++) std::cin>>t[i];
std::cout << r(0,0);
}
r
renovator
@admin
ne znam bas da li bi tvoje resenje za filmove proslo zbog veoma malog memorijskog ogranicenja(64kB)
edit : tacnije, sigurno ne bi jer samo "queue<int> q[10002]" zauszima 400kB..
p
pyost
U sred takmicenja su nam rekli da ignorisemo memorijsko ogranicenje ;)

Inace, sada sam pogledao resenje za Zecova na YUOI, i, ako me secanje dobro sluzi, identicno je kao i moje - iste komande, isti princip, sve isto. A ipak imam samo 70 bodova na tom zadatku ??? Da li je to zato sto ta resenja nisu zvanicna ili sta vec, ali definitivno se zalim, samo da dodjem do svog kôda.

Povodom toga, da li se zna do kada su zalbe?
s
specijalac
koliko ih prolazi na drzavno iz A kategorije (obichno, tj ranijih godina)??
I shta mislite kolika ce biti granica za prolaz?
t
trobok
Iz A kategorije prolazi do 100, iz B oko 60
t
trobok
zjuu ovde je pitanje bilo sa koliko poena ce da se prolazi
ja sam mislio koliko ljudi prolazi :)
prosle godine je i za A i za B crta bila na 100 poena ako se dobro secam, kazu da su nesto tezi zadaci ove godine, tako da ce verovatno biti nesto niza crta
r
renovator
[q]U sred takmicenja su nam rekli da ignorisemo memorijsko ogranicenje[/q]

ee, kakav je to nacin da vi saznate da je mem. ogranicenje zanemareno ,
a mi ( konkretno, takmicari u mom mestu ) ne ! To zaista nije fer..
Koliko sam cuo, i ranije se desavalo da su takmicari iz BG-a ponekada bili "povlasceni".
Naravno, ne kazem to tebi, vec organizatorima ( i ne verujem da ce oni ovo citati, ali cisto da
izrazim nezadovoljstvo )..
Takodje, nije mi jasno zasto je uopste to ogranicenje stajalo obzirom na to da je zvanicno resenje
memorijski zahtevnije..

Sad sta je tu je...
s
specijalac
Koji sve okruzi postoje na informatici??

Bio sam na dms.org.yu i tamo su samo NIS, NS, BG..? da li je to sve... ili? znam da ima josh najmanje Kraljevo i Krushevac

Proshle godine sam bio 2. razred tako da nisam bio puno ambiciozan, shto se takm tiche ali sam video da je na drzavno (republichko) takmichenje proshlo 88 ljudi?? :o

Da li to znachi da ce ove godine prolaznost biti negde oko 50 i neshto bodova, jer nema dovoljno ljudi sa vishe...?

P.S. sve shto govorim vezano je za A kategoriju.
s
specijalac
Ako mozesh Relja poshalji vashu listu za A kategoriju?
ti si iz Krushevca??

pozdravi
r
renovator
[quote author=Igor C-Fogarasi link=topic=10263.msg11788#msg11788 date=1175542680]
Ako mozesh Relja poshalji vashu listu za A kategoriju?
ti si iz Krushevca??

pozdravi
[/q]

Da , ja sam iz Krusevca.
Inace , bilo je samo 4 takmicara, a rezultati su otprikike sledeci :
Branislav Milojkovic (B) ~270
jedan decko (A) ~50
drugi decko (B) ~150
Ja (A) 263

Inace, zanimaju me rezultati iz Kg-a ..Iz svih vecih mesta rezultati su dostupni sem iz Kg-a..
â½manâ½amazing
Hm...chudo da jos uvek nema rezultata iz ostalih mesta ne racunajuci BG NS NI...
Ajde ko zna nek postue...
s
specijalac
Ne razumem koji nam josh gradovi nedostaju osim Kragujevca??
m
maki88
Takmicenje je ove godine za B kategoriju mnogo teze nego prosle. Sad se prvi put takmicim, i imao sam oko 140(0+90+50). da li neko moze samo da mi kaze ideju kako se radi 1. zadatak (broj nacina formiranja vlade) p.s. radim u pascalu i zato nisam razumeo resenje koje ste poslali..
r
renovator
ideja je da se isprobaju sve kombinacije...To mozes uraditi rekurzivno..
k
kgstefan88
210
gaus-100
zecovi-100
filmovi- (samo) 10
k
kgstefan88
evo rezultata iz KG-a:
1)
Popovic Strahinja 280 (100+80+100)
imao bi on svih 300 ali je umesto niza od 200001 clanova napravio niz od 200000
2)
Micic Milan (100+100+57)
3)
Nikolic Stefan (100+100+10)
.
.
.
.
s
sanja
@namestaljka
a ti onda napravi svoj sajt i imaj toliki ugled da dobijas zadatke pre takmicenja. Ja verujem i Bobi i Relji da zadaci nisu bili tu pre takmicenja. Uostalom, Relja nije resio ceo jedan od spornih zadataka, a Gaus uopste nije toliko tezak zadatak, tako da i da su zadaci bili tu i ne bismo bili nesto u prednosti. A da, principi... Kahm kahm primetno je da se jedan okrug konstantno favorizuje u odnosu na druge pa niko ne prica nista na tu temu...
r
renovator
@namestaljka namestaljka

prva stvar: zasto ne pokazes svoje pravo lice ,nego otvaras novi account ?

druga stvar: na osnovu cega verujes da su moderatori imali pristup zadacima? Jel sam ja nesto inace los u programiranju pa je rezultat koji sam ostvario nerealan ?Kao sto vidis ima ljudi koji su bolje uradili..

treca stvar: A ko je ovde, recimo, kompetentniji od Slobe i jos par ljudi ?

I sve si mogao da izlozis na normalan, a ne prost nacin..Nauci malo kako da se obracas ljudima koje ne poznajes...
r
renovator
da dodam jos par stvari ( na osnovu mojih pretpostavki koje ne moraju biti tacne, ali necu nista precizirati )..

Inace, zao mi je sto je savest nekih ljudi koji imaju veze sa organizacijom
takmicenja prilicno jeftina..Cemu favorizacija ljudi iz sopstvenog regiona ? Sta cemo postici time ? Ucinicemo nekom koga poznajemo , samo zato sto ga poznajemo.
I da nas mozda obrukaju na IOI-u.. Ta takmicenja su, nista drugo, nego postupak odabira tima za nasu olimpijsku ekipu.
No, ja sam svestan toga da je veoma tesko da se ceo sistem dovede u normalu.Ali bih voleo da bar tome tezimo..Ja sam sigran da u zemljama koje postizu zapazene rezultate na IOIu nema favorizovanja ( sto ne znaci da su losi rezultati rezultat favorizovanja )..
Najvise bih voleo kada se niko u ovoj prici ne bi pronasao..Ali bih takodje voleo da se neko pronadje i promeni svoj stav...

Eto, toliko od mene..( mozda malo se*em , ali nije strasno :) )..
b
boba5551
Da ima opravdane argumente i da nije neka kukavica, onda bi se predstavio/la. Da je imao/la 300 poena, ne bi pokusavao/la da kritikuje druge koji su uradili dobro. To je ono sto bi se u narodu reklo - U tudjem oku vidi trn, a u svom ne vidi ni drvo.
â½manâ½amazing
Rez objavljeni...
[url]http://www.yuoi.nis.edu.yu/[/url]
Prolaz sa 80 poena. Cya there... :)