Tại một nông trường chè ở Thái Nguyên, có N luống chè xếp thành một hàng ngang. Luống thứ i có sản lượng là A_i kg. Giám đốc cần phân công K công nhân đi thu hoạch. Để đảm bảo tính liên tục, mỗi công nhân phải thu hoạch một dải các luống chè liên tiếp nhau. Hãy tìm cách chia N luống chè này cho K công nhân sao cho khối lượng chè lớn nhất mà một công nhân phải hái là nhỏ nhất có thể.

Input:

Dòng 1: Hai số nguyên N và K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^4).

Output: Khối lượng chè lớn nhất mà một công nhân phải hái trong phương án tối ưu.

Ví dụ:

Input:

5 3
2 4 1 3 5

Output:

6

(Giải thích: Chia thành 3 đoạn: [2, 4], [1, 3], [5]. Tổng các đoạn lần lượt là 6, 4, 5. Khối lượng lớn nhất là 6).

Dọc theo một tuyến đường cao tốc thẳng tắp có N trạm thu phí tại các tọa độ X_i. Công ty viễn thông cần lắp đặt các trạm phát sóng Wifi dọc theo tuyến đường. Biết rằng mỗi trạm Wifi có bán kính phủ sóng là R (tức là có thể phủ sóng trong đoạn [V - R, V + R] nếu đặt ở tọa độ V). Tìm số lượng trạm Wifi ít nhất cần lắp đặt để tất cả N trạm thu phí đều có mạng.

Input:

Dòng 1: Hai số nguyên N và R (1 <= N <= 10^5, 0 <= R <= 10^9).

Dòng 2: N số nguyên Xi là tọa độ của các trạm thu phí (0 <= Xi <= 10^9).

Output: Số lượng trạm Wifi tối thiểu.

Ví dụ:

Input:

5 2
1 4 5 10 12

Output:

3

Bạn được cung cấp một chuỗi s. Mỗi ký tự là 0 hoặc 1. Bạn muốn tất cả các số 1 trong chuỗi tạo thành một phân đoạn liền kề. Ví dụ: nếu chuỗi là 0, 1, 00111 hoặc 01111100, thì tất cả 1 đều tạo thành một phân đoạn liền kề và nếu chuỗi là 0101, 100001 hoặc 11111111111101 thì điều kiện này không được đáp ứng. Bạn có thể xóa một số 0 (có thể không cần xóa) khỏi chuỗi. Số 0 tối thiểu mà bạn phải xóa là bao nhiêu?

Đầu vào: Dòng đầu tiên chứa một số nguyên t (1≤t≤100) - số lượng trường hợp kiểm tra. Sau đó t dòng tiếp theo, mỗi dòng đại diện cho một trường hợp thử nghiệm. Mỗi dòng chứa một chuỗi s (1≤ | s |<=100); mỗi ký tự của s là 0 hoặc 1.

Đầu ra: In số nguyên t, trong đó số nguyên thứ i là câu trả lời cho mẫu thử thứ i (số tối thiểu là 0 mà bạn phải xóa khỏi s).

Input:

3
010011
0
1111000

Output:

2
0
0

Trạm thu phát sóng nhận được một chuỗi tín hiệu vô tuyến S gồm các chữ cái in thường. Để giải mã thông điệp cốt lõi, hệ thống cần trích xuất ra một đoạn tín hiệu liên tiếp dài nhất mà trong đó không có bất kỳ ký tự nào bị lặp lại (mỗi ký tự chỉ xuất hiện tối đa 1 lần). Hãy xác định độ dài của đoạn thông điệp cốt lõi đó.

Input: Một xâu S chỉ gồm chữ cái in thường (Độ dài <= 10^5).

Output: Độ dài của đoạn tín hiệu không lặp ký tự dài nhất.

Ví dụ:

Input:

abcabcbb

Output:

3

(Giải thích: Đoạn tín hiệu dài nhất là abc, bca hoặc cab).

Để khôi phục lại sảnh chính của một ngôi đền cổ có kích thước 2 x N (2 hàng, N cột), các kiến trúc sư sử dụng những viên gạch hoa hình chữ nhật có kích thước 1 x 2. Có thể đặt gạch nằm ngang (chiếm 1x2 ô) hoặc nằm dọc (chiếm 2x1 ô). Hãy tính xem có bao nhiêu cách khác nhau để lát kín toàn bộ sảnh đền này? Kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho 10^9+7.

Input: Một số nguyên dương N (1 <= N <= 10^6).

Output: Số cách lát gạch modulo 10^9+7.

Ví dụ:

Input:

3

Output:

3

(Giải thích: 3 cách gồm: 3 viên dọc; 1 viên dọc 2 viên ngang; 2 viên ngang 1 viên dọc).

Một bộ nhớ đệm lưu trữ các tiến trình dưới dạng một chuỗi S. Bộ nhớ này được coi là "ổn định" nếu không có bất kỳ 2 loại tiến trình (ký tự) nào có số lần xuất hiện (tần suất) bằng nhau. Em có quyền xóa bớt một số tiến trình ra khỏi bộ nhớ. Hãy tìm số lượng tiến trình ít nhất cần xóa để bộ nhớ đạt trạng thái ổn định.

Dữ liệu vào: Xâu S chỉ gồm chữ cái in thường (1 <= len(S) <= 10^5).

Kết quả ra: Số lượng ký tự ít nhất cần xóa.

Ví dụ:

Input:

aaabbbcc

Output:

2

(Tần suất ban đầu: a=3, b=3, c=2. Xóa 1 chữ b và 1 chữ c. Tần suất mới: a=3, b=2, c=1. Các tần suất đều khác nhau).