Hệ nhị phân (hay hệ đếm cơ số hai) là một hệ đếm dùng hai ký tự để biểu đạt một giá trị số, bằng tổng số các lũy thừa của 2. Hai ký tự đó thường là 0 và 1; chúng thường được dùng để biểu đạt hai giá trị hiệu điện thế tương ứng (có hiệu điện thế, hoặc hiệu điện thế cao là 1 và không có, hoặc thấp là 0). Do có ưu điểm tính toán đơn giản, dễ dàng thực hiện về mặt vật lý, chẳng hạn như trên các mạch điện tử, hệ nhị phân trở thành một phần kiến tạo căn bản trong các máy tính đương thời.
Sau khi đọc về hệ nhị phân, Sắn rất thích thú với các con số 0 và 1. Thấy Sắn thích, bố đố Sắn bài tập như sau: Cho một dãy số nguyên A gồm N phần tử và một số nguyên K. Bố đố sắn tìm ra một đoạn con ngắn nhất gồm các phần tử liên tiếp [L, R] thoả mãn:
- Chuyển hết các phần tử của đoạn con này sang hệ nhị phân, tính U là tổng các bit 1 của các số vừa chuyển được.
- U ≥ K.
Tuy nhiên bố cho dữ liệu lớn quá, Sắn đang bối rối. Các bạn hãy giúp Sắn nhé.
Dữ liệu nhập:
- Dòng 1 là hai số nguyên N và K.
- Dòng 2 là dãy số nguyên A.
Kết quả xuất ra:
- in một số nguyên duy nhất là độ dài đoạn con ngắn nhất thoả mãn yêu cầu của đề bài. Nếu không tìm được đoạn con nào thoả mãn hãy in -1.
Ràng buộc:
- 1 ≤ N ≤ 100000
- 0 ≤ A[i] ≤ 109
- 1 ≤ K ≤ 1012
bài dạng tìm kiếm nhé, giới hạn thời gian 1s
