DNA vòng
Đề bài
Mô tả
Bạn đang thực tập tại một nhóm nghiên cứu tin sinh học về DNA. Một sợi DNA gồm nhiều gen, các gen được chia thành nhiều loại khác nhau gọi là loại gen. Các loại gen được phân định bởi những đoạn nucleotide đặc biệt gọi là dấu hiệu gen. Mỗi loại gen có một dấu hiệu bắt đầu duy nhất và một dấu hiệu kết thúc duy nhất.
Sau nhiều công việc vất vả (nuôi vi khuẩn, tách tế bào, kỹ thuật protein, ...), nhóm của bạn có thể chuyển DNA về dạng chỉ gồm các dấu hiệu gen, loại bỏ toàn bộ vật chất di truyền nằm giữa các dấu hiệu.
Nhóm nghiên cứu đưa ra một giả thuyết thú vị: cách diễn giải gen phụ thuộc vào việc các dấu hiệu của một số loại gen có tạo thành cấu trúc lồng nhau đúng hay không. Để xác định các dấu hiệu của loại gen có tạo thành cấu trúc lồng nhau đúng trong một dãy dấu hiệu hay không, ta xét dãy con của gồm tất cả các dấu hiệu của loại gen (các và , không bỏ sót cái nào). Các dãy sau (và chỉ các dãy sau) được coi là cấu trúc lồng nhau đúng:
- ;
- , trong đó là một cấu trúc lồng nhau đúng;
- , trong đó và là các cấu trúc lồng nhau đúng.
Với nền tảng tin học của mình, bạn được giao nghiên cứu tính chất này, nhưng có thêm một khó khăn. Nhóm đang nghiên cứu một loại DNA đặc biệt gọi là DNA vòng, tức là DNA tạo thành một vòng khép kín. Để nghiên cứu tính lồng nhau trên DNA vòng, cần cắt vòng tại một vị trí nào đó, thu được một dãy dấu hiệu xác định (chiều đọc được cố định bởi các tính chất phân tử). Việc một loại gen có tạo thành cấu trúc lồng nhau đúng hay không giờ còn phụ thuộc vào vị trí cắt.
Nhiệm vụ của bạn là tìm vị trí cắt sao cho số loại gen tạo thành cấu trúc lồng nhau đúng là lớn nhất.
Hình dưới minh họa ví dụ thứ nhất. Với vị trí cắt được đánh dấu (ngay trước dấu hiệu thứ , đọc theo chiều kim đồng hồ), các dấu hiệu của loại gen tạo thành cấu trúc lồng nhau đúng.

Dữ liệu vào
Dòng đầu tiên chứa số nguyên , độ dài của DNA.
Dòng tiếp theo chứa dãy DNA gồm dấu hiệu. Mỗi dấu hiệu là một ký tự đứng liền trước một số nguyên , trong đó s e cho biết đó là dấu hiệu bắt đầu hay kết thúc, còn là loại gen của dấu hiệu. Dãy được cho thu được từ DNA vòng bằng cách cắt tại một vị trí bất kỳ.
Dữ liệu ra
In ra một dòng gồm hai số nguyên và , trong đó là vị trí cắt làm cho số loại gen khác nhau tạo thành cấu trúc lồng nhau đúng là lớn nhất, còn là số lớn nhất đó. DNA được cắt ngay trước dấu hiệu thứ của dữ liệu vào (ví dụ, vị trí cắt trong hình có ). Nếu có nhiều vị trí cắt cùng cho giá trị lớn nhất, in ra nhỏ nhất.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 9 e1 e1 s1 e2 s1 s2 e42 e1 s1 |
3 1 | Cắt trước dấu hiệu thứ được dãy s1 e2 s1 s2 e42 e1 s1 e1 e1; loại cho s1 s1 e1 s1 e1 e1, lồng nhau đúng. Loại chỉ lồng nhau đúng khi cắt tại hoặc , khi đó loại không lồng nhau đúng; loại chỉ có một dấu hiệu nên không bao giờ lồng nhau đúng. Vậy , và là vị trí nhỏ nhất đạt được. |
| 8 s1 s1 e3 e1 s3 e1 e3 s3 |
8 2 | Cắt trước dấu hiệu thứ được dãy s3 s1 s1 e3 e1 s3 e1 e3: loại cho s1 s1 e1 e1 và loại cho s3 e3 s3 e3, cả hai đều lồng nhau đúng. Mọi vị trí cắt khác chỉ cho nhiều nhất một loại. |
Bình luận