huynhkim
13-09-2010, 11:04 PM
Bài 1. Siêu mã
Siêu mã là một loại mã có nhiều ứng dụng quan trọng trong lĩnh vực mã hóa và truyền tin. Trong bài này, ta xét bài toán đơn giản sau đây về siêu mã. Cho u và v là hai xâu kí tự khác rỗng có độ dài hữu hạn. Xâu u được gọi là xâu con của xâu v nếu u có thể nhận được từ v bằng cách xóa bớt ít nhất một kí tự trong v. Một tập X các xâu khác rỗng có độ dài hữu hạn được gọi là siêu mã nếu mọi cặp u, v bất kỳ thuộc X, u không là xâu con của v và v không là xâu con của u.
Cho trước một tập X = {x1, x2, ..., xN} gồm N xâu khác rỗng, mỗi kí tự trong xâu là 0 hoặc 1. Hãy kiểm tra xem X có là một siêu mã hay không?
Dữ liệu: vào từ file văn bản HCODE.INP có định dạng như sau:
• Dòng đầu tiên chứa số nguyên dương N (N ≤ 500);
• Dòng thứ i trong N dòng tiếp theo ghi xâu xi của tập X, độ dài của xâu xi không quá 15, với i = 1, 2, ..., N.
Kết quả: ghi ra file văn bản HCODE.OUT có định dạng như sau:
• Nếu X là siêu mã thì ghi số 1;
• Nếu X không là siêu mã thì dòng đầu tiên ghi số 0, dòng thứ hai ghi chỉ số i nhỏ nhất mà hoặc xi là xâu con của xj hoặc xj là xâu con của xi, với xi, xj thuộc X, 1 ≤ i < j ≤ N.
Ví dụ:
HCODE.INP
5
1111
100101
01011
000
0001000
HCODE.OUT
0
2
Hiện nay, mình đang ôn tập, chuẩn bị tham gia thi OLP 2k10 này.
Mọi người cùng nhau vào đây chia sẻ thuật toán của các bạn nhé ! Mình đã code đc, nhưng thấy thuật toán chưa tốt lắm !
Siêu mã là một loại mã có nhiều ứng dụng quan trọng trong lĩnh vực mã hóa và truyền tin. Trong bài này, ta xét bài toán đơn giản sau đây về siêu mã. Cho u và v là hai xâu kí tự khác rỗng có độ dài hữu hạn. Xâu u được gọi là xâu con của xâu v nếu u có thể nhận được từ v bằng cách xóa bớt ít nhất một kí tự trong v. Một tập X các xâu khác rỗng có độ dài hữu hạn được gọi là siêu mã nếu mọi cặp u, v bất kỳ thuộc X, u không là xâu con của v và v không là xâu con của u.
Cho trước một tập X = {x1, x2, ..., xN} gồm N xâu khác rỗng, mỗi kí tự trong xâu là 0 hoặc 1. Hãy kiểm tra xem X có là một siêu mã hay không?
Dữ liệu: vào từ file văn bản HCODE.INP có định dạng như sau:
• Dòng đầu tiên chứa số nguyên dương N (N ≤ 500);
• Dòng thứ i trong N dòng tiếp theo ghi xâu xi của tập X, độ dài của xâu xi không quá 15, với i = 1, 2, ..., N.
Kết quả: ghi ra file văn bản HCODE.OUT có định dạng như sau:
• Nếu X là siêu mã thì ghi số 1;
• Nếu X không là siêu mã thì dòng đầu tiên ghi số 0, dòng thứ hai ghi chỉ số i nhỏ nhất mà hoặc xi là xâu con của xj hoặc xj là xâu con của xi, với xi, xj thuộc X, 1 ≤ i < j ≤ N.
Ví dụ:
HCODE.INP
5
1111
100101
01011
000
0001000
HCODE.OUT
0
2
Hiện nay, mình đang ôn tập, chuẩn bị tham gia thi OLP 2k10 này.
Mọi người cùng nhau vào đây chia sẻ thuật toán của các bạn nhé ! Mình đã code đc, nhưng thấy thuật toán chưa tốt lắm !