toj_2872_5.cpp

Tianjin University Online Judge 的80多道题目 .

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
string s,t;
int le,j,p[12];
int ans[12];

void Add(int ans[12],int p[12])
{
  int len=ans[0],j;
  if (len<p[0]) len=p[0];
  for (j=1;j<=len;j++)
    {
      ans[j]+=p[j];
      ans[j+1]+=int(ans[j]/10);
      ans[j]=ans[j]%10;
    }
  if (ans[len+1]>0) len++;
  ans[0]=len;
}

void Find(int i,int le)
{
  if (i>=s.length()) return;
  if (s[i]>='0'&&s[i]<='9')
    {
      if (s[i]>t[i]) 
	{
	  //Add(ans);return;
	  p[0]=le+1;
	  for (j=1;j<=11;j++) p[j]=0;
	  p[le+1]=1;
	  Add(ans,p);
	  return;
	}
      if (s[i]==t[i]) Find(i+1,le);
      if (s[i]<t[i]) return;
    }
  if (s[i]=='?')
    {
      p[0]=le;
      for (j=1;j<=11;j++) p[j]=0;
      p[le]=(9-int(t[i])+48);
      if (9-int(t[i])+48==0) {p[0]=1;p[1]=0;}
      Add(ans,p);
      Find(i+1,le-1);
    }
}

int main()
{
  while (cin>>s)
    {
      if (s=="#") break;
      cin>>t;
      le=0;
      memset(ans,0,sizeof(ans));ans[0]=1;
      for (j=0;j<s.length();j++)
	if (s[j]=='?') le++;
      if (le>0) Find(0,le);
      for (j=ans[0];j>=1;j--) cout <<ans[j];cout <<endl;
    }
  return 0;
}