JOI 2021 - Bitaro and IOI

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 \(N\). Mỗi ký tự của \(S\) là một trong các ký tự B, I, T, A, R, O.

Hãy xác định có thể chọn một dãy con gồm các ký tự của \(S\) theo đúng thứ tự xuất hiện, không nhất thiết liên tiếp, để được xâu IOI hay không. Nói cách khác, hãy xác định có tồn tại bộ ba số nguyên \((i, j, k)\) thỏa mãn tất cả các điều kiện sau hay không:

  • \(1 \le i < j < k \le N\).
  • Ký tự thứ \(i\) của \(S\) là I.
  • Ký tự thứ \(j\) của \(S\) là O.
  • Ký tự thứ \(k\) của \(S\) là I.

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

Nếu IOI là một dãy con của \(S\), in ra Yes; ngược lại, in ra No.

Ràng buộc

  • \(1 \le N \le 100\).
  • \(S\) là xâu có độ dài \(N\).
  • Mỗi ký tự của \(S\) là một trong các ký tự B, I, T, A, R, O.

Ví dụ

Ví dụ 1

Input 
8
BITAROOI
Output 
Yes
Giải thích

Các bộ ba \((2, 6, 8)\) và \((2, 7, 8)\) đều thỏa mãn các điều kiện đối với \((i, j, k)\). Do đó, IOI là một dãy con của \(S\), nên in ra Yes.

Ví dụ 2

Input 
6
BBOOII
Output 
No
Giải thích

Không có dãy con nào của \(S\) bằng IOI, nên in ra No.

Ví dụ 3

Input 
5
IOIOI
Output 
Yes

Ví dụ 4

Input 
9
RATRATRAT
Output 
No

Ví dụ 5

Input 
1
A
Output 
No

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: