Mihai a primit de ziua lui un joc de puzzle. Jocul are N piese confecţionate prin lipirea unor bucăţi de dimensiune 1x1 (ilustrate în figurile de mai jos prin X); aceste bucăţi le vom numi în continuare, pe scurt, X-uri. Pentru confecţionarea unei piese se respectă următoarele reguli:
1. X-urile sunt aşezate unul peste altul, formând coloane ce pot avea înălţimi diferite, apoi coloanele se aliniază în partea de jos şi se lipesc între ele, una după cealaltă, de la stânga spre dreapta;
2. pe o coloană sunt cel mult nouă X-uri;
3. toate piesele au acelaşi număr de coloane.
Exemple:
În figurile 1, 2, 3, 4 sunt piese de puzzle care respectă regulile descrise, iar în figura 5 și în figura 6 NU sunt piese de puzzle, pentru că nu pot fi obţinute prin lipirea unor coloane de X-uri, una după cealaltă, de la stânga spre dreapta.
Fiind mic, Mihai nu poate rezolva puzzle-ul, dar poate face o singură operaţie: alege două piese şi le îmbină în dreptul laturilor de sus, răsturnând una dintre piese sus-jos (fără să o rotească sau să o răstoarne stânga-dreapta). Dacă în urma acestei operaţii el obţine un dreptunghi format din coloane complete de X-uri, toate coloanele având aceeaşi înălţime, este mulţumit. De exemplu, piesa din figura 1 și cea din figura 2 pot fi îmbinate în modul descris.
În figura 7 este piesa din figura 2 răsturnată sus-jos. În figura 8 este ilustrat dreptunghiul care se obţine din piesa din figura 1 şi piesa din figura 2 răsturnată sus-jos.
Observaţi că, dacă am roti piesa din figura 4, am putea să o îmbinăm cu piesa din figura 1, dar rotaţia nu este permisă.
Vom codifica o piesă printr-un număr natural, fiecare cifră din număr reprezentând (în ordine de la stânga la dreapta) câte X-uri se află pe coloana corespunzătoare din piesă.
De exemplu:
– piesa din figura 1 este codificată 4232;
– piesa din figura 2 este codificată 1323;
– piesa din figura 3 este codificată 4444;
– piesa din figura 4 este codificată 3231.
Cerința
Determinați care este numărul de moduri în care Mihai poate alege câte două piese dintre cele N pentru a face o operaţie în modul descris mai sus.
Date de intrare
Fișierul de intrare puzzle.in conține pe prima linie un număr natural N ce reprezintă numărul de piese din joc. Pe linia a doua se găsesc N numere naturale, separate prin câte un singur spațiu, reprezentând codificările celor N piese.
Date de ieșire
Fișierul de ieșire puzzle.out va conține o singură linie pe care va fi scris numărul cerut.
Restricții și precizări
2 ≤ N ≤ 100 000- Numerele care reprezintă codificările pieselor au acelaşi număr de cifre (cel mult
5) și nu conțin cifra0. - Într-o operaţie nu contează care dintre piese este răsturnată, ca urmare perechea formată din piesa
aşi piesabeste considerată ca fiind aceeaşi cu perechea formată din piesabşi piesaa. - Dreptunghiul obţinut în urma unei operaţii poate avea înălţimea mai mare decât
9. - Pentru teste valorând
30de puncteN ≤ 1000. - În concurs s-au acordat
10puncte din oficiu. Aici se acordă punctele pentru exemplul din enunț.
Exemplu
puzzle.in
5 222 432 234 123 111
puzzle.out
3
Explicație
Se pot îmbina 3 perechi de piese: piesa 1 cu piesa 5, piesa 2 cu piesa 3, piesa 2 cu piesa 4. Piesele 3 și 4 s-ar putea îmbina corect dacă una dintre ele ar fi răsturnată stânga-dreapta sau rotită, dar acest lucru nu e permis.
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 puzzle:
#include <stdio.h>
#include <assert.h>
#define NMAX 100001
long long n, lg;
long long nr;
long long x[NMAX], fr[NMAX];
long long complementar(long long x);
long long redus (long long x);
long long farazero(long long x);
long long lungime(long long x);
int main(){
long long i, aux, v, ok;
FILE *fin=fopen("puzzle.in","r");
FILE * fout=fopen("puzzle.out","w");
ok=fscanf(fin,"%d", &n);
assert(ok==1);
assert(n>1 && n<=100000);
for (i=1; i<=n; i++){
ok=fscanf(fin,"%d", &x[i]);
assert(ok==1);
assert(x[i]>0 && x[i]<=99999);
assert(farazero(x[i]));
aux=redus(x[i]);
fr[aux]++;
}
aux=x[1];
v=0;
while (aux>0) {
v=v*10+1;
aux/=10;
}
lg=lungime(x[1]);
for (i=2; i<=n; i++)
assert(lungime(x[i])==lg);
for (i=1; i<=9*v; i++){
aux=complementar(i);
nr=nr+fr[i]*fr[aux];
}
nr=nr+fr[0]*(fr[0]-1);
nr/=2;
fprintf(fout,"%lld\n",nr);
fclose(fout);
return 0;
}
long long complementar(long long x){
long long p=1, cx=x, uc, i;
long long cmax=0;
long long nr=0;
while (x) {
if (x%10>cmax)
cmax=x%10;
x/=10;
}
for (i=0; i<lg; i++){
uc=cmax-cx%10;
nr=nr+uc*p;
p*=10;
cx/=10;
}
return nr;
}
long long redus (long long x){
long long p=1, cx=x, uc;
long long cmax=0, cmin=9;
long long nr=0;
while (x){
if (x%10>cmax)
cmax=x%10;
if (x%10<cmin)
cmin=x%10;
x/=10;
}
while (cx>0){
uc=cx%10-cmin;
nr=nr+uc*p;
p*=10;
cx/=10;
}
return nr;
}
long long farazero(long long x){
while (x>0){
if (x%10==0)
return 0;
x/=10;
}
return 1;
}
long long lungime(long long x){
long long lg=0;
while (x>0){
lg++;
x/=10;
}
return lg;
}
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 #2440 puzzle
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2440 puzzle 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!