Cod sursa(job #2140581)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 23 februarie 2018 17:31:14
Problema Cifre Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 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][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]][1] ++;
      }
    } 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][0 < j] += dp[p][i + 1][k][true][0] + dp[p][i + 1][k][true][1];
            dp[p][i][k + (j == c)][false][0 < j] += dp[p][i + 1][k][false][0] + dp[p][i + 1][k][false][1];
          }
        } else{
          for(int k = 0 ; k <= 10 ;k++){
            dp[p][i][k + (j == c)][j < lim[p][i]][0 < j] += dp[p][i + 1][k][true][0] + dp[p][i + 1][k][true][1];
            dp[p][i][k + (j == c)][j < lim[p][i]][0 < j] += dp[p][i + 1][k][false][0] + dp[p][i + 1][k][false][1];
          }
        }
      }
    }
  }
}
int main()
{
  readnumber(0);
  readnumber(1);
  int k = 0;
  in>>c>>k;
  computedp(0);
  computedp(1);
  int result = 0;
  bool ok = 0;
  for(int j = 1 ; j <= l[0] ;j++){
    for(int i = k ; i <= 10 ;i++){
      result -= dp[0][j][i][true][1];
      if(1 < j)
        result -= dp[0][j][i][false][1];
    }
  }
  for(int j = 1 ; j <= l[1] ;j++){
    for(int i = k ; i <= 10 ;i++){
      result += dp[1][j][i][true][1];
      if(1 < j)
        result += dp[1][j][i][false][1];
    }
  }
  out<<result / double(dif);
  return 0;
}