Fișierul intrare/ieșire domino3.in, domino3.out Sursă ONI 2019 clasa a 7-a
Autor Maria Niță Adăugată de avatar Matteoalexandru Matteo.Verz Matteoalexandru
Timp de execuție pe test 0.4 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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ă:

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii