Các nhà nghiên cứu đang tìm một vắc xin để chống lại một loại vi rút nguy hiểm có tên là RTU. Họ đã nghiên cứu được N vắc xin, mỗi vắc xin chứa một loại vi rút yếu, sẽ được tiêm vào người để tạo ra kháng thể giúp cơ thể chống lại vi rút RTU. Các nhà nghiên cứu cần tìm một vắc xin tốt nhất trong N loại đã nghiên cứu được. Việc tính toán độ tương tác giữa các Axit Ribonucleic (viết tắt RNA) của các loại vi rút có trong vắc xin với vi rút RTU là rất cần thiết cho việc này. Một RNA bao gồm bốn loại phân tử: Guanine (G), Adenine (A), Cytosine (C), và Uracil (U).

Bạn được cho cấu trúc RNA của vi rút RTU và của N vi rút có trong N vắc xin đang nghiên cứu. Cấu trúc RNA có dạng là một xâu kí tự chỉ gồm các kí tự 'G', 'A', 'C', 'U' tương ứng là các loại phân tử như trên. Biết rằng, vi rút trong vắc xin nào có sự tương tác cao hơn với vi rút RTU thì loại vắc xin đó tốt hơn.

Độ tương tác giữa hai vi rút có cấu trúc RNA là s1 và s2 được tính như sau:

● Một phân tử Guanine (là kí tự 'G') trong s1 và một phân tử Cytosine (là kí tự 'C') trong s2 cho ta một đơn vị tương tác.

● Một phân tử Cytosine (là kí tự 'C') trong s1 và một phân tử Guanine (là kí tự 'G') trong s2 cho ta một đơn vị tương tác.

● Bất kì cặp phân tử nào khác mô tả trên của s1 và s2 không cho một đơn vị tương tác nào.

Độ tương tác giữa s1 và s2 sẽ được tính bằng tổng độ tương tác giữa tất cả các cặp phân tử giữa hai cấu trúc RNA.

Yêu cầu: Cho cấu trúc RNA của vi rút RTU và của N vi rút có trong N vắc xin. Bạn hãy tìm vắc xin tốt nhất trong số đó.

Dữ liệu: Vào từ file VACCINE.INP gồm:

• Dòng đầu chứa số N là số vắc xin (N ≤ 1000);
• • Dòng thứ hai chứa một xâu kí tự chỉ gồm các kí tự 'G', 'A', 'C', 'U' là RNA của vi rút RTU (độ dài xâu không quá 1000).

• N dòng tiếp theo, mỗi dòng chứa một xâu kí tự chỉ gồm các kí tự 'G', 'A', 'C', 'U' là RNA của N vi rút có trong N vắc xin (độ dài mỗi xâu không quá 1000).

Kết quả: Ghi ra file văn bản VACCINE.OUT gồm một số nguyên dương là thứ tự của vắc xin tốt nhất tìm được, nếu có nhiều vắc xin tốt như nhau thì in ra số thứ tự nhỏ nhất.

Ví dụ:

VACCINE.INP

2
ACGGU
UAUAAGAG
AGCAAA

VACCINE.OUT

2

Giải thích: Vaccin thứ nhất có tổng độ tương tác là 2 (1 * 2 + 2 * 0), còn vaccin thứ 2 có độ tương tác là 3 (1 * 2 + 1 * 1).

Nguồn