PTIT122F spoj PTIT – Số siêu tự nhiên

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT122F/

1. Đề bài PTIT122F spoj

Một số siêu tự nhiên là một chuỗi chứa các chữ số và dấu hỏi (ví dụ như 36?1?8). Một số X phù hợp với một số siêu tự nhiên W nếu X có thể được tạo thành từ W bằng cách thay thế dấu hỏi bằng các chữ số tùy ý. Ví dụ: 365198 phù hợp với số siêu tự nhiên 36?1?8, nhưng 360199, 361028 hoặ 36128 thì không. Viết chương trình đọc số siêu tự nhiên W và số X (có cùng độ dài n), và xác định số các số phù hợp với W và lớn hơn X.

Dữ liệu:

Gồm nhiều bộ test, mỗi bộ test gồm 2 dòng:

–          Dòng 1 chứa số siêu tự nhiên W

–          Dòng 2 chứa số nguyên X

Độ dài các số từ 1 đến 10 kí tự.

Dữ liệu kết thúc bởi dấu #

Kết quả:

Với mỗi bộ test, in ra trên 1 dòng số các số phù hợp với W và lớn hơn X.

Example

Input:
36?1?8

236428

8?3

910

?

5
#

Output:

100

0
4

2. Hướng dẫn PTIT122F spoj PTIT

– Thực hiện quay lui điền số vào các dấu ? và đếm kết quả

3. Code tham khảo PTIT122F spoj PTIT

const   fi='';
        nmax=10;
type    data=longint;
var
        f:text;
        vt:array[1..10] of data;
        W,X:string;
        n:data;
        spt:data; // spt cua vt;
        res:data;
        sl:data;
        KQ:string;

procedure try;
var
        c:char;
begin
        if sl=spt then
                begin
                        if W>x then
                                inc(res);
                end
        else
                for c:='0' to '9' do
                        begin
                                inc(sl);
                                W[vt[sl]]:=c;
                                try;
                                dec(sl);
                        end;
end;

procedure xuli;
var     i,j:data;
begin
        fillchar(vt,sizeof(vt),false);
        n:=length(W);
        kq:=w;
        spt:=0;
        for i:=1 to n do
                if w[i]='?' then
                        begin
                                inc(spt);
                                vt[spt]:=i;
                        end;
        for i:=1 to spt do
                kq[vt[i]]:='0';
        if KQ>=X then
                begin
                        writeln(round(exp(ln(10)*spt)));
                        exit;
                end;
        for i:=1 to spt do
                kq[vt[i]]:='9';
        if KQ<X then
                begin
                        writeln('0');
                        exit;
                end;
        sl:=0;
        res:=0;
        try;
        writeln(res);
end;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        repeat
                readln(f,w);
                if W='#'then break;
                readln(f,X);
                xuli;
        until 1=2;
        close(f);
end;

begin
        docfile;
end.