infoarena

infoarena - concursuri, probleme, evaluator, articole => Concursuri => Subiect creat de: Mihai Calancea din Februarie 26, 2012, 22:45:10



Titlul: OJI 2012
Scris de: Mihai Calancea din Februarie 26, 2012, 22:45:10
Sambata, 3 martie, ora 9:00 va avea loc Olimpiada Judeteana de Informatica.
Bafta tuturor! :)


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Februarie 27, 2012, 15:11:54
Aici http://infoarena.ro/forum/index.php?topic=7289.msg53430#msg53430  (http://infoarena.ro/forum/index.php?topic=7289.msg53430#msg53430) a intrebat cineva daca avem voie sa folosim STL-ul si nu i s-a dat un raspuns concret. Avem voie sa-l folosim? De exemplu sortarea din STL, sau implementarea heapurilor (make_heap, etc) le putem folosi?


Titlul: Răspuns: OJI 2012
Scris de: c a e n din Februarie 27, 2012, 15:19:50
Pai aici (http://olimpiada.info/oji2012/OJI_ONI_good_coding_practice.pdf) scrie ce header-e ai voie sa folosesti, deci daca instructiunea se gaseste in unul din ele, poti s-o folosesti linistit.


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Februarie 27, 2012, 17:02:01
Multumesc mult de raspuns. Eu de vreo 3 saptamani am invatat sa folosesc STL-ul cum trebuie, dar nu eram sigur daca merge si la olimpiada. Dar de-acum stiu.
Succes tuturor la OJI!!!


Titlul: Răspuns: OJI 2012
Scris de: UAIC-Padurariu-Cristian din Februarie 27, 2012, 18:41:50
Cat de mare e posibilitatea sa se dea dinamica la clasele 11-12?


Titlul: Răspuns: OJI 2012
Scris de: Buleandra Cristian din Februarie 27, 2012, 18:51:29
Foarte probabil... Eu zic ca se da o dinamica pe matrice si un APM :)) .


Titlul: Răspuns: OJI 2012
Scris de: Sorin Rita din Februarie 27, 2012, 18:56:43
Flux credeti ca se da ? N-am vazut in niciuna din problemele din anii anteriori.


Titlul: Răspuns: OJI 2012
Scris de: Buleandra Cristian din Februarie 27, 2012, 19:16:07
Flux credeti ca se da ? N-am vazut in niciuna din problemele din anii anteriori.

Sigur nu se da flux la OJI ... Nici la ONI nu prea se da, a fost o problema cu flux anul trecut parca la baraj...


Titlul: Răspuns: OJI 2012
Scris de: UAIC-Padurariu-Cristian din Februarie 28, 2012, 20:18:42
Se pot da LCA sau RMQ la clasa a 11-a? :-k


Titlul: Răspuns: OJI 2012
Scris de: Andrei Grigorean din Februarie 28, 2012, 21:47:12
Nu.


Titlul: Răspuns: OJI 2012
Scris de: Pop Marcel din Februarie 29, 2012, 14:39:33
Se da si geometrie la clasa a 12-a?


Titlul: Răspuns: OJI 2012
Scris de: Cristian Lambru din Februarie 29, 2012, 14:42:51
Posibil: cerc3 (http://infoarena.ro/problema/cerc3) si mosia (http://infoarena.ro/problema/mosia)


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 01, 2012, 20:54:27
Nu prea am fost eu la multe olimpiade, dar unde am fost, documentația pentru STL era pe desktop. Era că așa trebuia să fie sau a uitat-o cineva pe acolo? E ok să o folosim?


Titlul: Răspuns: OJI 2012
Scris de: Sorin Rita din Martie 01, 2012, 20:55:59
Asa trebuie sa fie.


Titlul: Răspuns: OJI 2012
Scris de: Boaca Cosmin din Martie 01, 2012, 21:28:55
Vreo sansa sa se dea probleme ce tin de biconexitate , gen descompunere in comp biconexe sau determinarea punctelor de aritculatie ?


Titlul: Răspuns: OJI 2012
Scris de: FMI Ciprian Olariu din Martie 01, 2012, 21:32:45
Vreo sansa sa se dea probleme ce tin de biconexitate , gen descompunere in comp biconexe sau determinarea punctelor de aritculatie ?
Cred ca asemeni problemelor de flux,problemele de biconexitate pot fi date incepand cu proba de baraj  :wink:


Titlul: Răspuns: OJI 2012
Scris de: Andrei Grigorean din Martie 02, 2012, 01:03:46
Vreo sansa sa se dea probleme ce tin de biconexitate , gen descompunere in comp biconexe sau determinarea punctelor de aritculatie ?

Eu am primit la OJI in clasa a XI-a o problema unde a trebuit sa aflu muchiile critice.


Titlul: Răspuns: OJI 2012
Scris de: Petrisor Andrei din Martie 02, 2012, 10:28:58
La clasa a X-a cam ce s-ar putea da? :?


Titlul: Răspuns: OJI 2012
Scris de: Visan Radu din Martie 02, 2012, 10:34:50
In ultimii ani au dat PD+siruri de caractere la a 10-a.


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 02, 2012, 13:07:57
Referitor la clasa a 10-a, probleme în care să se găsească cel mai scurt drum într-o matrice pe care există niște obstacole. Pentru asta îți sugerez să știi sau să ai idee de algoritmul lui Lee și parcurgerea în lățime.

Mai cineva de părere că subiectele nu ar trebuie să fie mai mult de o pagină?  :D


Titlul: Răspuns: OJI 2012
Scris de: Sorin Rita din Martie 02, 2012, 15:56:34
Sigur la 9 incepe,da ?  :D

Si da, anul trecut la a 10a a fost groaznica una din probleme din cauza lungimii enuntului. Nu inteleg de ce unii autori insista sa introduca si chestii inutile. Nu cred ca intereseaza pe nimeni partea artistica a problemei.


Titlul: Răspuns: OJI 2012
Scris de: FMI Romila Remus Arthur din Martie 02, 2012, 16:53:07
Sorin, partea artistica a problemelor(ce au mai facut Boolanel si Zaharel) reprezinta sarea si piperul olimpiadei.Fara ele, parca nu ar mai avea acelasi farmec. :)


Titlul: Răspuns: OJI 2012
Scris de: Sorin Rita din Martie 02, 2012, 19:05:31
Nu zic sa nu fie, eu vorbeam de cazul in care se exagereaza. La olimpiada mai e si stresul, te grabesti sa nu pierzi prea multa vreme si cand vezi ca enuntul e asa mare risti sa nu te concentrezi cand citesti sau sa sari peste anumite parti care contineau informatii importante.


Titlul: Răspuns: OJI 2012
Scris de: Visan Radu din Martie 02, 2012, 22:15:10
@Sorin da, la 9 incepe
Din cate am vazut, la a 10-a se pune accentul pe Lee/Fill. Grafuri si arbori banuiesc ca nu dau, nu?


Titlul: Răspuns: OJI 2012
Scris de: Sorin Rita din Martie 02, 2012, 22:43:30
Nu o sa primesti la a 10a grafuri sau arbori.


Titlul: Răspuns: OJI 2012
Scris de: Gabriel Bitis din Martie 02, 2012, 23:06:38
Succes maine tuturor!
Cei mai buni sa se califice la ONI !  :weightlift:


Titlul: Răspuns: OJI 2012
Scris de: Mihai Calancea din Martie 02, 2012, 23:24:57
Bafta tuturor! :)


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 02, 2012, 23:26:45
Baftă tuturor și din partea mea. :D


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Martie 03, 2012, 12:50:32
Cum a fost la olimpiada? Cum vi s-au parut subiectele?
La clasele XI-XII, la problema "blis", partea a 2-a, cum ati impartit subsecventele?


Titlul: Răspuns: OJI 2012
Scris de: abcd efgh din Martie 03, 2012, 13:31:53
Sincer au fost destul de ciudate problemele, a doua cel putin...

Prima se rezolva prin dinamica, intr-o complexitate de O(N*K*logN) cred sau ceva de genu. Am vrut sa caut valoarea minima printr-un AIB pe doua dimensiuni, dar nu intra in memoria...asa ca am ramas cu O(N^2*K^2).
A doua problema e un mister.

Daca a rezolvat cineva una din probleme sa ma lumineze si pe mine.


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Martie 03, 2012, 13:46:12
A doua problema cred ca se rezolva asa:
Vad cate piste de biciclete am pe orizontala si cate pe verticala intre punctele A si B cu tot cu lungimile lor (pentru exemplul dat 2+2+3=7), iar apoi iau o submatrice care contine doar pietonalele dintre punctul A si punctul B Pentru exemplu dat o matrice de forma C[2][4] (4 linii si 2 coloane) si calculez distanta minima de la punctul A la B in aceasta matrice, distanta ce o calculez cu teorema lui Pitagora(in acest caz distanta este 4.4721359). Acum adun lungimea minima de pe piste cu lungimea minima de pe pietonale si obtinem rezultatul dorit: 7+4.4721359=11.4721359).

