Fişierul intrare/ieşire:joc19.in, joc19.outSursăONI 2014, clasa a 10-a
AutorAlin BurtaAdăugată detudorv96Tudor Varan tudorv96
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Joc19

Costel are o mare pasiune pentru rezolvarea cubului Rubik, atât de mare încât a început sa faca cercetari si calcule diverse pornind de la acest joc. Ultima lui idee, inspirata de cubul Rubik, foloseste un cub de latura 2 unitati, compus din 8 cuburi cu latura de o unitate (cub unitate), având fetele exterioare colorate. Fiecare cub unitate are 3 fete exterioare si fiecare dintre acestea este colorata cu una dintre cele 10 culori disponibile, codificate prin cifrele de la 0 la 9.

Identificarea cuburilor unitate se face conform specificatiilor din Figura 1. Cubul care nu este vizibil în Figura 1 are coordonatele (1, 1, 2). Cubul lui Costel permite efectuarea urmatoarelor tipuri de mutari, asemanatoare cu cele din cubul Rubik:
M1: Paralelipipedul 1 contine cuburile unitate de coordonate: (1, 1, 1); (1, 2, 1); (2, 1, 1); (2, 2, 1). Acesta este un disc asezat orizontal si poate fi rotit cu 90 de grade catre dreapta, în sensul acelor de ceasornic.

M2: Paralelipipedul 2 contine cuburile unitate de coordonate: (1, 1, 2); (1, 2, 2); (2, 1, 2); (2, 2, 2). Acesta este un disc asezat orizontal si poate fi rotit cu 90 de grade catre dreapta, în sens invers acelor de ceasornic.

M3: Paralelipipedul 3 contine cuburile unitate de coordonate: (1, 1, 1); (2, 1, 1); (1, 1, 2); (2, 1, 2). Acesta este un disc asezat vertical si poate fi rotit cu 90 de grade catre planul îndepartat, în sens invers acelor de ceasornic.

M4: Paralelipipedul 4 contine cuburile unitate de coordonate: (1, 2, 1); (2, 2, 1); (1, 2, 2); (2, 2, 2). Acesta este un disc asezat vertical si poate fi rotit cu 90 de grade catre planul îndepartat, în sensul acelor de ceasornic.

Prin configuratie se întelege memorarea culorii fiecarei fete exterioare a celor 8 cuburi unitate, deci culorile celor 24 de fete exterioare. Aplicând o succesiune valida de mutari se obtine o alta configuratie.
Pentru usurinta memorarii unei configuratii, Costel utilizeaza desfasurarea în plan a celor 6 fete ale cubului sau dupa modelul din Figura 2, care ilustreaza modul în care sunt dispuse fetele în desfasurare. Fiecare fata a cubului contine patru fete exterioare ale cuburilor unitate având, în ordine, coordonatele specificate în figura.

Cerinta

Fiind date o configuratie initiala si o configuratie finala ale jocului, determinati numarul minim de mutari prin care se poate ajunge de la configuratia initiala la configuratia finala si succesiunea corespunzatoare de mutari prin care se poate obtine configuratia finala.

Date de intrare

Fisierul de intrare joc19.in contine 12 linii corespunzatoare configuratiei initiale, câte doua linii pentru fiecare dintre cele sase fete; pe fiecare linie sunt memorate câte doua cifre, separate prin exact un spatiu (pe primele doua linii se afla elementele fetei 1, pe urmatoarele doua linii se afla elementele fetei 2, … , pe liniile 11 si 12 se afla elementele fetei 6).
Pe urmatoarele 12 linii se afla elementele configuratiei finale, câte doua linii pentru fiecare dintre cele sase fete; pe fiecare lnie sunt memorate câte doua cifre, separate prin exact un spatiu.

Date de iesire

Fisierul de iesire joc19.out va contine pe prima linie, un numar natural MIN, reprezentând numarul minim de mutari determinat. Pe urmatoarele MIN linii succesiunea de mutari care transforma configuratia initiala în cea finala, pe fiecare linie fiind scris un numar natural cuprins între 1 si 4 ce reprezinta numarul asociat unei mutari.

Restrictii

  • Se garanteaza ca pentru toate datele de test exista solutie, aceasta având cel mult 11 mutari.
  • Orice solutie cu numar minim de mutari care conduce la obtinerea configuratiei finale va obtine punctajul maxim.

Exemplu

joc19.injoc19.out
1 2
3 1
2 7
5 4
2 9
9 4
2 9
4 5
5 8
2 3
6 4
1 7
2 2
9 1
2 7
5 4
7 9
4 4
1 9
3 5
8 3
5 2
6 4
1 2
1
3

Explicatie

Se efectueaza mutarea discului 3, catre planul îndepartat, adica mutarea 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?