Simulare OJI VII | puzzle

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 32MB Input: puzzle.in Output: puzzle.outPoints by default: 10p

Mihai a primit de ziua lui un joc de puzzle. Jocul are NN piese confecționate prin lipirea unor bucăți de dimensiune 111 \cdot 1 (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:

  • 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;
  • Pe o coloană sunt cel mult 99 X-uri;
  • Toate piesele au același număr de coloane.

În figurile 1,2,3,41, 2, 3, 4 sunt piese de puzzle care respectă regulile descrise, iar în figura 55 și în figura 66 NU sunt piese de puzzle, pentru că nu pot fi obținute prin lipirea unor coloane de XX-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 XX-uri, toate coloanele având aceeași înălțime, este mulțumit. De exemplu, piesa din figura 11 și cea din figura 22 pot fi îmbinate în modul descris.
În figura 77 este piesa din figura 22 răsturnată sus-jos. În figura 88 este ilustrat dreptunghiul care se obține din piesa din figura 11 și piesa din figura 22 răsturnată sus-jos.
Observați că, dacă am roti piesa din figura 44, am putea să o îmbinăm cu piesa din figura 11, 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 XX-uri se află pe coloana corespunzătoare din piesă.
De exemplu:

  • piesa din figura 11 este codificată 42324232;
  • piesa din figura 22 este codificată 13231323;
  • piesa din figura 33 este codificată 44444444;
  • piesa din figura 44 este codificată 32313231.

Cerință

Determinați care este numărul de moduri în care Mihai poate alege câte două piese dintre cele NN 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 NN ce reprezintă numărul de piese din joc. Pe linia a doua se găsesc NN numere naturale, separate prin câte un singur spațiu, reprezentând codificările celor NN 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

  • 2N1052 \leq N \leq 10^5;
  • Numerele care reprezintă codificările pieselor au același număr de cifre (cel mult 55) și nu conțin cifra 00.
  • Într-o operație nu contează care dintre piese este răsturnată, ca urmare perechea formată din piesa aa și piesa bb este considerată ca fiind aceeași cu perechea formată din piesa bb și piesa aa.
  • Dreptunghiul obținut în urma unei operații poate avea înălțimea mai mare decât 99.
  • Pentru teste valorând 3030 de puncte N1 000N \leq 1 \ 000.

Exemplu

puzzle.in

5
222 432 234 123 111

puzzle.out

3

Explicație

Se pot îmbina 33 perechi de piese: piesa 11 cu piesa 55, piesa 22 cu piesa 33, piesa 22 cu piesa 44. Piesele 33 și 44 s-ar putea îmbina corect dacă una dintre ele ar fi răsturnată stânga-dreapta sau rotită, dar acest lucru nu e permis.

Log in or sign up to be able to send submissions!