Bacalaureat 2011

[•dany123]

Mda, e dezastru national cu BAC-ul asta, sub 50% promovabilitate... Voi ce-ati facut? sper ca nu se pune problema de trecut, eu am luat 8.70 la info, chiar cu 0.10 mai mult decat ma asteptam, iar media 8.55, ceea ce e ok, zic eu.

[•PlayLikeNeverB4]

Eu 9.40 la info. Habar n-am ce am gresit, dar asta e.

[•moon]

Nu pot sa cred asa ceva... Corectorii de la proba de informatica sunt incompetenti din toate punctele de vedere. Un tip rezolva ultima problema cu un for , de la 10000 la 99999, iar la explicatie spune ("Programul este eficient pentru ca ia doar numerele de 5 cifre") . A luat 10 curat. Asta e bataie de joc da-o incolo. Si asa au facut la toti !!!! Cei ce au rezolvat problema INEFICIENT au luat 10 puncte. RESTUL SUB 5. Rusine sa le fie profesorilor corectori !!!!!!!!!!!!!!!!!!!!!!

[•PlayLikeNeverB4]

Pai da ma, ia doar numerele de 5 cifre in loc sa ia multimea tuturor numerelor naturale  

P.S.: Ce ma enerveaza pe mine e ca pe astia cu 10 la info nu-i vezi la olimpiada sa faca mare branza. (sa nu generalizam, desigur, dar majoritatea)

[•skull]

Eu 9.40 la info. Habar n-am ce am gresit, dar asta e.

Sunt exact in aceeasi situatie. Cum sa ai pretentii sa fie corectori buni cand nici macar pe barem n-au fost in stare sa puna un algoritm corect...

[•moon]

E clar... daca folosesti mai mult de 2 variabile si un for in program, bagi corectorii in ceata.

[•SpiderMan]

Acum eu nu sunt pe a 12-a si poate nu sunt in masura sa comentez, dar pot spune ca informatica nu e o materie foarte usoara, dar bac-ul nu e asa de greu. Acum, daca profesorii astia sunt batuti in cap, sa-i scoata naibii afara, si sa puna profesori care au ceva in cap si care pot face fata si la algoritmi mai rigurosi, in acelasi timp corecti, nu doar ce-i pe barem. De ce trebuie sa ne facem noi romanii de rahat, facand lucruri aiurea, de ce trebuie sa fim noi speciali tot timpul, cand de fapt nu suntem. Mai bine sa corecteze profesorii capabili, si atat . Parerea mea.  Sa va fie rusine !

[•PlayLikeNeverB4]

Sau daca sunt incapabili sa inteleaga un algoritm, sa-l scrie pe calculator si sa se uite daca da bine. Ma rog, asta ar lua cam mult timp, dar daca altfel nu se poate...

[•moon]

Nu ar merge asa... profesorii trebuie sa-si dea seama ce a vrut sa faca elevul. Daca spre exemplu un elev baga un quicksort la ultima problema si scrie un algoritm de o pagina , dar greseste o variabila ? Then what ?

[•PlayLikeNeverB4]

Mda, ziceam si eu... In fine, nu mai conteaza. A trecut.

[•pauldb]

Ar fi minunat daca chiar ar exista profesorii astia capabili despre care vorbiti voi, dar eu sincer nu cred ca exista. Putinii profesori buni din tara prefera (probabil) sa-si investeasca timpul in elevii care merita si care au potential pentru olimpiada. Ce este mai ingrijorator insa, este ca nici viitorii profesori nu sunt cu nimic mai buni. Am colegi de facultate, cu dreptul de a deveni profesori si cu note mari la practica, care au probleme cand vine vorba sa stearga un caracter dintr-un sir de caractere. Si in general te-ai astepta ca macar un student proaspat absolvit sa fie in stare sa faca asa ceva. E foarte trist ce se intampla acum in Romania.

[•moon]

Aveti cumva idee cine se ocupa de contestatii ? E vreo comisie speciala la Bucuresti ? Sau iar o sa dau peste niste profesori incapabili   A ajuns sa-mi traga informatica ( 8.70 ) media in jos...

Si am avut o singura greseala minuscula... am pus for(i=1;i<=s1;i++) in loc de for(i=1;i<=s1 && i<=9;i++) la ultima problema. Dar de aici pana la 8.70.... of....

[•moon]

Am avut noroc cu corectorii ( de la Colegiul National "Mircea cel Batran" Constanta) ... am luat 9,80.

[•dany123]

A mai dat cineva admiterea la mate-info (unibuc) azi?
La problema de info eu n-am avut alta idee decat backtracking si merge destul de bine pana la n=20, apoi timpul creste destul de mult...
Bineinteles ca problema n-avea nici macar un exemplu de date de intrare (sau macar o limita la n-ul ala), iar baremul ca de obicei fara niciun program in el..

Solutiile mele sunt astea, sper sa fie corecte. A gasit cineva o metoda mai rapida sau o formula directa (cum imi zicea un coleg).

( link: subiect, barem )

