|
Titlul: Spirala Scris de: CHERA Laurentiu din Martie 11, 2009, 16:58:57 Citat 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! :shock: Titlul: Răspuns: Spirala Scris de: alexandru din Martie 11, 2009, 17:25:01 daca timp maxim : 1sec il faci cum zice acolo :D ....mereu creezi o noua matricea care este parcurgerea in spirala a celalatei :D. Daca nu ma insel se observa ca prima linie ramana mereu constanta :D
Titlul: Răspuns: Spirala Scris de: CHERA Laurentiu din Martie 11, 2009, 17:26:30 Multumesc de indicatie! Exact, primele n+1 elemente raman neschimbate! :D
Titlul: Răspuns: Spirala Scris de: alexandru din Martie 11, 2009, 18:03:20 si u te pregatesti pt oji :D?
Titlul: Răspuns: Spirala Scris de: CHERA Laurentiu din Martie 11, 2009, 18:08:48 :D Da! Ma dispera! Nici nu stiu ce algoritmi sa mai invat! :D
Titlul: Răspuns: Spirala Scris de: alexandru din Martie 11, 2009, 18:52:44 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 :)) Titlul: Răspuns: Spirala Scris de: CHERA Laurentiu din Martie 11, 2009, 20:01:08 Sunt din Bals! Se dau si grafuri? Pana acum nu am gasit probleme la a X-a cu grafuri! :D
Titlul: Răspuns: Spirala Scris de: alexandru din Martie 11, 2009, 20:05:48 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 ;)
Titlul: Răspuns: Spirala Scris de: Nad Acrepuic din Martie 11, 2009, 20:13:59 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 ? :? Titlul: Răspuns: Spirala Scris de: CHERA Laurentiu din Martie 11, 2009, 20:15:05 Am rezolvat-o! E simplu! O problema ce se rezolva la fel este alee din 2007! Mai grea perle! :P
Titlul: Răspuns: Spirala Scris de: alexandru din Martie 11, 2009, 20:49:04 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 :D Titlul: Răspuns: Spirala Scris de: Florian Marcu din Martie 11, 2009, 21:04:48 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! :) ] Titlul: Răspuns: Spirala Scris de: Emanuel Cinca din Martie 11, 2009, 22:19:52 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 :D pe aceasta cale va urez si eu multa bafta la OJI... sa nu ne pice probleme usoare... ci probleme pe care le stim rezolva :peacefingers: Titlul: Răspuns: Spirala Scris de: Nad Acrepuic din Martie 12, 2009, 00:22:35 @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 :sad: 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 + / - :eyebrow: Titlul: Răspuns: Spirala Scris de: Emanuel Cinca din Martie 12, 2009, 00:45:25 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... Titlul: Răspuns: Spirala Scris de: alexandru din Martie 12, 2009, 07:07:43 Citat se refera la comportamentul si in principal la ajutorul oferit pe forum. Deci conform karmei nu sunt un baita cuminte :evil: si care incruca pe toti :evil: :evil:@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 :D ..pur si simplu o faci cum zice in program ...n-ai alta solutie :P Titlul: Răspuns: Spirala Scris de: Florian Marcu din Martie 12, 2009, 08:55:24 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). :)Titlul: Răspuns: Spirala Scris de: CHERA Laurentiu din Martie 12, 2009, 14:30:28 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! :ok: Legat de Karma! Habar nu am de ce o am asa mica! :D
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! :D http://www.univ-ovidius.ro/math/Doc/Admitere/CentruPregatire/2006/Info/LASD2v4.pdf (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 :)) Titlul: Răspuns: Spirala Scris de: Gabriel Bitis din Martie 12, 2009, 14:51:32 Legat de Karma! Habar nu am de ce o am asa mica! :D Eu am o vaga banuiala... Titlul: Răspuns: Spirala Scris de: alexandru din Martie 12, 2009, 17:49:28 Citat 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 :PTitlul: Răspuns: Spirala Scris de: vai de mine din Martie 12, 2009, 18:23:59 Alexandre.. tu ai merita un ban frumos... vorbesti cam mult si aiurea.
Titlul: Răspuns: Spirala Scris de: go gcc din Martie 12, 2009, 18:59:29 @alexandru : Cum adica nu te interesaza ca ai karma negativa, asta insemna ca esti enervant (te-ai gandit la asta ?). [-X
Daca tot e optiunea de stergere de conturi ar trebui folosita. Titlul: Răspuns: Spirala Scris de: Sima Cotizo din Martie 12, 2009, 19:01:28 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.
|