1612 - Cifre10

Elevii clasei pregătitoare se joacă la matematică cu numere. Învățătoarea are un săculeț plin cu jetoane, pe fiecare dintre ele fiind scrisă câte o cifră. Fiecare elev și-a ales din săculeț mai multe jetoane, cu care și-a format un număr. Pentru ca totul să fie mai interesant, elevii s-au grupat în perechi. Doamna învățătoare a oferit fiecărei perechi de elevi câte o cutiuță pentru ca cei doi să își pună împreună jetoanele. De exemplu, dacă unul din elevii unei echipe și-a ales jetoane cu care a format numărul 5137131 iar celălalt elev și-a ales jetoane cu care a format numărul 6551813, atunci cutiuța echipei va conţine 5 jetoane cu cifra 1, câte 3 jetoane cu cifra 3 şi 5 şi câte un jeton cu cifrele 6, 7 şi 8.

Doar Andrei stătea supărat pentru că numărul de elevi al clasei era impar iar el nu avea partener, motiv pentru care nu și-a mai ales jetoane. Din această cauză, doamna învățătoare i-a spus:

“- Alege o echipă din a cărei cutiuță poţi lua o parte din jetoane, dar ai grijă ca fiecare dintre cei doi elevi să-și mai poată forma numărul lui din jetoanele rămase, iar tu să poți forma un număr nenul cu jetoanele extrase!“.

Dar cum Andrei nu se mulţumea cu puţin, a vrut să aleagă acea echipă din a cărei cutiuță îşi poată forma un număr de valoare maximă folosind jetoanele extrase.

Cerința

Scrieţi un program care să citească numărul N de cutiuțe și numerele formate de elevii fiecărei perechi și care să determine:

1) Numărul de cutiuțe din care Andrei poate lua jetoane respectând condiția pusă de doamna învățătoare;

2) Care este cel mai mare număr nenul pe care îl poate forma Andrei respectând aceeași condiție.

Date de intrare

Fișierul de intrare input.txt conține pe prima linie numărul natural P reprezentând cerința din problemă care trebuie rezolvată. Pe a doua linie numărul natural N, iar pe următoarele N linii câte două numere naturale separate printr-un spațiu reprezentând numerele formate de elevii fiecărei perechi.

Date de ieșire

• Dacă valoarea lui P este 1, fişierul de ieşire output.txt va conţine pe prima linie un număr natural reprezentând rezolvarea primei cerințe, adică numărul de cutiuțe din care Andrei poate lua jetoane.
• Dacă valoarea lui P este 2, fişierul de ieşire output.txt va conţine pe prima linie un număr natural reprezentând rezolvarea celei de a doua cerințe, adică numărul maxim pe care îl poate forma Andrei.

Restricții și precizări

• 0 < N ≤ 10000

Exemplul 1

input.txt:

1

3

1010 2000

12 34

1515 552

output.txt:

1

Explicație:

Cu jetoanele extrase din prima cutiuță Andrei nu poate forma un număr diferit de 0. Din a doua cutiuță Andrei nu poate lua jetoane astfel încât cei doi elevi să își mai poată forma numerele 12 și 34.

Andrei poate extrage jetoane doar din a treia cutiuță(două jetoane cu cifra 5).

Exemplul 2

input.txt:

2

5

16815  38861

12  385

5137131  6551813

15033  11583

4704  240

output.txt:

5311

Explicație:

Numărul maxim pe care Andrei îl poate forma este 5311 și se obține din cutiuța a treia.

Exemplul 3

input.txt:

2

99999999999999

16815  38861

12  385

5137131  6551813

15033  11583

4704  240

Output:

Input-ul nu convine conditiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare(n):

   if not(1<=n<=1000):
       print("Input-ul nu convine conditiilor")
       exit()

with open("input.txt", "r") as f, open("output.txt", "w") as g:

   a = [0] * 10
   b = [0] * 10
   n, i, x, y, j, k, p, cod, cate, maxim, minim = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

   p = int(f.readline())
   n = int(f.readline())
   verificare(n)

   for i in range(1, n + 1):
       x, y = map(int, f.readline().split())

       a = [0] * 10
       b = [0] * 10

       while x:
           a[x % 10] += 1
           x = x // 10

       while y:
           b[y % 10] += 1
           y = y // 10

       cod = 0
       for j in range(9, -1, -1):
           if a[j] > 0 and b[j] > 0:
               minim = min(a[j], b[j])
               for k in range(1, minim + 1):
                   cod = cod * 10 + j

       if cod:
           cate += 1

       if cod > maxim:
           maxim = cod

   if p == 1:
       g.write(f"{cate}")
   else:
       g.write(f"{maxim}")

</syntaxhighlight>