|
Titlul: 300 Diviz Scris de: Adrian Diaconu din Ianuarie 21, 2007, 23:51:30 Aici puteţi discuta despre problema Diviz (http://infoarena.ro/problema/diviz).
Titlul: Raspuns: 300 Diviz Scris de: Sachelarie Bogdan din Februarie 07, 2007, 13:10:59 N-am inteles prea bine evitarea numararii de mai multe ori a unui subsir identic. In solutia oficiala scrie "pentru a numara subsirurile distincte ( adica sa nu numaram subsiruri egale de doua ori ), daca suntem in starea (j, i, r) actualizam starea (j+1, first[cif][i+1], (r*10+cif) mod K) daca si numai daca intre pozitiile i+1 si first[cif][i+1]-1 in numarul N nu mai apare nici o cifra cif", dar daca first[cif][i+1] indica prima pozitie a cifrei cif in numar, atunci conditia de mai sus sigur e indeplinita. Iau numa 20p pt ca nu implementez bine chestia asta. #-o
Titlul: Raspuns: 300 Diviz Scris de: Bogdan-Cristian Tataroiu din Februarie 07, 2007, 13:35:17 Nu stiu exact ce vroia sa zica autorul articolului, nici eu nu am inteles cand am citit :)
Starile (j, i, r) inseamna numarul de subsiruri care se termina fix la pozitia i, au lungimea j si dau restul r. Trebuie sa initializezi pentru subsirurile de lungime 1 doar primele aparitii ale fiecarei cifre, pentru a nu le numara de mai multe ori. Astfel starile (1, first[cif][0], cif % K) sunt initializate cu 1 pentru cif de la 1 la 9 (subsirurile trebuie sa fie nenule si trebuie sa nu inceapa cu 0), iar de la o stare (j, i, r) actualizezi tot timpul starea (j + 1, first[cif][i + 1], (r * 10 + cif) % K). Aduni pe parcurs toate starile cu j cuprins intre A si B si cu r == 0 si ai solutia. Titlul: Raspuns: 300 Diviz Scris de: Sachelarie Bogdan din Februarie 07, 2007, 14:09:13 -Dap. Asa iese. Ar trebui modificat articolul cu pricina. Totusi iau un tle pe ultimu test. [working on it...]
Titlul: Raspuns: 300 Diviz Scris de: Mircea Pasoi din Februarie 07, 2007, 22:58:27 -Dap. Asa iese. Ar trebui modificat articolul cu pricina. Totusi iau un tle pe ultimu test. [working on it...] E wiki, poate modifica oricine. Titlul: Raspuns: 300 Diviz Scris de: David si Goliat din Februarie 25, 2007, 21:52:16 E ceva special pe testele 3,4,6,7,8,9,10 ?? Ca iau la toate incorect
Titlul: Răspuns: 300 Diviz Scris de: Airinei Adrian din Februarie 25, 2007, 23:04:14 Nu cred ca sunt speciale atatea teste, ai un bug ceva in program. Uite un test mai mic, poate te ajuta
Cod: 10 3 7 Cod: 60 Titlul: Răspuns: 300 Diviz Scris de: David si Goliat din Februarie 25, 2007, 23:16:37 da, imi da 60
Titlul: Răspuns: 300 Diviz Scris de: Airinei Adrian din Februarie 25, 2007, 23:19:49 In cazul asta da-ti teste singur, fa un brute-force si compara rezultatele cu programul tau. Ar trebui sa gasesti repede ca la prea multe teste ai WA.
Titlul: Răspuns: 300 Diviz Scris de: Salajan Razvan din August 17, 2012, 16:27:33 Salut ! Am facut si eu o dinamica in B*N*K*10 dar iau TLE pe ultimul test; ceva idei de optimizare : http://infoarena.ro/job_detail/779421?action=view-source .
Titlul: Răspuns: 300 Diviz Scris de: Emanuel Nrx din Decembrie 13, 2015, 01:14:02 Stiu ca nu s-a mai postat de mult timp la problema aceasta, dar nu cumva limita de timp este cam mica? Adica initial era mai mare de 0.2 secunde, iar acum sunt foarte multe surse (printre care si a mea) care primesc 90 pct cu tle pe ultimul test. Daca se poate sa se mareasca limita cu 0.05 secunde ar fi nemaipomenit :D
Titlul: Răspuns: 300 Diviz Scris de: Adrian Budau din Decembrie 16, 2015, 00:26:30 Da, am marit cu 0.05 ca sa pastram regula cu limite de timp de 2 ori cat sursa oficiala. Am reevaluat toate surseled in 2013 incoace.
|