Tên bài: DÂY ĐÈN TRANG TRÍ
Mã bài: COLORS
File chương trình: COLORS.PY
File dữ liệu: COLORS.INP
File kết quả: COLORS.OUT
Dẫn dắt
Minh
vừa mua một bộ dây đèn nhấp nháy để trang trí cho dịp lễ sắp tới. Dây đèn gồm 
bóng đèn được
mắc nối tiếp, mỗi bóng đèn phát ra một màu sắc nhất định thuộc bộ 
màu cơ bản
(các màu được đánh số từ 
đến ).
Bố của
Minh đưa ra một thử thách: “Con hãy tìm một đoạn dây đèn liên tiếp ngắn nhất
sao cho đoạn đó chứa đầy đủ tất cả loại màu”. Nếu tìm được, Minh sẽ được thưởng một món quà.
Yêu cầu
Cho
dãy số 
gồm phần tử mô tả
màu của các bóng đèn theo thứ tự (
). Hãy tìm độ dài của đoạn con liên tiếp ngắn nhất chứa
đủ các số nguyên từ đến .
Dữ liệu (Input)
·
Dòng đầu tiên chứa hai số
nguyên dương 
và 
(
).
·
Dòng thứ hai chứa số
nguyên 
(
).
Kết quả (Output)
·
Ghi ra một số nguyên duy nhất
là độ dài của đoạn dây đèn ngắn nhất thỏa mãn yêu cầu.
·
Nếu không tồn tại đoạn dây nào
chứa đủ màu,
ghi ra số 0.
Ràng buộc (Constraints)
·
30% số điểm: 
.
·
60% số điểm: 
.
·
100% số điểm: 
, 
.
Ví dụ (Sample)
|
COLORS.INP |
COLORS.OUT |
GIẢI THÍCH |
|
10 3 1 2 1 3 2 2 1 3 1 1 |
3 |
Đoạn ngắn nhất chứa đủ 3 màu (1, 2, 3) là đoạn từ vị trí 2 đến 4: 2 1 3 (độ dài 3).Cũng có các đoạn khác như 3 2 2 1 (độ dài 4) nhưng không tối ưu bằng. |
1.gif)