Các nhà sinh học phát hiện ra một loại chuỗi DNA lạ. Nó được mô tả như một chuỗi gồm 𝒏 ký tự xây dựng từ tập {𝑨,𝑩}. Một chuỗi DNA không thể đột biến được nữa nếu chuỗi đó chỉ gồm toàn ký tự A. Ví dụ chuỗi 𝑨𝑨𝑨 là một chuỗi không thể đột biến nữa. Các nhà sinh học phát hiện ra điều kỳ lạ này và đã tiến hành nghiên cứu chi tiết hơn. Họ phát hiện ra chỉ có hai loại đột biến cho loại DNA này. Loại đột biến thứ nhất là hoán đổi một ký tự bất kỳ của chuỗi theo quy tắc 𝑨 → 𝑩 hoặc B → A. Loại đột biến thứ hai thay đổi tiền tố của chuỗi. Cụ thể là thay đổi tất cả các ký tự từ vị trí 1 đến vị trí 𝒌 (𝟏 ≤ 𝒌 ≤ 𝒏) với quy tắc 𝑨 → 𝑩 hoặc B → A.
Yêu cầu: Hãy tính số phép đột biến ít nhất để biến đổi một chuỗi DNA ban đầu sang chuỗi DNA kết thúc chỉ chứa toàn ký tự 𝑨. Đây là loại chuỗi DNA không thể đột biến được nữa.
Dữ liệu: Vào từ file văn bản DNA.INP: - Dòng đầu tiên chứa số nguyên 𝒏 với 1 ≤ 𝑛 ≤ 106; - Dòng thứ hai chứa xâu ký tự 𝒔 chỉ trạng thái đầu tiên của chuỗi DNA.
Kết quả: Đưa ra file văn bản DNA.OUT gồm 1 dòng duy nhất ghi số lần biến đổi ít nhất để đưa chuỗi DNA từ trạng thái 𝒔 về trạng thái không đột biến được nữa.
Ví dụ:
DNA.INP | DNA.OUT |
4 ABBA |
2 |
12 AAABBBAAABBB |
4 |
Rewrite the following sentences that keep the same meaning.
1. Our spending will have to be reduced next year. back
We will have ______________ spending next year.
2 The children were absolutely certain that the film would be fantastic. doubt
There _____________ of the children that the film would be fantastic.
3 Did anyone raise the subject of the school trip? brought
Can you tell me ____________ the subject of the school trip?
4 I started learning French two years ago. been
I ________________________.
5 They are moving our oral examination to an earlier date. forward
Our oral examination ______________ an earlier date.