Đệ Quy Quay Lui

Tính tổng \(n\) số nguyên dương đầu tiên.

Dữ liệu

• Số test \(t (t \le 10)\)
• \(t\) dòng, mỗi dòng 1 số nguyên không âm \(n (n \le 10^5)\)

Kết quả

• \(t\) dòng, \(1 + 2 + ... + n\)

Sample Input

3
5
6 
10

Sample Output

15
21
55

Tính \(n! = 1 \times 2 \times 3 \times \dots \times n\).

Input

• Số test \(t (t \le 100)\)
• \(t\) dòng, mỗi dòng 1 số nguyên không âm \(n (n \le 20)\)

Output

• \(t\) dòng, \(n!\)

Example

3
2 
3
4 

2
6
24

\(F_1 = F_2=1\)

\(F_n=F_{n-1}+F_{n-2}\) với \(n > 2\)

Tính \(F_n\)

Input

• Số test \(t (t \le 5)\)
• \(t\) dòng, mỗi dòng 1 số nguyên dương \(n (n \le 50)\)

Output

• \(t\) dòng, \(F_n\)

Example

3
1
2
3 

1
1
2

Kiến đang ở ô \((1,1)\) và muốn đi đến ô \((n,m)\).

Biết rằng nếu kiến đang ở ô \((x,y)\) thì kiến có thể đi đến \(1\) trong \(2\) ô \((x + 1,y)\) và \((x,y+1)\).

Tính số đường đi kiến có thể đi đến ô \((n,m)\)

Dữ liệu

• \(n,m (1 \le n,m \le 6)\)

Kết quả

• Số đường đi

Sample Input

2 2

Sample Output

2

Cho hai số nguyên dương \(a\) và \(b\) (\(a, b \leq 2.000.000.000\)).

Yêu cầu: Hãy viết chương trình tìm ước chung lớn nhất (UCLN), bội chung nhỏ nhất (BCNN) của hai số \(a\) và \(b\).

Input

• Chứa số nguyên dương \(a\) và \(b\).

Output

• Chứa hai số UCLN, BCNN.

Example

6 8

2 24

Viết chương trình nhập vào một số nguyên dương \(n\) (\(n \leq 1.000.000.000.000.000\)).

Hãy in ra các yêu cầu sau:

• Số chữ số của \(n\),
• Tổng các chữ số của \(n\).

Input

• Nhập số nguyên dương \(n\).

Output

• Dòng 1 in ra số chữ số của \(n\).
• Dòng 2 in ra tổng các chữ số của \(n\).

Example

4326 

4    
15

Cho hai số nguyên \(x\) và \(n\), hãy tính lũy thừa \(x^n\).

Input

• Là hai số nguyên \(x\) và \(n\) cách nhau một khoảng trắng (\(1 \le x \le 1000, 1 \le n \le 10^{18}\))

Output

• Là 4 số cuối của lũy thừa \(x^n\) (\(x^n \mod\ 10^4\))

Example

2 3

8

3 2

9

Đất nước Văn Lang thời cổ xưa đã có những hiểu biết tân tiến về số học. Tương truyền rằng, vua Hùng Vương thứ \(17\) cùng các trưởng lão trong triều đình đã phát minh ra các số huyền bí. Các số này giúp chỉ dẫn đường vào kho tàng của đất nước. Theo các chứng tích khảo cổ, các nhà khoa học kết luận rằng số huyền bí cơ sở \(a\) bằng tích của (\(3^{d}−1\)) với mọi ước số \(d>0\) của \(a\).

Bờm thích số học đồng thời cũng rất thích tìm hiểu lịch sử đất nước. Bạn hãy giúp Bờm tính số huyền bí cơ sở \(a\) (\(1 \leq a \leq 10^{9}\)). Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số huyền bí cơ sở a khi chia cho \(20122007\).

Input

• Gồm một số nguyên \(a\) duy nhất.

Output

• In ra số nguyên duy nhất là phần dư của số huyền bí cơ sở \(a\) khi chia cho \(20122007\).

Constraints

• \(1 \leq a \leq 10^{9}\)

Example

10 

7291779

Sinh xâu nhị phân độ dài \(n\).

Yêu cầu: Cho \(n\) hẫy in tất cả các xâu nhị phân theo thứ tự từ điển.

Input

• Số nguyên dương \(n (n \leq 12)\).

Output

• Tất cả các xâu nhị phân theo thứ tự từ điển.

Example

3 

000
001
010
011
100
101
110
111

Cho một dãy số nguyên dương gồm \(N\) phần tử và một số nguyên \(K\). Hãy đếm số lượng dãy con có tổng bằng \(K\).

Một dãy số \(A\) được gọi là dãy con của dãy số \(B\), nếu \(B\) loại bỏ một số phần tử thì thu được \(A\).

VD: \(\{1, 3\}\) là dãy con của \(\{1, 2, 3\}\), còn \(\{2, 1\}\) không phải dãy con của \(\{1, 2, 3\}\).

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(N, K\).
• Dòng thứ 2 gồm \(N\) số nguyên dương \(A_i\).

Output

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

Example

