Một đoạn con độ dài K được gọi là "Đẹp" nếu tổng các phần tử trong đó chia hết cho số nguyên X cho trước.

Hãy đếm số lượng đoạn con Đẹp.

Input:

• Dòng 1: N, K, X.

• Dòng 2: N số nguyên A[i].

Output:

• Số lượng đoạn con Đẹp.

Ví dụ 1:

Input:

5 3 3
1 2 3 4 5

Output:

2

Ví dụ 2:

Input:

4 2 2
1 1 1 1

Output:

3

Hãy tìm giá trị NHỎ NHẤT trong mỗi cửa sổ độ dài K.

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên A[i].

Output:

• Dãy min của từng cửa sổ.

Ví dụ 1:

Input:

5 3
10 4 2 15 8

Output:

2 2 2

Ví dụ 2:

Input:

3 1
5 1 9

Output:

5 1 9

Bạn biết giá vàng trong N ngày liên tiếp.

Bạn muốn thực hiện chiến thuật: Mua vào ngày i và bán ra vào đúng ngày i + K.

Hãy tìm lợi nhuận cao nhất có thể đạt được (Giá bán - Giá mua).

Nếu bị lỗ, hãy in ra "-inf".

Input:

• Dòng 1: N, K (1 <= K < N).

• Dòng 2: N số nguyên A[i] là giá vàng.

Output:

• Lợi nhuận cao nhất.

Ví dụ 1:

Input:

6 2
1 5 3 8 2 10

Output:

3

Giải thích: max(3-1, 8-5, 2-3, 10-8) = 3

Ví dụ 2:

Input:

5 1
10 9 8 7 6

Output:

-inf

Nhà An có N cái cây, cây thứ i có chiều cao ban đầu là A[i] cm. An vừa mua được M lọ thuốc tăng trưởng cực tốc. Mỗi lọ thuốc khi tưới vào một cái cây bất kỳ sẽ giúp cây đó cao thêm đúng 1 cm ngay lập tức (một cây có thể được tưới nhiều lọ thuốc).

An muốn sử dụng M lọ thuốc này một cách hợp lý nhất để chiều cao của cái cây thấp nhất trong vườn là cao nhất có thể.

Yêu cầu: Hãy tính chiều cao của cái cây thấp nhất sau khi An đã sử dụng tối ưu toàn bộ M lọ thuốc.

Dữ liệu vào: Đọc từ thiết bị chuẩn (bàn phím)

Dòng đầu tiên chứa hai số nguyên dương N và M (1 <= N <= 10^5, 0 <= M <= 10^9).

Dòng thứ hai chứa N số nguyên biểu diễn chiều cao ban đầu của các cây A[1], A[2], ..., A[N] (0 <= A[i] <= 10^9).

Dữ liệu ra: Ghi ra thiết bị chuẩn (màn hình)

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input:

3 4 
2 4 6

Output:

5

Giải thích ví dụ:

Có 3 cây với chiều cao lần lượt là 2, 4, 6. An có 4 lọ thuốc.

Phương án tối ưu:

Dùng 3 lọ thuốc cho cây thứ nhất: Chiều cao từ 2 -> 5.

Dùng 1 lọ thuốc cho cây thứ hai: Chiều cao từ 4 -> 5.

Cây thứ ba không dùng thuốc: Chiều cao giữ nguyên là 6.

Sau khi dùng hết 4 lọ thuốc, chiều cao của các cây là: 5, 5, 6. Cái cây thấp nhất trong vườn lúc này cao 5cm. Đây là kết quả tối ưu nhất.

Để lắp ráp 1 con robot cần N loại linh kiện, loại thứ i cần A[i] cái. Trong kho đang có sẵn B[i] cái loại i. Bạn có thể mua thêm linh kiện với giá 1 đồng/cái. Bạn có K đồng. Hỏi có thể lắp ráp tối đa bao nhiêu con robot?

Dữ liệu vào:

Dòng 1: N và K.

Dòng 2: Mảng A (nhu cầu).

Dòng 3: Mảng B (có sẵn).

Dữ liệu ra:

Số robot tối đa.

Ràng buộc:

1 <= N <= 100

1 <= K <= 10^12

Ví dụ:

Input:

3 10 
2 3 1 
10 10 10

Output:

6

Giải thích: Với K = 10 sẽ lắp tối đa được 6 con robot

Trong buối học hôm nay, Trang đã được cô giáo giới thiệu một kiến thức mới về dãy số - đó chính là dãy số có quy luật. Một dãy số có n phần tử [a1, a2, ...,an] được gọi là dãy số có quy luật nếu với mọi i (1 < i ≤ n) thì a; = ai-1 + k và giá trị k là giá trị không đổi với mọi i.

Vào buổi tối, khi Trang vừa mới tìm hiểu về dãy số quy luật thì đã đến 11h đêm, cô chuẩn bị đi ngủ. Nhưng khi chuẩn bị đi ngủ, Trang mới nhớ ra, cô cần phải làm rất nhiều bài tập về nhà mà cô giáo giao vào sáng nay. Đề bài như sau:

Cho một dãy số có n phần tử [a1, a2,..., an]. Với mỗi phần tử ai (1 ≤ i ≤ n), Trang có thể thực hiện duy nhất một trong 3 thao tác:

