In caz ca va intrebati de ce unele surse iau 90, 95 si nu suta:

"Cârtita doreste sa se plimbe prin toate galeriile de sub teren trecând o singura data prin fiecare, dar pentru acest lucru trebuie sa ajunga nevatamata mergând la suprafata terenului la un patratel de unde sa intre în sistemul de galerii."

Cateva surse (pana si oficiale) nu iau in considerare acest aspect si incep euler-ul din nodul 1. Pe testul 5 acest lucru este gresit, deoarece nodul 1 al galeriei este pazit de catre o vulpe.

Asadar am introdus in eval si cazul acesta particular pentru ca sa se respecte pe deplin cerinta (sa fie identic cu OJI unde s-au luat multe punctaje de 95)

Se mai fac astea de la OJI disponibile? 

Cateva is deja gata. Ce se intampla cu restu?! Am inteles ca pana in iunie trebuiau puse pe site 

Limita de timp a fost marita la 0.4. Imi cer scuze pentru neplacerile create.

Prin backtracking inteleg acele metode in care incerci solutii si apoi le verifici.

Da, iei pe rand fiecare combinatie posibila de numere. Insa, pentru a afisa in ordine crescatoare dupa S si pentru a evita solutiile invalide apar niste complicatii. 

O metoda ar fi sa faci pentru toate S-urile un back(int k, int sum, int sum_now) (k ii pozitia curenta pentru care generezi, sum ii suma la care vrei sa se ajunga, sum_now ii suma curenta a numerelor pana la pozitia k-1, inclusiv)
De asemenea, retinerii sumei partiale pentru fiecare element ajuta pentru calcularea mai rapida. (sp[ i ] = sp[ i-1 ] + a[ i ])

pentru fiecare pozitie k va fi un for in care se testeaza elementele:

Cod:

void back(int k, int sum, int sum_now) {
        for(int i = max (0, sum - sum_now - (sp[ m ] - sp[ k ]); i <= min(sum - sum_now, a[ k ]); ++i) {
               v[ k ] = i;
               back(k+1, sum, sum_now + i);
       }
}

max (0, sum - sum_now - (sp[ m ] - sp[ k ]) - verifica cazul in care toate elementele de la k+1 pana la m vor fi maxime, astfel incat sa se evite problema solutiilor invalide (in care suma obinuta in back e mai mica decat ar trebui sa fie)

Nu ar trebui sa se obtina nici duplicate, nici solutii invalide cand ajungi la k maxim. 

Nu. Problema nu e din ceva concurs, e din viata reala, deci putem fi flexibili.

Orice alta precizare poate modifica radical algoritmul, inclusiv ordinea aceea cand S-urile sunt egale.

Daca nu ma insel, tot timpul vor exista (a[1] + 1) * (a[2] + 1) * (a[3] + 1) *... * (a[m] + 1) solutii. (Incerci sa obtii toate combinatiile posibile). Nu exista algoritmi care au complexitatea mai buna decat Backtracking.

LE: Se pot aplica optimizari, precum cele care le-ai precizat mai sus, dar in fond tot backtracking este 

Mai sunt si alte restrictii si precizari?

Care este ordinea de generare cand suma este aceeasi? (b-urile alea sunt sortate sau nu?)

Am trimis o sursă care află corect doar T, și am primit 0 puncte...
Presupun că nu se respectă condiția: Se acordă: 40% din punctaj pentru determinarea corectă a numărului T

Da, aici ai dreptate, am uitat sa pun evaluator la problema. Multumesc pentru ca ai postat.  

LE: Un evaluator a fost adaugat iar sursele au fost reevaluate. Imi cer scuze pentru neplacerile create.

Aici testele nu sunt publice. Problema aceasta a fost data la un concurs ce a avut loc pe site, poate asta http://www.infoarena.ro/happy-coding-2006/solutii te ajuta.

1 ≤ N ≤ 10^9

Tu inmultesti tot odata si e normal sa iti faca overflow. Fa cate o inmultire si apoi modulo.

Cod:

 -2
388.631
-2
-2
1351.801
-2
1111.424
-2
176.357
586.031
-2
-2
-2
-2
-2
-2
1414.214

pentru m = 3, trebuie calculat (2 ^ k) % (m - 1), adica (2 ^ k) % 2 = 0. rezulta ca oricat ar fi a, am calcula (a ^ 0 + 1) % m = 2. Asta nu e valabil pentru testul 4 1 3

Foarte grele problemele. 27/85 au scos mai mult de zero.

Cat legat de problema Bacterii, pentru orice numar prim P = 2 ^ x + 1 nu functioneaza teorema lui Fermat. (m = 3 cazul cel mai evident)

Testele la problema asta sunt busite sau restrictia asta nu e in regula:

Cod:

1 ≤ v[i] ≤ 2 * 10^9

http://www.infoarena.ro/job_detail/951076?action=view-source sursa asta ia suta. Am declarat un vector de frecventa pentru numere mai mai mici decat 10^6 si nu am luat Killed by signal.

Bravo!

Pentru exemplul al doilea 1 2 3 2 3 1 4 3 4 nu este un raspuns valid? Fiecare combo posibil are o singura aparitie, iar numarul de resetari este minim.

LE: Nu apare fiecare combo posibil(lipseste 1 4 3 2 spre exemplu), doar secventa de taste apare fara sa fie necesara resetarea.

Stiti ceva de clasament?

Felicitari si la mai multe in continuare