Costel are o mare pasiune pentru rezolvarea cubului Rubik, atât de mare încât a început să facă cercetări și calcule diverse pornind de la acest joc. Ultima lui idee, inspirată de cubul Rubik, folosește un cub de latură 2 unități, compus din 8 cuburi cu latura de o unitate (cub unitate), având fețele exterioare colorate. Fiecare cub unitate are 3 fețe exterioare şi fiecare dintre acestea este colorată cu una din cele 10 culori disponibile, codificate prin cifrele de la 0 la 9.


Figura 1	Figura 2

Identificarea cuburilor unitate se face conform specificaţiilor din Figura 1. Cubul care nu este vizibil în Figura 1 are coordonatele (1, 1, 2). Cubul lui Costel permite efectuarea următoarelor tipuri de mutări, asemănătoare cu cele din cubul Rubik:

M1: Paralelipipedul `1` conține cuburile unitate de coordonate: `(1, 1, 1)`; `(1, 2, 1)`; `(2, 1, 1)`; `(2, 2, 1)`. Acesta este un disc așezat orizontal și poate fi rotit cu `90` de grade către dreapta, în sensul acelor de ceasornic.
M2: Paralelipipedul `2` conține cuburile unitate de coordonate: `(1, 1, 2)`; `(1, 2, 2)`; `(2, 1, 2); (2, 2, 2)`. Acesta este un disc așezat orizontal și poate fi rotit cu `90` de grade către dreapta, în sens invers acelor de ceasornic.
M3: Paralelipipedul `3` conține cuburile unitate de coordonate: `(1, 1, 1)`; `(2, 1, 1)`; `(1, 1, 2)`; `(2, 1, 2)`. Acesta este un disc așezat vertical și poate fi rotit cu `90` de grade către planul îndepărtat, în sens invers acelor de ceasornic.
M4: Paralelipipedul `4` conține cuburile unitate de coordonate: (1, 2, 1); (2, 2, 1); (1, 2, 2); (2, 2, 2). Acesta este un disc așezat vertical și poate fi rotit cu `90` de grade către planul îndepărtat, în sensul acelor de ceasornic.

Prin configurație se înțelege memorarea culorii fiecărei fețe exterioare a celor 8 cuburi unitate, deci culorile celor 24 de feţe exterioare. Aplicând o succesiune validă de mutări se obține o altă configurație.

Pentru ușurința memorării unei configurații, Costel utilizează desfășurarea în plan a celor 6 fețe ale cubului său după modelul din Figura 2, care ilustrează modul în care sunt dispuse fețele în desfăşurare. Fiecare faţă a cubului conţine patru feţe exterioare ale cuburilor unitate având, în ordine, coordonatele specificate în figură.

Cerință

Fiind date o configuraţie iniţială şi o configuraţie finală ale jocului, determinați numărul minim de mutări prin care se poate ajunge de la configurația inițială la configurația finală şi succesiunea corespunzătoare de mutări prin care se poate obţine configuraţia finală.

Date de intrare

Fișierul de intrare joc5.in conține:

12 linii corespunzătoare configuraţiei iniţiale – câte două linii pentru fiecare din cele şase feţe; pe fiecare linie sunt memorate câte două cifre, separate prin exact un spaţiu (pe primele două linii se află elementele feței 1, pe următoarele două linii se află elementele feței 2, … , pe liniile 11 și 12 se află elementele feței 6).
Pe următoarele 12 linii se află elementele configurației finale – câte două linii pentru fiecare din cele şase feţe; pe fiecare linie sunt memorate câte două cifre, separate prin exact un spaţiu.

Date de ieșire

Fișierul de ieșire joc5.out va conține:

Pe prima linie, un număr natural MIN, reprezentând numărul minim de mutări determinat.
Pe următoarele MIN linii succesiunea de mutări care transformă configuraţia iniţială în cea finală, pe fiecare linie fiind scris un număr natural cuprins între 1 și 4 ce reprezintă numărul asociat unei mutări.

Restricții și precizări

