Afişează mesaje
Am vazut niste idei de rez a problemei de am cazut in cur da io zic ca cel mai usor s-ar face cum am facut-o io 
!!! cine nu vrea sa stie rezolvarea sa nu citeasca mai departe!!!!
Se face cu un algoritm arhicunoscut:greedy daca stim ca trebuie sa fie prima din punct de vedere lexicografic atunci punem tot timpu 0 si numa daca nu se poate(un sir de booleane ne spune daca o fost luat nr sau nu) atunci punem 1 si nu mai veificam nimic(ceea ce reduce marimea sirului la jumatate).Mai trebuie facuta o precizare imp.:la inceput se pun n de 0 si la sf n-1 de 0 si atunce cand pornim greedyu toate nr de forma 10000, 1100 ,1110 se iau ca si cum ar fi folosite si dupa ce se termina greedy punem zerourile ca sa apara si ele.
prin metoda asta nu ne trebuie decat un singur sir 500.000 de booleane care daca chiar vreau se poate trece in lucru pe biti si si face mult mai mic da neeee
!
io am luat 100 asa ca puti incerca
Nu se poate spune ca e greedy, considera urmatorul contraexemplu: sa zicem ca la pasul k se poate pune si 0 si 1. Alegem 0, facem un nr n de pasi inainte si ne blocam (pentru ca 0 a fost alegerea gresita). Acum trebuie sa facem n pasi inapoi si sa punem 1. Dar greedy nu face intoarceri, ci contruieste solutia progresiv alegand optiunea care pare cea mai buna la un moment dat. !!! cine nu vrea sa stie rezolvarea sa nu citeasca mai departe!!!!Se face cu un algoritm arhicunoscut:greedy daca stim ca trebuie sa fie prima din punct de vedere lexicografic atunci punem tot timpu 0 si numa daca nu se poate(un sir de booleane ne spune daca o fost luat nr sau nu) atunci punem 1 si nu mai veificam nimic(ceea ce reduce marimea sirului la jumatate).Mai trebuie facuta o precizare imp.:la inceput se pun n de 0 si la sf n-1 de 0 si atunce cand pornim greedyu toate nr de forma 10000, 1100 ,1110 se iau ca si cum ar fi folosite si dupa ce se termina greedy punem zerourile ca sa apara si ele.
prin metoda asta nu ne trebuie decat un singur sir 500.000 de booleane care daca chiar vreau se poate trece in lucru pe biti si si face mult mai mic da neeee
!io am luat 100 asa ca puti incerca
Probabil ca ai folosit backtracking nerecursiv si nu ti-ai dat seama.
