Chụp Ảnh Công Bằng (Gold)

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

Nông dân có $N$ con bò đứng trên một hàng rào, mỗi con thuộc một trong 8 giống (đánh số từ 1 đến 8). Mỗi con bò có một vị trí nguyên trên hàng rào (không có hai con cùng vị trí).

Nông dân muốn chụp một bức ảnh bao gồm một đoạn liên tiếp các con bò (theo vị trí) sao cho:

Có ít nhất $K$ giống bò xuất hiện trong ảnh ( $K \geq 2$ ).
Tất cả các giống xuất hiện trong ảnh phải có số lượng bằng nhau.

Kích thước bức ảnh được tính bằng hiệu giữa vị trí lớn nhất và nhỏ nhất của các con bò trong ảnh. Hãy tìm kích thước lớn nhất có thể, hoặc in $- 1$ nếu không tồn tại bức ảnh hợp lệ.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $K$ .

$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}$ và $b_{i}$ — vị trí và giống của con bò thứ $i$ .

Dữ liệu ra

Một số nguyên duy nhất — kích thước lớn nhất của bức ảnh hợp lệ, hoặc $- 1$ nếu không tồn tại.

Ràng buộc

$1 \leq N \leq 100 000$
$2 \leq K \leq 8$
$0 \leq x_{i} \leq 10^{9}$
$1 \leq b_{i} \leq 8$
Không có hai con bò cùng vị trí

Ví dụ

Input	Output	Giải thích
9 2 1 1 5 1 6 1 9 1 100 1 2 2 7 2 3 3 8 3	6	Đoạn từ vị trí 2 đến 8 chứa 2 con giống 1, 2 con giống 2, 2 con giống 3. Có 3 giống ( $\geq K = 2$ ), mỗi giống 2 con. Kích thước = $8 - 2 = 6$ .
10 3 0 1 1 2 2 2 3 3 4 3 5 3 6 3 7 2 8 2 9 1	-1	Không tồn tại đoạn nào có $\geq 3$ giống với số lượng bằng nhau.

Bình luận

Không có bình luận tại thời điểm này.