Se garantează că pentru toate datele de test există soluție, aceasta având cel mult 11 mutări.
Orice soluţie cu număr minim de mutări care conduce la obţinerea configuraţiei finale va obţine punctajul maxim.

Exemplu

joc5.in joc5.out Explicație

1
3

Se efectuează mutarea discului 3, către planul îndepărtat, adică mutarea 3.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Joc5:

#include <fstream>
#include <cmath>

#define FIN "joc5.in"
#define FOU "joc5.out"
#define Cmax 500000
#define init 999999

using namespace std;


int in1, in2, in3, in4;                         //configuratia initiala
int fi1, fi2, fi3, fi4;                         //configuratia finala
int cr1, cr2, cr3, cr4;                         //configuratia curenta
int C1[Cmax], C2[Cmax], C3[Cmax], C4[Cmax];     //coada
int prim, ultim;                                //indicii necesari cozii
short Nr[Cmax];                                 //numarul minim de mutari
int Pr[Cmax];                                   //indicele din C al mutarii precedente
short Mv[Cmax];                                 //numarul mutarii

int putere(int e)
{
    int i, rez = 1;
    for(i=1;i<=e;i++) rez *= 10;
    return rez;
}

void SetCif(int &x, int c, int i)
{
    int p = putere(7-i);
    x = ((x / p) * 10 + c) *  ( p / 10 ) + x % ( p / 10);
}

int GetCif(int x, int i)
{
    int p = putere(6-i);
    return  (x / p) % 10;
}

int E_Final(int n1, int n2, int n3, int n4)
{
    return n1 == fi1 && n2 == fi2 && n3 == fi3 && n4 == fi4;
}

int E_Egal(int n1, int n2, int n3, int n4, int poz)
{
    return n1 == C1[poz] && n2 == C2[poz] && n3 == C3[poz] && n4 == C4[poz];
}

int Apare(int n1, int n2, int n3, int n4)
{
    int i , cat;
    cat  = max(1, ultim - 50);
    for(i = ultim - 50 ; i <= ultim; i++ )
        if(C1[i] == n1 && C2[i] == n2 && C3[i] == n3 && C4[i] == n4 && i != prim) return 1;
    return 0;
}

void read()
{
    ifstream in(FIN);
    int x, y, z, t;
    in1 = in2 = in3 = in4 = init;
    //citesc configuratia initiala
    in>>x>>y>>z>>t; SetCif(in1, x, 3); SetCif(in2, y, 3); SetCif(in1, z, 4); SetCif(in2, t, 4);  //fata 1
    in>>x>>y>>z>>t; SetCif(in3, x, 1); SetCif(in3, y, 2); SetCif(in4, z, 1); SetCif(in4, t, 2);  //fata 2
    in>>x>>y>>z>>t; SetCif(in1, x, 5); SetCif(in2, y, 5); SetCif(in1, z, 6); SetCif(in2, t, 6);  //fata 3
    in>>x>>y>>z>>t; SetCif(in1, x, 1); SetCif(in2, y, 1); SetCif(in1, z, 2); SetCif(in2, t, 2);  //fata 4
    in>>x>>y>>z>>t; SetCif(in3, x, 5); SetCif(in3, y, 6); SetCif(in4, z, 5); SetCif(in4, t, 6);  //fata 5
    in>>x>>y>>z>>t; SetCif(in3, x, 3); SetCif(in3, y, 4); SetCif(in4, z, 3); SetCif(in4, t, 4);  //fata 6
    fi1 = fi2 = fi3 = fi4 = init;
    //citesc configuratia finala
    in>>x>>y>>z>>t; SetCif(fi1, x, 3); SetCif(fi2, y, 3); SetCif(fi1, z, 4); SetCif(fi2, t, 4);  //fata 1
    in>>x>>y>>z>>t; SetCif(fi3, x, 1); SetCif(fi3, y, 2); SetCif(fi4, z, 1); SetCif(fi4, t, 2);  //fata 2
    in>>x>>y>>z>>t; SetCif(fi1, x, 5); SetCif(fi2, y, 5); SetCif(fi1, z, 6); SetCif(fi2, t, 6);  //fata 3
    in>>x>>y>>z>>t; SetCif(fi1, x, 1); SetCif(fi2, y, 1); SetCif(fi1, z, 2); SetCif(fi2, t, 2);  //fata 4
    in>>x>>y>>z>>t; SetCif(fi3, x, 5); SetCif(fi3, y, 6); SetCif(fi4, z, 5); SetCif(fi4, t, 6);  //fata 5
    in>>x>>y>>z>>t; SetCif(fi3, x, 3); SetCif(fi3, y, 4); SetCif(fi4, z, 3); SetCif(fi4, t, 4);  //fata 6
    in.close();
}

