Bài tập

Cho dãy gồm \(n\) số nguyên. Hãy đếm xem trong dãy có bao nhiêu số dương và bao nhiêu số âm (số \(0\) không thuộc loại nào).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên, cách nhau bởi dấu cách.

Output

Gồm hai dòng, đúng theo định dạng sau:

• Dòng thứ nhất: SO DUONG: theo sau là số lượng số dương.
• Dòng thứ hai: SO AM: theo sau là số lượng số âm.

Constraints

• \(1 \le n \le 1000\)
• \(|a_i| \le 10^9\)

Sample Input 1

6
4 0 -7 9 -1 -1

Sample Output 1

SO DUONG: 2
SO AM: 3

Cho một xâu \(S\) độ dài \(N\) chỉ gồm hai loại ký tự A và B. Hãy đếm số đoạn con liên tiếp của \(S\) (tính theo vị trí bắt đầu và kết thúc, hai đoạn ở vị trí khác nhau được tính là khác nhau) thỏa mãn đồng thời:

• Độ dài \(L\) của đoạn thỏa \(1 \le L \le M\);
• Trong đoạn có đúng \(K\) ký tự A.

Input

• Dòng 1: ba số nguyên \(N\), \(M\), \(K\).
• Dòng 2: xâu \(S\) gồm \(N\) ký tự.

Output

• In ra một số nguyên là số đoạn con thỏa mãn.

Constraints

• \(1 \le N < 255\)
• \(1 \le K \le M \le 14\)

Sample Input

10 4 2
BAABABAAAB

Sample Output

12

Chủ trại có \(N\) con trâu, con thứ \(i\) cày được đúng \(a_i\) đơn vị diện tích. Hãy đếm số cách chọn một tập con các con trâu có tổng diện tích cày được đúng bằng \(S\). Hai tập được xem là khác nhau nếu có một con trâu thuộc tập này mà không thuộc tập kia (các con trâu được phân biệt theo chỉ số, kể cả khi \(a_i\) bằng nhau). Đồng thời hãy cho biết số con trâu ít nhất trong một tập như vậy.

Input

• Dòng 1: hai số nguyên \(N\) và \(S\).
• Dòng 2: \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• Nếu không có cách chọn nào, in KHONG CHON DUOC.
• Ngược lại in hai số cách nhau một dấu cách: số cách chọn và số con trâu ít nhất của một cách chọn.

Constraints

• \(1 \le N \le 32\)
• \(1 \le S \le 3.2 \times 10^{10}\)
• \(1 \le a_i \le 10^9\)

Sample Input 1

6 7
1 2 3 4 5 6

Sample Output 1

4 2

Sample Input 2

5 100
3 8 20 5 9

Sample Output 2

KHONG CHON DUOC

Explanation

Ở ví dụ 1 có 4 tập: \(\{1,6\}\), \(\{2,5\}\), \(\{3,4\}\), \(\{1,2,4\}\); tập nhỏ nhất có 2 con.

Cho số nguyên dương \(K\) và \(m\) số nguyên dương \(a_1, a_2, \dots, a_m\). Đếm xem trong các số \(1, 2, \dots, K\) có bao nhiêu số chia hết cho ít nhất một trong các số \(a_i\).

Input

• Dòng đầu chứa hai số nguyên \(K\) và \(m\).
• Dòng thứ hai chứa \(m\) số nguyên \(a_1, \dots, a_m\).

Output

In ra một số nguyên là đáp số.

Constraints

• \(1 \le K \le 10^9\), \(1 \le m \le 15\).
• \(1 \le a_i \le 10^9\).

Sample Input

30 3
4 6 10

Sample Output

11

Explanation

Có \(7\) bội của \(4\), \(5\) bội của \(6\), \(3\) bội của \(10\); trừ đi các số bị đếm hai lần (\(12\) và \(24\); \(20\); \(30\)) ta được \(7+5+3-2-1-1 = 11\).