P142SUMG spoj PTIT – Mã hóa
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P142SUMG/ 1. Đề bài P142SUMG spoj Mã hóa là một bước quan trọng trong việc truyền thông tin. Một trong những thuật toán đơn giản đó là dịch vòng tất cả các kí tự của từ mã (nội dung cần mã hóa) sang phải d kí tự. Chẳng hạn với d = ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P142SUMG/
1. Đề bài P142SUMG spoj
Mã hóa là một bước quan trọng trong việc truyền thông tin. Một trong những thuật toán đơn giản đó là dịch vòng tất cả các kí tự của từ mã (nội dung cần mã hóa) sang phải d kí tự. Chẳng hạn với d = 5, kí tự ‘A’ được mã hóa bằng ‘F’, ‘B’ bằng ‘G’, …, ‘Z’ bằng ‘E’.
Với một nội dung đã được mã hóa, để giải mã, người ta sẽ tìm khoảng cách dịch d và sau đó dịch ngược lại nội dung sang trái d kí tự. Khoảng cách d này được tính bằng số bước dịch sang phải từ chữ cái ‘E’ đến chữ cái được sử dụng nhiều nhất trong nội dung đã được mã hóa.
Cho biết nội dung sau khi được mã hóa, các bạn hãy khôi phục lại từ mã ban đầu?
Input
Dòng đầu tiên là số lượng bộ test T (T <= 100).
Mỗi bộ test là một nội dung đã được mã hóa, gồm nhiều chuỗi các chữ cái in hoa nằm trên một dòng (<= 1000 kí tự).
Output
Với mỗi test, in ra khoảng cách d và nội dung từ mã ban đầu. Nếu không giải mã được vì có nhiều giá trị d, in ra “NOT POSSIBLE”.
Example
Input:
3
RD TQIJW GWTYMJWX INFWD JSYWNJX ZXJ F XNRUQJ JSHWDUYNTS YJHMSNVZJ
THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
XVIDRE TFCCVXZRKV GIFXIRDDZEX TFEKVJK
Output:
5 MY OLDER BROTHERS DIARY ENTRIES USE A SIMPLE ENCRYPTION TECHNIQUE
10 JXU GKYSA RHEMD VEN ZKCFI ELUH JXU BQPO TEW
NOT POSSIBLE
2. Cách làm bài P142SUMG spoj PTIT
– Xây dựng mảng A, với A[c] là số lượng kí tự xuất hiện của kí tự c (c kiểu dữ liệu kí tự , c=’A’..’Z’);
– Dựa vào mảng ở trên, bạn tìm kí tự xuất hiện nhiều nhất. và tạm gọi biến “đếm” là số lượng của kí tự đó.
– Nếu có quá 1 kí tự có số lượng kí tự lớn nhất, tức là dem = A[c] (c=’A’..’Z’). thì xuất “NOT POSSIBLE” và kết thúc.
– Ngược lại, các bạn sẽ giải mã xâu S trên. dễ dàng tính được khoảng cách dịch thông qua định nghĩa của đề bài.
– Tiếp tục giải mã….
3. Code tham khảo bài toán P142SUMG 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 | const fi='; type data=longint; var f:text; S:ansistring; n:data; A:array['A'..'Z'] of data; procedure xuli; var i:data; c:char; ktmax:char; d,dem:data; begin fillchar(a,sizeof(a),0); n:=length(s); for i:=1 to n do if s[i]<>' ' then inc(A[s[i]]); ktmax:='A'; for c:='B' to 'Z' do if a[ktmax]<a[c] then ktmax:=c; dem:=0; for c:='A' to 'Z' do if a[ktmax]=a[c] then inc(dem); if dem<>1 then begin writeln('NOT POSSIBLE'); exit; end; d:=ORD(ktmax)-ord('E'); if d<0 then d:=d+26; write(d,' '); for i:=1 to n do if s[i]<>' ' then begin if ord(s[i]) in [65+d..90] then s[i]:=chr(ord(s[i])-d) else s[i]:=chr(ord(s[i])-d+26); end; write(s); writeln; end; procedure docfile; var i:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do begin readln(f,s); xuli; end; close(f); end; begin docfile; end. |
