Gigel vrea să confecţioneze un ornament pentru pomul de iarnă format din pătrăţele frumos colorate. Pătrăţelele pot arăta ca în desenul alăturat. Se observă faptul că ele pot avea 4 culori diferite pe cele 4 laturi, 3, 2 sau chiar o singură culoare pe toate cele 4 laturi ale pătrăţelului.
Gigel are la dispoziţie n (n pătrat perfect) pătrăţele egale de acest tip cu laturile colorate doar în patru culori (alb, roşu, galben, albastru). Le vom numerota simplu de la 1 la 4.
Cerința
Să se scrie un program care primeşte o listă de n pătrăţele colorate şi determină o aranjare a lor sub forma de pătrat de forma k•k (k•k = n) astfel încât două laturi adiacente să aibă aceeaşi culoare, precum şi numărul de astfel de aranjări.
Date de intrare
Fişierul de intrare ornament.in va conţine pe prima linie valoarea n. Următoarele n linii vor conţine câte patru numere naturale N, E, S, V separate prin câte un spaţiu, reprezentând cele 4 culori ale laturilor pătrăţelelor. Ordinea laturilor este considerată: Nord, Est, Sud, Vest şi pătrăţelele nu se vor roti. Ultima linie din fişierul de intrare va conţine una dintre valorile 1 sau 2; valoarea 1 indică faptul că este cerută o soluţie corectă, iar valoarea 2 indică faptul că este cerut numărul de soluţii corecte.
Date de ieșire
În cazul cerinţei 1 fişierul de ieşire ornament.out va conţine k linii. Fiecare linie va conţine câte k valori reprezentând numerele de ordine ale pătrăţelelor din fişierul de intrare, aranjate astfel încât să fie respectată condiţia din enunţ. În cazul cerinţei 2, fişierul de ieşire va conţine pe prima linie un singur număr natural reprezentând numărul de soluţii corecte.
Restricții și precizări
• n = 4, 9, 16
• Pentru datele de intrare problema are întotdeauna soluţie, în timpul indicat.
Exemplul 1:
ornament.in
16 4 4 1 1 4 3 1 2 2 2 2 3 4 1 3 2 1 1 3 1 1 3 1 1 2 4 1 3 3 1 1 4 3 2 4 1 1 3 2 2 1 4 4 3 1 1 2 4 4 3 3 2 2 1 1 3 4 4 3 1 2 4 4 4 1
ornament.out
2 3 4 9 10 7 8 1 16 12 6 11 13 14 5 15
Explicație
Soluţia corespunde aranjării
|-4-| |-2-| |-4-| |-3-| 2 3 3 2 2 1 1 2 |-1-| |-2-| |-3-| |-4-| |-1-| |-2-| |-3-| |-4-| 2 3 3 4 4 1 1 4 |-2-| |-1-| |-1-| |-1-| |-2-| |-1-| |-1-| |-1-| 4 4 4 1 1 3 3 4 |-4-| |-2-| |-1-| |-4-| |-4-| |-2-| |-1-| |-4-| 2 3 3 1 1 1 1 4 |-3-| |-1-| |-3-| |-3-|
Exemplul 2:
ornament.in
16 4 4 1 1 4 3 1 2 2 2 2 3 4 1 3 2 1 1 3 1 1 3 1 1 2 4 1 3 3 1 1 4 3 2 4 1 1 3 2 2 1 4 4 3 1 1 2 4 4 3 3 2 2 1 1 3 4 4 3 1 2 4 4 4 2
ornament.out
1
Explicație
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 Ornament:
//Marinel Serban ianuarie 2015
#include <fstream>
#include <cmath>
#include <cstdlib>
using namespace std;
ifstream fin ("ornament.in");
ofstream fout("ornament.out");
long k, l, m, n;
long a[18][18], b[18][18];
int luate[20], CeFac;
long long sol = 0;
void scrie()
{
int i, j;
for (i = 1; i <= k; i++)
{
for (j = 1; j <= k; j++)
fout << a[i][j] << ' ';
fout << '\n';
}
//fout << '\n';
fout.close();
}
void back(long l, long c)
{
long p;
if (l == k + 1) //am umplut k linii
{
if (CeFac == 1)
{
scrie();
exit(0);
}
sol++;
}
else
for (p = 1; p <= n; ++p) //parcurg cele n patratele
if (!luate[p]) //daca nu l-am luat inca
if (l == 1 || b[p][1] == b[a[l-1][c]][3])
if (c == 1 || b[p][4] == b[a[l][c-1]][2])
{ //se potriveste
luate[p] = 1; //l-am luat
a[l][c] = p; //il pun la locul lui
if (c == k) //daca am umplut linia
back(l+1, 1); //trec la linie noua
else //altfel
back(l, c+1); //trec in aceiasi linie mai departe
a[l][c] = 0; //iau patratelul
luate[p] = 0; //
}
}
void Rezolva()
{
back(1, 1); //plec de la prima pozitie
}
void ReadData()
{
int i;
fin >> n;
k = sqrt(n); //atata e k
for (i = 1; i <= n; i++)
fin >> b[i][1] >> b[i][2] >> b[i][3] >> b[i][4];
fin >> CeFac;
Rezolva();
if (sol == 0)
fout << -1 << '\n'; //nu e cazul dar...
else
fout << sol << '\n';
fout.close();
}
int main()
{
ReadData();
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 
.
Rezolvarea problemei #2124 Ornament
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2124 Ornament 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!