Cod sursa(job #2434349)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 1 iulie 2019 16:01:05
Problema Cifre Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("cifre.in");
ofstream out("cifre.out");

int dp[17][17][2][2];

int a, b, c, k;

int f(int p)
{
    if(p < 0)
        return 0;

    memset(dp, 0, sizeof(dp));

    vector <int> v;

    while(p)
    {
        v.push_back(p % 10);
        p /= 10;
    }

    if(v.size() == 0)
        v.push_back(0);

    reverse(begin(v), end(v));

    int n = v.size();

    dp[0][0][0][0] = 1;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            for(int flag = 0; flag <= 1; flag++)
            {
                for(int nenul = 0; nenul <= 1; nenul++)
                {
                    for(int cif = 0; cif <= 9; cif++)
                    {
                        if(flag == 0 && cif > v[i])
                            continue;

                        bool new_flag = 1;
                        bool new_comp = 1;
                        int new_cnt = j;

                        if(cif == c && (c > 0 || nenul == 1)) new_cnt++;
                        if(flag == 0 && cif == v[i])          new_flag = 0;
                        if(nenul == 0 && cif == 0)            new_comp = 0;

                        dp[i + 1][new_cnt][new_flag][new_comp] += dp[i][j][flag][nenul];
                    }
                }
            }
        }
    }

    int sum = 0;

    for(int i = k; i <= n; i++)
        sum += dp[n][i][0][1] + dp[n][i][1][1];

    if(c == 0 && k <= 1)
        sum++;

    return sum;
}

int main()
{
    in >> a >> b >> c >> k;

    int fav = f(b) - f(a - 1);
    int all = b - a + 1;

    out << fixed << setprecision(5) << fav * 1.0 / all;
}