Gen Chiến Thắng

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John phân tích bộ gen của Bessie -- một chuỗi $S$ độ dài $N$ ( $1 \leq N \leq 3000$ ) gồm các chữ cái in hoa.

Với mỗi cặp $(K, L)$ thỏa $1 \leq L \leq K \leq N$ , FJ thực hiện:

Lấy tất cả các chuỗi con độ dài $K$ (k-mer) của $S$ : $S [0 . . K - 1], S [1 . . K], \dots, S [N - K . . N - 1]$
Trong mỗi k-mer, tìm chuỗi con độ dài $L$ nhỏ nhất theo thứ tự từ điển (nếu hòa, lấy vị trí trái nhất)
Ghi lại vị trí bắt đầu (0-indexed) trong $S$ của chuỗi con đó vào tập $P$

Với mỗi $v$ từ 1 đến $N$ , đếm số cặp $(K, L)$ mà $| P | = v$ .

Input	Output	Giải thích
8 AGTCAACG	11 10 5 4 2 2 1 1	Có 11 cặp $(K, L)$ cho $\| P \| = 1$ , 10 cặp cho $\| P \| = 2$ , v.v. Ví dụ $(K, L) = (8, 1)$ : chỉ 1 k-mer (toàn bộ chuỗi), chuỗi con 1 ký tự nhỏ nhất là 'A' tại vị trí 0, nên $\| P \| = 1$ .

Bình luận

Không có bình luận tại thời điểm này.