Ideea am avut-o mai tarziu si nu am mai avut timp sa implementez. Am luat doar cazurile speciale cand cei 2 se afla pe aceeasi linie sau coloana, sau cazul in care intre ei nu se afla nicio pista.


Titlul: Răspuns: OJI 2012
Scris de: Petru Trimbitas din Martie 03, 2012, 13:52:24
A doua problema cred ca se rezolva asa:
Vad cate piste de biciclete am pe orizontala si cate pe verticala intre punctele A si B cu tot cu lungimile lor (pentru exemplul dat 2+2+3=7), iar apoi iau o submatrice care contine doar pietonalele dintre punctul A si punctul B Pentru exemplu dat o matrice de forma C[2][4] (4 linii si 2 coloane) si calculez distanta minima de la punctul A la B in aceasta matrice, distanta ce o calculez cu teorema lui Pitagora(in acest caz distanta este 4.4721359). Acum adun lungimea minima de pe piste cu lungimea minima de pe pietonale si obtinem rezultatul dorit: 7+4.4721359=11.4721359).

Ideea am avut-o mai tarziu si nu am mai avut timp sa implementez. Am luat doar cazurile speciale cand cei 2 se afla pe aceeasi linie si respectiv pe aceeasi coloana.

Asa am facut si eu. La cerinta a 2-a m-am gandit ca rasp e 1 sau 2. Raspunsul e 1 atunci cand un interval se termina la destinatie. Cum se demonstreaza corectitudinea ?


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Martie 03, 2012, 14:03:37
A doua problema cred ca se rezolva asa:
Vad cate piste de biciclete am pe orizontala si cate pe verticala intre punctele A si B cu tot cu lungimile lor (pentru exemplul dat 2+2+3=7), iar apoi iau o submatrice care contine doar pietonalele dintre punctul A si punctul B Pentru exemplu dat o matrice de forma C[2][4] (4 linii si 2 coloane) si calculez distanta minima de la punctul A la B in aceasta matrice, distanta ce o calculez cu teorema lui Pitagora(in acest caz distanta este 4.4721359). Acum adun lungimea minima de pe piste cu lungimea minima de pe pietonale si obtinem rezultatul dorit: 7+4.4721359=11.4721359).

Ideea am avut-o mai tarziu si nu am mai avut timp sa implementez. Am luat doar cazurile speciale cand cei 2 se afla pe aceeasi linie si respectiv pe aceeasi coloana.

Asa am facut si eu. La cerinta a 2-a m-am gandit ca rasp e 1 sau 2. Raspunsul e 1 atunci cand un interval se termina la destinatie. Cum se demonstreaza corectitudinea ?

Pot fi mai multe raspunsuri, nu doar 1 si 2. De exemplu in matrice daca pleca de la A(2,2) putea avea urmatoarele trasee de lungime minima:
(2,2)->(2,4)->(4,4)->(5,7)->(8,7)
(2,2)->(4,2)->(4,4)->(5,7)->(8,7)
(2,2)->(3,2)->(3,3)->(4,3)->(4,4)->(5,7)->(8,7)
si lista poate continua.


Titlul: Răspuns: OJI 2012
Scris de: Cezar Mocan din Martie 03, 2012, 14:07:26
In principiu e putere de 2 raspunsul b) de la a 2-a... ca se poate splitui drumul in doua parti de fiecare data cand intalneste o intersectie de vertical-orizontal.


Titlul: Răspuns: OJI 2012
Scris de: Petru Trimbitas din Martie 03, 2012, 14:07:40
Poti sa desenezi ? nu se cerea numarul de drumuri minime ? eu ma gandeam ca te poti duce doar in dreapta sau in sus ca altfel te departezi.


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Martie 03, 2012, 14:16:12
Poti sa desenezi ? nu se cerea numarul de drumuri minime ? eu ma gandeam ca te poti duce doar in dreapta sau in sus ca altfel te departezi.
In cazul de mai sus am mers ori in sus ori in dreapta. Vezi ca punctul P(i,j) are coordonatele pe Ox i si pe Oy j. Deci punctul P[i,j] este pe linia j coloana i.


Titlul: Răspuns: OJI 2012
Scris de: Sorin Rita din Martie 03, 2012, 14:27:14
La prima pana la urma care e complexitatea optima ? Eu aveam O(n*k^2)


Titlul: Răspuns: OJI 2012
Scris de: Vladu Sorin din Martie 03, 2012, 15:12:27
Imi spune si mie ce am gresit la sursa? Sau...cum puteam sa fiu in timpul de executie?
<Clasa a IX-a>
Cod:
#include<iostream>
#include<fstream>

using namespace std; // p=numar iarba uscata sub un elicopter q=numar total iarba sub un elicopter :@

ifstream f;
ofstream g;

int m,n,k,t[101][101],c[41][41],i,j,h=1,N1=0,N2=0,p=0,sw[101][101],y=0,q=0;
int u[41];
float jum,pq;

int main()
{
f.open("elicop.in");
g.open("elicop.out");

f >> m >> n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
f >> t[i][j];

f >> k;
for(i=1;i<=k;i++)
for(j=1;j<=5;j++)
f >> c[i][j];

jum=1/2;

for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
sw[i][j]=0;

for(i=1;i<=k;i++)
{
y=0;
if(c[i][5]==1)
{
if(c[i][2]<c[i][4])
while(sw[c[i][3]][c[i][4]]==0)
{
for(j=c[i][2]+y;j<=c[i][4];j++)
{
if(t[c[i][1]+y][j]==0)
p++;
sw[c[i][1]+y][j]=1;
q++;
}
y++;
}
if(c[i][2]>c[i][4])
while(sw[c[i][3]][c[i][4]]==0)
{
for(j=c[i][2]-y;j>=c[i][4];j--)
{
if(t[c[i][1]-y][j]==0)
p++;
sw[c[i][1]-y][j]=1;
q++;
}
y++;
}
}
if(c[i][5]==-1)
{
if(c[i][1]<c[i][3])
while(sw[c[i][3]][c[i][4]]==0)
{
for(j=c[i][1]+y;j<=c[i][3];j++)
{
if(t[j][c[i][2]+y]==0)
p++;
sw[j][c[i][2]+y]=1;
q++;
}
y++;
}
if(c[i][1]>c[i][3])
while(sw[c[i][3]][c[i][4]]==0)
{
for(j=c[i][1]-y;j>=c[i][3];j--)
{
if(t[j][c[i][1]-y]==0)
p++;
sw[j][c[i][1]-y]=1;
q++;
}
y--;
}
}
pq=p/q;
if(p==0)
N1++;
if(pq>jum)
{
N2++;
u[h]=i;
h++;
}
}

g << N1 << '\n' << N2 << " ";
for(j=1;j<=N2;j++)
g << u[j] << " ";

f.close();
g.close();

return 0;
}
Cea de mai sus este Problema cu Elicopterele ( I ).

Cod:
#include<iostream>
#include<fstream>

using namespace std;

ifstream f;
ofstream g;

int n,p,c[361],cl,rtr,i,j,Euro,oc[361],h=1,sw[361],ultim;
float x,r[361];

void citire()
{
f >> n >> p;
for(i=1;i<=n;i++)
f >> c[i];
}

float inv(int n)
{
x=1/n;
}

void afisare()
{
g << Euro << '\n';
for(h=1;h<=p;h++)
g << oc[h] << " ";
}

int main()
{
f.open("roata.in");
g.open("roata.out");

citire();

cl=n;

for(i=1;i<=n;i++)
rtr+=c[i];
Euro=rtr;

for(j=1;j<=n;j++)
sw[j]=0;

while(rtr>0)
{
if(cl>=1)
{
cl--;
for(j=1;j<=n;j++)
if(sw[j]==0)
{
sw[j]=1;
j=n;
}
}
for(j=1;j<=n;j++)
{
if(r[j]==1)
{
r[j]=0;
rtr--;
c[j]--;
ultim=j;
}
if(c[j]==0)
{
sw[j]=0;
cl++;
oc[h]=j;
h++;
}
}
for(i=1;i<=n;i++)
if(sw[i]==1)
r[i]+=inv(n);
}

afisare();

f.close();
g.close();

return 0;
}
Cea de mai sus este Problema cu Roata ( II ).


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 03, 2012, 16:47:39
La a 2-a problemă la a 11-a nici nu trebuia creezi vreo marice. Ideea era să comprimi pistele de biciclete ca și cum ar fi o dreaptă, după care calculai cu Pitagora distanța dintre cele două puncte, la care adugai lățimea pistelor (acum drepte) prin care trece drumul direct de la Gigel la prietenul lui.

