Nguồn : https://cses.fi/problemset/task/1628/ Cho bạn một dãy X gồm n số nguyên. Đếm số cách bạn có thể chọn 1 tập con của X có tổng bằng S.

Input

Dòng 1: Gồm 2 số nguyên n và S (1 ≤ n ≤ 40, ~ 1 ≤ S ≤ 10^9 ~).

Dòng 2: n số ~ a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) ~ là phần tử của dãy X.

Output

In ra số cách bạn có thể chọn 1 tập con của X có tổng bằng S.

Sample Input

4 5
1 2 3 2

Sample Output

3

Nguồn đề: thầy Nguyễn Thanh Tùng

Nhà thi đấu đa năng của Trường đang được khởi công xây dựng. Kinh phí từ ngân sách cấp có hạn nên hạng mục đường chạy ở trước nhà thi đấu không được duyệt. Nhà trường quyết định kêu gọi phụ huynh và học sinh cùng các thầy cô đóng góp công sức để có một đường chạy hoàn hảo cho học sinh rèn luyện thể lực.

Đường chạy phải hoàn toàn bằng phẳng, mọi điểm trên đường phải có cùng độ cao (gọi là cùng một mặt thủy chuẩn). Địa hình đường chạy tương lai được chia thành n khúc đánh số từ 1 đến n, từ trái sang phải. Độ cao khúc thứ i so với độ cao mặt đường thiết kế là ~ h_i~ ,~ i = 1 ÷ n~. ~h_i > 0~ nghĩa là phải hớt đi khối lượng đất cao ~h_i~, ngược lại, nếu ~h_i~ < 0 – chổ trũng, cần lấp đất thêm vào để đạt độ bằng phẳng thiết kế. Đất hớt ở chổ cao có thể lấp vào các chổ trũng, việc này không có gì khó khăn. Việc cào thêm đất ở đâu đó lấp vào chổ trũng cũng nhẹ nhàng. Phần đất hớt còn thừa sẽ chuyển vào tôn nền cho nhà thi đấu. Đây là một công việc hết sức vất vả. Ai nhận thi công đoạn nào thì chỉ lấp các khúc trũng trong đoạn đảm nhiệm.

Với tinh thần “Đâu cần thanh niên có, đâu khó có thanh niên” các chi đoàn khối 11 xung phong đảm nhiệm thi công đoạn các khúc liên tục có phần đất dư thừa chuyển đi tôn nền là lớn nhất. Nếu có nhiều đoạn có cùng số đất dư thừa như nhau thì bạn sẽ chọn đoạn có độ dài lớn nhất, tức là nhiều khúc nhất. Nếu có nhiều đoạn cùng độ dài và cùng số đất dư thừa, đoạn trái nhất (có số thứ tự khúc đầu tiên của đoạn nhỏ nhất) sẽ được chọn. Đoàn trường đánh giá rất cao tinh thần của các bạn khối 11 vì vậy bổ sung thêm một quy tắc là nếu mọi khúc đều phải lấp thêm thì các bạn của chúng ta được chọn đoạn dài nhất và trái nhất đòi hỏi tổng số đất lấp thêm là ít nhất. Ví dụ, đường chạy được chia thành 11 khúc với độ cao tương ứng của các khúc là (5, -3, 4, -3, -5, 2, -1, 3, -2, 4, 2) Đoàn viên thanh niên khối 11 sẽ đảm nhiệm đoạn từ khúc 6 đến hết khúc 11 với số lượng đất chuyển đi tôn nền là 8.

Hãy xác định số đất các bạn khối 11 phải chuyển đi tôn nền, số thứ tự của khúc đầu và khúc cuối của đoạn được chọn.

Input:

Dòng đầu tiên chứa một số nguyên n ~(1 ≤ n ≤ 10^6)~,

Dòng thứ 2 chứa n số nguyên ~h_1, h_2, . . ., h_n (|h_i| ≤ 10^9, i = 1 ÷ n)~, các số ghi cách nhau một dấu cách.

Output:

Dòng đầu tiên chứa một số nguyên ans xác định số đất cần xử lý trong đoạn được chọn. ~ans ≥ 0~ chỉ số đất dư thừa cần chuyển đi, ~ans < 0~ – số đất cần lấp thêm, dòng thứ hai chứa 2 số nguyên ghi cách nhau một dấu cách xác định khúc đầu và khúc cuối của đoạn được chọn.

Sample Input

11
5 -3 4 -3 -5 2 -1 3 -2 4 2

Sample Output

8
6 11

Nguồn đê: https://codeforces.com/contest/1391/problem/D

