catanedelcu

de fapt sunt 11 segmente...dar problema ramane :)

wmutex

Un palindrom P cu n cifre determina un numar "unic" U format din primele [(n+1)/2] cifre, restul cifrelor fiind "oglindite":

U = U(P)

"Schema" dupa care se poate calcula urmatorul palindrom P' dat fiind palindromul P este urmatoarea:

1. Pentru palindromuml P se calculeaza "unicul" U;
2. Se aduna la U unu: U' = U+1;
3. Se reface palindromul pornind de data asta de la "unicul" U' si nu de la U, astfel se obtine urmatorul palindrom P'.

Pentru numerele date:

P = 7997, U = 79, U' = 80, P' = 8008;
P = 41314, U = 413, U' = 414, P' = 41414;
P = 99999, U = 999, U' = 1000, P' = 100001.

wmutex

Oops... comentariul meu anterior e refera la problema anterioara. :D

wmutex

Ok, sunt gata sa bag mana in foc ca profu' nu vrea sa ne dea mai mult de nota 8, si-a sucit problema in asa fel... Dar nu stiu sa explic deocamdata. :D

Una dintre solutii (XY inseeamna linia care e trasa pornind din X si ajungand direct in Y): CA, AD, DC, CF, FG, GD, DE, EH, HG, GD, DE, EB, BA. Cu bold sunt insemnate liniile parcurse a doua oara.

Acuma, de ce nu se poate nota mai mare de 8? Ok, asta e o problema de grafuri euleriene... :-)

A13x34

EB BA AC CF FG GH HE ED DC CA AD DG

Eu am luat nota 9.

Je

Trebuie un nr par de laturi ca sa reusesti sa-l parcurgi fara dubluri, in cazul de fata numarul minim de dubluri e 1, deci ma multumesc si cu nota 9:P

wmutex

(@Je: Nu intotdeauna. Un pentagon, de exemplu, poate fi parcurs fara a trece de doua ori prin aceeasi latura, si laturile sunt in numar impar.)

Heh... mi-am dat seama unde am gresit. Ok, s-o iau de la un capat.

O conditie ca un graf de genul asta sa fie parcurs "dintr-o singura linie" e ca sa aiba 0 sau 2 noduri de grad impar (gradul unui nod fiind numarul de segmente/linii care au un capat in acel nod). Daca are 0 noduri de grad impar graful poate fi parcurs incepand din nu conteaza care nod si terminand in acelasi nod. Daca are 2 noduri de grad impar atunci poate fi parcurs "drintr-o singura linie" doar incepand dintr-unul din nodurile de grad impar si terminand in celalalt nod de grad impar.

Greseala mea a fost c-am considerat graful din problema fara linia AC, care poate fi parcurs dintr-o singura linie daca se incepe din E sau din G, si se termina in G respectiv E. M-am gandit: "ca sa ajung sa trag linia AC trebuie sa trec peste 2 linii deja trase, fie ca am terminat in E, fie ca am terminat in G. Asa ca rectific afirmata mea de mai inainte: se poate lua maxim 8 daca se porneste din G sau E.

Nu mai stiu de ce n-am considerat si celelalte noduri de grad impar din graf, A si C, ca puncte de start... dar felicitari lui A13x34 pentru c-a facut-o. :-)