Pcb este o problemă frumoasă, dar cred că a avut mereu o neclaritate în enunț. Zice așa: "Antonio doreşte să aprindă toate becurile din intervalul [1, X]". Dar nu menționează că celelalte becuri trebuie să fie obligatoriu stinse.

Ambele probleme se rezolvă cu șmenul lui Mars.

Solutiile sunt postate aici http://www.infoarena.ro/preoji2016/solutii. Sper ca in scurt timp toate problemele sa aiba rezolvarile.

Multumesc,o sa incerc o rezolvare mai "matematica"

Nu e vorba de asta. Probabil este din cauza ca sunt teste in care tot intervalul de la 1 la 500000 este zero. Nu ai prevazut acest caz.

Multumesc, Adrian. Acum pare totul in regula.

Mai e un lucru ciudat: am facut problema compact2 de 100 de puncte si imi afizeaza in continuare 30p la scor.

Buna ziua,
Daca am problema Defrag facuta de 100, de ce nu pot vedea celelalte surse?

Vreau să spun două lucruri:
1. Aur, Aur, Aur, Aur
2. Zdrobiți-i pe chinezi

Solution to Problem#1

Suppose we have the function DownHeap(k, n). This function takes A[k] and unifies the heap A[2*k] with the heap A[2*k+1]. Using this function, we can create now the entire heap with the function

Cod:

void MakeHeap()
{
   for (i=n/2; i>=1; i--)
	DownHeap(i, n);
}

Let’s consider h=log(n) the number of levels in this heap. DownHeap(k, n) function uses only nodes from the levels 0..h-1. For each node from the level i there are al most h-i descents in heap. But on the level i and are 2^i nodes. So the number of operations is given by the sum ((h-i) * 2^i), i = 0..h-1. Elementary mathematical calculations show that this amount is less than 2*n. So the complexity of creating heap is O(n).

Interestingly, a former student of mine received at an interview the following problem: Given an array of length n which is the inorder-traversal of a binary tree, organize the array as a min-heap in O (n) time complexity. But the problem that I have just given the solution is known to have O (n) time complexity. Strange problem, in my opinion.

I apologize for my very bad English.

Draga prietene, intr-adevar nu se precizeaza ca nu ai voie STL, la fel cum nu precizeaza daca ai sau voie cu sabii ninja la BAC. Ce zici, ai voie? Nici armele atomice nu sunt interzise explicit. Se pare ca s-au omis multe lucruri in programa de bac.

Lasand gluma la o parte, eu am impresia ca STL se foloseste in general in olimpiade si concursuri. E mai comod sa le utilizezi decat sa implementezi de exemplu o coada de prioritati.
Daca mergi sa te angajezi la un job de Java, degeaba zici de lower_bound din STL ca s-ar putea sa nu fii inteles, desi exista si in Java functii de cautare binara. La facultati am vazut chiar anunturi explicite prin care se precizeaza ca nu ai voie cu STL.

Nu e voie cu STL, programa de bac e foarte clara. De altfel nici la admitere la facultati nu e voie cu STL.

Concursul live al zilei a doua este aici:
http://boi2014.etu.edu.tr:8890/Ranking.html

Revin cu cateva modificari, s-au mai acordat niste minute in plus concurentilor din cauza unor probleme de la o problema. Baietii nostri s-au mai zbatut pentru niste puncte, deci punctajele corecte sunt;

Dupa ziua I situatia in clasament este:
1. Un bulgar - 225 puncte
2. Mihai Andreescu - 200 puncte
....
10.Radu Szasz - 87 puncte
10.Mihai Gheorghe - 87 puncte
13. Tudor Tiplea - 82 puncte

Avem deci un aur, trei argint.

Rezultatele barajului 2 de la Vaslui sunt pe pagina oficiala:
http://lspvs.ro/lot2014/?pag=rezultateSeniori
http://lspvs.ro/lot2014/?pag=rezultateJuniori
In curand vor fi postate si problemele de azi.
Incercam sa fim prompti pentru toti cei interesati.