Cod:

Pt n= 1 produsul maxim este: 1
Pt n= 2 produsul maxim este: 2
Pt n= 3 produsul maxim este: 3
Pt n= 4 produsul maxim este: 4
Pt n= 5 produsul maxim este: 6
Pt n= 6 produsul maxim este: 9
Pt n= 7 produsul maxim este: 12
Pt n= 8 produsul maxim este: 18
Pt n= 9 produsul maxim este: 27
Pt n= 10 produsul maxim este: 36
Pt n= 11 produsul maxim este: 54
Pt n= 12 produsul maxim este: 81
Pt n= 13 produsul maxim este: 108
Pt n= 14 produsul maxim este: 162
Pt n= 15 produsul maxim este: 243
Pt n= 16 produsul maxim este: 324
Pt n= 17 produsul maxim este: 486
Pt n= 18 produsul maxim este: 729
Pt n= 19 produsul maxim este: 972
Pt n= 20 produsul maxim este: 1458
Pt n= 21 produsul maxim este: 2187
Pt n= 22 produsul maxim este: 2916
Pt n= 23 produsul maxim este: 4374 (1-2 sec)
Pt n= 24 produsul maxim este: 6561
Pt n= 25 produsul maxim este: 8748
Pt n= 26 produsul maxim este: 13122
Pt n= 27 produsul maxim este: 19683 (21 secunde)
...etc

Daca raspunsurile astea sunt cele corecte atunci vad ca produsul maxim iese din descompunerea lui n in suma de 3-uri si 2-uri, cu cat mai multi 3 (ex: 27= 3+3+3+..+3 (de 9 ori) => produsul = 3^9 = 19683).  de ce imi vin ideile deabea acum 

[•PlayLikeNeverB4]

Solutia mea este urmatoarea: Pentru fiecare K de la 1 la N calculezi produsul maxim. Acel produs maxim se calculeaza astfel: Fie v[i]=numarul de elemente alea subvectorului cu numarul i. Initial luam cate 1 element in fiecare subvector, dupa care adaugam pe rand cate unul in fiecare pana ajungem la un total de N elemente. In acest moment calculam produsul v[1] * v[2] * ... * v[k].
Mi-au dat rezultatele la fel, deci ma gandesc ca e bine, chiar daca nu iti pot justifica solutia. A fost doar asa intuitiv. Probabil exista si metode mai eficiente, insa oricum e mai bine decat backtracking.

Asa ceva:

Cod:

#include <iostream>
using namespace std;

int i,j,k,N;
int v[1000];
long long P,Pmax;

int main()
{
	cout << "n= "; cin >> N;
	for(k=1;k<=N;k++)
	{
		for(i=1;i<=k;i++) v[i]=1;
		for(i=1,j=N-k;j;j--,i++)
		{
			v[i]++;
			if(i==k) i=0;
		}
		for(i=1,P=1;i<=k;i++)
			P*=v[i];
		Pmax=max(P,Pmax);
	}
	cout << "Produsul maxim: " << Pmax << '\n';
}

[•dany123]

Exact pe acelasi principiu am mers si eu doar ca solutia ta e mult mai eleganta.. si eficienta...

[•auRSTAR]

Poti rezolva problema prin programare dinamica

Cod:

	sol[0]=sol[1]=1;
	for(i=2;i<=n;i++)
		for(j=i-1;j>=0;--j)sol[i]=max(sol[i],sol[j]*(i-j));

[•mathboy]

Cred ca ar merge o dinamica gen P[ i ] - produsul maxim pe care il poti obtine pornind cu i elemente in vector.
P[0] = 1;
P[ i ] = max(P[i - 1] * 1, P[i - 2] * 2, P[i - 3] * 3...., P[i - k] * k), k <= i; (adaugi 1, 2 .... k)

Observam ca cel mai bine este sa adaugam de fiecare data 3 pentru i >= 4 => P[ i ] = P[i - 3] * 3;
[LE] Acum am vazut ca a mai postat cineva solutia cu programare dinamica. Ma gandesc ca ar prinde bine cuiva o explicatie

[•PlayLikeNeverB4]

Wow, foarte tare. E mult mai elegant cu programare dinamica, insa complexitatea e aceeasi ca si la solutia mea, nu? O(N^2)

[•skull]

Daca vrei eficienta poti sa faci liniar, desi e mult mai frumos cu dinamica.

Cod:

int main ()
{
    int N, rez = 1;
    cin >> N;
    while ( N )
    {
        if ( N >= 3 && N != 4) { rez *= 3; N -= 3; }
        if ( N == 4 ) { rez *= 4; N -= 4; }
        if ( N == 2 ) { rez *= 2; N -= 2; }
        if ( N == 1 ) { rez = 1; N--; }
    }
    cout << rez;
    return 0;
}

Sau verifici direct restul impartirii lui N la 3 si ridici la putere in timp logaritmic si devine si mai eficient.

[•MciprianM]

Puteti testa solutiile aici.
Si pe infoarena s-a mai discutat legat de problema asta: link