ZCMU—1455

1455: A>B？

Time Limit: 1 Sec  

Memory Limit: 128 MB

​​Submit​​​][​​Status​​​][​​Web Board​​]

Description

下午4:30，小明和小黃在str實驗室A題，小黃對小明說：好餓啊，去不去食堂吃飯？小明說：等一下！我要把這題碼出來，XXOJ馬上破200了。可是....... 一個小時以後，小明還是停留在#include<iostream>上。小黃受不了了！但是小黃的APM實在太慢了，你能幫助他們早點去食堂吃飯嗎？

小明的題是這樣的：

輸入一個含字元‘X ’的整數A，‘X’可以表示0-9任意一個數字

再輸入一個整數B

請問有多少個這樣的A滿足 A>B?

Input

輸入A，B，A與B的長度相同，且不超過10

Output

每行輸出A可能的個數

Sample Input

12X3X4

123456

X9

Sample Output

60

HINT

第一個案例，第一個X可以為4,5,6,7,8,9任意一個數，第二個X可以為0,1,2,3,4,5,6,7,8,9任意一個數，故有60個A滿足A>B

第二個案例，不存在這樣的X滿足A>B

【分析】

一開始以為長度控制在10内是讓你暴力搜的...後來發現自己真蠢...

直接判斷就可以了,從高位往低位判斷，在前面全部相同的情況，如果某一位已經比下面那個數的同一位一位大了，那麼後面的X不需要判斷，直接ans+10^(這一位往後X的個數)  ...因為比較懶是以懶得去算數學公式了。。公式是肯定可以算的，連x的兩個情況也懶得算了...讓程式去算吧~

【代碼】

#include <stdio.h>
#include <string.h>
char s[11];
char ss[11];
int f[11];
int ans;
void find(int deep)
{
  if (s[deep]=='\0')  return;
  if (s[deep]==ss[deep]) find(deep+1);
  if (s[deep]=='X')
  {
    find(deep+1);
    ans+=(57-ss[deep])*f[deep];
  }
  else
    if (s[deep]>ss[deep])
      ans+=f[deep];
}

int main()
{
  while (~scanf("%s%s",s,ss))
  {
    memset(f,0,sizeof(f));
    f[strlen(ss)]=1;
    for (int j=strlen(ss)-1;j>=0;j--) f[j]=f[j+1]*(s[j+1]=='X'?10:1);
    ans=0;
    find(0);
    printf("%d\n",ans);
  }
}