Rezolvare completă PbInfo #2154 okcpp

Despre numărul natural N spunem că are proprietatea okcpp dacă oricum alegem K cifre ale sale vom găsi printre ele cel puţin P cifre distincte (oricare k cel puțin p).

Cerințe

(1) Fiind date numerele naturale K, P, A și B să se calculeze și să se afișeze numărul de numere okcpp din intervalul [A,B].
(2) Fiind date numerele naturale K, P și N să se calculeze și să se afișeze cel mai mic număr okcpp care este mai mare sau egal cu N.

Date de intrare

Fișierul de intrare okcpp.in conține pe primul rând numărul C.

Dacă C=1, atunci pe al doilea rând se vor afla scrise, separate prin spațiu, numerele naturale K, P, A și B. Dacă C=2, atunci pe al doilea rând se vor afla scrise, separate prin spațiu, numerele naturale K, P și N.

Date de ieșire

Dacă C=1, atunci în fişierul de ieşire okcpp.out se va scrie numărul de numere okcpp din intervalul [A;B].

Dacă C=2, atunci în fişierul de ieşire okcpp.out se va scrie cel mai mic număr natural okcpp care este mai mare sau egal cu N.

Restricții și precizări

  • 1 ≤ P ≤ 10
  • P ≤ K ≤ numărul de cifre al lui N ≤ 18
  • Pentru 20% din teste cerinţa va fi C=1.
  • Pentru cerința C=1 vom avea 0 ≤ A < B < 1018 și B-A ≤ 10000.
  • Pentru cerința C=2 se garantează că există întotdeauna soluție.

Exemplul 1

okcpp.in

1
5 2 99997 100001

okcpp.out

3

Explicație

Avem K=4 și P=2. În intervalul [99997;100001] sunt trei numere okcpp: 99997, 99998 și 100001.

Exemplul 2

okcpp.in

2
5 3 99997

okcpp.out

100023

Explicație

Avem K=5, P=3 și N=99997. Se observă uşor că numerele 99997, 99998, …, 100022 nu corespund. Primul număr care corespunde cerinţelor este 100023.

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 okcpp:

#include <vector>
#include <string>
#include <fstream>
#include <numeric>
#include <algorithm>
using namespace std;

bool isGoodFrequency(vector<int> C, int K, int P)
{
    sort(C.begin(), C.end(), greater<int>());
    if (C[P - 1] == 0) return false;
    return (accumulate(C.begin(), C.begin() + P - 1, 0) < K);
}

bool isGood(string &S, int K, int P)
{
    vector<int>  C(10);
    for (char d : S) C[d - '0']++;
    return isGoodFrequency(C, K, P);
}

bool canFill(vector<int> C, int K, int P, int N)
{
    while (N--) (*min_element(C.begin(), C.end()))++;
    return isGoodFrequency(C, K, P);
}

string findNext(string S, int K, int P)
{
    if (isGood(S, K, P)) return S;

    vector<int> C(10);
    for (char d : S) C[d - '0']++;

    int     i       = S.length() - 1;
    bool    found   = false;
    for (; i >= 0; i--)
    {
        C[S[i] - '0']--;
        for (char d = S[i] + 1; d <= '9'; d++)
        {
            C[d - '0']++;
            if (canFill(C, K, P, S.length() - i - 1)) { found = true; S[i] = d; break; }
            C[d - '0']--;
        }
        if (found) break;
    }

    if (i < 0)
    {
        S       = string(S.length() + 1, '0');
        S[0]    = '1';
        i       = 0;
        C[1]++;
        if (!canFill(C, K, P, S.length() - 1)) return "-1";
    }

    for (i++; i < S.length(); i++)
        for (char d = '0'; d <= '9'; d++)
        {
            C[d - '0']++;
            if (canFill(C, K, P, S.length() - i - 1)) { S[i] = d; break; }
            C[d - '0']--;
        }

    return S;
}

int main()
{
    ifstream    f("okcpp.in");
    ofstream    g("okcpp.out");
    int         C, K, P, ns;
    long long   A, B, X;
    string      S;

    f >> C ;
    if(C == 1)
    {
        f >> K >> P >> A >> B;
        ns = 0;
        for( X = A; X <= B ; X ++)
        {
            S = to_string(X);
            if(isGood(S, K, P))
            {
                ns ++;
            }
        }
        g << ns << endl;
    }
    else
    {
        f >> K >> P >> S;
        g << findNext(S, K, P) << endl;
    }

    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 #2154 okcpp

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2154 okcpp 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!