• Thay giá trị ai thành ai + 1.

• Thay giá trị ai thành ai - 1.

• Giữ nguyên giá trị ai.

• Yêu cầu: Tính số lượng ít nhất phần tử ai bị thay đổi thành ai + 1 hoặc ai - 1 để dãy trên trở thành một dãy số có quy luật.

Tuy nhiên, sau khi làm bài xong, vẫn còn t bài tập mà Trang vẫn chưa chắc chắn. Nên Trang đã nhờ các bạn, hãy viết chương trình để giúp Trang kiểm tra kết quả nhé.

Đầu vào:

Dòng đầu tiên: Gồm một số nguyên dương t (t ≤ 20), là số bài tập Trang còn chưa chắc chắn.

Các dòng tiếp theo là dữ liệu của t bài tập, với bài tập thứ i (1 ≤ i ≤ t):

• Dòng thứ i x 2: Gồm một số nguyên dương n (2 < n ≤ 10^5), là số phần tử của dãy số trong bài tập thứ i.

• Dòng thứ i x 2 + 1: Gồm n số nguyên ay, az, a3,..., an là các giá trị của dãy số trong bài tập thứ i.

Đầu ra: Gồm t dòng, mỗi dòng gồm một số nguyên là số lượng ít nhất phần tử ai bị thay đổi thành ai+1 hoặc ai-1 để trở thành một dãy số có quy luật. Nếu không thể biến đổi dãy số có quy luật thì in ra -1.

Ví dụ:

Input:

3
3
2 2 2
4
9 6 1 -5
3
8 9 3

Output:

0
3
-1

Giải thích:

• Ở bài tập đầu tiên, dãy đã cho là dãy số có quy luật với k = 0;

• Ở bài tập thứ 2, ta sẽ biến dấy thành [10, 5, 0,- 5], khi đó nó là dãy số có quy luật với k = -5.

Hãy xem xét một hệ thống tiền tệ của ngân hàng XYZ bao gồm n đồng xu. Mỗi đồng xu có một giá trị nguyên dương. Nhiệm vụ của bạn là tính số cách riêng biệt mà bạn có thể tạo ra số tiền x bằng cách sử dụng số xu có sẵn. Ví dụ: nếu số xu là (2,3,5) và tổng mong muốn là 9, có 8 cách: 2 + 2 + 5; 2 + 5 + 2; 5 + 2 + 2; 3 + 3 + 3; 2 + 2 + 2 + 3; 2 + 2 + 3 + 2; 2 + 3 + 2 + 2; 3 +2 + 2 + 2;

Đầu vào: Dòng tiên có hai số nguyên n và x là số xu và số tiền mong muốn. Dòng thứ hai có n số nguyên phân biệt c1, c2,..., cn là giá trị của mỗi đồng xu.

Ràng buộc: 1 <= n <= 100; 1 <= x <= 10^6; 1 <= ci<= 10^6;

Đầu ra: In ra kết quả lấy dư với 10^9 + 7

Input:

3 9
2 3 5

Output:

8

Một dãy số được gọi là Bitonic nếu nó được chia thành hai dãy đầu tăng dần và dãy tiếp theo giảm dần. Nhiệm vụ của bạn là tìm tổng lớn nhất dãy con Bitonic của dãy số A[]. Ví dụ với dãy A[] = {1, 15, 51, 45, 33, 100, 12, 18, 9} ta có kết quả là 194 tương ứng với dãy Bitonic {1, 15, 51, 100, 18, 9}.

Đầu vào: Dòng đầu tiên đưa vào N là số phần tử của dãy A[]; Dòng tiếp theo đưa vào N số A[i]; các số được viết cách nhau một vài khoảng trống

Ràng buộc: 1<=N<=100;1<=A[i]<=100

Input:

8
7 8 8 19 3 6 2 15

Output:

49

Cho măng 2 chiều A gồm N hàng và N cột, hàng được đánh số từ 1 đến N từ trên xuống dưới, cột được đánh số từ 1 tới N từ trái sang phải, hãy tìm 1 đường đi từ một ô ở cột 1 tới một ô ở cột N sao cho các phần tử trên đường đi đó là lớn nhất có thế. Biết ràng ở mỗi bước đi từ ô hiện tại (i, j) chỉ có thể đi sang phải (i, j + 1) hoặc đi xưỗng ô dưới bên phải (i + 1, j + 1) hoặc đi lên trên bên phải (i - 1, j + 1). Hãy tìm đường đi có tổng các số trên đường đi là lớn nhất.

Đầu vào: Dòng 1 là N; N dòng tiếp theo mỗi dòng gồm N số

Ràng buộc:

1 <= N <= 100

-100 <= A[i][j] <= 100

Đầu ra: In ra đáp án của bài toán

Input:

5
2 -8 2 9 0
-5 6 6 -1 6
3 5 0 2 9
9 -8 9 7 0
-4 6 1 -2 0

Output:

40

Cho xâu S chỉ bao gồm các ký tự viết thường và dài không quá 1000 ký Tự. Hãy tìm xâu con đối xing dài nhất của S.

Đầu vào: Dòng duy nhất chứa xâu S

Ràng buộc: 1<=len(S)<=1000;

Đầu ra: In ra đáp án của bài toán

Input

abccbxabbaxuv

Output:

6