COCI 2019/2020 - Contest 4 - Nivelle - VNOJ: VNOI Online Judge

COCI 2019/2020 - Contest 4 - Nivelle

Điểm: 1,50 (OI)

Giới hạn thời gian: 1.5s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Người đăng:

Mondeus

Nguồn bài:

COCI 2019/2020 - Contest 4

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bojan 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

Copy

4
honi

Sample output 1

Copy

1 4

Sample input 2

Copy

7
nivelle

Sample output 2

Copy

4 7

Sample input 3

Copy

6
ananas

Sample output 3

Copy

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

Hãy đọc nội quy trước khi bình luận.

23

hieuhfgr đã bình luận 2:08:06 sa, 20/06/2024

Mô sai (my sol)

Hints:

minimize $(d i f f) / (r - l + 1)$ với $d i f f$ là số lượng phần tử khác nhau trong đoạn $(l, r)$ . Vậy $d i f f$ có độ lớn là bao nhiêu?

Ta cố định $d i f f$ và duyệt tuần tự theo $i$

Solution:

Bài toán của ta là việc in ra đoạn $(l, r)$ nhỏ nhất mà sao cho $d i f f / (r - l + 1)$ là bé nhất. vì $1 \leq d i f f \leq 26$ (chỉ có $26$ màu khác nhau) nên ta sẽ xét từng đoạn mà bằng với $d i f f$ . Gọi $c n t [i] [x]$ là số lượng kí tự $x$ xuất hiện trong đoạn $s [1. . i]$ . Vậy việc còn lại của ta là duy trì một con trỏ $j$ ý nghĩa là ta xét đoạn $(j, i)$ và kiểm tra điều kiện qua mảng $c n t$ . DPT: O(n*26)

lần đầu viết sol mong mọi ng đừng downvote T_T