void move3(int &n1, int &n2, int &n3, int &n4)   //vd1 -> Nord
{
    int a1, a2;
    a1 = GetCif(n1, 1); a2 = GetCif(n1, 2);
    SetCif(n1, GetCif(n1, 3), 1); SetCif(n1, GetCif(n1, 4), 2);
    SetCif(n1, GetCif(n1, 5), 3); SetCif(n1, GetCif(n1, 6), 4);
    SetCif(n1, GetCif(n4, 4), 5); SetCif(n1, GetCif(n3, 4), 6);
    SetCif(n4, a1, 4); SetCif(n3, a2, 4);
    a1 =  GetCif(n3, 5); SetCif(n3, GetCif(n3, 6),5); SetCif(n3, GetCif(n4, 6), 6);
    SetCif(n4, GetCif(n4, 5),6); SetCif(n4, a1, 5);
}

void move4(int &n1, int &n2, int &n3, int &n4)   //vd2 -> Nord
{
    int a1, a2;
    a1 = GetCif(n2, 1); a2 = GetCif(n2, 2);
    SetCif(n2, GetCif(n2, 3), 1); SetCif(n2, GetCif(n2, 4), 2);
    SetCif(n2, GetCif(n2, 5), 3); SetCif(n2, GetCif(n2, 6), 4);
    SetCif(n2, GetCif(n4, 3), 5); SetCif(n2, GetCif(n3, 3), 6);
    SetCif(n4, a1, 3); SetCif(n3, a2, 3);
    a1 =  GetCif(n3, 1); SetCif(n3, GetCif(n4, 1), 1); SetCif(n4, GetCif(n4, 2), 1);
    SetCif(n4, GetCif(n3, 2), 2); SetCif(n3, a1, 2);
}

void move1(int &n1, int &n2, int &n3, int &n4)   //od3 -> Est
{
    int a1, a2;
    a1 = GetCif(n1, 3); SetCif(n1, GetCif(n1, 4) ,3); SetCif(n1, GetCif(n2, 4) ,4);
    SetCif(n2, GetCif(n2, 3) ,4); SetCif(n2, a1 ,3);
    a1 = GetCif(n1, 2); a2 = GetCif(n2, 2);
    SetCif(n1, GetCif(n4, 6), 2); SetCif(n2, GetCif(n3, 6), 2);
    SetCif(n4, GetCif(n2, 5), 6); SetCif(n3, GetCif(n1, 5), 6);
    SetCif(n2, GetCif(n3, 1), 5); SetCif(n1, GetCif(n4, 1), 5);
    SetCif(n3, a1, 1); SetCif(n4, a2, 1);
}

void move2(int &n1, int &n2, int &n3, int &n4)   //od4 -> Est
{
    int a1, a2;
    a1 = GetCif(n3, 3); SetCif(n3, GetCif(n3, 4) ,3); SetCif(n3, GetCif(n4, 4) ,4);
    SetCif(n4, GetCif(n4, 3) ,4); SetCif(n4, a1 ,3);
    a1 = GetCif(n1, 1); a2 = GetCif(n2, 1);
    SetCif(n1, GetCif(n4, 5), 1); SetCif(n2, GetCif(n3, 5), 1);
    SetCif(n4, GetCif(n2, 6), 5); SetCif(n3, GetCif(n1, 6), 5);
    SetCif(n2, GetCif(n3, 2), 6); SetCif(n1, GetCif(n4, 2), 6);
    SetCif(n3, a1, 2); SetCif(n4, a2, 2);
}

