Bài 3. Mật khẩu (HSG THPT Bắc Ninh 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT Bắc Ninh 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Điệp viên Smith có gói tin quan trọng cần bảo mật nên anh đặt mật khẩu. Smith ghi vào sổ dãy ~A~ có ~N~ số nguyên ~A_1, A_2, A_3, \ldots, A_N (1 \le A_i \le 10^6)~. Dãy ~A~ có ít nhất ~M~ giá trị khác nhau. Mật khẩu của Smith là một đoạn con liên tiếp ~A_L, A_{L+1}, \ldots, A_R (1 \le L \le R \le N)~ ngắn nhất chứa đủ ~M~ giá trị khác nhau. Khi đó, giá trị ~R - L + 1~ là độ dài của mật khẩu.

Do Smith được giao quá nhiều nhiệm vụ quan trọng và đột xuất nên tạm thời anh ấy bị quên mất mật khẩu. Smith muốn dò lại mật khẩu từ dãy số ~A~ nhưng để việc tìm kiếm thuận lợi anh cần tìm chính xác độ dài của mật khẩu đó.

Yêu cầu: Bạn hãy giúp Smith tìm độ dài của mật khẩu.

Dữ liệu vào

Dữ liệu vào từ thiết bị vào chuẩn gồm hai dòng:

  • Dòng 1: Ghi 2 số nguyên dương ~N, M (N \le 5 \times 10^6, M \le N)~;
  • Dòng 2: Ghi ~N~ số nguyên dương ~A_1, A_2, A_3, \ldots, A_N (1 \le A_i \le 10^6)~.

Kết quả

Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Input 1

10 4
5 2 1 1 3 2 1 3 2 1

Output 1

5

Đoạn con (5, 2, 1, 1, 3) có đủ 4 giá trị khác nhau {5, 2, 1, 3} và không có đoạn nào ngắn hơn thoả mãn.

Ràng buộc

  • Subtask 1: Có 60% số test ứng với 60% số điểm có ~1 \le N \le 10^2~;
  • Subtask 2: Có 40% số test ứng với 40% số điểm có ~10^2 < N \le 5 \times 10^6~.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout). Vẫn có thể giữ đoạn freopen("MATKHAU.INP", ...) nếu đặt trong điều kiện if (fopen("MATKHAU.INP", "r")).


Đang tải...