Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P165PROI - ROUND 5I - Đột biến gen

Các nhà sinh học vừa phát hiện ra một loại cấu trúc DNA alpha đặc biệt được cấu trúc bởi chỉ các Nucleotit A và B. Đặc biệt hơn, họ còn phát hiện ra một loại gen omega chỉ gồm nucleotit A nhưng vô cùng hiếm, để nghiên cứu sâu hơn về omega họ quyết định tổng hợp omega từ alpha bằng các phương pháp đột biến nhân tạo. May mắn thay họ tìm ra hai phương pháp đột biến có thể gây ảnh hưởng đến alpha: họ có thể làm thay đổi 1 nuleotit ở một vị trí bất kỳ trên đoạn gen alpha (A thành B hoặc B thành A), phương pháp thứ hai là thay đổi cả đoàn đầu của gen (những nuc A chuyển thành B và ngược lại). Để tiết kiệm chi phí họ quyết định tìm ra số lần gây đột biến ít nhất có thể để biến alpha thành omega.

Hãy giúp họ.

Input

Dòng đầu tiên chứa số tự nhiên n là số nucleotit của gen alpha (1 <= n <= 1000000)

Dòng thứ hai là biểu diễn của gen alpha.

Output

Kết quả bài toán.

Example

Input:

12

AAABBBAAABBB Output: 4


Được gửi lên bởi:adm
Ngày:2016-03-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2022-08-19 15:53:50
quy hoạch động
2016-07-22 16:22:24
đoạn đầu tính từ phan tu dau tien den 1 vi tri bat kì tùy ban chọn
2016-04-04 18:31:50 KienPM_PTIT-Jokers
cho em hỏi "phương pháp thứ hai là thay đổi cả đoàn đầu của gen" là thay đổi cả đoạn đầu của gen ạ? đoạn đầu là tính từ đâu đến đâu ạ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.