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

Có N cái cây. Mỗi ngày, một cái cây sẽ tự lớn thêm 1cm. Bạn có thể dùng thuốc tăng trưởng để làm 1 cái cây bất kỳ lớn thêm K cm ngay lập tức (mỗi ngày chỉ dùng thuốc 1 lần). Bạn muốn tất cả các cây đều đạt chiều cao tối thiểu là H. Hỏi sau ít nhất bao nhiêu ngày thì đạt được mục đích? (Giả sử ban đầu các cây cao 0). Lưu ý: Bài này hơi khó, ta đổi sang bài đơn giản hơn: Bài Toán Bơm Bóng Tên bài thay thế: Bơm Bóng Bay Mô tả: Có N quả bóng. Bạn cần bơm sao cho quả bóng nhỏ nhất có kích thước càng lớn càng tốt sau M lần bơm thêm (mỗi lần bơm tăng 1 đơn vị cho 1 quả). -> Binary Search kết quả kích thước tối thiểu.

Dữ liệu vào:

N và M.

Kích thước ban đầu của N quả bóng.

Dữ liệu ra:

Kích thước nhỏ nhất tối đa có thể đạt được.

Ràng buộc:

N, M <= 10^5

Ví dụ:

Input:

3 4 
2 4 6

Output:

5

Để 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