Fișierul intrare/ieșire | domino3.in, domino3.out | Sursă | ONI 2019 clasa a 7-a |
---|---|---|---|
Autor | Maria Niță | Adăugată de | Matteo.Verz • Matteoalexandru |
Timp de execuție pe test | 0.4 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Domino3 (clasa a 7-a)
Î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ță
Scrieți un program care rezolvă cerințele 1 și 2 descrise în enunț
Date de intrare
Fișierul de intrare domino3.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 domino3.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
- 1 ≤ N ≤ 104
- Dacă C=1, 1 ≤ di ≤ 1000, iar dacă C=2, 1 ≤ di ≤ 109, pentru 1≤i≤N.
- Numerele din șirul B vor fi afișate fără zerouri nesemnificative (de exemplu, dacă în urma aplicării regulilor din enunț în șirul B se obține numărul 0204 se afișează 204).
- Pentru teste în valoare de 30 de puncte cerința este 1.
Exemplu
domino3.in | domino3.out | Explicații |
---|---|---|
1 5 2 3 15 4 7 |
12 30 2040 60 252 | Cerința este 1, deci trebuie să determinăm sumele numerelor din jocurile de dimensiune 2, 3, 15, 4 și 7. |
2 5 12 30 2040 60 252 |
1 2 23 52 204 |
Din șirul 12 30 2040 60 252 se formează: |