Numărul de drumuri minime de dubla dacă drumul direct trecea prin interesecția a unei drepte orizontale cu una verticală (cel puțin așa cred).

La prima am făcut doar prima cerință, unde găseam cea mai mare secvență de cifre de 1 consecutive, iar dacă mai rămânea spațiu până la K, adăugam ce era după, cu condiția că dacă secvența maximă de mai mică decât K și e la sfârșit, să compar cu a doua secvență ce mai mare, iar dacă aceea este mai mare, o afișam pe aia. M-am chinuit vreo jumătate de oră să găsesc o formulă de dinamică pentru a 2-a cerință, dar nici acum n-am găsit-o, presupun că intra backtracking în 1.5 secunde.

Eu unul nu am implementat nici o problemă complet că ideile au venit prea târziu sau deloc. :(

Soluțiile oficiale nu le-am citit că nu prea am timp acum.

Bravo celor care s-au calificat! Eu aștept rezultatul încă, dar sunt aproape sigur că nu e unul bun.

PS: Are cineva idee de ce nu pot compara două float-uri?


Titlul: Răspuns: OJI 2012
Scris de: Ilie Ionut din Martie 03, 2012, 17:06:16
In caz ca ii trebuie cuiva evaluatoarele... http://ler.is.edu.ro/~cex_is/Informatica/pregatire.html


Titlul: Răspuns: OJI 2012
Scris de: FMI Ekart Dragos-Ioan din Martie 03, 2012, 17:24:14
Cine a patit ca la clasa a X-a sa faca la prima problema sa nu faca punctul a si sa faca punctul b si sa primeasca 0 puncte?


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 03, 2012, 17:59:22
Ai afișat ceva (orice) pentru primul punct? Dacă nu, e normal să iei 0 puncte.

Vai, am venit acasă foarte senin că știam că nu mă calific, că nu am făcut de peste 100.

În timpul concursului, observam că MinGW-ul îmi evalua expresia (sqrt(float(x_i*x_i + y_i*y_i)) <  sqrt(float(x_p*x_p + y_p*y_p))) && (sqrt(float(x_i*x_i + y_i*y_i)) > sqrt(float(x_p*x_p + y_p*y_p))) ca fiind adevărată (95% sigur că nu am greșit, un sfert de oră am verificat asta și am și rescris-o de câteva ori. Am chemat unul dintre supraveghetori să întreb, dar nici nu am deschis bine gura că mi-a zis că nu are cu se să mă ajute, că ce știu eu să fac, asta fac. Până la urmă am presupus (prin absurd) că pe float, sau orice valoare ar returna funcția sqrt, nu merg operatorii < și >, așa că am scos partea aceea din program. Ideea era să calculez drumul cel mai scurt de la punctul mai aproape de origine, la celălalt, chiar dacă cel care era mai aproape, era în dreapta celuilalt.

Știu că nu luam 200, dar mai scoteam și eu ceva.


Titlul: Răspuns: OJI 2012
Scris de: FMI Ekart Dragos-Ioan din Martie 03, 2012, 18:06:43
am afisat un rezultat dar gresit si dupa "\n" si mi-a dat pe matrice bine, dar am luat pe teste incorect
Si eu am cerut unul din supraveghetor legat de intelegerea primei partie pentru punctul a si am primit ca nu ma pot ajuta . Desi nu era o treaba de rezolvare , tu prin ce metoda ai facut-o?


Titlul: Răspuns: OJI 2012
Scris de: c a e n din Martie 03, 2012, 18:32:35
In enunt scria ca primesti 20% pentru prima cerinta si punctaj complet pentru ambele, dar nu scria ca primesti 80% pentru a doua cerinta. In mod normal, ai crede ca se dau puncte si daca rezolvi doar a doua cerinta, dar am mai intalnit probleme in care nu era valabil.

Totusi, esti sigur ca matricea a fost corecta pe toate testele, sau banuiesti? Nu de alta, dar daca ai inteles cum sa faci cerinta a doua, prima e cam triviala (numeri *-le, scrie si in enunt) :-?


Titlul: Răspuns: OJI 2012
Scris de: Visan Radu din Martie 03, 2012, 18:36:37
Dar totusi, nu mi se pare normal sa punctezi doar prima cerinta/amandoua si sa nu punctezi nimic daca e facuta doar a 2-a cerinta..


Titlul: Răspuns: OJI 2012
Scris de: Vlad Eugen Dornescu din Martie 03, 2012, 18:44:10
Trebuia sa afisezi ceva, orice, pe prima linie .... si ti s-ar fi luat in considerare a doua ...  :)


Titlul: Răspuns: OJI 2012
Scris de: FMI Ekart Dragos-Ioan din Martie 03, 2012, 18:51:30
si recunosc nu mi-a trecut prin cap sa fac numararea *  ](*,) ](*,) ](*,)(dar pentru atat sa nu primesc nimic e cam nasol ) si sunt convis ca am facut bine cu matricea (sunt cateca teste care mi-au depasit timp(doar pentru 4 teste), nu cu astea am treapa ) dar din cate am inteles si eu din problema asa se puncteaza(doar a sau amandou) si eu sunt curios daca e corect modul asta de punctare
Si da am pus o valoare gresita pe prima linie (din metoda mea am incercat sa calculez si aia si nu mi-a dat o valoare bune) si am tiparit


Titlul: Răspuns: OJI 2012
Scris de: UAIC-Padurariu-Cristian din Martie 03, 2012, 20:01:15
Mi s-au parut putin exagerate subiectele de la 11-12. Nu mi se pare normal ca un singur elev din toata tara sa rezolve problema a doua de 100. Sunt foarte putini care au punctajul general peste 100. Nu mi-a venit sa cred cand am citit problemele si nu am gasit niciun graf. Toti colegii mei au lucrat grafuri si toata lumea se astepta sa fie macar o problema de genu asta, pana si profesorii. Sper ca la anu sa fie mai bine. :)


Titlul: Răspuns: OJI 2012
Scris de: c a e n din Martie 03, 2012, 20:06:25
Si eu ma asteptam sa fie un pic diferit la a 10-a. Cand am vazut subiectele, ma gandeam sa intreb comisia cati ani are Miruna :(


Titlul: Răspuns: OJI 2012
Scris de: mdmdmd din Martie 03, 2012, 20:08:57
Trebuia sa afisezi ceva, orice, pe prima linie .... si ti s-ar fi luat in considerare a doua ...  :)

Luat de pe olimpiada.info: Sfaturi de buna practica pentru OJI si ONI - DOC (http://olimpiada.info/oji2012/index.php?cid=regulament)

Cod:

3. Respectați formatul fișierului de de ieșire!
De exemplu, fie o problemă care are două cerințe: a) și b). Să presupunem că se cere ca răspunsul pentru cerința a) trebuie se găsească pe linia 1, iar răspunsul pentru cerința b) să se găsească pe linia 2. În situația în care nu ați reușit să rezolvați cerința a) dar aveți un răspuns pentru b), veți scrie răspunsul pentru cerința b) pe linia 2 și nu pe prima linie  !


Titlul: Răspuns: OJI 2012
Scris de: Vlad Eugen Dornescu din Martie 03, 2012, 20:35:49
Si ce ti se pare ca am scris ?  :fighting:


Titlul: Răspuns: OJI 2012
Scris de: Boaca Cosmin din Martie 03, 2012, 20:55:52
Mm de acord cu faptul ca la 11 - 12 au fost cam grele :) . Nu prea au semanat cu nimic din anii trecuti dar felicitari celor care s-au descurcat bine si au facut 100 + .


