Tên chương trình: GEN.PAS
Một số vi rút, ví dụ vi rút cúm gia cầm H5N1, có khả năng tái tổ hợp gien khi chúng thâm nhập vào cơ thể các động vật có vú. Để nghiên cứu vắc xin chống các loại vi rút này, trong phòng thí nghiệm người ta dùng enzim cắt gien thành từng đoạn ngắn. Từ đó, ta thu được một họ S các đoạn gien ngắn. Mỗi đoạn trong S được biểu diễn bởi một dãy chứa tối đa 3 trong số 4 loại thành phần A, G, T và C, và không có thành phần nào xuất hiện quá 3 lần trong cùng một đoạn. Ví dụ, kết quả cắt gien có thể là họ các đoạn gien ngắn sau đây:
(A, AA, AAA, A, G, T, AG, AT, AC, GT, GGGAAATTT).
Tiếp đến, người ta dùng một enzim khác kích hoạt để tạo ra các gien mới từ các đoạn gien trong S. Mỗi gien mới được tạo từ 3 đoạn ngắn không giống hệt nhau trong họ S và ba đoạn chỉ có thể nối được thành gien mới khi số lượng thành phần mỗi loại trong ba đoạn hoặc là như nhau, hoặc khác nhau từng đôi.
Ví dụ:
· Có thể ghép ba đoạn AGTT, AGGTT và AGGGTT, bởi vì số lượng thành phần A và số lượng thành phần T ở mỗi đoạn là như nhau, số lượng phần tử G khác nhau từng đôi một.
· Có thể ghép ba đoạn A, AA và AAA, bởi vì tuy chúng cùng chỉ chứa một thành phần A nhưng có số thành phần là khác nhau.
Như vậy, từ họ các đoạn gien S, theo qui tắc trên, người ta tạo ra được một số gien mới, trong đó có một số gien giống nhau và có thể còn một số đoạn không sử dụng.
Yêu cầu: Cho họ các đoạn gien S, hãy xác định cách tạo các gien mới sao cho số lượng đoạn không sử dụng là ít nhất.
Dữ liệu: Vào từ file văn bản GEN.INP:
· Dòng đầu tiên chứa số nguyên N (1≤ N ≤ 20000) là số lượng đoạn gien trong họ S;
· Mỗi dòng trong số N dòng tiếp theo mô tả một đoạn gien là một xâu gồm không quá 9 ký tự từ tập {A, G, T, C}.
Kết quả: Đưa ra file văn bản GEN.OUT:
Dòng đầu tiên chứa số nguyên M là số lượng đoạn gien không sử dụng,
M dòng sau: mỗi dòng chứa một xâu ký tự mô tả một đoạn gien không sử dụng
http://vnoi.info/index.php?option=com_content&task=view&id=168&Itemid=70
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn