Barbara Bennett's Wild Numbers

http://acm.pku.edu.cn/JudgeOnline/problem?id=3340

Description

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.

Input

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 #.

Output

For each test case, write a single line containing the number of n-digit numbers matching W and greater than X (n is the length of W and X).

Source

Tehran 2006


Solving

wild number란 숫자중에 ?를 포함한 숫자이다. 하나의 wild number a와 완전한 숫자 b가 주어졌을 때 a > b인 숫자는 몇개가 존재하는가?

12?78?4 와 1237861을 살펴보자 첫번째 ?에 들어갈 수 있는 수는 {3,4,5,6,7,8,9} 7가지 이다. 이 중 3이 들어가는 경우 두번째 ?까지 숫자가 같게 되고 두번째 물음표는 {7,8,9}가 들어갈 수 있다. 첫 번째 ?에 3보다 큰 수가 있는 경우 두 번째 ?의 숫자에 상관없이 더 큰 수가 된다.

?가 몇 개가 나올지 알 수 없으므로 이를 재귀적으로 구성하여 문제를 풀자.

#include <cstdlib> #include <cstdio> char w[11], x[11]; long long pow10(int count) { int p = 1; int i = 0; for (i = 0; i < count; i++) p*=10; return p; } long long count(int index, int wildCount) { if (w[index] == 0) return 0; if (w[index] == '?') { return count(index+1, wildCount-1) + ('9' - x[index]) * pow10(wildCount-1); } else if (w[index] < x[index]) return 0; else if (w[index] > x[index]) return pow10(wildCount); else return count(index+1, wildCount); } int main() { while (scanf("%s", w) > 0) { if (w[0] == '#') break; scanf("%s", x); int wildCount = 0; for (int i = 0; w[i]; i++) if (w[i] == '?') wildCount++; printf("%I64d\n", count(0, wildCount)); } return 0; }