Titlul: Răspuns: OJI 2012
Scris de: Andrei Grigorean din Martie 03, 2012, 20:59:30
Si eu ma asteptam sa fie un pic diferit la a 10-a. Cand am vazut subiectele, ma gandeam sa intreb comisia cati ani are Miruna :(

Mi-au furat personajul :((


Titlul: Răspuns: OJI 2012
Scris de: Cristian Lambru din Martie 03, 2012, 21:03:10
Eu totusi am o curiozitate, daca subiectele de la OJI erau atat de grele (cel putin la clasele XI-XII), ma intreb retoric cum vor fi la nationala?


Titlul: Răspuns: OJI 2012
Scris de: Popescu Silviu din Martie 03, 2012, 21:04:50
Salut,

Am calculat acum procentele pentru OJI (Bucuresti)  :( si e cam suparator (primul punctaj e ala de la OJI si celalalt e procentul )

clasa a IX-a         clasa a X-a      clasa a XI-a      clasa a XII-a   
134   70.27972028   120   61.53846154   56   34.92723493   54   32.99389002
130   68.18181818   115   58.97435897   53   33.05613306   49   29.9389002
121   63.46153846   113   57.94871795   48   29.93762994   48   29.32790224
110   57.69230769   110   56.41025641   42   26.1954262   48   29.32790224
110   57.69230769   103   52.82051282   41   25.57172557   43   26.27291242
106   55.59440559   100   51.28205128   34   21.20582121   40   24.43991853
100   52.44755245   95   48.71794872   32   19.95841996   38   23.21792261
94   49.3006993   85   43.58974359   31   19.33471933   32   19.55193483
92   48.25174825   82   42.05128205   29   18.08731809   25   15.27494908
88   46.15384615   45   23.07692308   27   16.83991684   20   12.21995927
74   38.81118881   35   17.94871795   27   16.83991684   17   10.38696538
70   36.71328671   35   17.94871795   25   15.59251559   12   7.33197556

totusi , nu sunt definitive (inca n-au afisat toate judetele )


Titlul: Răspuns: OJI 2012
Scris de: c a e n din Martie 03, 2012, 21:14:14
Mi-au furat personajul :((
Deci, cati ani are Miruna? :P


Titlul: Răspuns: OJI 2012
Scris de: Visan Radu din Martie 03, 2012, 21:27:58
Poate cineva care a luat 100 pe unul din subiecte/amandoua sa prezinte ideea de rezolvare? (asta daca nu cer prea mult)



PS: clasa a 10-a


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 03, 2012, 21:42:47
Cum trebuia facuta prob. "culori" ca sa nu iasa din memorie la clasa a 10-a???
Eu am gasit solutia, am scris-o pe un vector "int" si mi-a iesit din memorie.


Titlul: Răspuns: OJI 2012
Scris de: Paul-Dan Baltescu din Martie 03, 2012, 21:43:04
Si eu ma asteptam sa fie un pic diferit la a 10-a. Cand am vazut subiectele, ma gandeam sa intreb comisia cati ani are Miruna :(

Mi-au furat personajul :((

Oamenii astia chiar nu au nici un pic de decenta? :P


Titlul: Răspuns: OJI 2012
Scris de: Boaca Cosmin din Martie 03, 2012, 21:45:59
Citat
Si eu ma asteptam sa fie un pic diferit la a 10-a. Cand am vazut subiectele, ma gandeam sa intreb comisia cati ani are Miruna

Mi-au furat personajul (

Oamenii astia chiar nu au nici un pic de decenta?

Daca nu ii dai in judecata pentru drepturile de autor n-ai rezolvat nimic .


Titlul: Răspuns: OJI 2012
Scris de: Andrei Alexandrescu din Martie 03, 2012, 21:49:41
Sunt curios de o chestie... unde scrie cu ce compilator se evalueaza?


Titlul: Răspuns: OJI 2012
Scris de: Visan Radu din Martie 03, 2012, 21:55:06
@Andrei: mi se pare ca scrie in "Sfaturi de buna practica pt OJI si ONI". Link-ul de unde poti sa iei documentul: http://olimpiada.info/oji2012/index.php?cid=regulament


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 03, 2012, 21:56:33
Serios, subiectele la 11-12 nu mi s-au părut grele, cel puțin mie, că nu reușii eu să le implementez la timp, e altă treabă.  ](*,)
Sper să se ia acordul de la autori și să se pună în arhivă, sunt curios dacă ideile mele chiar mergeau, dacă da, o să fiu frustrat până anu viitor. :fighting:

PS: A mai fost cineva la Cantemir-Vodă la info II, sus? Sunt doar curios pe cine am văzut acolo.
PSS: Sper ca la anu să se folosească Code::Blocks!!

@partea cu Miruna, când am citit și eu aia am început să cânt asta (http://www.youtube.com/watch?v=AFZSyeDh6fE).

EDIT: Compilatorul am impresia că e gcc 3.3.1, nu bag mâna-n foc.


Titlul: Răspuns: OJI 2012
Scris de: Costea Vlad din Martie 03, 2012, 22:14:40
Cand se publica subiectele?


Titlul: Răspuns: OJI 2012
Scris de: Andrei Grigorean din Martie 03, 2012, 22:36:13
Salut,

Am calculat acum procentele pentru OJI (Bucuresti)  :( si e cam suparator (primul punctaj e ala de la OJI si celalalt e procentul )

clasa a IX-a         clasa a X-a      clasa a XI-a      clasa a XII-a   
134   70.27972028   120   61.53846154   56   34.92723493   54   32.99389002
130   68.18181818   115   58.97435897   53   33.05613306   49   29.9389002
121   63.46153846   113   57.94871795   48   29.93762994   48   29.32790224
110   57.69230769   110   56.41025641   42   26.1954262   48   29.32790224
110   57.69230769   103   52.82051282   41   25.57172557   43   26.27291242
106   55.59440559   100   51.28205128   34   21.20582121   40   24.43991853
100   52.44755245   95   48.71794872   32   19.95841996   38   23.21792261
94   49.3006993   85   43.58974359   31   19.33471933   32   19.55193483
92   48.25174825   82   42.05128205   29   18.08731809   25   15.27494908
88   46.15384615   45   23.07692308   27   16.83991684   20   12.21995927
74   38.81118881   35   17.94871795   27   16.83991684   17   10.38696538
70   36.71328671   35   17.94871795   25   15.59251559   12   7.33197556

totusi , nu sunt definitive (inca n-au afisat toate judetele )

Initiativa celor din Bucuresti mi se pare buna: primii 6 de la fiecare clasa se califica automat, iar celelalte 7 locuri se distribuie in functie de rezultatele la nivel national. DAR modul in care se face distribuirea mi se pare in neregula. De ce? Pentru ca indiferent cat de grele sunt subiectele primii 3 din tara tot vor avea punctaj foarte mare. De fapt vrei sa vezi IN GENERAL ce s-a intamplat la clasa respectiva, sa faci un fel de medie pentru toti concurentii. Daca se aplica regulamentul toate cele 7 locuri merg la clasele a IX-a si a X-a, ceea ce nu e deloc ok.


Titlul: Răspuns: OJI 2012
Scris de: c a e n din Martie 03, 2012, 22:37:11
Citat
Cand se publica subiectele?
Le poti lua de-aici (http://ler.is.edu.ro/~cex_is/Informatica/pregatire.html). Pe mine ma interesau solutiile :-"


Titlul: Răspuns: OJI 2012
Scris de: Andrei Grigorean din Martie 03, 2012, 22:48:54
Si eu ma asteptam sa fie un pic diferit la a 10-a. Cand am vazut subiectele, ma gandeam sa intreb comisia cati ani are Miruna :(

Mi-au furat personajul :((

Oamenii astia chiar nu au nici un pic de decenta? :P

E strigator la cer ce se intampla in tara asta. Se fura tot, dom'ne! Pana si dragostea vietii mi-au furat-o!!


Titlul: Răspuns: OJI 2012
Scris de: c a e n din Martie 03, 2012, 22:52:12
Poate la anu' o combina cu Boolanel in vreo problema...


Titlul: Răspuns: OJI 2012
Scris de: Fara nume din Martie 03, 2012, 23:27:00
la problema "Culorile" se rezolva cu o formula simpla
cam asta ar fi tot programul :

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int main()
{
   int c=5,i,n;
   f>>n;
   for(i=3;i<n;i++)
      c=c+3;
   g<<c*3;
   return 0;
}
regula este ca pentru 3 scanduri sunt : 3 x 3 = 9 combinatii posibile
                    pentru 4 scanduri sunt : 3 x 5 = 15 combinatii posibile
                    pentru 5 scanduri sunt : 3 x 8 = 24 combinatii posibile si etc...astept sa se posteze testele..
Pentru celelalte solutii se iese din timp foarte usor (0,2 secunde e prea putin pentru back-uri sau recursive complicate cu mii de if-uri...)


Titlul: Răspuns: OJI 2012
Scris de: theo .c din Martie 03, 2012, 23:36:01
la problema "Culorile" se rezolva cu o formula simpla
cam asta ar fi tot programul :

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int main()
{
   int c=5,i,n;
   f>>n;
   for(i=3;i<n;i++)
      c=c+3;
   g<<c*3;
   return 0;
}
regula este ca pentru 3 scanduri sunt : 3 x 3 = 9 combinatii posibile
                    pentru 4 scanduri sunt : 3 x 5 = 15 combinatii posibile
                    pentru 5 scanduri sunt : 3 x 8 = 24 combinatii posibile si etc...astept sa se posteze testele..
Pentru celelalte solutii se iese din timp foarte usor (0,2 secunde e prea putin pentru back-uri sau recursive complicate cu mii de if-uri...)
Eu am facuto cu umpic de dinamica...retineai pt fiecare culare nr de garduri care se pot termina in culoare x, unul actual si unul precedent(de fiecare data il actualizai ca sa iti intre in memroie)-pt ca nu aveai nevoie decat de nr de culori de la precedenta vopsire...implementai pe numere mari si cred ca puteai sa iei 100 daca erai atent...eu am lua doar 80:(...oricum citisem undeva ca daca ai sub 50 de puncte nu te califici la clasa 5-12....si astra ar fi greu de crezut..oricum eu sunt din bucuresti si ma cam oftic :(


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Martie 03, 2012, 23:37:59
Am citit de curiozitate problemele de la celelalte clase si nu se compara ca si grad de dificultate cu cele de a XI-a si a XII-a. Sunt de acord ca ei sunt mai mici dar totusi e cam mare diferenta. La a 9-a, la prima problema, la prima cerinta, faci doar o suma a elementelor din vector si ai 20p asigurat.
Acest lucru este confirmat si aici: http://olimpiada.info/oji2012/index.php?cid=statistici (http://olimpiada.info/oji2012/index.php?cid=statistici) . Media primilor 50 din clasamentul national la clasa a 9-a este de 137p, in timp ce la clasa a XI-XII-a este de aproximativ 70p. Deci nu mi se pare ok sa fie asa mare diferenta. E dubla diferenta dintre a 9-a si a XII-a.


Titlul: Răspuns: OJI 2012
Scris de: Mihai Calancea din Martie 03, 2012, 23:45:39
la problema "Culorile" se rezolva cu o formula simpla
cam asta ar fi tot programul :

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int main()
{
   int c=5,i,n;
   f>>n;
   for(i=3;i<n;i++)
      c=c+3;
   g<<c*3;
   return 0;
}
regula este ca pentru 3 scanduri sunt : 3 x 3 = 9 combinatii posibile
                    pentru 4 scanduri sunt : 3 x 5 = 15 combinatii posibile
                    pentru 5 scanduri sunt : 3 x 8 = 24 combinatii posibile si etc...astept sa se posteze testele..
Pentru celelalte solutii se iese din timp foarte usor (0,2 secunde e prea putin pentru back-uri sau recursive complicate cu mii de if-uri...)

Si cat ai luat pe chestia asta?


Titlul: Răspuns: OJI 2012
Scris de: Fara nume din Martie 03, 2012, 23:49:53
la problema "Culorile" se rezolva cu o formula simpla
cam asta ar fi tot programul :

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int main()
{
   int c=5,i,n;
   f>>n;
   for(i=3;i<n;i++)
      c=c+3;
   g<<c*3;
   return 0;
}
regula este ca pentru 3 scanduri sunt : 3 x 3 = 9 combinatii posibile
                    pentru 4 scanduri sunt : 3 x 5 = 15 combinatii posibile
                    pentru 5 scanduri sunt : 3 x 8 = 24 combinatii posibile si etc...astept sa se posteze testele..
Pentru celelalte solutii se iese din timp foarte usor (0,2 secunde e prea putin pentru back-uri sau recursive complicate cu mii de if-uri...)

Si cat ai luat pe chestia asta?
Pai mi-am dat seama de solutie fix cand am dat paste pe stick cu sursa..si era deja prea tarziu ](*,)..nu mai puteam schimba nimic... :fool:
la prima problema am ciupit 20 de puncte, trebuia doar sa numeri stelutele  :thumbdown:


Titlul: Răspuns: OJI 2012
Scris de: Fara nume din Martie 03, 2012, 23:52:06
la problema "Culorile" se rezolva cu o formula simpla
cam asta ar fi tot programul :

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int main()
{
   int c=5,i,n;
   f>>n;
   for(i=3;i<n;i++)
      c=c+3;
   g<<c*3;
   return 0;
}
regula este ca pentru 3 scanduri sunt : 3 x 3 = 9 combinatii posibile
                    pentru 4 scanduri sunt : 3 x 5 = 15 combinatii posibile
                    pentru 5 scanduri sunt : 3 x 8 = 24 combinatii posibile si etc...astept sa se posteze testele..
Pentru celelalte solutii se iese din timp foarte usor (0,2 secunde e prea putin pentru back-uri sau recursive complicate cu mii de if-uri...)
Eu am facuto cu umpic de dinamica...retineai pt fiecare culare nr de garduri care se pot termina in culoare x, unul actual si unul precedent(de fiecare data il actualizai ca sa iti intre in memroie)-pt ca nu aveai nevoie decat de nr de culori de la precedenta vopsire...implementai pe numere mari si cred ca puteai sa iei 100 daca erai atent...eu am lua doar 80:(...oricum citisem undeva ca daca ai sub 50 de puncte nu te califici la clasa 5-12....si astra ar fi greu de crezut..oricum eu sunt din bucuresti si ma cam oftic :(
ai dreptate..am fost pe aproape cu dinamica..m-am gandit si la ea pt ca 5000 e o valoare prea mare pt back...dar na...asta este la anul de acuma :weightlift:


Titlul: Răspuns: OJI 2012
Scris de: Mihai Calancea din Martie 03, 2012, 23:53:30
Pai nu e buna solutia aia. Solutia buna e dinamica. + numere mari (din pacate..).


Titlul: Răspuns: OJI 2012
Scris de: Fara nume din Martie 03, 2012, 23:55:01
probabil ca da...


Titlul: Răspuns: OJI 2012
Scris de: theo .c din Martie 04, 2012, 00:02:15
Pai nu e buna solutia aia. Solutia buna e dinamica. + numere mari (din pacate..).
Mergea si cu o formula doar ca nu cea scris mai sus..pe testele mici iti dadea corect:

Citat
int aflu()
{
    int moduri=1;
    for(int k=2;k<=n;k++)
    {
        switch(ultim)
        {
            case 1:{ultim=2;break;}
            case 2:{if(k==n)moduri*=2;else moduri*=3;ultim=2;k++;break;}
            case 3:{moduri*=2;ultim=2;break;}
        }
    }
    return moduri;
}
int main()
{
    in>>n;
    ultim=1;
        total+=2*aflu();
    ultim=2;
        total+=2*aflu();
    ultim=3;
        total+=aflu();
    out<<total;
    return 0;
}
Da intr-adevar subiectele de la a X a nu au fost prea grele ,cel putin problema asta.


Titlul: Răspuns: OJI 2012
Scris de: Mihai Calancea din Martie 04, 2012, 00:14:24
Din nou. Cat ai luat cu asta?  :-k
L.E: De fapt asta aduce a recurenta de la dinamica. Cred ca e ok. Dar nu e formula.


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 04, 2012, 01:47:29
la problema "Culorile" se rezolva cu o formula simpla
cam asta ar fi tot programul :

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int main()
{
   int c=5,i,n;
   f>>n;
   for(i=3;i<n;i++)
      c=c+3;
   g<<c*3;
   return 0;
}
regula este ca pentru 3 scanduri sunt : 3 x 3 = 9 combinatii posibile
                    pentru 4 scanduri sunt : 3 x 5 = 15 combinatii posibile
                    pentru 5 scanduri sunt : 3 x 8 = 24 combinatii posibile si etc...astept sa se posteze testele..
Pentru celelalte solutii se iese din timp foarte usor (0,2 secunde e prea putin pentru back-uri sau recursive complicate cu mii de if-uri...)

pai nu e bine. poti sa faci si pe foaie pentru 1, 2, 3 si 4.

Eu am zis sa o fac prima data prin back, dar pt N=25 stateam mult si asteptam degeaba. Dupa aia am luat toate rezulatele de la 1 la 20 din back si le-am descompus in factori primi.

Cazurile speciale erau:
1. N=1  -> g << 5
2. N=2  -> g << 8
3. N=3  -> g << 14

Restul mai trebuia sa pui o singura conditie:

Daca (N%2==0) g <<  8 * 3^(n/2-1)
Altfel g <<  14* 3^(n/2-1)


Titlul: Răspuns: OJI 2012
Scris de: Oancea Catalin din Martie 04, 2012, 09:09:24
Eu am facuto cu umpic de dinamica...retineai pt fiecare culare nr de garduri care se pot termina in culoare x, unul actual si unul precedent(de fiecare data il actualizai ca sa iti intre in memroie)-pt ca nu aveai nevoie decat de nr de culori de la precedenta vopsire...implementai pe numere mari si cred ca puteai sa iei 100 daca erai atent...eu am lua doar 80:(...oricum citisem undeva ca daca ai sub 50 de puncte nu te califici la clasa 5-12....si astra ar fi greu de crezut..oricum eu sunt din bucuresti si ma cam oftic :(
Nu trebuie sa ai peste 50 de puncte pt calificare. Sunt judete unde nu s-au depasit 40 de puncte si exista elevi calificati la ONI si cu 18 puncte.  :annoyed: Aici (http://olimpiada.info/oji2012/index.php?cid=rezultate&w=lic) te poti uita. (Un exemplu: Teleorman - merg la ONI toti care nu au luat 0 puncte) ...seems legit


Titlul: Răspuns: OJI 2012
Scris de: Paul-Dan Baltescu din Martie 04, 2012, 09:34:33
Un scop al Olimpiadei este si acela de a populariza informatica in randul elevilor din intreaga tara. Daca ai spirit competitiv, participa la Algoritmiada, .campion, topcoder, codeforces, etc. :)


Titlul: Răspuns: OJI 2012
Scris de: Iulian Marcu din Martie 04, 2012, 11:48:54
Salut! Vreau si eu sa aflu cum e cu contestatiile... Adica se fac maine? Intre ce ore? Eu nu am fost anuntat despre contestatii in sala de concurs si vreau sa ma lamuresc. Multumesc!


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 04, 2012, 11:51:47
Au afisat solutiile.

Intre asta:

Cod:
#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int a[500000], n, putere;

void prod()
{
    a[0]=1;
    a[1]=3;

    int t=0, x=0, i;

    while(putere)
    {
        for(i=1; i<=a[0]; ++i)
        {
            x=a[i]*3+t;
            a[i]=x%10;
            t=x/10;
        }
        while(t)
        {
            a[++a[0]]=t%10;
            t/=10;
        }
        putere--;
    }
}

void par1()
{
    int x=0, t=0, i;

    for(i=1; i<=a[0]; ++i)
    {
        x=a[i]*8+t;
        a[i]=x%10;
        t=x/10;
    }
    while(t)
    {
        a[++a[0]]=t%10;
        t/=10;
    }
}

void impar1()
{
    int x=0, t=0, i;

    for(i=1; i<=a[0]; ++i)
    {
        x=a[i]*2+t;
        a[i]=x%10;
        t=x/10;
    }
    while(t)
    {
        a[++a[0]]=t%10;
        t/=10;
    }
}

void impar2()
{
    int x=0, t=0, i;

    for(i=1; i<=a[0]; ++i)
    {
        x=a[i]*7+t;
        a[i]=x%10;
        t=x/10;
    }
    while(t)
    {
        a[++a[0]]=t%10;
        t/=10;
    }
}

int main()
{
    f>>n;

    if(n==1)
    {
        g<<5<<"\n";
        return 0;
    }

    if(n==2)
    {
        g<<8<<"\n";
        return 0;
    }

    if(n==3)
    {
        g<<14<<"\n";
        return 0;
    }

    putere=n/2-2;

    prod();

    if(n%2==0)
    {
        par1();
        for(int i=a[0]; i>=1; --i) g<<a[i];
    }

    else
    {
        impar1();
        impar2();
        for(int i=a[0]; i>=1; --i) g<<a[i];
    }
}

si asta :

Cod:
#include<fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int n,i,A[10000];
unsigned long long nr=1;
void mul(int A[], int B)
{
int i, t = 0;
for (i = 1; i <= A[0] || t; i++, t /= 10)
A[i] = (t += A[i] * B) % 10;
A[0] = i - 1;
}
int main()
{f>>n;
 if(n==1)g<<5;
 else if(n==2)g<<8;
  else if(n==3)g<<14;
    else if(n%2==0)
  {A[1]=8;
   A[0]=1;
for(i=1;i<=(n-2)/2;i++)
mul(A,3);
for(i=A[0];i>=1;i--)
g<<A[i];
   }

       else if(n%2!=0)
   {A[1]=14;
   A[0]=1;
for(i=1;i<=(n-3)/2;i++)
mul(A,3);
for(i=A[0];i>=1;i--)
g<<A[i];
   }
  f.close();
  g.close();
return 0;
}

care e MAREA DIFERENTA?

Prima e sursa mea din concurs si mi-a dat MLE la toate testele.
Cealalta e solutia oficiala(una dintre multe altele).


Titlul: Răspuns: OJI 2012
Scris de: Mihai-Alexandru Dusmanu din Martie 04, 2012, 12:16:19
Pai diferenta este ca tu ai declarat asa
Cod:
int a[500000]
Chestia asta inseamna aproximativ 2 MB de memorie, iar tu aveai disponibil doar 1MB. La OJI / ONI trb sa ai foarte mare grija la memoria declarata, deoarece nu este ca pe infoarena (aici ti se pune doar memoria folosita). Si, din pacate, in cazuri ca acesta nu se poate face nimic :( (Am avut si eu aceeasi problema la ONI anu' trecut si am pierdut vreo 70 de puncte :D ).


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Martie 04, 2012, 13:11:37
Nu stiti la facultate este olimpiada si pentru studenti? Sunt in clasa a XII-a si abia am prins gustul olimpiadei. Imi pare rau ca nu m-am apucat sa lucrez intens mai devreme. Imi place foarte mult sa codez.


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 04, 2012, 14:12:20
Citat
Cel mai scurt drum dintre două puncte în plan se obţine pe linie dreaptă. Astfel dacă eliminăm porţiunile de traversare a pistelor de biciclete, traseul lui Gigel către prietenul lui trebuie să fie un segment. Această lungime se calculează cu teorema lui Pitagora, la care se adaugă lungimile de traversare orizontală şi verticală.
Soluţia nu este unică de fiecare dată! Dacă traseul lui Gigel intersectează punctul de intâlnire a două piste de biciclete, numărul soluţiilor se dublează, fiindcă Gigel poate traversa zona în două moduri: orizontal-vertical sau vertical-orizontal. În ambele cazuri două laturi alăturate  ale aceluiaşi dreptunghi, deci ambele sunt soluţii corecte. Astfel, numărul soluţiilor distincte pentru orice teste de intrare este o putere a lui 2.
:banana:

Baftă pe mai departe celor care s-au calificat, ne vedem la anul.


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 04, 2012, 16:49:36
Pai diferenta este ca tu ai declarat asa
Cod:
int a[500000]
Chestia asta inseamna aproximativ 2 MB de memorie, iar tu aveai disponibil doar 1MB. La OJI / ONI trb sa ai foarte mare grija la memoria declarata, deoarece nu este ca pe infoarena (aici ti se pune doar memoria folosita). Si, din pacate, in cazuri ca acesta nu se poate face nimic :( (Am avut si eu aceeasi problema la ONI anu' trecut si am pierdut vreo 70 de puncte :D ).

OK. Dar cum calculez cata memorie folosesc?

Si in plus de asta ai vazut ce punctaje sau luat, nu trebuia sa avem memorie ceva mai mare, ca la 11-12 ?


Titlul: Răspuns: OJI 2012
Scris de: Mihai-Alexandru Dusmanu din Martie 04, 2012, 17:05:37
OK. Dar cum calculez cata memorie folosesc?

Si in plus de asta ai vazut ce punctaje sau luat, nu trebuia sa avem memorie ceva mai mare, ca la 11-12 ?

In general, pentru a vedea cati MB ocupa un vector poti sa folosesti urmatoarea comanda:
Cod:
printf("%lf", 1.0 * sizeof(a) / 1024 / 1024);
unde a este vectorul pentru care vrei sa vezi ce dimensiune ocupa (orientativ) .

In legatura cu punctajele, nu stiu ce sa zic. Nu sunt in masura sa comentez limitele de memorie ale problemelor. Poate ca exact asta s-a dorit a fi cea mai mare dificultate a primei probleme (daca nu ma insel, culori era prima) : gasirea unei solutii "cat mai optime" din pdv al memoriei.


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 04, 2012, 17:25:39
In legatura cu punctajele, nu stiu ce sa zic. Nu sunt in masura sa comentez limitele de memorie ale problemelor. Poate ca exact asta s-a dorit a fi cea mai mare dificultate a primei probleme (daca nu ma insel, culori era prima) : gasirea unei solutii "cat mai optime" din pdv al memoriei.

De obicei, un program optim e unul cu timp de rulare cat mai mic. De aceea au pus timp : 0.2 sec. La "Culori"(care era defapt a 2-a) au pus si o conditie suplimenatara la Restrictii "N<=45" ca sa vezi ca nu e ca raspuns "un numar format pe 15 cifre" (maxim pe categoria intregi). Daca e numar mai mare de 15 cifre inseamna ca e pe numere mari exact cum cerea si problema.

Plus de asta daca nu ma crezi poti face un back-tracking de proba (exact cum am facut eu acolo) sa vezi ca dupa N>20 problema iese din timp, iar pt N=19 solutia era formata din 6 cifre, deci pt N=5000 solutia avea ceva "cifre".


In legatura cu memoria nu au fost nici ei prea corecti. La prima prob. au dat 4MB cu 3MB pt stiva. Daca ce zici tu e adevarat inseamna ca acum eram calificat la ONI.



Titlul: Răspuns: OJI 2012
Scris de: Visan Radu din Martie 04, 2012, 17:43:20
La culori eu am facut un back care mergea in 0.198 sec pt n=28, mai mult nu mai mergea si am luat doar 10 pct. :thumbdown:


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 04, 2012, 19:06:50
La culori eu am facut un back care mergea in 0.198 sec pt n=28, mai mult nu mai mergea si am luat doar 10 pct. :thumbdown:

Tu ai folosit codeblocks?

Eu am avut un rapan de calculator si la tastatura numerica semnul " / " era defapt semnul " * ", si invers.


Titlul: Răspuns: OJI 2012
Scris de: Visan Radu din Martie 04, 2012, 19:10:28
MinGW am folosit. Eu am avut singurul monitor din ala mare din toata sala, palpaia imaginea, tastatura tot trecea in romana. Pe langa astea, au facut olimpiada in 3 scoli ca nu aveau destule calculatoare.


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 04, 2012, 20:18:42
MinGW am folosit. Eu am avut singurul monitor din ala mare din toata sala, palpaia imaginea, tastatura tot trecea in romana. Pe langa astea, au facut olimpiada in 3 scoli ca nu aveau destule calculatoare.

Dar atunci cum ai aflat timpul de executie? Pe minGW 2.05 dupa ce se termina rularea programului iti scrie 2 randuri , iar pe unu din ele "return 0"(sau o val pe care o scrii tu dupa return). In schimb pe codeblocks, pe pagina compilatorului iti afiseaza si timpul de executie cu  mii-mi in coada.


Titlul: Răspuns: OJI 2012
Scris de: Mihai-Alexandru Dusmanu din Martie 04, 2012, 20:31:29
Dar atunci cum ai aflat timpul de executie? Pe minGW 2.05 dupa ce se termina rularea programului iti scrie 2 randuri , iar pe unu din ele "return 0"(sau o val pe care o scrii tu dupa return). In schimb pe codeblocks, pe pagina compilatorului iti afiseaza si timpul de executie cu  mii-mi in coada.

O solutie ar fi asta:
Cod:
#include <ctime>

...

int main() {
    clock_t t1, t2;

    t1 = clock();

    //program

    t2 = clock();

    double diff = 1.0 * t2 - 1.0 * t1;

    printf("%lf", diff / CLOCKS_PER_SEC);

    return 0;
}


Titlul: Răspuns: OJI 2012
Scris de: Visan Radu din Martie 04, 2012, 21:21:49
Pai <ctime>, 2 variabile double, start si stop, unde vrei sa inceapa sa contorizeze start=clock(), unde sa se opreasca stop=clock si apoi printf("%lf", (stop-start)/CLOCKS_PER_SEC).



LE:seamana cu ce a scris Mihai mai sus


Titlul: Răspuns: OJI 2012
Scris de: Vlad Eugen Dornescu din Martie 04, 2012, 22:08:18
Foarte inspirat autorul de la problema 'parc' (Sa copieze o problema dintr-o carte prafuita de mate si s-o propuna la OJI, in loc sa propuna un graf, un arbore, UN CEVA sa puteti departaja concurentii corect ... Nu-i de mirare ca au fost multe surprize ... neplacute din pacate


Titlul: Răspuns: OJI 2012
Scris de: Petru Trimbitas din Martie 04, 2012, 22:20:55
Foarte inspirat autorul de la problema 'parc' (Sa copieze o problema dintr-o carte prafuita de mate si s-o propuna la OJI, in loc sa propuna un graf, un arbore, UN CEVA sa puteti departaja concurentii corect ... Nu-i de mirare ca au fost multe surprize ... neplacute din pacate
De unde a copiat-o ?

Departajarea chiar ca a fost proasta.


Titlul: Răspuns: OJI 2012
Scris de: Cosmin Negruseri din Martie 04, 2012, 23:16:57
Dornescule am citit problema parc si pare foarte ok. Ca are o sursa sau alta de inspiratie nu schimba faptul ca e o problema draguta.

Ce legatura are asta cu suprizele tale?


Titlul: Răspuns: OJI 2012
Scris de: Mihai Calancea din Martie 04, 2012, 23:21:50
Dornescule am citit problema parc si pare foarte ok. Ca are o sursa sau alta de inspiratie nu schimba faptul ca e o problema draguta.

Ce legatura are asta cu suprizele tale?

Problema e ok, si mi s-ar fi parut misto sa apara la un SRM/runda de Codeforces. Dar la judeteana, intr-un asemenea set, mi se pare ca face o departajare proasta. Si asta e destul de evident pentru toata lumea..


Titlul: Răspuns: OJI 2012
Scris de: Cosmin Negruseri din Martie 04, 2012, 23:27:28
Vad scoruri foarte variate la ambele probleme la 11-12. Ai doua probleme pe care poti departaja, ambele cu ceva punctaje intermediare. Problemele nu au fost super dure. Au avut subpuncte pe care puteai lua puncte chiar daca nu le faceai pe amandoua. Nu stiu ce vreti mai mult de atat.

Tot timpu se poate mai bine da hai sa nu avem pretentii sa se lucreze la problemele de OJI cate un an inainte de concurs ca sa fie balansate perfect.


Titlul: Răspuns: OJI 2012
Scris de: FMI Romila Remus Arthur din Martie 04, 2012, 23:28:23
Care a fost, mai exact, sursa de inspiratie a autorului problemei Parc?


Titlul: Răspuns: OJI 2012
Scris de: Florin Chirica din Martie 04, 2012, 23:34:09
Stie cineva daca se organizeaza ONI By Net anul asta? :)

Multumesc.


Titlul: Răspuns: OJI 2012
Scris de: Fl. C. din Martie 04, 2012, 23:44:44
Stie cineva daca se organizeaza ONI By Net anul asta? :)

Multumesc.

Asa scrie in regulament:
Citat
Complementar etapei naționale a Olimpiadei de Informatică, se va organiza olimpiada online (InfONline), la care pot participa elevii care nu s-au calificat la etapa naţională a Olimpiadei de Informatică. Olimpiada online (InfONline) va utiliza subiectele şi testele de evaluare de la etapa națională a Olimpiadei de Informatică, după o metodologie specifică, care va fi publicată pe site-ul central al olimpiadei.


Titlul: Răspuns: OJI 2012
Scris de: Savin Tiberiu din Martie 05, 2012, 10:15:02
Si mie mi se pare draguta problema parc.


Titlul: Răspuns: OJI 2012
Scris de: Eugenie Daniel Posdarascu din Martie 05, 2012, 10:48:28
Salut,

Am calculat acum procentele pentru OJI (Bucuresti)  :( si e cam suparator (primul punctaj e ala de la OJI si celalalt e procentul )

clasa a IX-a         clasa a X-a      clasa a XI-a      clasa a XII-a   
134   70.27972028   120   61.53846154   56   34.92723493   54   32.99389002
130   68.18181818   115   58.97435897   53   33.05613306   49   29.9389002
121   63.46153846   113   57.94871795   48   29.93762994   48   29.32790224
110   57.69230769   110   56.41025641   42   26.1954262   48   29.32790224
110   57.69230769   103   52.82051282   41   25.57172557   43   26.27291242
106   55.59440559   100   51.28205128   34   21.20582121   40   24.43991853
100   52.44755245   95   48.71794872   32   19.95841996   38   23.21792261
94   49.3006993   85   43.58974359   31   19.33471933   32   19.55193483
92   48.25174825   82   42.05128205   29   18.08731809   25   15.27494908
88   46.15384615   45   23.07692308   27   16.83991684   20   12.21995927
74   38.81118881   35   17.94871795   27   16.83991684   17   10.38696538
70   36.71328671   35   17.94871795   25   15.59251559   12   7.33197556

totusi , nu sunt definitive (inca n-au afisat toate judetele )

Initiativa celor din Bucuresti mi se pare buna: primii 6 de la fiecare clasa se califica automat, iar celelalte 7 locuri se distribuie in functie de rezultatele la nivel national. DAR modul in care se face distribuirea mi se pare in neregula. De ce? Pentru ca indiferent cat de grele sunt subiectele primii 3 din tara tot vor avea punctaj foarte mare. De fapt vrei sa vezi IN GENERAL ce s-a intamplat la clasa respectiva, sa faci un fel de medie pentru toti concurentii. Daca se aplica regulamentul toate cele 7 locuri merg la clasele a IX-a si a X-a, ceea ce nu e deloc ok.

Parerea mea este ca daca tot califica primii 6 de la fiecare clasa (vb. de Bucuresti acum), macar ar putem sa faca media lui peste prajit in functie de primii 6 si nu primii 3. Ar fi putin mai echilibrat totusi.

PS: Regula oricum e proasta din toate punctele de vedere


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 05, 2012, 10:53:35
Cine poate si cand pune problemele de la OJI in arhiva, si poate si cele de la gimnaziu.....?

App, nu vi se pare ciudat ce s-a intamplat anu asta la OJI? Toata lumea sa aiba punctaje mici la clasele 10-12, iar la clasa a-10-a sa nu dea Lee (Alee, Insule, Rj, etc.), problemele din anii anteriori.

L.E.  Cui i s-a mai intamplat sa piarda 100 puncte sau o calificare din cauza ca declarat un vector prea mare ( culori - a[500000] (eu) si in sursa oficiala a[10000]- pt 100 pct.)?


Titlul: Răspuns: OJI 2012
Scris de: Petru Trimbitas din Martie 05, 2012, 14:31:50
Cine poate si cand pune problemele de la OJI in arhiva, si poate si cele de la gimnaziu.....?

App, nu vi se pare ciudat ce s-a intamplat anu asta la OJI? Toata lumea sa aiba punctaje mici la clasele 10-12, iar la clasa a-10-a sa nu dea Lee (Alee, Insule, Rj, etc.), problemele din anii anteriori.

L.E.  Cui i s-a mai intamplat sa piarda 100 puncte sau o calificare din cauza ca declarat un vector prea mare ( culori - a[500000] (eu) si in sursa oficiala a[10000]- pt 100 pct.)?

Si eu am pierdut 100 p anul trecut pt ca am scris int in loc de short intr-un loc :). Doar asa o sa inveti. Data urmatoare:

Cod:
cout<<sizeof(a)/(1000*1000)

Nu mi se pare deloc ciudat sa avem probleme originale la oji. Mi-ar fi placut o demonstratie a corectitudinii la problema parc :).


Titlul: Răspuns: OJI 2012
Scris de: Simoiu Robert din Martie 05, 2012, 15:25:57
AS putea baga eu pb. de la OJI anul asta :) ?


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 05, 2012, 19:11:16
Citat
Si eu am pierdut 100 p anul trecut pt ca am scris int in loc de short intr-un loc :). Doar asa o sa inveti. Data urmatoare:

Da, dar tu te-ia calificat la ONI , eu nu. La judetul meu s-au califcat 2 cu 25 pct fiecare. Daca stiam asta si mai stiam ca la prima prob. trebuia doar sa numar niste blestemate de stelute si la cealalta sa fac un simplu back pe care probabil luam vreo 20 pct. acum aveam 40 si eram calofocat de pe primul loc la ONI.


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 05, 2012, 19:11:51
AS putea baga eu pb. de la OJI anul asta :) ?

Daca poti e perfect! Mersi!


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 05, 2012, 19:54:36
@Alex, citez din pagina mea de profil
Citat
- am reuşit "performanța" să uit, în programul pentru un concurs, declarat un vector de 100000001 elemente
:-' m-a costat chestia asta 100 de puncte.

Nu mai fiți revoltați ca v-ați/nu v-ați calificat la ONI, eu nu m-am calificat și nu regret asta, știu că m-aș fi putut califica dacă nu aș fi șters o chestie din program (cel puțin presupun), dar știu că nu aș fi luat 200 de puncte, ceea ce înseamnă că mai am de lucru. Până la urmă la olimpiadă nu trebuie să fii bun, ci să fii mai bun ca alții, cum scria într-o carte căreia i-am uitat numele.

De-a drumu', sunt o grămadă de concursuri la care puteți participa înafară de olimpiadă, multe dintre ele mult mai bine organizate și cu subiecte mai interesante.


Titlul: Răspuns: OJI 2012
Scris de: Andrei Grigorean din Martie 05, 2012, 20:21:23
De-a drumu', sunt o grămadă de concursuri la care puteți participa înafară de olimpiadă, multe dintre ele mult mai bine organizate și cu subiecte mai interesante.

Va asteptam la Runda 4 (http://infoarena.ro/algoritmiada-2012/runda-4) a concursului Algoritmiada 2012! ;)


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 05, 2012, 20:25:57

Nu mai fiți revoltați ca v-ați/nu v-ați calificat la ONI, eu nu m-am calificat și nu regret asta, știu că m-aș fi putut califica dacă nu aș fi șters o chestie din program (cel puțin presupun), dar știu că nu aș fi luat 200 de puncte, ceea ce înseamnă că mai am de lucru. Până la urmă la olimpiadă nu trebuie să fii bun, ci să fii mai bun ca alții, cum scria într-o carte căreia i-am uitat numele.


Stai o secunda, aici e o mica diferenta intre tine si mine. Tu zici ca daca stergeai o chestie din program luai 100pct. Dar inainte sa termin ce am de zis vreau sa-mi raspunzi la o intrebare : "Iti rula programul si cu bug-ul ala?", sau doar iti dadea alte numere, sau mesaj de eroare in fereastra compilatorului?


Titlul: Răspuns: OJI 2012
Scris de: Ababab din Martie 05, 2012, 21:08:19
Scuze dacă m-am făcut înțeles greșit, nu mă comparam pe mine cu tine sau cu altcineva, tot ce vroiam să zic e că oricum nu făceam de 200, chiar dacă mai strângeam ceva să mă calific și eu.

În ce ai citat tu, eu am zis că dacă nu scoteam luam (probabil) 100, am scris în paginile anterioare care a fost motivul pentru care am scos acea parte. Probabil a fost vina mea, probabil nu, cine știe.


Titlul: Răspuns: OJI 2012
Scris de: Albu Alexandru din Martie 05, 2012, 21:16:48
Scuze dacă m-am făcut înțeles greșit, nu mă comparam pe mine cu tine sau cu altcineva, tot ce vroiam să zic e că oricum nu făceam de 200, chiar dacă mai strângeam ceva să mă calific și eu.

În ce ai citat tu, eu am zis că dacă nu scoteam luam (probabil) 100, am scris în paginile anterioare care a fost motivul pentru care am scos acea parte. Probabil a fost vina mea, probabil nu, cine știe.

Am stiut de la inceput ca nu la mine te-ai referit ci in general, dar eu vreau sa spun urmatoarea chestie: sunt clasa a-10-a si eu si prietenul meu cel mai bun am facut amandoi cate o problema(eu pe a 2-a, el pe prima). Mie mi-a dat raspunsul corect pentru orice test posibil pt. ca am facut-o si pe numere mari si cu recurenta exact ca in sursa oficiala, iar el a facut programul tot ca in sursa oficiala respectiv problemei lui, dar lui nu-i dadea raspunsul corect ( ii dadea un numar negativ foarte mare sau ceva de genu). Concluzie: el avea un bug in problema ( main() sau alta functie ) iar eu nu aveam nici un bug, ci doar am declarat vectorul prea mare. ( a[500000] in loc de a[10000] sau chiar a[5000] ).

Aici am vrut eu sa ajung. ( referitor la mesajul anterior ).


Titlul: Răspuns: OJI 2012
Scris de: Bogdan Ciubotaru din Martie 06, 2012, 10:44:05
Citat
#include <fstream>
using namespace std;

int main()
{
   ofstream g("parc.out");
   g<<11.472136<<"\n"<<1;
}

Sursa de 12 puncte la clasele 11-12 la problema parc ! Genial, nu ?


Titlul: Răspuns: OJI 2012
Scris de: Buleandra Cristian din Martie 06, 2012, 14:55:42
Citat
#include <fstream>
using namespace std;

int main()
{
   ofstream g("parc.out");
   g<<11.472136<<"\n"<<1;
}

Sursa de 12 puncte la clasele 11-12 la problema parc ! Genial, nu ?

Nu chiar... Era destul de previzibil ca o sa fie si teste in care este un singur drum. :D


Titlul: Răspuns: OJI 2012
Scris de: Bogdan Ciubotaru din Martie 06, 2012, 21:41:51
Dar din cate imi aduc aminte, vorbim despre OJI 2012 si suntem la un nivel net superior editiilor anterioare, nu ? :)


Titlul: Răspuns: OJI 2012
Scris de: Eugenie Daniel Posdarascu din Martie 07, 2012, 09:00:41
La nationala au fost faze mult mai penale. Gen un tip a afisat 3(primu numar care i-a venit in minte) si a luat 30 de puncte. Iar OJI nu poti spune ca este la un nivel foarte ridicat. 12 puncte nu mi se  pare a fi ceva extraordinar. E chiar ok pentru un caz particular. :)