Contest ôn thi HSG9 và giao lưu lớp 10 Chuyên (lần 2) - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Tên tệp tin	6 (p)	1.0s	256M
2	Tích chính phương	5 (p)	0.5s	1G
3	Phép chia nguyên	3 (p)	1.0s	1G
4	Xâu đối xứng	2 (p)	1.0s	1G

1. Tên tệp tin

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

Bài tập mà Q đang giải có yêu cầu đọc dữ liệu từ tệp văn bản $S$.inp. Do quá vội, Q đã gõ dư một ký tự q vào cuối phần tên tệp. Ví dụ, với tên tệp được yêu cầu là DIV.inp, Q đã gõ nhầm thành DIVq.inp.

Yêu cầu: Cho biết tên tệp tin đã gõ nhầm, hãy tìm lại xâu ký tự $S$.

Input

Đọc từ bàn phím tên tệp văn bản được gõ nhầm (dưới dạng *.inp hoặc *q.inp như đã mô tả ở trên).
Dữ liệu đảm bảo độ dài xâu $S$ không vượt quá $1000$ và chỉ chứa các ký tự trong bảng chữ cái tiếng Anh (a-z và A-Z).

Output

In ra màn hình xâu ký tự $S$ tìm được.

Example

Test 1

Input

DIVq.inp

Output

DIV

Note

Xâu $S$ cần tìm là DIV.

2. Tích chính phương

Điểm: 5 (p) Thời gian: 0.5s Bộ nhớ: 1G Input: SQPROD.inp Output: SQPROD.out

Bạn được cho một số nguyên dương $P$. Tìm hai số nguyên dương $L, D$ sao cho:

$L + D = P$
$L \times D$ là số chính phương.

Input

Đọc từ tệp văn bản SQPROD.inp:
- Dòng đầu tiên gồm một số nguyên dương $T$ ($1 \le T \le 10^4$) là số lượng bộ dữ liệu cần xử lý.
- Tiếp theo là $T$ dòng, mỗi dòng gồm một số nguyên dương $P$ ($1 \le P \le 10^6$).

Output

Ghi ra tệp văn bản SQPROD.out:
- Gồm $T$ dòng, dòng thứ $i$ gồm hai số nguyên dương $L, D$ là kết quả của bộ dữ liệu thứ $i$ nếu tìm được; ngược lại, dòng thứ $i$ gồm hai số -1 -1.

Example

Test 1

Input

Output

1 1
1 4
-1 -1

Note

Trong bộ dữ liệu đầu tiên, ta có $(1, 1)$ là một cặp số thỏa mãn vì $1 + 1 = 2$ và $1 \times 1 = 1 = 1^2$.
Tương tự, trong bộ dữ liệu thứ hai ta có $1 + 4 = 5$ và $1 \times 4 = 4 = 2^2$.

Scoring

$30\%$ số điểm có $P$ là số chẵn.
$20\%$ số điểm khác có $T = 1$.
$20\%$ số điểm khác có $T \le 30$.
$10\%$ số điểm khác có $P \le 1000$.
$10\%$ số điểm khác có $P \le 10^5$.
$10\%$ số điểm còn lại không có giới hạn gì thêm.

3. Phép chia nguyên

Điểm: 3 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: DIV.inp Output: DIV.out

Để giúp các bạn trong lớp ôn lại kiến thức về phép chia lấy dư, thầy giáo của Alice đưa ra một bài toán như sau:

Cho một dãy số nguyên $a_1, a_2, \dots, a_n$, với $a_i \neq 0$. Với mỗi cặp $(i, j)$ ($1 \le i, j \le n$), tính giá trị $\lfloor \frac{a_i}{a_j} \rfloor$, với $\lfloor x \rfloor$ là số nguyên lớn nhất không vượt quá $x$.

