Question

În oraşul Olimpidia, toate băncile au hotărât să adopte o convenţie în ceea ce priveşte identificarea clienţilor săi, astfel încât fiecare cont deschis de un client să aibă asociat un cod format din exact 6 cifre:

prima cifră (cea mai din stânga cifră a codului) va reprezenta numărul băncii (acest lucru fiind posibil deoarece în oraş nu sunt mai mult de 9 bănci, acestea fiind numerotate începând de la 1);
a doua cifră va reprezenta genul persoanei (1 pentru genul masculin şi 2 pentru genul feminin);
ultimele 4 cifre vor reprezenta suma aflată în contul persoanei în momentul în care se aplică stabilita convenţie.
Cerința
Cunoscând numărul total de conturi deschise şi codurile corespunzătoare acestora să se determine suma maximă pe care o are o persoană de gen masculin într-un cont aflat la banca X.

Date de intrare
Fişierul de intrare conturi.in conţine pe prima linie numerele naturale N X, care reprezintă numărul de conturi deschise la băncile din oraş, respectiv numărul băncii pentru care trebuie aflată suma maximă. Pe următoarele N linii se află N numere naturale nenule, câte un număr pe o linie, reprezentând codurile conturilor, obţinute în urma aplicării convenţiei.

Date de ieșire
Fişierul de ieşire conturi.out va conţine o singură linie pe care va fi scrisă suma maximă pe care o persoană de gen masculin o are într-un cont aflat la banca X.

Restricții și precizări
1 ≤ N ≤ 100
1 ≤ X ≤ 9
Pentru datele de test se garantează că există cel puţin un cont la banca X aparţinând unei persoane de gen masculin.



Exemplu
conturi.in

5 2
213400
515000
229088
326909
217044
conturi.out

7044
Explicație
Există 5 conturi: 3 la banca 2, unul la banca 5 şi unul la banca 3.
Dintre cele 3 conturi deschise la banca 2, sunt 2 conturi deţinute de bărbaţi, unul cu suma 3400, celălalt cu suma 7044. Suma maximă cerută este 7044.

Answer 1

Complexitate timp : O(N)
Complexitate memorie: O(1)

Putem accesa cifrele numarului in complexitate O(1).
Codul este format din 6 cifre. Fie un numar x. Prin operatia x%10 obtinem ultima cifra a numarului. Ca sa accesam penultima cifra calculam x/10%10. Pentru a accesa antepenultima cifra calculam x/100%10. 
Conform acestui tipar, pentru a accesa prima cifra a codului de 6 cifre folosim x/10000%10 (eventual si x/1 000 000 deoarece este prima cifra). Pentru a accesa a doua cifra a numarului calculam x/10000%10. 

Fie X numarul bancii. Mai intai trebuie sa vedem daca clientul cu codul A are cont deschis la acea banca, deci  daca A/1000000 =X.  Daca clientul are cont deschis la acea banca verificam daca este barbat A/10000%10 =1. 
Suma o putem calcula prin accesarea in acelasi mod a ultimelor 4 cifre.

#include <iostream>

using namespace std;

int main()
{
   ifstream fin("conturi.in");
   ofstream fout("coduri.out);

   unsigned long long cod, sMax = 0, sCurent;
   unsigned short N, X;
   fin>>N>>X;
   for(unsigned short i=1; i<=N; i++)
   {
      fin>>cod;
      if(cod/1000000==X && cod/10000%10 == 1)
      {
         sCurent = 1000*cod/1000%10 + 100*cod/100%10 + 10*cod/10%10 + cod%10;
        if(sCurent > sMax) sMax = sCurent;
     }
     fout<<sCurent;
}