Rezultatele din prima zi sunt pe pagina oficiala:
http://lspvs.ro/lot2014/?pag=rezultateSeniori
http://lspvs.ro/lot2014/?pag=rezultateJuniori

In perioada 7-14 mai 2014 va avea loc la Vaslui a doua tabara de pregatire si selectie a lotului national de informatica.
Pagina oficiala: http://lspvs.ro/lot2014/

Din cate tin eu minte, de obicei se face o sedinta imediat dupa probele de ONI sau dupa baraj si se discuta. Anul trecut de exemplu parca nu s-a facut, nu mai tin minte exact. Si eu sustin OJI cu 3 probleme in 4 ore. Facem lobby printre membrii comisiei nationale si discutam cu doamna Dumitriu si daca suntem multi care sustinem asta, atunci se poate schimba. Wef, concluzia este ca trebuie sa vii iar in comisii la ONI !

Buna seara tuturor,
Vreau in primul rand sa felicit atat pe elevii care s-au calificat la ONI, cat si pe cei care nu s-au calificat.
Opinia mea este ca topicuri precum acesta nu ar trebui deschise. Sunt pline de frustrari. Iata doua motive pentru care spun asta:
1. In orice competitii, fie sportive, fie scolare se dau sanse egale tuturor tarilor. Daca nu ar fi asa, la Campionatul Mondial de Fotbal s-ar califica numai vreo doua tari sud-americane si restul europene.
2. La OJI nu prea conteaza punctajul. Important este sa fii sau nu calificat. Faptul ca in acest an concurentul Velea a luat 200 puncte la OJI nu inseamna nimic. Unii ating forma maxima atunci cand trebuie (la ONI/baraj/loturi), altii OJI e punctul maxim. Priviti un clasament de anul trecut de la OJI
http://olimpiada.info/oji2013/index.php?cid=rezultate&w=lic&judet=&clasa=12
Si apoi cautati clasamentul de la ONI. Eu am gasit cu usurinta un elev calificat la OJI cu 59 puncte care l-a intrecut pe unul cu 200. Si nu e singurul exemplu, cautati si veti gasi nenumarate. Q.e.d.
3. Daca punctajele de la OJI conteaza asa de mult, atunci ce rost mai are faza nationala?

Spor va doresc tuturor.

Prietene, parerea mea este ca ar trebui sa ceri ajutorul profesorului tau de informatica. Faptul ca inveti structuri inseamna ca esti probabil in clasa a X-a deja. Eroarea din programul tau este asemanatoare cu eroarea din urmatoarea secventa:

Cod:

for (i = 1; 1 <= 100; i++)
   cin >> n;
for (i = 1; 1 <= 100; i++)
  cout << n;

Sigur nu iti va afisa 100 de valori distincte.
Apleaca-te mai cu atentie asupra teoriei si problemelor simple daca vrei sa devii informatician.
Succes.

Concursul (ziua 2) este live pe aceeasi adresa ca si in prima zi:
http://ceoi2013.hsin.hr/index.php?page=live_results

Avem in acest moment urmatoarele rezultate:
Andrei Heidelbacher - aur
Mihai Popa - argint
Silviu Popescu - bronz
Daniel Posdarascu - bronz

Pe tari:
Croatia - 1 aur, 2 argint
Romania - 1 aur, 1 argint, 2 bronz
Slovacia - 1 aur, 1 bronz
Polonia - 2 argint
Cehia - 1 argint, 1 bronz
Ungaria - 2 bronz
...

Felicitari baietilor, cred ca rezultatele sunt foarte bune!

Salutari tuturor infoarenautilor!

Daca doriti sa urmariti live rezultatele de la CEOI:
http://ceoi2013.hsin.hr/index.php?page=live_results

Succes baietilor!