Spirala

[•chera_lary]

Se consideră un automat de criptare format dintr-un tablou cu n linii şi n coloane, tablou ce conţine toate numerele de la 1 la n2 aşezate ”şerpuit” pe linii, de la prima la ultima linie, pe liniile impare pornind de la stânga către dreapta, iar pe cele pare de la dreapta către stânga (ca în figura alăturată).
Numim ”amestecare“ operaţia de desfăşurare în spirală a valorilor din tablou în ordinea indicată de săgeţi şi de reaşezare a acestora în acelaşi tablou, ”şerpuit” pe linii ca şi în cazul precedent.
De exemplu, desfăşurarea tabloului conduce la şirul: 1 2 3 4 5 12 13 14 15 16 9 8 7 6 11 10, iar reaşezarea acestuia în tablou conduce la obţinerea unui nou tablou reprezentat în cea de-a doua figură alăturată.
După orice operaţie de amestecare se poate relua procedeul, efectuând o nouă amestecare. S-a observat un fapt interesant: că după un număr de amestecări, unele valori ajung din nou în poziţia iniţială (pe care o aveau în tabloul de pornire). De exemplu, după două amestecări, tabloul de 4x4 conţine 9 dintre elementele sale în exact aceeaşi poziţie în care se aflau iniţial (vezi elemente marcate din figură).

Cerinţă
Pentru n şi k citite, scrieţi un program care să determine numărul minim de amestecări ale unui tablou de n linii necesar pentru a ajunge la un tablou cu exact k elemente aflate din nou în poziţia iniţială.

Voi cum ati verifica dupa cate amestecari se repeta un element? Pe mine ma dispera! Problema poate fi gasita si in arhiva de probleme! In sectiunea download oji2003 cls X! 

[•alexandru92]

daca  timp maxim : 1sec  il faci cum zice acolo    ....mereu creezi o noua matricea care este parcurgerea in spirala a celalatei .  Daca nu ma insel se observa ca prima linie ramana mereu constanta

[•chera_lary]

Multumesc de indicatie! Exact, primele n+1 elemente raman neschimbate!

[•alexandru92]

si  u  te  pregatesti pt  oji ?

[•chera_lary]

  Da! Ma dispera! Nici nu stiu ce algoritmi sa mai invat!

[•alexandru92]

pai............deobicei se p_dinamic, back  ,greedy  sau grafuri .........depinde de cum au ei chef
Ps : din ce  localitate esti ?? .......si eu is in aceeasi situatie )

[•chera_lary]

Sunt din Bals! Se dau si grafuri? Pana acum nu am gasit probleme la a X-a cu grafuri!

[•alexandru92]

cauta OJI 2004  Problema Rome Si Julieta .......prin  algoritmul lui Lee (un BFS) se face usor.......pt restu  ori p_dinamic ori back la alegere

[•ciuperca]

Daca ne da o dinamica pe arbori sau niste aib 2D cu operatii dubioase pe multimi disjuncte 
... ar fi nasol astea sunt destul de grele si am vazut in unii ani probleme dinastea. 
Voi le-ati invatat pastea ? 

[•chera_lary]

Am rezolvat-o! E simplu! O problema ce se rezolva la fel este alee din 2007! Mai grea perle!

[•alexandru92]

perle grea??  ........aia mi-a luat 5 minute sa o fac.(si am luat 100 <<evaluat cu evaluatorul de la oji>>)  ca sa mearga pe infoarena  trebuie sa mai optimizez dar mi lene. 
@)Nad Acrepuic
II posibil la  problema de dinamica sa dea o problema cu suma maxima in piramida. rezolvarea ii identica ca si la cea cu triughin numai ca ai 3D si 2D

[•Florian]

niste aib 2D cu operatii dubioase pe multimi disjuncte 
... ar fi nasol astea sunt destul de grele si am vazut in unii ani probleme dinastea. 

Cat optimism! Stiu ca discutia este total off-topic, insa unde ai vazut tu la oji aib - uri ?

[ rog un moderator sa mute discutia in alt topic. LE: Multumesc! ]

[•c_e_manu]

