== include(page="template/taskheader" task_id="cypher") ==
Tocmai aţi găsit cutia fermecată ce conţine 100 de puncte la o problemă de la testul practic. Totuşi, pentru a o putea deschide trebuie să spargeţi un cifru. Cifrul este construit ca un mecanism cu 4 discuri cu numere de la 0 la 9, sub fiecare disc aflându-se 2 butoane sub formă de săgeţi, fiecare buton deplasând discul de deasupra sa în ordinea indicată de săgeţi. Pentru o imagine mai clară asupra cum arată cifrul consultaţi poza de mai jos.
Aceasta problema are dificultate medie
!problema/cypher?image.jpg!
Tocmai aţi găsit cutia fermecată ce conţine 100 de puncte la o problemă de la testul practic. Totuşi, pentru a o putea deschide trebuie să spargeţi un cifru. Cifrul este construit ca un mecanism cu 4 discuri cu numere de la 0 la 9, deasupra fiecarui disc aflându-se 2 butoane sub formă de săgeţi, fiecare buton deplasând discul de deasupra sa în ordinea indicată de săgeţi. Pentru o imagine mai clară asupra cum arată cifrul consultaţi poza de mai jos.
Fiecare configuraţie în care poate ajunge cifrul poate fi codificată printr-un număr pe 4 cifre. De exemplu starea din poză corespunde numărului 8056.
!problema/cypher?img5.jpg!
Fiecare configuraţie în care poate ajunge cifrul poate fi codificată printr-un număr pe 4 cifre. De exemplu starea din poză corespunde numărului 3886.
Pentru a obţine cele 100 de puncte voi trebuie să aduceţi cifrul dintr-o stare iniţială I ~1~ I ~2~ I ~3~ I ~4~ într-o stare finală F ~1~ F ~2~ F ~3~ F ~4~ printr-un număr minim de apăsări de buton, fără a trece printr-o configuraţie interzisă.
h2. Date de intrare
Fişierul de intrare $cypher.in$ va conţine pe prima linie starea iniţiala I ~1~ I ~2~ I ~3~ I ~4~, şi pe a 2-a linie starea finală F ~1~ F ~2~ F ~3~ F ~4~.
Fişierul de intrare $cypher.in$ va conţine pe prima linie un număr T reprezentând numărul de teste din fişier.
Fiecare test are următorul format:
Pe prima linie se găseşte starea iniţială I ~1~ I ~2~ I ~3~ I ~4~, şi pe a 2-a linie starea finală F ~1~ F ~2~ F ~3~ F ~4~.
Pe a 3-a linie se găseşte numărul N reprezentând numărul de stări interzise, iar pe următoarele N linii se găsesc cate 4 numere R ~1~ R ~2~ R ~3~ R ~4~ reprezentând stările interzise.
*Hint*
Dacă o stare este reprezentată ca un număr de 4 cifre, pentru a trece la următoarea stare trebuie adunat sau scăzut la acesta o putere a lui 10. 6666 + {1, 10, 100, 1000}. Atenţie la overflow!
h2. Date de ieşire
Fişierul de ieşire $cypher.out$ va conţine numărul minim de mutări pentru a ajunge din starea iniţială în starea finală în condiţiile precizate în enunţ, sau -1 în cazul în care acest lucru este imposibil.
Fişierul de ieşire $cypher.out$ va conţine T valori, fiecare pe câte o linie, reprezetând numărul minim de mutări pentru a ajunge din starea iniţială în starea finală în condiţiile precizate în enunţ, sau -1 în cazul în care acest lucru este imposibil.
h2. Restricţii
* 30% din teste au T = 1
* 70% din teste au T = 10
* N ≤ 9999
h2. Exemplu
table(example). |_. cypher.in |_. cypher.out |
| 8 0 5 6
| 2
8 0 5 6
6 5 0 8
5
8 0 5 7
