.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » spirala1

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
spirala1


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
2MB / 1MB

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 următoarea figură.



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 figura următoare).


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ă.

Date de intrare

Fişierul de intrare spirala1.in conţine pe prima linie cele două numere n şi k despărţite printr-un spaţiu.

Date de ieşire

Fişierul de ieşire spirala1.out conţine o singură linie pe care se află numărul de amestecări determinat.

Restricţii

3<=n<=50
Datele de intrare sunt alese astfel încât numărul minim de amestecări necesare să nu depăşească 2*109.
La încheierea programului nu se va solicita apăsarea unei taste.

Exemple

spirala1.inspirala1.out
4 9 2
6 36 330

autor: Prof. Rodica Pintea
propunător: Prof. Marinel Şerban
Liceul de Informatica
marinel.serban@gmail.com
Articole recomandate
Probleme recomandate
De la OJI 2003: submult, text1, taxe1, compus1, pinochio, visul, gardul, paranteze, sirul, tort
De acelaşi autor: fisc, cartonase2, cartoane, joc8, tramvai1, suma2, sg1, volei1, team, elfi, cezar1, piramida1, mosia, vanatoare, poligon3, panglica, cerc, tablou1, radioactiv, solitar
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, scara, programs, iepuras2, fry, policefm, turist, kfactor, cuc, prime, sqr, evaluare, factk, div3, divizor, euclid, stop, matricea, mutare, viteza, ingerasi, prieteni, robinson, romeo, perechi1, sume1, fact, tzigla, cifru2, elfi, vraji, desen2, exponent, trapez, resturi, exp1, ron, gardul, tort, poligon3, sume2, smith, biliard, printesa, secvente1, ultime4, padure, multiplu1, 235, iepurasi, numar3, cmmmc, randomizare, divizori, pitag, bileprime, pin, canguri, numar4, jocprim, covor, nivfractie, cmmdcsecv, ai, grupe2, numerus, sport2, fagure, grad2, sumdivprod, oak, sumprod, paisprezece, numere10, proddiv, puncte4, trifoi, cartier, alune, intersectii, divider, minm, numere11, prodnr, boltz, vistiernic, secvp, extraprime, divizori1, cumpanit, cntgcd, nrdiv, numere12, daruri, imprimanta, puteri, reflex, tg, sprime, diferenta, concurs4, vapoare, inventie, prime2
Despre backtracking: acop, bipal, magic2, vagoane, friends, tricouri, festival, numar, pento, ro, jobs, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, paianjen, medii, monkey, scara1, numere8, banda1, cofetar, gradina, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, avioane, jb, prisme, triburi1, genab, dineu, antitero, ornament, virgule
Chestionare recomandate
surse trimise | ajutor