Rezolvare completă PbInfo #2017 P2017

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 reprezenatrea 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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema P2017:

//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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2017 P2017

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2017 P2017 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!