TRUTIN - Truyền tin
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 3.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

       Nam là một học sinh rất yêu thích môn sinh học, cậu thích khám phá các loài động thực vật. Trong chuyến đi hang Sơn Đoòng mùa hè này, cậu đã khám phá được N loài động thực vật lạ. Một loài được mã hóa bởi một chuỗi K ký tự la tinh viết hoa (≤ K ≤ 200). Phấn khích với kết quả tìm được, Nam muốn gửi các chuỗi mã hóa này về cho thầy giáo của mình. Để tiết kiệm dung lượng 3G, Nam định gửi các chuỗi mã hóa ứng với từng loài như sau:

1) Hoặc truyền đầy đủ K ký tự của chuỗi mã hóa đó, tốn dung lượng đường truyền là K byte.

2) Nếu chuỗi gửi sau chỉ khác một chuỗi gửi trước nào đó m ký tự (m ≤ K/2). Nam chỉ cần gửi đi m ký tự khác nhau này, mỗi ký tự tốn 2 byte (1 byte vị trí và một byte nội dung ký tự), tổng cộng chỉ tốn 2*m byte (2*m  K). Ví dụ:

      Chuỗi gửi trước nào đó: ABCDE

      Chuỗi gửi sau: AXYDE

      Vậy thay vì gửi chuỗi đầy đủ AXYDE tốn 5 byte thì chỉ cần gửi đi 2 cặp (2,X) và (3,Y) tốn 4 byte.

Yêu cầu: Bạn hãy giúp Nam tìm cách truyền tin sao cho dung lượng đường truyền là thấp nhất.

Dữ liệu nhập:

- Dòng đầu tiên là 2 số nguyên N và K (≤ N ≤ 1000, 1 ≤ K ≤ 200)

- Trong N dòng tiếp theo, dòng thứ i là K ký tự la tinh viết hoa tương ứng với các chuỗi mã hóa của loài động thực vật thứ i (dữ liệu cho đảm bảo các chuỗi mã hóa khác nhau từng đôi một)

Dữ liệu xuất:

- Dòng thứ nhất là tổng số byte ít nhất dùng để truyền tin.

- Trong N dòng tiếp theo, dòng thứ i là hai số nguyên ui và vi thể hiện cách truyền tin trong lần truyền thứ i: ui là chỉ số của chuỗi truyền đi. Nếu vi = 0, chuỗi ui được truyền đầy đủ. Nếu vi ≠ 0, chuỗi ui được truyền theo cách thứ 2 dựa trên chuỗi vi (xem ví dụ để rõ hơn).

(nếu có nhiều cách truyền tin có cùng số byte ít nhất, chỉ cần in ra một cách bất kỳ)

Ví dụ

  • input
    4 5
    ABCDE
    AXYDE
    ABUVE
    VWXYZ
    output
    18
    1 0
    4 0
    2 1
    3 1

Giải thích:

- Truyền chuỗi thứ nhất đầy đủ, tốn 5 byte.

- Truyền chuỗi thứ tư đầy đủ, tốn 5 byte.

- Truyền chuỗi thứ hai dựa theo chuỗi thứ nhất, tốn 4 byte.

- Truyền chuỗi thứ ba dựa theo chuỗi thứ nhất, tốn 4 byte.

Tổng cộng tốn 18 byte.

Back to Top