VOI 17 Bài 1 - Virus

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 3.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đọc đề gốc tại đây.

"TextFile" là một virus chuyên tấn công các file văn bản theo phương thức sau: Sao chép một đoạn các ký tự liên tiếp trong trong nội dung của file văn bản vào bộ nhớ trong, thay đổi một số ký tự trong đoạn này, sau đó chèn đoạn văn bản đã thay đổi vào ngay sau đoạn văn bản vừa sao chép trong file văn bản.

Vinh đang phát triển phần mềm để phát hiện một file văn bản đã bị nhiễm virus nói trên hay chưa. Vì thế, Vinh cần giải quyết bài toán sau: Cho xâu ký tự ~T~ và số nguyên không âm ~k~, xâu con gồm các ký tự từ vị trí ~p~ đến vị trí ~q~ của xâu ~T~ được gọi là đoạn có khả năng bị virus sao chép mức ~k~ nếu nó sai khác với xâu con gồm các ký tự từ vị trí ~q+1~ đến vị trí ~q+(q-p+1)~ của xâu ~T~ ở không quá ~k~ vị trí.

Ví dụ, xét xâu T = zabaaxy và ~k = 1~. Đoạn văn bản ab từ ký tự thứ ~2~ đến ký tự thứ ~3~ là đoạn văn bản độ dài ~2~ có khả năng bị virus sao chép mức ~1~ vì nó khác với đoạn văn bản aa gồm các ký tự từ ký tự thứ ~4~ đến ký tự thứ ~5~ của xâu ~T~ ở ~1~ vị trí.

Yêu cầu: Cho xâu ký tự ~T~ và ~n~ số nguyên không âm ~k_1, k_2, \ldots, k_n~. Với mỗi giá trị ~k_i~, hãy tìm độ dài đoạn dài nhất trong xâu ~T~ có khả năng bị virus sao chép ở mức ~k_i~ ~(i = 1, 2, \ldots, n)~.

Input

  • Dòng đầu chứa số nguyên dương ~n~ ~(n \le 10)~.
  • Dòng thứ hai chứa một xâu ~T~ gồm các chữ cái in thường lấy từ tập 26 chữ cái tiếng Anh từ a đến z.
  • Dòng thứ ~i~ trong số ~n~ dòng tiếp theo ghi số nguyên không âm ~k_i~ ~(k \le 10, i = 1, 2, \ldots, n)~.

Output

Ghi ra ~n~ dòng, dòng thứ ~i~ ghi một số nguyên không âm là độ dài đoạn dài nhất có khả năng bị virus sao chép ở mức ~k_i~, ~i = 1, 2, \ldots, n~. Ghi ~0~ nếu không tìm được đoạn như vậy.

Giới hạn

Ký hiệu ~m~ là độ dài của xâu ~T~.

  • Có ~40\%~ số lượng test thoả mãn điều kiện: ~m \le 300~;
  • Có thêm ~30\%~ số lượng test thoả mãn điều kiện: ~m \le 3\,000; \; k_i = 0~ với mọi ~i~;
  • ~30\%~ số lượng test còn lại thoả mãn điều kiện: ~m \le 3\,000~.

Sample Input 1

2
zabaaxy
0
1

Sample Output 1

1
2

Sample Input 2

2
zcaabcaaaa
0
1

Sample Output 2

2
4

Note

Giải thích: Trong test ví dụ 2, đoạn dài nhất có khả năng bị virus sao chép ở mức ~0~  là aa có độ dài ~2~, đoạn dài nhất có khả năng bị virus sao chép ở mức ~1~ là caab có độ dài ~4~.

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • -1
    phanhuykhang   commented on Aug. 7, 2022, 12:15 p.m.

    Bài này theo mình thấy thì test vẫn còn khá yếu, code cày trâu sub1 mà vẫn có thể ăn được sub2 & sub3


  • 1
    0855250956   commented on Jan. 17, 2022, 3:10 p.m. edited

    hình như output 2 của bài này sai, phải là 3 4 chứ nhỉ. có 2 đoạn caa không bị thay đổi. Edit: em đọc chưa kĩ đề =))