2650 Leonardo's Code

[•fireatmyself]

http://acm.tju.edu.cn/toj/showp2650.html

nu reusesc sa iau accepted. am incercat urmatoarea idee:

fie S, sirul meu din input si V sirul care trebuie sa-l afisez. fixez V[0] = t ('A'<=t<='Z'), apoi pe V[ V[0] ] il fac S[0], pe V[ V[ V[0] ] ] = S[ V[0] ], s.a.m.d pana cand, fie am ajuns de unde am plecat (V[0] = t), fie la o contradictie (vreau sa ii atribui lui V[l] o litera cand el are deja atribuita o alta sau vrea sa atribui o litera deja atribuita). in cel de-al doilea caz, pun V[0] = u (prima litera nefolosita anterior), resetez contoarele si pozitile folosite in aceasta bucla si reiau algoritmul. daca sunt pe cazul doi. caut primul V[l] necompletat (=0), ii atribui o valoare w (prima valoare nefolosita anterior) si reiau algoritmul.

sa nu fie buna ideea?

               

[•greco]

E greu de urmarit ce zici pentru ca vorbesti de detaliile de implementare in loc sa descrii algoritmul propriu-zis. Incearca sa formulezi in termeni de cicluri solutia (nu conteaza ce vectorii tii si ce minuni mai faci pe-acolo).

 

[•fireatmyself]

m-am gandit ca ajuta mai mult asa 

here goes another try

eu impart permutarea in cicluri astfel: initial ii fixez literei A o alta litera si incerc sa formez un ciclu pe baza acestei presupuneri. dupa ce am reusit trec la prima litera care nu face parte din niciun ciclu anterior, fac alta presupunere si repet rationamentul.

impartirea in cicluri se face astfel:
am considerat permutarea care cifreaza mesajul ca fiind o funcitie bijectiva de tipul f(x) = y, unde x si y sunt litere. mie mi se da, pentru un x, f(y). daca eu fixez un y pentru prima pozitie, este evident ca voi determina si alte valori ale acestei functii. spre exemplu:

   A B C D ....
f: _ _ _ _
   D B E C ....

daca fixez ca f(A) = C, stiu automat ca f(C) = D, apoi ca F(D) = E, etc.

algoritmul meu se opreste in trei situatii:
1. fie m-am intors la pozitia de la care am inceput si mi-a rezultat ca f(A) = C (pt exemplul de mai sus)
2. fie am ajuns la o contradictie: atribui lui f(x) o valoare, dar f(x) fusese setat anterior cu o alta.
3. incerc sa atribui o valoare de doua ori pentru doua elemente distincte

*cazurile 2 si 3 pot fi privite ca o incalcare a surjectivitatii, respectiv a injectivitatii functiei f.

daca sunt intr-unul din ultimele 2 cazuri, atunci consider alta valoare initiala si reiau algoritmul.
daca nu am ajuns la nico contradictie, inseamna ca am determina o parte din (sau chiar toate) valorile lui f si, prin urmare, voi relua algoritmul din primul x nesetat (daca acesta exista).

[•greco]

Ma scuze sunt sigur ca ai explicat ok, dar eu nu prea pot sa urmaresc. Uite daca te ajuta hint: nu te intereseaza permutarea data ci doar lungimile ciclurilor din ea. Si cand calculezi un ciclu nu exista cazuri particulare, daca incepi din t si mergi pe ciclu vei ajunge tot in t pentru ca altfel n-ar fi bijectiva, adica n-ar fi permutare.

[•fireatmyself]

nu-i nimic varule. important e sa inteleaga cel ce citeste si orice sfat este binevenit

cat despre problema... nu mi-am dat seama ca ajung tot in t, desi eu tot presupuneam ca e bijectiva  multam pentru sfaturi