cred ca ar putea fi si redenumit topicul... numai despre problema Spirala nu se vorbeste aici 

cat despre probleme... niciodata nu poti stii suficient de multi algoritmi ca sa fii asigurat! e bine sa inveti cat mai mult, dar sa fii constient ca nu va fii neaparat suficient pentru a obtine rezultatul dorit.. poti stii multe si sa prinzi o zi proasta sau invers... inveti putin, dar iti vine inspiratia pe moment...

plus ca mai conteaza si concurenta... deagaba faci 150 de puncte daca sunt vreo 15 inaintea ta... dar e super cand scoti 100 si ceilalti au mai putin

pe aceasta cale va urez si eu multa bafta la OJI... sa nu ne pice probleme usoare... ci probleme pe care le stim rezolva 

[•ciuperca]

@florian

Am auzit de la cineva ca problema lacusta de la oji 2005 s-ar face cu aib 2d. Nu am rezolvat-o inca pentru ca nu stiu ce e aia aib 2d (am auzit ca e foarte greu de implementat  ).
 
@alexandru92
Mama cum ai reusit sa faci perle ca eu nu mam prins de ea 
P.S Ce e chestia aia care apare deasupra semnului cu conectat / deconectat ? E un fel de rating la concursuri? Si de ce pot da + / -

[•c_e_manu]

lacusta e dinamica...

+/- e karma utilizatorului... karma, popularitate sau un fel de rating cu zici tu, dar nu de la concursuri... se refera la comportamentul si in principal la ajutorul oferit pe forum...

[•alexandru92]

se refera la comportamentul si in principal la ajutorul oferit pe forum.

Deci conform  karmei  nu sunt un baita cuminte  si care incruca pe toti   
@Nad Acrepuic  la perle daca ei  un creion si te uiti atent la enunt o sa vezi ca pentru unele numere este imposibil  sa creez un lant, plus ai unele restricitii datorita transofrmarii perlelror ..pur si simplu  o faci  cum zice in program ...n-ai alta solutie

[•Florian]

Am auzit de la cineva ca problema lacusta de la oji 2005 s-ar face cu aib 2d. Nu am rezolvat-o inca pentru ca nu stiu ce e aia aib 2d (am auzit ca e foarte greu de implementat  ).

Nu e nevoie de aib 2d. E suficienta programarea dinamica in O(n^3). Desi cu foarte putin efort, se poate scoate dinamica in O(n^2). 

[•chera_lary]

Da! Asa este! Lacusta este foarte simpla! Am rezolvat-o cu dinamica O(n^2)! Se observa ca matricea poate fi calculata in L(aduni minimul de pe linia anterioara, iar in cazul in care minimul se afla exact deasupar urmatoarei coborari aduni urmatorul minim)!La sfarsit costul se afla in celula de pe pozitia n,n!  Legat de Karma! Habar nu am de ce o am asa mica!

Subiectele sunt rezolvate si pe Infoarena in sectiunea download, dar v-am mai atasat aici un linck catre alte rezolvari date de o universitate, parca din Constanta!
http://www.univ-ovidius.ro/math/Doc/Admitere/CentruPregatire/2006/Info/LASD2v4.pdf

[editat de moderator] nu mai posta consecutiv; foloseste butonul "modifica"
Si eu cred ca incep sa inteleg )

[•gabitzish1]

Legat de Karma! Habar nu am de ce o am asa mica!

Eu am o vaga banuiala...

[•alexandru92]

Legat de Karma! Habar nu am de ce o am asa mica! 

A  ta e mica ?? .............dar mite a mea ??.........dar ma rog mie  nu-mi pasa .............de chestiile astia

[•ioooi]

Alexandre.. tu ai merita un ban frumos... vorbesti cam mult si aiurea.

[•0000]

@alexandru : Cum adica nu te interesaza ca ai karma negativa, asta insemna ca esti enervant (te-ai gandit la asta ?).
Daca tot e optiunea de stergere de conturi ar trebui folosita. 

[•sima_cotizo]

Stiu ca presiunea OJI-ului este din ce in ce mai mare, dar eu va recomand sa luati o gura de aer si sa va potoliti.