JOI 2021 - IOI String

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 400 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho xâu \(S\) có độ dài lẻ \(N\). Mỗi ký tự của \(S\) là một chữ cái tiếng Anh in hoa.

Một xâu IOI là xâu thỏa mãn tất cả các điều kiện sau:

  • Độ dài của xâu là số lẻ.
  • Mỗi ký tự là I hoặc O, và hai loại ký tự này xuất hiện xen kẽ.
  • Ký tự đầu tiên là I.

Ví dụ, I, IOI, IOIOIOI là các xâu IOI, còn JOI, IIOOII, OIOIO không phải là xâu IOI.

Bạn có thể thực hiện thao tác sau không hoặc nhiều lần: chọn một ký tự của \(S\) và thay ký tự đó bằng một chữ cái tiếng Anh in hoa tùy ý.

Hãy tìm số thao tác ít nhất cần thực hiện để biến \(S\) thành một xâu IOI.

Dữ liệu vào

Dòng thứ nhất chứa số nguyên \(N\).

Dòng thứ hai chứa xâu \(S\).

Dữ liệu ra

In ra số thao tác ít nhất cần thực hiện để biến \(S\) thành một xâu IOI.

Ràng buộc

  • \(1 \le N \le 99\).
  • \(N\) là số lẻ.
  • \(S\) là xâu có độ dài \(N\).
  • Mỗi ký tự của \(S\) là một chữ cái tiếng Anh in hoa.

Ví dụ

Ví dụ 1

Input 
5
JJOOI
Output 
3
Giải thích

Chẳng hạn, có thể biến \(S\) thành một xâu IOI sau \(3\) thao tác như sau:

  1. Thay ký tự thứ \(1\) của \(S\) bằng I.
  2. Thay ký tự thứ \(2\) của \(S\) bằng O.
  3. Thay ký tự thứ \(3\) của \(S\) bằng I.

Không thể biến \(S\) thành một xâu IOI bằng ít hơn \(3\) thao tác, nên in ra \(3\).

Ví dụ 2

Input 
7
IOIOIOI
Output 
0
Giải thích

Có thể không cần thực hiện thao tác nào.

Ví dụ 3

Input 
7
BEAVERS
Output 
7

Ví dụ 4

Input 
5
OIOIO
Output 
5

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: