Pracsiu Dan (dnprx) Într-un joc de domino, fiecare piesă este împărțită în două zone, în fiecare zonă fiind înscris un număr natural. Dacă jocul are dimensiunea d, în joc vor exista toate piesele distincte care se pot forma cu numere cuprinse între 0 și d. Două piese sunt considerate identice dacă au înscrise aceleași numere, indiferent de ordinea lor. Astfel, piesele (3,7) și (7,3) sunt identice. De exemplu, jocul de dimensiune d = 2 va avea 6 piese distincte:
Suma tuturor numerelor de pe aceste piese este 12. Problema are două cerințe:
1. Dat fiind un șir format din N numere naturale nenule reprezentând dimensiunile unor jocuri de domino, să se determine pentru fiecare joc suma tuturor numerelor înscrise pe piesele din jocul respectiv.
2. Dat fiind un șir format din N numere naturale nenule reprezentând sumele tuturor numerelor de pe piesele unor jocuri de domino, se construiește mai întâi un șir de cifre, notat cu A, scriind în ordine toate numerele din șirul dat, fără spații între ele. Se cere să se construiască un șir strict crescător de numere naturale, notat cu B, parcurgând alternativ cifrele din șirul A de la stânga la dreapta și de la dreapta la stânga după cum urmează:
– primul număr din B este format din prima cifră din șirul A;
– al doilea număr din B se construiește concatenând (alipind) cifrele din A, începând de la dreapta către stânga, până când obținem un număr strict mai mare decât primul număr din B;
– al treilea număr din B se construiește concatenând cifrele din A de la stânga către dreapta (începând cu prima cifră care nu a fost deja utilizată), până când obținem un număr strict mai mare decât precedentul din B;
– al patrulea număr din B se construiește concatenând din nou cifrele din A de la dreapta la stânga (începând cu cea mai din dreapta cifră care nu a fost deja utilizată), până când obținem un număr strict mai mare decât al treilea din B;
– se continuă astfel alternativ, până când nu se mai poate forma un număr strict mai mare decât ultimul număr adăugat în B.
Cerința
Scrieți un program care rezolvă cerințele 1 și 2 descrise în enunț.
Date de intrare
Fișierul de intrare domino.in conține pe prima linie un număr natural C reprezentând cerința care trebuie rezolvată (1 sau 2). Pe a doua linie se află numărul natural N. Pe a treia linie se află N numere naturale nenule separate prin câte un spațiu d1, d2, …, dN.
Date de ieșire
Fișierul de ieșire domino.out va conține o singură linie. Dacă C = 1, pe prima linie se vor afișa N numere naturale separate prin câte un spațiu; al i-lea număr afișat reprezintă suma numerelor din jocul de domino având dimensiunea di (1 ≤ i ≤ N). Dacă C = 2, pe prima linie se vor afișa în ordine, separate prin câte un spațiu, valorile din șirul B determinat conform regulilor din enunț.
Restricții și precizări
1 ≤ N ≤ 10.000- Dacă
C = 1,1 ≤ di≤ 1000, iar dacăC = 2,1 ≤ di≤ 109, pentru1 ≤ i ≤ N. - Numerele din șirul
Bvor fi afișate fără zerouri nesemnificative (de exemplu, dacă în urma aplicării regulilor din enunț în șirulBse obține numărul0204se afișează204). - Pentru teste în valoare de
30de puncte cerința este 1.
Exemplul 1:
domino.in
1 5 2 3 15 4 7
domino.out
12 30 2040 60 252
Explicație
Cerinţa este 1, deci trebuie să determinăm sumele numerelor din jocurile de dimensiune 2, 3, 15, 4 și 7.
Exemplul 2:
domino.in
2 5 12 30 2040 60 252
domino.out
1 2 23 52 204
Explicație
Din șirul 12 30 2040 60 252 se formează:
