OLI 2024, Brașov, clasa a IX-a · Clasa a IX-aAlgoritmi elementariCifrele unui număr
Problema Cod
Algorel este noul responsabil al magazinului CODDE. Magazinul conține n produse de o calitate superioară.
Fiecărui produs i se asociază zilnic câte un cod, un număr natural nenul. Magazinul are mai mulți clienți fideli pe care Algorel încearcă să îi mulțumească zilnic, de aceea el alege în fiecare seară o serie de produse pentru a le oferi a doua zi clienților fideli la prețuri speciale, pentru aceasta generează un cod-cifră pe care îl trimite fiecărui client fidel.
Pentru a genera codul promoțional Algorel procedează astfel: alege produsele care au codurile cele mai mari m (1 ≤ m ≤ 6) numere prime, apoi calculează cifra de control a fiecărui numărului găsit, în final cu cifrele găsite construiește un număr natural cu cifrele generate în ordine crescătoare, iar apoi determină ultima cifră nenulă a factorialului numărului generat, cifra-cod generată o oferă tuturor clienților fideli.
Cerință
Algorel dorește să determine cât mai rapid cifra-cod și de aceea vă roagă să îl ajutați.
Date de intrare
Fișierul de intrare cod.in conține pe prima linie două numere naturale nenule n și m separate printr-un spațiu, pe următoarele linii se găsesc n numere naturale nenule.
Date de ieșire
Fișierul de ieșire cod.out conține pe prima linie o singură cifră.
Restricții și precizări
1 ≤ n ≤ 10.0001 ≤ m ≤ 62 ≤ valoare cod produs ≤ 106- Pentru 30% din teste
m = 1 - Pentru 70% din teste
2 ≤ m ≤ 6 - Șirul celor
nnumere naturale va conține întotdeauna cel puținmnumere prime - Cifra de control a unui număr natural se obține calculând în mod repetat suma cifrelor numărului până când suma va fi formată dint-o singură cifră. Cifra de control a numărului
1782este9(1782 -> 18 -> 9)
Exemple
10 1 10 131 20 19 19 131 200 1000 6 11
2
10 4 1000 11 509 100 10 11 149 220 509 5
6
Explicația exemplelor
Pentru primul exemplu. Pentru m = 1, se caută cel mai mare număr prim din șirul celor n numere citite, în cazul acesta numărul prelucrat este 131. Se formează numărul 5 din cifra de control corespunzătoare. Ultima cifră nenulă a lui 5! este 2.
Pentru al doilea exemplu. Pentru m = 4, se caută cele mai mari 4 numere prime din șirul celor n numere citite, în cazul acesta numerele căutate sunt 509, 509, 149, 11. Se formează numărul 2555 cu cifrele de control corespunzătoare numerelor găsite. Ultima cifră nenulă a lui 2555! este 6.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;