Sharif ICPC Regionals 2006 - Problem B

   1:#include <string>
   2:#include <vector>
   3:#include <fstream>
   4:#include <iomanip>
   5:#include <iostream>
   6:#include <algorithm>
   7:
   8:using namespace std;
   9:
  10:#define PROB_NAME   "B"
  11:
  12:typedef unsigned long long u64;
  13:
  14:u64 Pow10 [14] = {
  15:    1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
  16:    100000000, 1000000000, 10000000000, 100000000000,
  17:    1000000000000, 10000000000000
  18:};
  19:
  20:u64 WildCount (const string & w, const string & x, unsigned i, unsigned remw)
  21:{
  22:    if (i >= w.size()) return 0;
  23:    else if (w[i] == '?') return WildCount(w, x, i + 1, remw - 1) + Pow10[remw - 1] * ('9' - x[i]);
  24:    else if (w[i] > x[i]) return Pow10[remw];
  25:    else if (w[i] < x[i]) return 0;
  26:    else return WildCount(w, x, i + 1, remw);
  27:}
  28:
  29:int main ()
  30:{
  31:    ifstream fin (PROB_NAME ".in");
  32:  
  33:    string w, x;
  34:    while ((fin >> w >> x) && w != "#")
  35:        cout << WildCount(w, x, 0, (unsigned)count(w.begin(), w.end(), '?')) << endl;
  36:  
  37:    return 0;
  38:}
  39: