VACCINE - VACCINE
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 20.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: mikelhpdatke

      Amino acid là thành phần cơ bản của sự sống. Amino acid gồm 20 loại khác nhau {A,C,D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y}. Protein là một chuỗi amino acid và được biểu bởi một xâu kí tự P, trong đó P(t) là amino acid ở vị trí thứ t trong P. Các chuỗi amino acid khác nhau sẽ tạo ra các protein khác nhau. M-vaccine là một loại protein có độ dài không quá 500 amino acid được dùng để tiêu diệt các loại vi rút.

      Các nhà khoa học đang tập trung nghiên cứu protein của vi rút POKTE nhằm sản xuất ra các loại M-vaccine để tiêu diệt loại vi rút này.

      Ta nói, M-vaccine V có thể tiêu diệt được k amino acid trong protein P của vi rút POKTE nếu tồn hai dãy chỉ số (X1 < X2 <…<Xk) và (Y1 < Y2 <…<Yk) sao cho V(Xi) = P(Yi) với i =1…k. Mức độ tiêu diệt vi rút POKTE của M-vaccine V được xác định bằng giá trị k lớn nhất.

      Cho protein P của vi rút POKTE và N loại M-vaccine, nhiệm vụ của bạn là tìm loại M-vaccine trong N loại M-vaccine có mức độ tiêu diệt vi rút POKTE lớn nhất.

Dữ liệu vào: Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test.

- Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

- Với mỗi bộ dữ liệu, dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 200) là số lượng loại M-vaccine. Dòng thứ hai chứa một xâu độ dài không vượt quá 10000 là biểu diễn protein P của vi rút POKTE. N dòng tiếp theo, mỗi dòng chứa một xâu biểu diễn cho một loại M-vaccine. (độ dài  <= 500)

Dữ liệu ra:

Với mỗi bộ dữ liệu, ghi ra trên một dòng một số nguyên là mức độ tiêu diệt của loại M-vaccine có mức độ tiêu diệt vi rút POKTE lớn nhất.

Ví dụ

  • input
    1
    5
    ENRPPNVPES
    TEV
    LNRC
    HKVR
    FWW
    PWP
    output
    2
Back to Top