toj_2872_3.cpp

Tianjin University Online Judge 的80多道题目 .

/*2872.   Barbara Bennett's Wild Numbers Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 294   Accepted Runs: 140


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).
Sample Input

10?4?2
102333
36?1?8
236428
8?3
910
?
5
#

Sample Output

100
0
4



Source: Asia - Tehran 2006*/
#include<cstdio>
#include<cstring>
#include<cmath>
int main()
{
  char w[ 20 ] , x[ 20 ] , m[ 20 ],  temp;
  int i , j , lenW ,lenM , flag , result , power10;
  while( scanf( "%c" , &temp ) != EOF && temp != '#' )
    {
      ungetc( temp , stdin);
      scanf( "%s" , w );
      scanf( "%s%*c" , x );
      lenW = strlen( w );
      m[ 0 ] = -1;
      for ( lenM = 1 , i = 0; i < lenW; i++ )
	{
	  if ( w[ i ] == '?' )
	    {
	      m[ lenM ] = i;
	      lenM++;
	    }
	}
      for ( power10 = 1 , i = 1; i < lenM; i++ )
	  power10 *= 10;
      for ( result = 0 , i = 1; i < lenM; i++ , power10 /= 10 )
	{
	  flag = 0;
	  for ( j = m[ i - 1 ] + 1; j < m[ i ]; j++ )
	    {
	      if ( w[ j ] < x[ j ] )
		{
		  flag = -1;
		  break;
		}
	      else if ( w[ j ] > x[ j ] )
		{
		  flag = 1;
		  break;
		}
	    }
	  if ( flag == -1 )
	    break;
	  else if ( flag == 1 )
	    {
	      result += power10;
	      break;
	    }
	  else if ( flag == 0 )
	    {
	      result += ( 9 - ( x[ m[ i ] ] - '0' ) ) * power10 / 10;
	    }
	}
      printf( "%d\n" , result );
    }
  return 0;
}