Mã Hóa | Câu 4 - Đề thi HSG tin 12 Nghệ An | Năm 2013-2014

​ Bài 4. MÃ HÓA
            Nam rất thích thú với việc mã hóa các dữ liệu. There was a science conference in gimnasium, where Petya studied, and he decided to participate in it. Trong buổi thảo luận ở lớp Nam đã trình bày một ý tưởng rất thú vị rằng bạn ấy vừa «I invented an essentially new way of coding, which is impossible to decode , – Petya saiphát minh ra một cách mã hóa mới, có thể mã các thông tin, mà không ai có thể giải mã. Cách mã hóa đó là: – At the present time my coding works only for numbers. Let's consider an integer N, having t digits (in decimal notation ). Deleting the digits from this number by all possible ways, we will get some new numberVớiV Với một số nguyên N, xoá các chữ số từ con số này bằng mọi cách có thể, ta sẽ nhận được các số mới. Some way of deleting is to delete nothing. Một số cách xóa mà số mới thu được có giá trị bằng số cũ đó là khiIf we delete all digits, 0 is l ta xóa các chữ số 0 bên trái. Let's find the sum of all this numbers. Hãy tìm tổng của tất cả các con số mới thu được.This sum is the code of N». Tổng này chính là mã hóa của N.
            There were loud applauds.Một bạn trong lớp đã có ý kiến "Mình nghĩ cách mã hóa của cậu trên máy tính sẽ thực hiện mất nhiều thời gian với số có nhiều chữ số, chẳng hạn số có 100 chữ số. Your life is not enough to code only one number, having 100 digits. Không thể chờ để có một mã số cho số có 100 chữ số. Your algorithm can't be applied on practice ». Các mã hóa này của bạn không thể được áp dụng trên thực tế”. It was necessary to answer something. «No, no, and no. Nam đã trả lời "Không, không, không. Tomorrow I'll bring the realization of my algorithm, that will code the numbers, having 100 digits, in no more than 1 second», - that was the answer of Petya. Ngày mai mình sẽ đưa ra chương trình thực hiện cách mã hóa này, và sẽ mã hóa cho số có 100 chữ số trong thời gian không quá 1 giây" câu trả lời của Nam được cả lớp rất hoan nghênh.Of course, Petya couldn't write such a program. Bạn hãy giúp Nam viết chương trình đó.
 Task. Your program should input the integer N (1<=N <=10 ¹⁰⁰ ) and determine the integer S – the code of N (using Petya's method of coding).Yêu cầu: Cho số nguyên N (1 < N < 10¹⁰⁰) và xác định số nguyên S là mã hóa của N theo phương pháp mã hóa của Nam.
Input. Input consists of one line, which contains one integer N. The left digit of N is not zero. Dữ liệu: Vào từ file văn bản MAHOA.INP
- Chỉ một dòng duy nhất chứa một số nguyên N. (chữ số bên trái các chữ số của NOutput. You should output an integer S – the code of N. You should not output the leading zeroes. là khác 0).
Kết quả: Đưa ra file văn bản MAHOA.OUT:
- Chỉ một số duy nhất là số nguyên S tìm được.
Example. Ví dụ.
 

Input.Txt MAHOA.INP	Output.TxtNMAHOA.OUT
109 109	157 157

Giải thích test ví dụ:
 N = 109. After deleting we get the numbers: Sau khi xóa chúng ta nhận được các số:
 

vị trí xóa		1	2	3	1, 2	1, 3	2, 3	1, 2, 3
số mới	109	09	19	10	9	0	1	0

Tổng các số thu được: 109 + 09 + 19 + 10 + 9 + 0 + 1 + 0 = 157. So, the code of 109 is 157. Vì vậy, mã của 109 là 157.

Hướng dẫn giải.

Vì số N là số có đến 100 chữ số nên để tính kết quả cần xử lý số lớn.
Cách 1. Dùng tổ hợp xét sự xuất hiện của các số ở mỗi hàng sau đó tính tổng.
Cách 2. Sử dụng công thức. Giả sử N có dạng a₁a₂.......a_m
             Kết quả là: a₁.2⁰.11^m-1 + a₂.2¹.11^m-2 + ......+ a_m.2^m-1.11⁰

 

Code mẫu Pascal 1

const   fi='mahoa.inp';
        fo='mahoa.out';
type    mang=array[0..201] of longint;
        bignum=record
                 d:longint;
                 cs:mang;
               end;
var     f:text;
        n,m,i,j,k,l:longint;
        s:string;
        sl,res,a,b:bignum;
procedure doc;
begin
  assign(f,fi);
  reset(f);
  readln(f,s);
  close(f);
end;
procedure nhan(a:bignum;x:longint; var t:bignum);
var n,nho,i:longint;
    c:mang;
begin
  nho:=0;n:=a.d;
  fillchar(c,sizeof(c),0);
  for i:=1 to n do
    begin
      nho:=nho+a.cs[i]*x;
      c[i]:=nho mod 10;
      nho:=nho div 10;
    end;
  if nho>0 then
    begin
      inc(n);
      c[n]:=nho;
    end;
  t.d:=n;t.cs:=c;
end;
procedure tong(a,b:bignum; var s:bignum);
var n,nho,i:longint;
    c:mang;
begin
  n:=a.d;
  if b.d>n then n:=b.d;
  nho:=0;fillchar(c,sizeof(c),0);
  for i:=1 to n do
    begin
      nho:=nho+a.cs[i]+b.cs[i];
      c[i]:=nho mod 10;
      nho:=nho div 10;
    end;
  if nho>0 then
    begin
      inc(n);
      c[n]:=nho;
    end;
  S.d:=n;S.cs:=c;
end;
procedure lam;
begin
  n:=length(s);
  sl.d:=1;sl.cs[1]:=1;
  for i:=1 to n do
    begin
      nhan(res,11,a);
      nhan(sl,ord(s[i])-48,b);
      nhan(sl,2,sl);
      tong(a,b,res);
    end;
end;
procedure ghi;
begin
  assign(f,fo);
  rewrite(f);
  with res do
    for i:=d downto 1 do write(f,cs[i]);
  close(f);
end;
begin
  doc;
  lam;
  ghi;
end.

Code mẫu Pascal 2

const fip='mahoa.inp';
      fop='mahoa.out';
type bignum=string;
var  s: string;
     kq,tong1,tong2: bignum;
     c: array[0..101,0..101] of bignum;
procedure openf;
begin
     assign(input,fip); reset(input);
     assign(output,fop); rewrite(output);
end;
function cong(a,b: bignum): bignum;
var  c: bignum;
     i,x,y,carry,sum: longint;
begin
     while length(a)<length(b) do a:='0'+a;
     while length(b)<length(a) do b:='0'+b;
     carry:=0; c:='';
     for i:=length(a) downto 1 do
     begin
          x:=ord(a[i])-48;
          y:=ord(b[i])-48;
          sum:=x+y+carry;
          carry:=sum div 10;
          c:=chr(sum mod 10 + 48) + c;
     end;
     if carry>0 then c:='1'+c;
     cong:=c;
end;
function tiny_nhan(a: bignum; b: longint): bignum;
var  p: bignum;
     i,carry,x,tich: longint;
begin
     carry:=0; p:='';
     for i:=length(a) downto 1 do
     begin
          x:=ord(a[i])-48;
          tich:=x*b+carry;
          carry:=tich div 10;
          p:=chr(tich mod 10 + 48) + p;
     end;
     if carry>0 then p:=chr(carry+48)+p;
     tiny_nhan:=p;
end;
function huge_nhan(a,b: bignum): bignum;
var  p,temp: bignum;
     i,y,j: longint;
begin
     p:='0';
     for i:=length(b) downto 1 do
     begin
          y:=ord(b[i])-48;
          temp:=tiny_nhan(a,y);
          for j:=1 to length(b)-i do temp:=temp+'0';
          p:=cong(p,temp);
     end;
     while (p[1]='0') and (length(p)>1) do delete(p,1,1);
     huge_nhan:=p;
end;
procedure init_tohop;
var  i,j: longint;
begin
     for j:=0 to 101 do c[0,j]:='1';
     for i:=0 to 101 do
          for j:=0 to 101 do if j<i then c[i,j]:='0';
     c[1,1]:='1';
     for j:=2 to 100 do
          for i:=1 to j do c[i,j]:=cong(c[i,j-1],c[i-1,j-1]);
end;
procedure xuly;
var  i,j,k,x,max: longint;
     temp1,temp2: bignum;
begin
     init_tohop;
     readln(s);
     kq:='0';
     for i:=1 to length(s) do
     begin
          tong1:='0';
          x:=ord(s[i])-48;
          max:=length(s)-i;
          for j:=0 to max do
          begin
               temp1:=tiny_nhan(c[j,max],x);
               for k:=1 to j do temp1:=temp1+'0';
               tong1:=cong(temp1,tong1);
          end;
          tong2:='0';
          for j:=1 to i-1 do
          begin
               tong2:=cong(c[j,i-1],tong2);
          end;
          tong2:=cong(tong2,'1');
          temp2:=huge_nhan(tong1,tong2);
          kq:=cong(kq,temp2);
     end;
     writeln(kq);
end;
BEGIN
     openf;
     xuly;
END.

 ​Hai code mẫu Pascal ở trên chắc không ít bạn đọc sẽ khó hiểu, để hiểu được phần nào thì các bạn cần tìm hiểu TỔ HỢP và các xử lý cộng SỐ LƠN trong pascal.

Một số cách giải quyết bằng Python.

Cách 1: Sử dụng cách duyệt qua tất cả các số mới được tao ra. (Không tối ưu - chỉ để tham khảo)

Để giải bài tập này, bạn có thể sử dụng một vòng lặp để duyệt qua các số mới được tạo ra từ cách xóa chữ số của số nguyên a ban đầu. Sau đó, bạn có thể tính tổng của tất cả các số mới này để tìm ra mã hóa của số nguyên a. Tuy nhiên cách này không tối ưu, tôi chỉ trình bày để các bạn tham khảo. Với cách này khi duyệt qua tất cả các số mới được tạo ra thì sẽ có rất nhiều số. Ví dụ số 123, có 3 chữ số, thì khi xóa theo cách mã hóa trên thì sẽ có tới 2³ -1 = 7 số được tạo ra: 1, 2, 3, 12, 13, 23, 123. Như vậy nếu số a có 100 chữ số thì sẽ có 2¹⁰⁰ - 1 số mới được tạo ra. Do đó cách này sẽ không tối ưu bằng cách sử dụng TỔ HỢP như 2 code mẫu Pascal trên. Các bạn chỉ tham khảo thôi nhé.

with open('mahoa.inp','r') as f:
    a = f.readline().rstrip()
n = len(a) # Độ dài của a
s = 0 # Khởi tạo tổng các số mới là 0

# Duyệt qua các số mới được tạo ra từ cách xóa các chữ số của a
for i in range(1, 2**n):
    num = ''
    for j in range(n):
        if i & (1 << j):
            num += a[j]
    s += int(num)

with open('mahoa.out','w') as f:
    f.write(str(s))

Nhìn code thì các bạn cũng hiểu là không tối ưu rôi ha. Code này chỉ chạy đến test 3, sang test 4 là chạy quá 1 giây. Trong ví dụ trên chắc không ít bạn thắc mắc  if i & (1 << j): Ở đây, chúng ta sử dụng biểu thức  i & (1 << j) để kiểm tra xem bit thứ j của số mới i có bật hay không. Cụ thể, biểu thức này sẽ trả về một số có giá trị bằng 0 hoặc 2^j tùy thuộc vào bit thứ j của i có bật hay không. Nếu bit này bật, thì giá trị trả về sẽ là 2^j; ngược lại, nếu bit này tắt, thì giá trị trả về sẽ là 0.

Ví dụ: Nếu i = 5 (101 trong hệ nhị phân) và j = 1, thì biểu thức i & (1 << j) sẽ trả về giá trị 4 (100 trong hệ nhị phân), vì bit thứ 1 của i là 0.

Trong ví dụ của chúng ta, chúng ta sử dụng biểu thức này để kiểm tra xem chữ số nào của số nguyên a ban đầu sẽ được giữ lại trong số mới được tạo ra từ cách xóa chữ số của a.

Trong cách không tối ưu, các bạn có thể tham khảo thêm cách sử dụng hàm sau, trong hàm mình đã giải thích rồi ha:

def tao_so_moi(n, start):
    """
    Tạo số mới từ số n, bắt đầu từ vị trí start đến hết số.
    Các số mới tạo ra đưa vào danh sách new_numbers.
    """
    #Nếu số n chỉ còn lại 1 chữ số thì quay lại.
    if len(n) == 1:
        return

    #Loại bỏ tất cả các chữ số từ vị trí start và thử tìm tất cả các số mới rồi thêm chúng vào list.
    for i in range(start, len(n)):
        new_num = n[:i] + n[i+1:]
        new_numbers.append(int(new_num))
        tao_so_moi(new_num, i)

n='109'
new_numbers = [int(n)]
tao_so_moi(n, 0)
print(sum(new_numbers))

 

Cách 2: Sử dụng công thức toán học.

with open('mahoa.inp','r') as f:
    n = f.readline().rstrip()
m = len(n)
res = 0
for i in range(m):
    res += int(n[i])*2**i*11**(m-1-i)
with open('mahoa.out','w') as f:
    f.write(str(res))