# PBinfo #3694 – tomi – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Tomi este primarul ales în orașul Bittown. În oras sunt N locuitori și fiecare are un gard format din exact 60 de scânduri, fiecare dintre ele fiind vopsită în alb sau negru. Fiecare gard este codificat de Tomi printr-un număr natural a cărui reprezentare binară reproduce configurația gardului, de la stânga spre dreapta, scândurile negre fiind asimilate cu bitul 1 iar cele albe cu bitul 0. Astfel, ca exemplu, gardul care are doar ultimele două scânduri vopsite în negru va fi codificat de Tomi cu numărul 3. Tomi decide să-și construiască un gard care să fie reprezentativ pentru Bittown, adică să respecte toate regulile următoare:

1. Gardul primarului Tomi trebuie să aibă exact 60 de scânduri;
2. Trebuie să existe cel puțin K locuitori în Bittown care constată că pentru toate scândurile negre din gardul propriu, scândurile situate pe aceeași poziție în gardul primarului Tomi sunt vopsite tot în negru;
3. Numărul reprezentând codul gardului primarului Tomi trebuie să fie minim posibil.

Date de intrare
Fișierul de intrare tomi.in conține pe prima linie doua numere naturale N și K. Pe cea de-a doua linie se află N numere, reprezentând codurile gardurilor locuitorilor din Bittown.

Date de ieșire
Fișierul de ieșire tomi.out va conține un singur număr reprezentand codul gardului construit de primarul Tomi.

Restricții și precizări

1 ≤ N ≤ 100.000
Fiecare cod este strict mai mic decât 260.
Pentru 19 puncte, toți copiii vor avea doar codurile 1, 2 sau 3.
Pentru alte 38 puncte, codurile copiilor vor mai mici decât 60.

Exemplu:
tomi.in

6 3
1 1 5 8 10 8
tomi.out

5
Explicație
Răspunsul este 5 care are configurația în binar 101. Acesta este reprezentativ pentru codurile primelor trei garduri (1 1 5), pentru că le include configurațiile binare, respectând astfel regula 2.

## Cod sursă C++

```cpp
#include <bits/stdc++.h> 
using namespace std; 
ifstream f ("tomi.in"); 
ofstream g ("tomi.out"); 
const int nmax = 1e5 + 3; 
long long v[nmax], usu, act; 
int n, nr, k; 
int main() 
{ 
    f >> n >> k; 
    for (int i = 1; i <= n; ++i) 
        f >> v[i]; 
    usu = (1ll<<60) - 1ll; 
    for (long long i = 59; i >= 0; --i) 
    { 
        act = usu ^ (1ll<<i); 
        nr = 0; 
        for (int j = 1; j <= n; ++j) 
            if ((v[j] | act) == act) ++nr; 
        if (nr >= k) 
            usu = act; 
    } 
    g << usu << '\n'; 
    g.close();
    return 0; 
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3694)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3694/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3694/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)