COCI 2019/2020 - Contest 4 - Nivelle
Xem dạng PDFBojan thấy có ~N~ đồ chơi nằm ở trên kệ, được đánh số từ ~1~ đến ~N~. Mỗi đồ chơi được tô 1 trong trong 26 màu khác nhau. Mỗi màu được thể hiện bởi một chữ cái in thường trong bảng chữ cái tiếng Anh.
Với mỗi tập các đồ chơi, chúng ta có thể định nghĩa độ rực rỡ là số lượng màu của đồ chơi khác nhau, chia cho tổng số đồ chơi có trong tập. Bojan ghét sự rực rỡ. Bojan muốn chọn một đoạn con liên tiếp các đồ chơi.
Hãy giúp Bojan tìm một đoạn con liên tiếp các đồ chơi mà độ rực rỡ là nhỏ nhất có thể.
Input
Dòng đầu tiên chứa số nguyên ~N (1 \leq N \leq 100000)~, số lượng đồ chơi có trên kệ.
Dòng thứ hai chứa xâu ~S~ có độ dài ~N~. Kí tự thứ ~i~ trong xâu thể hiện màu của món đồ chơi thứ ~i~ trên kệ.
Output
In ra 2 vị trí ~L~ và ~R~ ~(1 \leq L \leq R \leq N)~, thể hiện đoạn con đồ chơi cần tìm là ở vị trí ~L, L+1,..., R~.
Nếu tồn tại nhiều đáp án thỏa mãn độ rực rỡ nhỏ nhất, hãy in đáp án bất kì.
Ví dụ
Sample input 1
4
honi
Sample output 1
1 4
Sample input 2
7
nivelle
Sample output 2
4 7
Sample input 3
6
ananas
Sample output 3
1 5
Ràng buộc
- 6 test đầu có ~N \leq 100~.
- 6 test sau có ~N \leq 2000~.
- 6 test sau khác thỏa ~S~ chỉ chứa ~a~, ~b~.
- 6 test sau khác thỏa ~S~ chỉ chứa ~a~, ~b~, ~c~, ~d~ và ~e~.
- 6 test còn lại không có ràng buộc gì thêm.
Bình luận
Cho mình hỏi mình thử sai test case mà sao lại ac ạ Mình thử nộp lấy test thôi
Vì trong 1 xâu có nhiều đoạn có giá trị độ rực rỡ bằng nhau ấy bạn
VD trong test 2:
7
nivelle
-thì đoạn 4 7 có giá trị rực rỡ là 0.5
-nhưng trong đoạn 5 6 cũng có giá trị rực rỡ là 0.5
=> bài này người ta không nói gì về đoạn nào sớm nhất hay sao thì có thể có nhiều đoạn
=> nên bài này bạn cout ra sai kqua nhưng có thể nộp lên vẫn AC ấy, tôi cũng vậy
Nếu tồn tại nhiều đáp án thỏa mãn độ rực rỡ nhỏ nhất, hãy in đáp án bất kì. Tại sao in một đoạn hợp lệ lại gọi là sai?
Okay bri
Mô sai (my sol)
Hints:
Solution: