Cod sursa(job #2140534)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 23 februarie 2018 16:33:41
Problema Cifre Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream in ("cifre.in");
ofstream out ("cifre.out");
int const nmax = 10;
int lim[2][5 + nmax];
int l[2];
int dif = 0;
void readnumber(int p){
  int a , a2;
  in>>a;
  if(p == 0){
    a--;
    dif -= a;
  } else
    dif += a;
  a2 = a;
  while(0 < a2){
    a2 /= 10;
    l[p]++;
  }
  for(int i = l[p] ; 0 < i ;i--){
    lim[p][i] = a % 10;
    a /= 10;
  }
}
int dp[2][5 + nmax][5 + nmax][2];
int c ;
void computedp(int p){
  for(int i = l[p] ; 0 < i ;i--){
    if(i == l[p]){
      for(int j = 0 ; j < 10 ; j++){
        dp[p][i][(j == c)][j <= lim[p][i]] ++;
      }
    } else{
      for(int j = 0 ; j < 10 ;j++){
        if(j == lim[p][i]){
          for(int k = 0 ; k <= 10 ;k++){
            dp[p][i][k + (j == c)][true] += dp[p][i + 1][k][true];
            dp[p][i][k + (j == c)][false] += dp[p][i + 1][k][false];
          }
        } else{
          for(int k = 0 ; k <= 10 ;k++){
            dp[p][i][k + (j == c)][j < lim[p][j]] += dp[p][i + 1][k][true] + dp[p][i + 1][k][false];
          }
        }
      }
    }
  }
}
int main()
{
  readnumber(0);
  readnumber(1);
  int k = 0;
  in>>c>>k;
  computedp(0);
  computedp(1);
  int result = 0;
  for(int i = k ; i <= 10 ;i++){
    result += dp[1][1][i][true];
    result -= dp[0][1][i][true];
  }
  out<<result / double(dif);
  return 0;
}