159 Dame

[ditzone]

Aici puteţi discuta despre problema Dame.

[Tabara Mihai]

va rog frumos sa-mi dati si mie o idee la problema asta......va rog!!!!                        

[•greco]

Dupa cum vi s-a mai spus, exista articole cu solutii oficiale la problemele care s-au dat in concurs, iar faptul ca nu le cititi inseamna ca nu merita scrise.

[Tabara Mihai]

uitasem de articole...sorry.        

[•Florian]

Cod:

 O alta solutie , matematica, se bazeaza pe un sablon de construire a solutiei in functie de restul lui N la 12.

    * Se insereaza numerele pare de la 2 la N intr-o lista
    * Daca restul lui N la 12 este 3 sau 9 se muta 2 la sfarsitul listei
    * Se insereaza numerele impare de la 1 la N in lista
    * Daca restul este 8 se interschimba perechile (3 1, 7 5, ...)
    * Daca restul este 2 se interschimba 1 cu 3 si 5 se muta la sfarsitul listei
    * Daca restul este 3 sau 9 se muta 1 si 3 la sfarsitul listei

Lista va codifica o solutie cum s-a precizat si inainte, al i-lea element reprezetand o dama pe randul i si pe coloana listai. 

Deci am implementat exact k in articol, insa iau doar 85 de puncte. Nu inteleg din ce cauza...banuiesc k din cauza k mai exista resturi n%12, kare nu sunt luate in considerare mai sus (ex: 0, 1 ,4,5,6,7,11...). In cazul acesta ce trebuie sa fac? Se poate de 100 folosind metoda asta?? 

[•marcelcodrea]

Daca resturile sunt "0,1,4,5,6,7,11" , solutia va fi reprezentata de lista care va contine in ordine numerele pare de la 2 la n , urmate de numerele impare de la 1 la n , practic se urmeaza doar pasii :

Cod:

 * Se insereaza numerele pare de la 2 la N intr-o lista
 * Se insereaza numerele impare de la 1 la N in lista

[•Florian]

Ai dreptate! Asa e! Luasem in considerare acest caz..inconstient...Multumesc pt raspuns! Deci probabil imi pica la testele 15,17,19 din alt motiv....


[Later edit] Mda...am mai rectificat ceva si iau 95 de puncte cu WA pe testul 19  . Evaluatorul ia in considerare toate solutiile care exista, nu? K de exemplu, programul meu, pt exemplul din problema  imi afiseaza o solutie diferita, insa corecta... A mai avut careva probleme cu testul 19? 

[•vlad_oltean]

se poate face backtracking pentru n mai mare ca 20?

[•wefgef]

Nu. Solutia oficiala este O(N). Poti consulta articolul cu solutii.

[•alex_mircescu]

Nu am absolut cea mai vaga idee ce se intampla cu testele busite: http://infoarena.ro/job_detail/236719
Idei? am dat toate testele pentru toate cazurile... si NIMIC... 
Ajutor, plzzz

LE: Greseam la impartirea cu 12, rest = 8 ... interschimbam si numerele pare... si trebuiau doar cele impare 

[•gigi1996]

salut. imi poate explica si mie cineva logic ideea cu impartirea la 12 si restul ramas?

[•wefgef]

Citeste articolul cu solutii, gasesti acolo un link catre wikipedia.

[•gigi1996]

ok,mersi mult.

[•gigi1996]

totusi nu inteleg de ce impartimi la 12,imi poate explica cineva? multumesc anticipat