Tin học trẻ toàn quốc - Sơ loại 2021 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Cặp số đồng đội (THTB Vòng Sơ loại)	100 (p)	1.0s	1G
2	Ước số (THTB Vòng Sơ loại)	100 (p)	1.0s	1G
3	Cân đĩa (THTB Vòng Sơ loại)	100 (p)	1.0s	1G
4	Tọa độ nguyên dương (LQD'20)	50 (p)	1.0s	256M
5	CSES - Grid Paths \| Đường đi trên lưới	50 (p)	1.0s	512M
6	Sinh nhị phân	25 (p)	1.0s	977M
7	Chia Bò Sữa	25 (p)	2.0s	256M

1. Cặp số đồng đội (THTB Vòng Sơ loại)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Kì thi Tin học trẻ là một trong những kì thi lớn dành cho học sinh phổ thông Việt Nam. Để tổ chức
thành công kì thi Tin học trẻ, ngoài Ban tổ chức kì thi thì Hội đồng Ban giám khảo đóng vai trò rất
quan trọng. Thầy Nguyễn Vũ Hoàng Vương là một thầy giáo trẻ nhưng đã tham gia Hội đồng Ban
giám khảo nhiều năm nay. Nhắc đến thầy Vương, Ban giám khảo đều nhớ về một đồng đội xuất sắc
và chân thành. Một bài toán số học lấy cảm hứng từ đồng đội được dùng làm đề thi Tin học trẻ năm
nay như sau:

Một cặp số nguyên dương $(a, b)$ mà $a$ chia hết cho $b$ hoặc $b$ chia hết cho $a$ được gọi là cặp số đồng
đội. Cặp số đồng đội $(a, b)$ và cặp số đồng đội $(u, v)$ được gọi là giống nhau khi $a = u$ và $b = v$.

Yêu cầu: Cho số nguyên dương $N(2 \le N \le 10^9)$, hãy đếm số cặp số đồng đội mà $a + b = N$.

Input

Vào từ thiết bị vào chuẩn gồm một số nguyên dương $N$ duy nhất.

Output

Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là số cặp số đồng đội thoả mãn.

Scoring

Subtask $1$ ($50\%$ số điểm): $N \le 10^3$;
Subtask $2$ ($30\%$ số điểm): $N \le 10^6$;
Subtask $3$ ($20\%$ số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input

Output

Note

Các cặp số đồng đội thỏa mãn:

(1, 9), (2, 8),
(5, 5), (8, 2), (9, 1)

2. Ước số (THTB Vòng Sơ loại)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Một số nguyên dương $n$ được phân tích thành thừa số nguyên tố như sau:

$n = p_1^{k_1} × p_2^{k_2} × ... × p_m^{k_m}$

Yêu cầu: Cho hai số nguyên không âm $A \le B$, đếm số lượng ước của $n$ trong đoạn $[A, B]$.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

Dòng đầu chứa số nguyên dương $m$;
Tiếp theo là $m$ dòng, dòng thứ $i$ chứa hai số nguyên dương $p_i$ và $k_i$, trong đó $p_i$, $k_i$ không vượt quá $10^9$ và các số $p_i$ là số nguyên tố đôi một khác nhau;
Ba dòng cuối tương ứng với ba câu hỏi, mỗi dòng chứa hai số nguyên không âm $A, B$ tương
ứng với một câu hỏi.

Output

Ghi ra thiết bị ra chuẩn ba dòng, mỗi dòng ghi ước số tìm được trả lời cho câu hỏi tương
ứng ở dữ liệu vào.

Scoring

Subtask $1$ (%40\%$ số điểm): $m \le 5; 0 \le A \le B \le 10^6$;
Subtask $2$ (%40\%$ số điểm): $m \le 10; 0 \le A \le B \le 10^9$;
Subtask $3$ (%20\%$ số điểm): $m \le 25; 0 \le A \le B \le 10^9$

Example

Test 1

Input

Output

5
9
5

3. Cân đĩa (THTB Vòng Sơ loại)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một cân hai đĩa và $n$ quả cân có khối lượng đôi một khác nhau $w_1, w_2, . . , w_n$. Tiến hành đặt lần
lượt từng quả cân lên một trong hai đĩa của cân và đảm bảo rằng tổng khối lượng bên trái luôn nhỏ
hơn hoặc bằng tổng khối lượng bên phải.

Yêu cầu: Cho $n$ quả cân có khối lượng $w_1, w_2, . . , w_n$, hãy đếm số cách xếp $n$ quả cân thỏa mãn.

Hai cách được gọi là khác nhau nếu thứ tự xếp các quả cân khác nhau hoặc tồn tại một quả cân nằm
ở đĩa khác nhau.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

Dòng 1: chứa số nguyên $n$;
Dòng 2: chứa $n$ số nguyên dương $w_1, w_2, . . , w_n$.

Output

Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số cách xếp $n$ quả cân lên đĩa.

Scoring

Subtask $1$ ($40\%$ số điểm): $n \le 7$ và $w_i \le 1000 (1 \le i \le n)$;
Subtask $2$ ($40\%$ số điểm): $n \le 14$ và $w_i \le 1000 (1 \le i \le n)$;
Subtask $3$ ($20\%$ số điểm): $n \le 28$ và $w_i = 2^{i−1} (1 \le i \le n)$.

Example

Test 1

Input

2
1 2

Output

Note

Ở ví dụ bên trái, có 8 cách sắp xếp các quả cân lên hai bàn cân như sau:

Đặt quả cân 1 bên trái rồi đặt quả cân 2 bên trái;
Đặt quả cân 1 bên trái rồi đặt quả cân 2 bên phải;
Đặt quả cân 1 bên phải rồi đặt quả cân 2 bên trái;
Đặt quả cân 1 bên phải rồi đặt quả cân 2 bên phải;
Đặt quả cân 2 bên trái rồi đặt quả cân 1 bên trái;
Đặt quả cân 2 bên trái rồi đặt quả cân 1 bên phải;
Đặt quả cân 2 bên phải rồi đặt quả cân 1 bên trái;
Đặt quả cân 2 bên phải rồi đặt quả cân 1 bên phải.
Tuy nhiên chỉ có 3 cách (cách 4, 7, 😎 là đảm bảo trong toàn bộ quá trình sắp xếp các quả cân,
đĩa bên trái luôn nhỏ hơn hoặc bằng đĩa cân bên phải.

Test 2

Input

3
10 11 12

Output

4. Tọa độ nguyên dương (LQD'20)

Điểm: 50 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trên mặt phàng tọa độ $Oxy$, cho 2 điểm $A(m;n)$ và $B(p;q)$. Vẽ đoạn thẳng $AB$.

Yêu cầu: Hãy xác định có bao nhiêu điểm có hoành độ và tung độ là các số nguyên dương thuộc đoạn thẳng $AB$ (không kể 2 mút của đoạn thẳng $AB$).

Dữ liệu

Một dòng chứa 4 số nguyên dương $m, n, p, q$ nằm trên một dòng ($m < p; n > q$) mỗi số cách nhau 1 dấu cách. Trong đó $m$ và $n$ lần lượt là hoành độ và tung độ của điểm $A$; $p$ và $q$ lần lượt là hoành độ và tung độ của điểm $B$.

Kết quả:

Ghi ra một số $k$ là số các điểm có tọa độ là các số nguyên dương theo yêu cầu trên.

Sample input

1 6 7 3

Sample output

Sample input

2 8 4 1

Sample output

Giới hạn: $m, n, p, q < 10^9$

Nguồn: TS10LQD 2020

5. CSES - Grid Paths | Đường đi trên lưới

Điểm: 50 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có tất cả $88418$ đường đi trên một lưới ô vuông $7 \times 7$ từ ô ở góc trái, bên trên xuống ô góc trái, bên dưới. Mỗi đường đi tương ứng với một xâu mô tả gồm $48$ kí tự, bao gồm các kí tự D (xuống), U (lên), L (trái), R (phải).

Ví dụ, đường đi

tương ứng với xâu DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

Bạn được cho trước một xâu mô tả đường đi, mà trong đó có chứa cả kí tự ? (đi hướng nào cũng được). Nhiệm vụ của bạn là tính số lượng đường đi khớp với xâu mô tả này.

Input

Dòng đầu vào duy nhất có một xâu $48$ ký tự gồm các ký tự ?, D, U, L và R.

Output

In ra một số nguyên: tổng số đường đi.

Example

Test 1

Input

??????R??????U??????????????????????????LD????D?

Output

6. Sinh nhị phân

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 977M Input: bàn phím Output: màn hình

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

Test 1

Input

Output

7. Chia Bò Sữa

Điểm: 25 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

5
2 1 2 1 2

Output

Test 2

Input

5
2 1 2 1 8

Output

-1

Test 3

Input

5
1 5 1 3 4

Output

11122
22211