3 2
1 2 1

2

Constraints

Trong tất cả test, ta có:

• \(N \le 20\)
• \(1 \le K, A_i \le 100\)

Nguồn: 2019 CHY

Con người có 4 loại ADN: A, X, T, G. Giả sử đoạn gien quy định màu da của con người là một chuỗi N ADN kết hợp từ 4 loại ADN trên (1 ≤ N≤ 20). Ví dụ một đoạn gien có 8 ADN là: AATXGGGT. Các ADN trong đoạn gien được đánh số từ 1 đến N.

Đoạn gien quy định màu da của thế hệ con cũng là một đoạn N ADN kết hợp từ gien của bố và gien của mẹ. Trong đó ADN thứ i (1≤ i ≤ N) được hình thành bằng cách lấy ADN thứ i tương ứng của gien bố hoặc gien mẹ. Ví dụ:

• Gien của bố: AATX

• Gien của mệ: GATT

• Gien của con chỉ có thể là 4 trường hợp sau: AATX, AATT, GATX, GATT.

Yêu cầu: Cho trước gien của bố và gien của mẹ, bạn hãy viết chương trình liệt kê các khả năng có thể xảy ra của gien thế hệ con.

Dữ liệu vào:

• Dòng thứ nhất: là số N biểu thị số ADN trong đoạn gien của bố và mẹ. (1 ≤ N≤ 20)

• Dòng thứ hai: đoạn gien của bố.

• Dòng thứ ba: đoạn gien của mẹ (hai đoạn gien này có chiều dài bằng N và chỉ gồm các ký tự A, X, T G)

Dữ liệu ra:

• Ghi số K là tổng số khả năng có thể xảy ra của đoạn gien thế hệ con.

Input

2
AT
GX

Output

4

Input

3
AXT
GXA

Output

4

Trải qua kì thi quan trọng xong, Sắn về quê bắt tay làm kinh doanh với mảnh đất quê hương. Sắn bắt đầu làm nông trại với \(N\) chú bò sữa. Chú bò thứ \(i\) sản xuất \(a_i\) đơn vị sữa mỗi ngày.

Mỗi sáng sớm Sắn lùa lũ bò ra đồng cỏ để ăn những ngọn cỏ ngon nhất, tối Sắn lại lùa bò về chuồng. Lần này Sắn nâng cấp máy và mua thêm một máy nữa. Bây giờ Sắn có hai máy vắt sữa phục vụ để vắt hết \(N\) chú bò. Để đảm bảo công suất hoạt động của hai máy vắt sữa, mỗi lần vắt Sắn sẽ chia đều \(N\) chú bò vào hai máy sao cho lượng sữa hai máy vắt được tương đương nhau. Bạn hãy liệt kê cho Sắn biết tất cả cách sắp \(N\) chú bò vào hai máy để đạt được điều này.

Input

• Dòng thứ nhất chứa 1 số nguyên \(N\) \((1 \leq N \leq 20)\)
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots a_N (1 \leq a_i \leq 10^9)\), là sản lượng sữa của \(N\) chú bò.

Output

• Nếu không có cách nào thỏa mãn, hãy in ra \(-1\).
• Ngược lại hãy in ra mỗi đáp án trên 1 dòng riêng: Mỗi cách gồm \(N\) số nguyên \(x_1,x_2, \dots x_N, (x_i \in \{1,2\})\), là máy mà chú bò thứ \(i\) được phân vào. Các cách được in theo thứ tự từ điển.

Example

5
2 1 2 1 2 

11212
12122
12221
21112
21211
22121

5
2 1 2 1 8 

-1

5
1 5 1 3 4 

11122
22211

Sinh các hoán vị của các số tự nhiên từ \(1\) đến \(n\).

Yêu cầu: Cho \(n\) hãy in tất cả các hoán vị của \(n\) số tự nhiên đầu tiên theo thứ tự từ điển.

Input

• Số nguyên dương \(n (n \leq 9)\).

Output

• Tất cả các hoán vị của \(n\) số tự nhiên đầu tiên theo thứ tự từ điển.

Example

3 

123
132
213
231
312
321

Một vòng tròn chứa \(2n\) vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ \(1\) đến \(2n\) theo chiều kim đồng hồ. Cần điền các số tự nhiên từ \(1\) đến \(2n\) mỗi số vào một vòng tròn nhỏ sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ \(1\) luôn là số \(1\).

Dữ liệu:

• Một dòng chứa số nguyên dương \(n (1 < n < 10)\)

Kết quả:

• Một dòng ghi số lượng các cách điền số tìm được (\(k\)).

Sample Input

3

Sample Output

2

Sample Input

4

Sample Output

4

Giải thích:

• Ví dụ 1:

\({1, 4, 3, 2, 5, 6}\)

\({1, 6, 5, 2, 3, 4}\)

• Ví dụ 2:

\({1, 2, 3, 8, 5, 6, 7, 4}\)

\({1, 2, 5, 8, 3, 4, 7, 6}\)

\({1, 4, 7, 6, 5, 8, 3, 2}\)

\({1, 6, 7, 4, 3, 8, 5, 2}\)