Cod sursa(job #1747404)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 24 august 2016 21:09:03
Problema Cifre Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.15 kb
//#include <iostream>
//#include <cstdio>
//#include <ctime>
//
//using namespace std;
//
//int from(int lo, int hi)
//{
//    return lo + rand()%(hi-lo);
//}
//
//
//int debugSolve(int a, int b, int c, int k)
//{
//	int rez = 0;
//    for (int i = a; i <= b; i++)
//	{
//		int x = i;
//        int cate = 0;
//        for (x; x; x /= 10)
//            if (x % 10 == c)
//				cate++;
//		if (cate >= k)
//			rez++;
//	}
//	return rez;
//}
//int debugSolve2(int a, int b, int c, int k)
//{
//	int rez = 0;
//    for (int i = a; i <= b; i++)
//	{
//		int x = i;
//        int cate = 0;
//        do {
//            if (x % 10 == c)
//				cate++;
//			x /= 10;
//        } while(x);
//		if (cate == k)
//			rez++;
//	}
//	return rez;
//}
//int a, b, c, k;
//
//int mat[20][20]; // cate nr de i cifre au j cifre c (pot sa inceapa cu 0)
//int smat[20][20]; // cate nr de i cifre au j cifre c
//int aha(int abcd, int j, bool first = false), B(int dig, int x, int j);
//
//int bonus(int nr, int j)
//{
//    int cate = 0;
//    while (nr > 0) {
//		cate++;
//		nr /= 10;
//    }
//    return mat[cate][j];
//}
//
//int solve()
//{
//	mat[0][0] = 1;
//    //mat[1][1] = 1;
//    //mat[1][0] = 9;
//    for (int i = 1; i <= 10; i++)
//        for (int j = 0; j <= 10; j++)
//			mat[i][j] = mat[i-1][j] * 9 + (j ? mat[i-1][j-1] : 0);
//	smat[0][0] =1;
//	//smat[1][1] = 1;
//    //smat[1][0] = (c == 0 ? 9 : 8);
//    for (int i = 1; i <= 10; i++)
//        for (int j = 0; j <= 10; j++)
//			smat[i][j] = (c == 0 ? 9*mat[i-1][j] : 8*mat[i-1][j] + (j ? mat[i-1][j-1] : 0)) + smat[i-1][j];
//	int rez = 0;
//	for (int z = k; z <= 10; z++) {
//		if (debugSolve2(0, b, c, z) != aha(b+1, z))
//			cerr << "";
//		if (debugSolve2(0, a-1, c, z) != aha(a, z))
//			cerr << "";
//		rez += aha(b+1, z, true) - aha(a, z, true);
////		if (c == 0)
////			rez += bonus(b+1, z) - bonus(a, z);
//	}
//	return rez;
//}
//
//int aha(int abcd, int j, bool first)
//{
//    int ten, nrcif;
//    if (abcd == 0) return 0;
//    for (ten = 1, nrcif = 0; ten <= abcd; ten *= 10, nrcif++);
//    if (j > nrcif) return 0;
//    ten /= 10;
//    int bcd = abcd % ten;
//    int A = abcd / ten;
//    if (debugSolve2(0, A*ten-1, c, j) != B(A, nrcif, j)) {
//		debugSolve2(0, A*ten-1, c, j) != B(A, nrcif, j);
//		cerr << "ERRORB\n";
//    }
//    if (debugSolve2(0, bcd-1, c, j-(A==c)) != aha(bcd, j-(A==c))) {
//		debugSolve2(0, bcd-1, c, j-(A==c)) != aha(bcd, j-(A==c));
//		if (j)
//			cerr << "ERRORA\n";
//    }
//    int v = 0;
//	if (c == 0 && A != c && ten>=10 && !first && j) {
//		v += aha(ten-1, j-1);
//	}
//    return B(A, nrcif, j) + aha(bcd, j-(A == c)) + v;// + (c==0 && nrcif == j && j && j!=1);
//}
//
//int B(int dig, int x, int j)
//{
//    dig--;
//    int s;
//    if (dig >= c && c != 0) {
//		s = dig * mat[x-1][j] + mat[x-1][j-1];
//    }
//    else {
//		s = dig * mat[x-1][j];
//		s += smat[x-1][j] + (c==0 && j == 1) - (c == 0 && j == 0);
//    }
//
//	return s;
//}
//
//
//int main()
//{
//    freopen("cifre.in", "r", stdin);
//    freopen("cifre.out", "w", stdout);
//
//    srand(time(NULL));
//    for (int i = 0; i < 1000; i++) {
//        a = from(0, 10000);
//        b = from(a, 10000);
//        c = from(0, 10);
//        k = from(0, 5);
////        a = 1;
////        b = 13;
////        c = 1;
////        k = 1;
//        int my = solve();
//        printf("%d ", my);
//        int bun = debugSolve(a, b, c, k);
//        printf("%d\n", bun);
//        if (my != bun) {
//			solve();
//            a = 0;
//            cerr << "ERROR\n";
//            if (c != 0)
//				cerr << "NOOOOOOOOOOOOOOO ALLLLLLLLLERRRRRRRRTTTTTTTTTT";
//        }
//
//    }
//
//    return 0;
//}
#include<cstdio>
#include<cstdlib>
#include<ctime>

int a, b, c, k, rez, op, n, cate, x;

int main()
{
    freopen("cifre.in", "r", stdin);
    freopen("cifre.out", "w", stdout);

    scanf("%d %d %d %d", &a, &b, &c, &k);

    srand(time(NULL));
    op = 1000000;

    for (int i = 1; i <= op; i++)
    {
        x = a + rand() % (b - a + 1);
        cate = 0;
        while (x)
        {
            if (x % 10 == c)
				cate++;
            x /= 10;
        }
        if(cate >= k)
			rez++;
    }

    printf("%.4lf\n", (double)rez / (double)op);

    return 0;
}