Simulare 2012 Baraj Seniori | alice

This was the problem page during the contest. Access the current page here.
Time limit: 0.1s Memory limit: 4MB Input: alice.in Output: alice.out

Într-o zi frumoasă de vară, Alice se juca în parc. Deodată, văzu un iepure cu ceas, numit Iepurele Alb, sărind grăbit în scorbura unui copac. Curioasă, Alice îl urmări şi sări şi ea în scorbură. Spre mirarea ei, ajunse într-o sală mare cu NN uşi încuiate. Pe fiecare uşă era scris câte un număr natural. Într-o clipă, lângă ea apăru Iepurele Alb şi-i spuse că doar uşile cu numere magice pot fi deschise dacă are cheile potrivite. Pentru a o ajuta, Iepurele Alb i-a explicat că un număr magic este un număr natural care poate fi redus la o cifră prin complementarea cifrelor acestuia faţă de cifra sa maximă din scrierea zecimală, apoi prin complementarea cifrelor numărului obţinut faţă de cifra sa maximă şi aşa mai departe până când se obţine o cifră. Evident, nu toate numerele naturale sunt numere magice. De exemplu, uşa cu numărul 12341234 poate fi deschisă cu cheia inscripţionată cu cifra 11 deoarece 12341234 este un număr magic ce poate fi redus la cifra 11 prin complementări repetate (12343210123210121011234 \rightarrow 3210 \rightarrow 123 \rightarrow 210 \rightarrow 12 \rightarrow 10 \rightarrow 1), iar uşa cu numărul 12041204 nu poate fi deschisă deoarece 12041204 nu este un număr magic (indiferent de câte ori s-ar repeta complementarea nu poate fi redus la o cifră: 12043240120432401204...1204 \rightarrow 3240 \rightarrow 1204 \rightarrow 3240 \rightarrow 1204 \rightarrow ... ).

Înainte să dispară, Iepurele Alb îi dădu o cheie aurie inscripţionată cu cifra KK şi o avertiză că poate deschide cu această cheie doar uşile cu numere magice ce pot fi reduse la cifra KK.

Cerință

Scrieţi un program care să citească numerele naturale NN, KK şi cele NN numere naturale scrise pe cele NN uşi, şi care să determine:

  • cel mai mare număr par dintre numerele scrise pe cele NN uşi;
  • numărul uşilor care pot fi deschise cu cheia aurie inscripţionată cu cifra KK.

Date de intrare

Pe prima linie a fișierului de intrare alice.in se găsesc numerele NN şi KK și pe cea de-a doua linie NN numere naturale reprezentând numerele scrise pe cele NN uşi.

Date de ieșire

Programul va afișa in fișierul de ieșire alice.out, în această ordine:

  • pe prima linie, un număr natural reprezentând cel mai mare număr par dintre numerele scrise pe cele NN uşi;
  • pe cea de-a doua linie, un număr natural reprezentând numărul uşilor care pot fi deschise cu cheia aurie inscripţionată cu cifra KK.

Restricții și precizări

  • 7N10 0007 \leq N \leq 10 \ 000;
  • 0K90 \leq K \leq 9;
  • complementarea cifrelor unui număr natural faţă de cifra sa maximă din scrierea zecimală constă în înlocuirea fiecărei cifre cc din număr cu diferenţa dintre cifra maximă şi cifra cc; de exemplu, cifra maximă a numărului 12341234 este 44 iar prin complementare se înlocuieşte cifra 11 cu 33, cifra 22 cu 22, cifra 33 cu 11 şi cifra 44 cu 00 rezultând numărul 32103210;
  • pe fiecare uşă este scris un singur număr natural;
  • există cel puţin o uşă pe care este scris un număr par;
  • numărul scris pe oricare uşă (din cele NN) este mai mare sau egal cu 10 şi mai mic sau egal cu 3280032800;
  • pentru rezolvarea corectă a cerinţei a) se acordă 20% din punctaj, iar pentru rezolvarea corectă a ambelor cerinţe se acordă 100% din punctaj.

Exemplu

alice.in

7 1
1204 1234 13 195 23 10 888

alice.out

1234
3

Explicație

  • Sunt N=7N = 7 uşi pe care sunt scrise numerele 12041204, 12341234, 1313, 195195, 2323, 1010, 888888. Cel mai mare număr par dintre cele scrise pe uşi este 12341234.
  • Cheia primită este inscripţionată cu cifra K=1 şi deschide 3 uşi cu numerele 1234, 23 şi 10 deoarece numerele magice dintre cele scrise pe uşi sunt: 12341234 (12343210123210121011234 \rightarrow 3210 \rightarrow 123 \rightarrow 210 \rightarrow 12 \rightarrow 10 \rightarrow 1), 1313 (1320213 \rightarrow 20 \rightarrow 2), 195195 (195804844195 \rightarrow 804 \rightarrow 84 \rightarrow 4), 2323 (2310123 \rightarrow 10 \rightarrow 1), 1010 (10110 \rightarrow 1), 888888 (8880888 \rightarrow 0). Numărul 12041204 nu este un număr magic.

Log in or sign up to be able to send submissions!