2014
01-26

# Barbara Bennett’s Wild Numbers

A wild number is a string containing digits and question marks (like 36?1?8). A number X matches a wild number W if they have the same length, and every non-question mark character in X is equal to the character in the same position in W (it means that you can replace a question mark with any digit). For example, 365198 matches the wild number 36?1?8, but 360199, 361028, or 36128 does not. Write a program that reads a wild number W and a number X from input, both of length n, and determines the number of n-digit numbers that match W and are greater than X.

There are multiple test cases in the input. Each test case consists of two lines of the same length. The first line contains a wild number W, and the second line contains an integer number X. The length of input lines is between 1 and 10 characters. The last line of input contains a single character #.

There are multiple test cases in the input. Each test case consists of two lines of the same length. The first line contains a wild number W, and the second line contains an integer number X. The length of input lines is between 1 and 10 characters. The last line of input contains a single character #.

36?1?8
236428
8?3
910
?
5
#

100
0
4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int main()
{
freopen("in.txt","r",stdin);
int ans,len;
char a[20],b[20];
while(1)
{
scanf("%s%s",a+1,b+1);
if(a[1]=='#') break;
ans = 0;
len = strlen(a+1)+2;
int f= 0;
int dp[20][2];
memset(dp,0,sizeof(dp));
a[len-1] = '0';
b[len-1] = '1';
for(int i=1; i<len; i++)
{
if(f==0)
{
if(a[i]=='?')
{
dp[i][0] = dp[i-1][0]*10+('9'-b[i]);
dp[i][1] = 1;
}
else
{
if(a[i]>b[i])
{
f=1;
dp[i][0]=max(dp[i-1][0]+dp[i-1][1],1);
}
else if(a[i]<b[i])
{
f=-1;
dp[i][0]=dp[i-1][0];
}
else
{
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][1];
}
}
}
else
{
if(a[i]=='?')
dp[i][0]=dp[i-1][0]*10;
else
dp[i][0]=dp[i-1][0];
}
}
printf("%d\n",dp[len-1][0]);
}
return 0;
}

1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

3. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环