BCACM11D spoj PTIT – Đường nguyên tố
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCACM11D/ 1. Đề bài BCACM11D spoj Cho hai số nguyên tố khác nhau có bốn chữ số. Người ta cho rằng hoàn toàn có thể biến đổi từ số này thành số kia sau một số bước theo quy tắc: Tại mỗi bước ta chỉ thay đổi một chữ số trong số trước ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCACM11D/
1. Đề bài BCACM11D spoj
Cho hai số nguyên tố khác nhau có bốn chữ số. Người ta cho rằng hoàn toàn có thể biến đổi từ số này thành số kia sau một số bước theo quy tắc: Tại mỗi bước ta chỉ thay đổi một chữ số trong số trước đó sao cho số tạo được trong mỗi bước đều là một số nguyên tố có bốn chữ số. Một cách biến đổi như vậy gọi là một “đường nguyên tố”.
Bài toán đặt ra là với một cặp số nguyên tố đầu vào, hãy tính ra số bước của đường nguyên tố ngắn nhất. Giả sử đầu vào là hai số 1033 và 8179 thì đường nguyên tố ngắn nhất sẽ có độ dài là 6 với các bước chuyển là:
1033
1733
3733
3739
3779
8779
8179
Input : Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test viết trên một dòng bao gồm hai số nguyên tố có 4 chữ số.
Output: Với mỗi bộ test, in ra màn hình trên một dòng số bước của đường nguyên tố ngắn nhất.
Example
Input:
3
1033 8179
1373 8017
1033 1033
Output:
6
7
0
2. Hướng dẫn giải bài BCACM11D spoj PTIT – Đường nguyên tố
– xây dựng trước sàng nguyên tố.
– sử dụng BFS, thay đổi từng chữ số.
3. Code tham khảo BCACM11D spoj PTIT – Đường nguyên tố
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 82 83 84 85 86 87 88 89 90 | const fi='; nmax=1000000; type data=longint; var f:text; snt:array[0..9999] of boolean; s,t,test:data; Q,c:array[0..nmax+1] of data; dau,cuoi:data; procedure sangnt; var i,j:data; begin fillchar(snt,sizeof(snt),true); snt[1]:=false; i:=2; while i<=sqrt(9999) do begin while snt[i] = false do inc(i); for j:=2 to 9999 div i do snt[i*j]:=false; inc(i); end; end; procedure them(x:data); begin inc(cuoi); q[cuoi]:=x; end; function layra:data; begin layra:=q[dau]; inc(dau); end; procedure xuli; var i,j,x,sobuoc,p,tmp,v:data; begin dau:=1; cuoi:=0; them(s); fillchar(c,sizeof(c),0); c[s]:=1; while dau<=cuoi do begin x:=layra; i:=1; while i<=1000 do begin p:=x div (i*10); tmp:=x mod i; for j:=0 to 9 do begin v:=p*i*10+i*j+tmp; if (v>1000) and (snt[v]) and (c[v]=0) then begin c[v]:=c[x]+1; if v = t then begin writeln(c[x]); exit; end; them(v); end; end; i:=i*10; end; end; writeln(0); end; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,test); for i:=1 to test do begin readln(f,s,t); xuli; end; close(f); end; begin sangnt; docfile; end. |
