P142SUMG spoj PTIT - Mã hóa - Kiến Thức 24h

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

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.

P142SUMG spoj PTIT – Mã hóa