Ma trận nhị phân là ma trận, mà các ô chỉ mang giá trị 0 hoặc 1. Một ma trận nhị phân được gọi là tốt khi tất cả các ma trận vuông con có độ dài chẵn (tức là chiều dọc/ngang), có số lượng lẻ các bit một. Cho một ma trận nhị phân a gồm n hàng và m cột, xác định số lần tối thiểu chỉnh sửa giá trị các ô để làm cho ma trận đã cho trở thành tốt.

Input

Dòng 1: Gồm 2 số nguyên n, m ~(1 ≤ n, m ≤ 10^6, n*m ≤ 10^6 ) ~.

n dòng tiếp theo mỗi dòng i chứa một chuỗi x có độ dài m, kí tự thứ j của x là giá trị của ô a[i,j] trong ma trận

Kết quả

In ra số lần tối thiểu chỉnh sửa giá trị các ô để làm cho ma trận đã cho trở thành tốt, nếu không thể hãy in ra -1.

Sample Input 1

3 3
101
001
110

Sample Output 1

2

Sample Input 2

7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011

Sample Output 2

-1

Nguồn : https://www.spoj.com/problems/CTRICK/ Có một dãy số nguyên gồm n phần tử chỉ gồm các số từ 1 đến n, mỗi số xuất hiện đúng 1 lần. Sắp xếp dãy sao cho sau khi sắp xếp, ta có thể thực hiện như sau.

Với i từ 1 đến n - 1, ta lần lượt chuyển i phần tử đầu về cuối, thì phần tử đầu tiên của dãy sau khi chuyển chính là i, ta loại bỏ số i ra khỏi dãy và tiếp tục

vd : n = 4 ta có thể sắp xếp dãy {1,2,3,4} thành như sau 2 1 4 3

i = 1, ta lần lượt chuyển i = 1 phần tử đầu về cuối dãy 2 1 4 3 => 1 4 3 2 , phần tử đầu của dãy là 1 ( đúng bằng i) ta loại bỏ 1 khỏi dãy, còn lại : 4 3 2

i = 2, ta lần lượt chuyển i = 2 phần tử đầu về cuối dãy 4 3 2 => 3 2 4 => 2 4 3 phần tử đầu của dãy là 2 ( đúng bằng i) ta loại bỏ 2 khỏi dãy, còn lại : 4 3

i = 3, ta lần lượt chuyển i = 3 phần tử đầu về cuối dãy 4 3 => 3 4 => 4 3 => 3 4 phần tử đầu của dãy là 3 ( đúng bằng i) ta loại bỏ 3 khỏi dãy, còn lại : 4

Input

Dòng đầu tiên chứa một số nguyên t - số lương test ~(1 \le t \le 5 )~

t dòng tiếp theo, mỗi dòng chứa một số nguyên n số lượng phần tử của dãy. ~(1 \le n \le 2.10^4 )~

** Tổng các n của t test không vượt quá ~2.10^4~

Output

Với mỗi test in ra n số nguyên trên một dòng -là cách sắp xếp của dãy thỏa mãn yêu cầu đề bài.

Sample Input 1

2
4
5

Sample Output 1

2 1 4 3 
3 1 4 5 2

Nguồn đề : https://www.spoj.com/problems/LPS/ Cho chuỗi s, tìm ra độ dài chuỗi palindrome dài nhất là chuỗi con của s.

Chuỗi con của s là một chuỗi kí tự gồm các kí tự liên tiếp trong s.

Input

Chuỗi s ~( 1 <= len(s) <= 2*10^5 )~

Kết quả

Độ dài chuỗi palindrome dài nhất là chuỗi con của s.

Sample Input

ababa

Sample Output

5

Nguồn đề: https://codeforces.com/contest/1371/problem/A

Hải có n cái gậy, lần lượt có độ dài là 1, 2, 3, ... n . Hải có thể nối các gậy lại với nhau, khi nối 2 gậy có độ dài a và b lại với nhau, Hải có được 1 cái gậy có độ dài là a + b. Khi gắn như vậy Hải không thể dùng 2 gậy cũ nữa thay vào đó Hải có thêm một gậy mới với độ dài a + b vừa tạo được.

Hải muốn tạo được nhiều gậy bằng nhau nhất có thể. Không nhất thiết là tất cả các gậy phải bằng nhau. Đố các bạn Hải có thể tạo được tối đa bao nhiêu cái gậy bằng nhau ?

Input

Dòng 1: t (1 ≤ t ≤ 1000) - số lượng test case. Dòng 1: n ~(1 ≤ n ≤ 10^9)~ - số lượng gậy Hải có.

Output

Với mỗi test case in ra số lượng tối đa các gậy có độ dài bằng nhau mà Hải có thể tạo được.

Sample Input

4
1
2
3
4

Sample Output

1
1
2
2