# PBinfo #2017 – P2017 – Rezolvare C++

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

## Enunț

Cerința
Să se răspundă la Q întrebări de forma: “Care este numărul natural minim x astfel încât cifra c să apară de cel puțin K ori în reprezentarea tuturor numerelor naturale nenule mai mici sau egale cu x?”

Date de intrare
Fișierul de intrare 2017.in conține pe prima linie numărul Q, iar pe următoarele Q linii se află câte două numere naturale c și K separate printr-un spațiu, reprezentând întrebările.

Date de ieșire
Fișierul de ieșire 2017.out va conține Q linii, pe linia i aflându-se răspunsul la întrebarea i.

Restricții și precizări

1 ≤ Q ≤ 10.000
1 ≤ c ≤ 9
1 ≤ K ≤ 10^12

Exemplu:
2017.in

5
1 7
5 5
5 11
1 1
6 13
2017.out

14
45
55
1
66
Explicație
Pentru prima întrebare cifra 1 apare de 7 ori în secvența 1, 10, 11, 12, 13, 14. Deci răspunsul va fi 14.

## Cod sursă C++

```cpp
//Popa Bogdan Ioan, clasa a 10-a, Colegiul National Aurel Vlaicu Orastie
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("2017.in");
ofstream fout("2017.out");
int Q;
ll K;
int c;
ll getFreq(ll n, int c)
{
    ll sol = 0;
    ll p10 = 1;
    ll k = 0;
    while(n >= c)
    {
        if(n % 10 > c)
            sol += (n / 10 + 1) * p10;
        else if(n % 10 == c)
            sol += (n / 10) * p10 + k + 1;
            else sol += (n / 10) * p10;
        k += (n % 10) * p10;
        n /= 10;
        p10 *= 10;
    }
    return sol;
}
ll query(int c, ll K)
{
    ll le = 1, ri = 1e13, mid, best;
    while(le <= ri)
    {
        mid = (le + ri) / 2;
        if(getFreq(mid, c) >= K)
        {
            best = mid;
            ri = mid - 1;
        }
        else le = mid + 1;
    }
    return best;
}
int main()
{
    for(fin >> Q; Q; Q--)
    {
        fin >> c >> K;
        fout << query(c, K) << "\n";
    }
    return 0;
}
```

## Resurse

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