Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cypher.in, cypher.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Boaca Cosmin •darkseeker | |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cypher
Aceasta problema are dificultate medie
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 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ă.
Date de intrare
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!
Date de ieşire
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.
Restricţii
- 30% din teste au T = 1
- 70% din teste au T = 10
- N ≤ 9999
Exemplu
| cypher.in | cypher.out |
|---|---|
| 2 8 0 5 6 6 5 0 8 5 8 0 5 7 8 0 4 7 5 5 0 8 7 5 0 8 6 4 0 8 0 0 0 0 5 3 1 7 8 0 0 0 1 0 0 0 9 0 0 1 0 0 0 9 0 0 1 0 0 0 9 0 0 1 0 0 0 9 0 0 0 | 14 -1 |
Explicaţie
Va trebui să mă credeţi pe cuvânt că 14 este numărul minim de apăsări de buton.