Tất nhiên, trong thời gian của tiết học, thầy giáo chỉ có thể đưa ra một dãy số với độ dài nhỏ để kiểm tra kiến thức các bạn. Alice muốn thử thách bản thân với những dãy số dài hơn. Để kiểm tra xem mình có tính đúng hay không, Alice muốn bạn tính tổng các giá trị $\lfloor \frac{a_i}{a_j} \rfloor$ giúp Alice nhé.

Input

Dòng đầu tiên gồm một số nguyên dương $n$ ($1 \le n \le 2 \cdot 10^5$).
Dòng tiếp theo gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 < |a_i| \le 3 \cdot 10^5$).

Output

Một dòng duy nhất là tổng các giá trị $\lfloor \frac{a_i}{a_j} \rfloor$ tìm được.

Ràng buộc bổ sung

20% số điểm có $n \le 2000$ và $a_i > 0$.
20% số điểm khác có $n \le 2000$.
20% số điểm khác có $0 < a_i \le 2000$.
20% số điểm khác có $|a_i| < 2000$.
10% số điểm khác có $a_i > 0$.
10% số điểm còn lại không có giới hạn gì thêm.

Example

Test 1

Input

4
1 2 3 4

Output

Note

Dưới đây là bảng các giá trị $\lfloor \frac{a_i}{a_j} \rfloor$:

	$1$	$2$	$3$	$4$
$1$	$1$	$2$	$3$	$4$
$2$	$0$	$1$	$1$	$2$
$3$	$0$	$0$	$1$	$1$
$4$	$0$	$0$	$0$	$1$

Tổng cần tìm là: $1 + 2 + 3 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17$.

4. Xâu đối xứng

Điểm: 2 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: PALIND.inp Output: PALIND.out

Có $N$ xâu $s_1, s_2, \dots, s_n$ ban đầu rỗng và $Q$ truy vấn. Truy vấn thứ $i$ gồm hai số nguyên $X_i, Y_i$ và ký tự $C_i$, yêu cầu thêm ký tự $C_i$ vào các xâu $s_j$ với mọi $j$ chia $X_i$ dư $Y_i$. Cho biết sau khi tất cả các truy vấn được thực hiện, có những xâu $s_j$ nào thỏa mãn: tồn tại cách sắp xếp lại các ký tự trong xâu để được một xâu đối xứng.

Input

Dòng đầu tiên gồm hai số nguyên dương $N, Q$ ($1 \le N, Q \le 2 \cdot 10^5$).
$Q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $X_i, Y_i$ và một ký tự $C_i$ thuộc bảng chữ cái tiếng Anh ($0 \le Y_i < X_i \le n$).

Output

Ghi ra tệp văn bản PALIND.out một dòng duy nhất gồm các giá trị $j$ thỏa mãn theo thứ tự tăng dần.

Example

Test 1

Input

Output

1 2 3 4 5

Note

Các ký tự được thêm vào như sau:

	1	2	3	4
$s_1$	a
$s_2$		b	a	b
$s_3$	a
$s_4$		b
$s_5$	a		a

Sau khi tất cả các ký tự đã được thêm, $s_1$ và $s_3$ có thể được sắp xếp thành a, $s_2$ có thể được sắp xếp thành bab, $s_4$ có thể được sắp xếp thành b, $s_5$ có thể được sắp xếp thành aa.

Scoring

$12\%$ số điểm có $c_i = $ a với mọi truy vấn.
$42\%$ số điểm khác có $n, m \le 2000$.
$18\%$ số điểm khác có $c_i = $ a hoặc $c_i = $ b với mọi truy vấn.
$28\%$ số điểm còn lại không có giới hạn gì thêm.

	\(1\)	\(2\)	\(3\)	\(4\)
\(1\)	\(1\)	\(2\)	\(3\)	\(4\)
\(2\)	\(0\)	\(1\)	\(1\)	\(2\)
\(3\)	\(0\)	\(0\)	\(1\)	\(1\)
\(4\)	\(0\)	\(0\)	\(0\)	\(1\)

	1	2	3	4
\(s_1\)	a
\(s_2\)		b	a	b
\(s_3\)	a
\(s_4\)		b
\(s_5\)	a		a