OJI 2012

[•gabitzish1]

Succes maine tuturor!
Cei mai buni sa se califice la ONI ! 

[•klamathix]

Bafta tuturor!

[•psycho21r]

Baftă tuturor și din partea mea.

[•flaviusc11]

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?

[•balakraz94]

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.

[•flaviusc11]

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.

[•S7012MY]

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 ?

[•flaviusc11]

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.

[•CezarMocan]

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.

[•S7012MY]

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.

[•flaviusc11]

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.

[•soriyn]

La prima pana la urma care e complexitatea optima ? Eu aveam O(n*k^2)

[•viSuaL9]

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 ).

[•psycho21r]

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?

[•ionutz32]

In caz ca ii trebuie cuiva evaluatoarele... http://ler.is.edu.ro/~cex_is/Informatica/pregatire.html

[•fulgerulnegru]

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?

[•psycho21r]

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.

[•fulgerulnegru]

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?

[•caen1]

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)

[•visanr]

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..

[•dornescuvlad]

Trebuia sa afisezi ceva, orice, pe prima linie .... si ti s-ar fi luat in considerare a doua ... 

[•fulgerulnegru]

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

[•federer]

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.

[•caen1]

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

[MoroJr]

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

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  !