# PBinfo #2940 – Cifra4 – Rezolvare C++

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

## Enunț

Cerința
Pentru reprezentarea numerelor s-a decis să nu se mai folosească cifra C. Astfel din șirul numerelor naturale se vor elimina toate numerele care conțin cifra C. Notăm noul șir cu S.

1) Să se determine al N-lea număr din șirul S.
2) Se dau Y și Z, două numere naturale din șirul S. Să se determine numărul de numere naturale eliminate dintre Y și Z.

Date de intrare
Fișierul de intrare cifra4.in conține pe primul rând numărul T reprezentând tipul cerinței.
Dacă T=1, atunci pe al doilea rând vor fi scrise, separate prin spațiu, cifra C și numărul N.
Dacă T=2, atunci pe al doilea rând vor fi scrise separate prin spațiu cifra C și două numere naturale Y și Z.

Date de ieșire
În fișierul de ieșire cifra4.out se va scrie pe primul rând un singur număr natural conform tipului cerinței.

Restricții și precizări

1 ≤ N ≤ 10^13
0 ≤ C ≤ 9
1 ≤ Y ≤ 10^13
1 ≤ Z ≤ 10^13
pentru 20% din teste N va avea cel mult 5 cifre
pentru 20% din teste Y și Z vor avea cel mult 6 cifre

Exemplul 1:
cifra4.in

1
0 11
cifra4.out

12
Explicație
Al 11 număr din șirul S care nu conţine cifra 0 este 12.

Exemplul 2:
cifra4.in

2
1 3 20
cifra4.out

10
Explicație
Numerele eliminate din intervalul [3,20] sunt 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
using namespace std;
ifstream in("cifra4.in");
ofstream out("cifra4.out");
long long n,nr,x,y,p9[30];
int t,c,i,k,v[30];
long long getpoz(long long x)
{
    long long nr=x;
    k=0;
    while(nr)
    {
        v[++k]=nr%10;
        nr/=10;
    }
    for(int i=1;i<=k;i++)
        if(v[i]>c)
            v[i]--;
    nr=0;
    for(i=k;i>=1;i--)
        nr=nr*9+v[i];
    if(c!=0)
        return nr+1;
    long long sol=0,p=1;
    nr=0;
    do
    {
        int cif=x%10;
        sol+=(cif-1)*p;
        p*=9;
        nr++;
        x/=10;
    }
    while(x>0);
    for(int i=1;i<nr;i++)
        sol+=p9[i];
    return sol;
}
int main()
{
    in>>t;
    p9[0]=1;
    for(i=1;i<=17;i++)
        p9[i]=p9[i-1]*9;
    if(t==1)
    {
        in>>c>>n;
        if(c!=0)
        {
            nr = n-1;
            while(nr)
            {
                v[++k]=nr%9;
                nr/=9;
            }
            for(i=1;i<=k;i++)
                if(v[i]>=c)
                    v[i]++;
            for(i=k;i>=1;i--)
                out<<v[i];
            return 0;
        }
        nr=n-1;
        i=1;
        while(1)
        {
            if(nr-p9[i]>=0)
            {
                nr -= p9[i];
                i++;
            }
            else
                break;
        }
        /// in i avem numarul de cifre al numarului cautat
        /// acum repretam in baza 9 numarul
        while(k<i)
        {
            v[++k]=nr%9;
            nr/=9;
        }
        for(i=1;i<=k;i++)
            if(v[i]>=c)
                v[i]++;
        for(i=k;i>=1;i--)
            out<<v[i];
        return 0;
    }
    in>>c>>x>>y;
    if(x>y)
        swap(x,y);
    out<<(y-x+1)-(getpoz(y)-getpoz(x)+1);
    return 0;
}
```

## Resurse

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