首页 > 基础算法 > 模拟法 > 英雄会第四届在线编程大赛·线上初赛
2014
03-14

英雄会第四届在线编程大赛·线上初赛

带通配符的数

比赛地址:http://hero.csdn.net/?ref=toolbar_logo

给定一个带通配符问号的数W,问号可以代表任意一个一位数字。

再给定一个整数X,和W具有同样的长度。

问有多少个整数符合W的形式并且比X大?

输入格式

多组数据,每组数据两行,第一行是W,第二行是X,它们长度相同。在[1..10]之间.

输出格式

每行一个整数表示结果。

答题说明

输入样例

36?1?8

236428

8?3

910

?

5

输出样例

100

0

4

 

友情提醒:

1、本题用OJ模式答题,答题时可把下面输入框内预留的函数全部直接去掉,自己另起函数名实现本题功能。

2、因为本系统的OJ模式对于Java 和 C# 的支持有问题,所以本题暂不支持这两种语言挑战。

——————————————————–

居然花了将近两个小时。模拟题,一定要细心。

注意问号的有无,还有int否会溢出,基本就差不多了。

#include <stdio.h>
#include <iostream>
using namespace std;

char str1[11], str2[11];
int num2;
long long getCnt(char str1[], char str2[]) {
    int i,   flag = 0, first = 0, last = 0;
    long long ans=1;
    for (i = 0; str1[i]; i++) {
        if (str1[i] == '?') {
            if (flag == 3) {
                ans *= 10;
            } else {
                if (!first) 
                    ans = '9' - str2[i];
                else {
                    if (flag == 0) {
                        ans *= 10;
                        ans += '9' - str2[i];
                        last = 0;
                    } else if (flag == 1) {
                        if(last == 0)
                            ans = ans * 10 + 10;
                        else
                            ans *= 10;
                        last = 1;
                    } else{
                        ans *= 10;
                        last = 1;
                    }
                }
            }
            first = 1;
        } else {
            if (flag)
                continue; 
            if (str1[i] < str2[i]) {
                if (first == 0)
                    return 0;
                else
                    flag = 2;
            } else if (str1[i] > str2[i]) {
                if (!first)
                    flag = 3; 
                else
                    flag = 1;
            }
        }
    }
    if(!first){
        if(flag) return 1;
        return 0;
    } 
    if(flag == 1 && last == 0){
        ans += 1;
    }
    return ans;
}
int main() {
    while (scanf("%s", str1) != EOF) {
        scanf("%s", str2);
        long long ans = getCnt(str1, str2);
        printf("%I64d\n", ans);
    }
    return 0;
}