void solve_and_print()
{
    int rez = init;
    int tm1, tm2, tm3, tm4;
    short R[100], Lm;
    int i, j, poz;
    //initializez
    prim = ultim = 1;
    C1[prim] = in1; C2[prim] = in2; C3[prim] = in3; C4[prim] = in4;
    Nr[1] = 0; Pr[1] = 0; Mv[1] = 0;
    while( prim <= ultim )
    {
        cr1 = C1[prim]; cr2 = C2[prim]; cr3 = C3[prim]; cr4 = C4[prim];
        if( E_Final(cr1, cr2, cr3, cr4) ) { rez = Nr[prim]; poz = prim; Lm = 0; break; }
        //move 1
        tm1 = cr1; tm2 = cr2; tm3 = cr3; tm4 = cr4;
        move1(tm1, tm2, tm3, tm4);
        if( E_Final(tm1, tm2, tm3, tm4) ) { rez = Nr[prim] + 1; poz = prim;  Lm = 1; break; }
        if( !Apare(tm1, tm2, tm3, tm4) ) { ultim++; C1[ultim] = tm1; C2[ultim] = tm2; C3[ultim] = tm3; C4[ultim] = tm4; Nr[ultim] = 1 + Nr[prim]; Pr[ultim] = prim; Mv[ultim] = 1; }
        //move 2
        tm1 = cr1; tm2 = cr2; tm3 = cr3; tm4 = cr4;
        move2(tm1, tm2, tm3, tm4);
        if( E_Final(tm1, tm2, tm3, tm4) ) { rez = Nr[prim] + 1; poz = prim;  Lm = 2; break; }
        if( !Apare(tm1, tm2, tm3, tm4) ) { ultim++; C1[ultim] = tm1; C2[ultim] = tm2; C3[ultim] = tm3; C4[ultim] = tm4; Nr[ultim] = 1 + Nr[prim]; Pr[ultim] = prim; Mv[ultim] = 2; }
        //move 3
        tm1 = cr1; tm2 = cr2; tm3 = cr3; tm4 = cr4;
        move3(tm1, tm2, tm3, tm4);
        if( E_Final(tm1, tm2, tm3, tm4) ) { rez = Nr[prim] + 1;  poz = prim;  Lm = 3; break; }
        if( !Apare(tm1, tm2, tm3, tm4) ) { ultim++; C1[ultim] = tm1; C2[ultim] = tm2; C3[ultim] = tm3; C4[ultim] = tm4; Nr[ultim] = 1 + Nr[prim]; Pr[ultim] = prim; Mv[ultim] = 3; }
        //move 4
        tm1 = cr1; tm2 = cr2; tm3 = cr3; tm4 = cr4;
        move4(tm1, tm2, tm3, tm4);
        if( E_Final(tm1, tm2, tm3, tm4) ) { rez = Nr[prim] + 1; poz = prim;  Lm = 4; break; }
        if( !Apare(tm1, tm2, tm3, tm4) ) { ultim++; C1[ultim] = tm1; C2[ultim] = tm2; C3[ultim] = tm3; C4[ultim] = tm4; Nr[ultim] = 1 + Nr[prim]; Pr[ultim] = prim; Mv[ultim] = 4; }

        prim++;
      
    }
    ofstream OUT(FOU);
    OUT << rez << '\n';
    //determin mutarile

    i = rez;
    if(Lm) { R[i] = Lm; i--;}
    while(Pr[poz])
    {
        R[i--] = Mv[poz];
        poz = Pr[poz];
    }
    for(j = 1; j <= rez ; j++ ) OUT << R[j] << '\n';
    OUT.close();
}

int main()
{
    read();
    solve_and_print();
   
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1109 Joc5

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1109 Joc5 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1109 Joc5