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ữ ...
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | 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. |
