1282 Palindrom3

[•andrei.12]

Aici puteti discuta despre problema Palindrom3.

[•wefgef]

Serios mah, 6 autori? )))

[•SpiderMan]

Asa scrie in solutia oficiala, pe toti 6 ii scrie la final.

Autori:    
Student Robert Hasna
Student Vlad Ionescu
Student Cosmin Tutunaru
Student Vlad Duţă
Student Dragoş Oprică
Student Alexandru Cazacu

[•DraStiK]

Pai era un compartiment intreg din ONI Expres. )

[•geniucos]

Salut!Am luat testul 3 si mie imi da un numar care incepe cu 2, iar la raspuns incepe cu 9(asta e singura diferenta).Ambele sun divizibile cu k dar nu stiu de ce mie imi da costul mai mic(ceea ce nu prea cred ca se poate).Ma poate ajuta si pe mine cineva?
Multumesc anticipat.

[•vendetta]

Nu am reusit sa inteleg exact dinamica ta... Dar tin minte ca si eu aveam probleme asemanatoare si din cat tin minte problema era la formarea noului rest. gen ma duc din starea (i, rest) in (newI, newRest) doar ca modul in care formam newRest nu era corect.

[•geniucos]

M-am gandit si eu ca gresesc asta dar cifra de pe pozitia aia nu influenteaza cu nimic restul practic daca te uiti in numarul mare ea este inmultita cu un numar de genul 100..01 care impartit la K da restul 0.Deci practic cifra aia nu are decat rol de a minimiza costul.M-am uitat de ai multe ori sa vad daca nu cumva am gresit cand am calculat numarul ala cu 0 si 1 modulo K dar nu prea vad unde as fi putut gresi. 

[•vendetta]

Intr-adevar, rolul cifrei diferite e doar de a minimiza costul; doar ca tu obti acest numar, cred, dintr-un numar pe care nu il puteai forma. Tind sa cred ca formula, dupa care formezi restul, e gresita. Descrie modul cum formezi noul rest...

[•geniucos]

Pai numarul cu care inmultesc cifra este 11,1001,100001,....Adica este 10*100^ceva+1.Se poate obtine numarul pe care il returneaza programul meu pentru ca am verificat de mana.Si eu cred ca problema ar putea fi la formare numarului cu care inmultesc dar nu prea vad nici o greseala. 

[•RazvanR104]

Salut,

Am facut problema. Dar am o intrebare.
Cunosc doua metode de a calcula resturile in dinamica. Aparent, una merge, cealalta nu.

Prima, cea de 100, este chiar cea din descrierea solutiei realizata de autori.

Cod:

int new_rest = (j + (P10[len - i] + P10[i - 1]) * k) % K;

unde j este vechiul rest, P10[y] = (10 ^ y) % K, k noua cifra adaugata la inceputul si sfarsitul numarului anterior din dinamica si K - numarul din input cu care numarul trebuie sa se divida

A doua:

Cod:

int new_rest = (j + P10[len - 2 * i + 1] * k) % K;
new_rest = (new_rest * P10[1] + k) % K;

Literele au ramas identice cu cele de mai sus.
Inteleg ambele variante, insa, a doua pare a fi incorecta. Nu inteleg de ce.

Ma poate ajuta cineva?

Va multumesc anticipat!

[•PlayLikeNeverB4]

Nu iese matematic ce ai scris acolo. Cum ai dedus acea formula?

[•RazvanR104]

Eu m-am gandit asa.

Sa spunem ca am un numar de forma aa si vreau sa-l aduc la forma baab.

Am restul de la aa, il numesc Rest. Ca sa aflu restul de la baab, fac urmatorul lucru.

aa * 10 + b -> (Rest * 10 + b) % K
si am restul lui aab la impartirea cu K acum

Adaug si b in fata
=> b * (10 ^ 3) + aab -> (b * (10 ^ 3) + Restul_lui_aab_la_impartirea_cu_K) % K

Si acum m-am gandit ca iese restul lui baab la impartirea cu K.

Rezultatele partiale ar trebui sa fie diferite fata de cealalta formula. Dar ma gandesc ca cel final ar trebui sa fie acelasi...

Ce e gresit?

[•PlayLikeNeverB4]

Acum inteleg de unde vine. Formula din codul tau e ((j + 10^N-2i+1 * k) * 10 + k) % K.
In cod adaugi invers cifrele. Deci, in exemplul tau ar trebui sa adaugi b * 10², fiindca exista doar aa deocamdata.

[•RazvanR104]

Nu merge... L-am scris in ambele moduri, nu iau 100p cu asta.... Ceva trebuie sa fie gresit.

//LE: Am inteles greseala asupra careia mi-ai atras atentia, si (cel putin cred eu) am corectat corespunzator.

Cod:

int new_rest = (j + P10[len - 2 * i] * k) % K;
new_rest = (new_rest * P10[1] + k) % K;

52p

[•PlayLikeNeverB4]

E gresita abordarea inversa. Mergand de la stanga la dreapta (i=1..N/2), tu practic stergi cifrele din capat (baab -> aa). Din pacate, asta face ca, avand o cifra k, sa poti sa ajungi din restul curent in mai multe resturi diferite cu acelasi cost.

Cel mai simplu test pe care l-am putut gasi este:
1 0 0 0 0 0 0 0 0 0
5015
5

Raspunsul corect e 5115 iar in varianta ta da 5005.

Asta fiindca daca adaugi la margine cifra 5, numarul devine 5xx5. Indiferent daca adaugi 5-ul la restul 0 sau 1, obtii tot restul 0. In general, j * 10 % K poate da valori egale pentru j-uri diferite. N-ai de unde sa stii care rest e cel bun.

In schimb, in varianta corecta j-ul nu se inmulteste cu nimic si, deci, pentru fiecare new_rest si o cifra k ai un unic j.

Interesant

[•badea_adi1999]

Salut!
Am si eu o intrebare , daca poate sa imi raspunda cineva.
Am rezolvat problema tot cu programare dinamica , asemenator cu solutia comisiei , doar ca nu am inceput de la mijloc (pentru ca nu mi se pare normal)
Am calculat intr-un vector puterile de zece modulo k , si am incercat , de la 1 la n/2 , sa pun urmatoarea cifra j , adaugand la restul actual j*zece + j * zece[n-i+1] (corespondentul)
Ma lovesc de testul al doilea , unde tabloul este 3 2 7 8 1 4 0 5 9 6 si k=3.
Numarul meu este mai mic decat cel al comisiei , avand doar 4 diferente (2 in primele n/2 cifre)
Este o pereche de 4 si 2 , pe care eu le fac 2 si ei 4, si o pereche de 8 cu 6 , pe care eu le fac 8 si ei le fac 6 .
Astfel suma cifrelor este exact aceeasi (k==3) , ambele sunt palindroame divizibile cu k ,
dar la mine mi se pare ca sunt 2 transformari mai putin si nu inteleg de ce nu e bine.
Intai am cautat sa am numar minim de trasnformari si pentru numarul minim am cautat ca raspunsul sa fie maxim.

Multumesc in avans pentru ajutor!