Vòng Chung kết Tin học trẻ 2021 Bảng B và C - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Sắp xếp (THTB TQ 2021)	100 (p)	1.0s	1G
2	Bài tập (THT B&C TQ 2021)	100 (p)	1.0s	1G
3	Bài khó (THT B&C TQ 2021)	100 (p)	1.0s	1G
4	Thử nghiệm Robot (THTB TQ 2021)	100 (p)	1.0s	1G
5	Xâu con (THTC Vòng Chung kết)	100 (p)	1.0s	1G
6	Cắt bánh (THTC Vòng Chung kết)	100 (p)	1.0s	1G

1. Sắp xếp (THTB TQ 2021)

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

Xâu $x$ được gọi là lớn hơn xâu $y$ nếu xâu $y$ là đoạn đầu của xâu $x$ hoặc xét kí tự đầu tiên khác nhau thì kí tự của xâu $x$ lớn hơn kí tự của xâu $y$.

Để luyện tập về việc so sánh hai xâu, Hồng đã tạo ra bài toán sau: Từ hai số nguyên dương $a,b (a < b)$, tạo ra một dãy số gồm $b - a + 1$ số: $a, a + 1, ... , b$. Sau đó, sắp xếp lại các số theo thứ tự từ điển (coi mỗi số là một xâu và sắp xếp tăng dần) bằng các thao tác như sau: Mỗi lần chọn
và lấy ra một số trong dãy rồi chèn lại vào dãy ở vị trí bất kì.

Ví dụ, nếu $a = 9, b = 11$ ta có dãy số gồm $3$ số $9, 10, 11$, dãy số được sắp xếp theo thứ tự từ điển là $10, 11, 9$ và cần ít nhất một thao tác (rút số $9$ khỏi dãy và chèn vào cuối dãy).

Yêu cầu: Cho hai số nguyên dương $a, b (a < b)$, hãy tính số thao tác ít nhất để sắp xếp các số $a, a + 1, ... , b$ theo thứ tự từ điển.

Input

Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương $a, b (a < b \le 10^9)$

Output

Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên là số thao tác ít nhất để sắp xếp các số $a, a + 1, ... , b$ theo thứ tự từ điển.

Scoring

Subtask $1$ ($20\%$ số điểm): $b - a = 1$;
Subtask $2$ ($20\%$ số điểm): $b - a \le 10$;
Subtask $3$ ($30\%$ số điểm): $b − a \le 1000$;
Subtask $4$ ($30\%$ số điểm): $b − a \le 10^5$;

Example

Test 1

Input

9 11

Output

2. Bài tập (THT B&C TQ 2021)

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

Hồng đã soạn được $n$ bài tập Tin học, bài thứ ݅$i(1 \le i \le ݊n)$ có độ khó là số nguyên dương $c_i$. Hồng được cô giáo yêu cầu gửi $m$ bài tập lên hệ thống luyện tập trực tuyến để tập huấn cho một nhóm các em học sinh khóa dưới. Nếu $m < n$, khi đó, Hồng phải loại bỏ $n - m$ bài tập, ngược lại nếu $m > n$ thì Hồng phải soạn thêm $m - n$ bài tập với độ khó là số nguyên dương. Khi đưa lên hệ thống $m$ bài tập, Hồng sẽ sắp xếp các bài theo độ khó tăng dần, gọi $d$ là chênh lệch độ khó lớn nhất của hai bài tập liên tiếp. Hồng mong muốn giá trị $d$ nhỏ nhất có thể.

Yêu cầu: Cho $n$ bài tập với độ khó là ܿ$c_1, c_2, ..., c_n$ và số $m$, hãy tìm giá trị $d$ nhỏ nhất.

Input

Vào từ thiết bị vào chuẩn:

Dòng đầu gồm hai số nguyên dương ݊$n, m (2 \le m, n \le 10^5; m \ne n)$;
Dòng thứ hai gồm ݊ số nguyên dương $c_1, c_2, ..., c_n$ $(c_i \le 10^9, 1 \le i \le n)$.

Output

Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên $d$ tìm được.

Example

Test 1

Input

5 4
8 5 9 10 10

Output

Test 1

Input

3 4
8 6 9

Output

3. Bài khó (THT B&C TQ 2021)

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

Một bài toán khó trong danh sách các bài mà Hồng lựa chọn để tập huấn cho các em học sinh khóa
dưới như sau:

Cho hai số nguyên dương $n, t$,cần tìm một bộ gồm ít số nguyên dương nhất, giả sử bộ tìm được gồm $k$ số nguyên dương $a_1, a_2,..., a_k$ thì:

\[(a_1 + t)\times (a_2 + t) \times...\times(a_k + t) = n\times a_1 \times a_2 \times...\times a_k.\]

Yêu cầu: Cho $2$ số nguyên dương $n, t$, hãy tìm số nguyên dương $k$ thoả mãn.

Input

Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên $n, t (n, t \le 1000)$

Output

Ghi ra thiết bị ra chuẩn gồm một dòng chứa số nguyên $k$ là số lượng số ít nhất để tồn tại bộ gồm $k$ số nguyên dương thoả mãn, nếu không tồn tại ghi số $-1$.

Example

Test 1

Input

4 1

Output

4. Thử nghiệm Robot (THTB TQ 2021)

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

Công ty HP vừa thiết kế một loại robot thông minh mới. Để đánh giá khả năng tự vận hành của robot, người ta tạo ra một bức tường từ ݊ cột các khối lập phương, các cột đặt cạnh nhau, bề dày bức tường là 1, độ cao cột thứ $i$ là ܽ$a_i$ (do ܽ$a_i$ khối lập phương tạo lên). Có ݉$m$ robot tham gia thử nghiệm. Trước tiên người ta chia ݊$n$ cột thành ݉$m$ đoạn bằng ݉$m − 1$ điểm cắt ݇$k_1, ݇k_2, . . , ݇k_{m-1} (݇k_0 = 0 < k_1 < ... < ݇k_{m-1} < k_m = n)$. Robot thứ ݅ được giao nhiệm vụ xếp lại đoạn từ cột ݇$k_{i-1} + 1$ đến cột ݇$k_i$ sao cho các cột trong đoạn có độ cao bằng nhau. Robot chỉ có thể thực hiện một trong hai loại thao tác, mỗi thao tác mất 1 đơn vị thời gian.

Thao tác 1: Lấy khối trên cùng của một cột trong đoạn được giao để bỏ đi;
Thao tác 2: Lấy một khối mới, đặt khối đó lên trên cùng của một cột trong đoạn được giao.

Thời gian kết thúc thử nghiệm là thời gian mà robot cuối cùng hoàn thành xong nhiệm vụ.

Yêu cầu: Cho $a_1, a_2, ..., a_n$ và ݉$m$. Hãy tìm $m− 1$ điểm cắt để chia cột thành ݉$m$ đoạn sao cho thời gian thử nghiệm là nhanh nhất, biết các robot đều thực hiện các thao tác tối ưu.

Input

Vào từ thiết bị nhập chuẩn:

Dòng đầu chứa hai số nguyên $n, m$;
Dòng thứ hai gồm ݊$n$ số nguyên không âm $a_1, a_2, ..., a_n (a_i \le 10^6)$

Output

Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là thời gian ít nhất để thử nghiệm.

Scoring

Subtask $1$ ($25\%$ số điểm): $m = 1; n \le 10$;
Subtask $2$ ($25\%$ số điểm): $m = 2; n \le 1000$;
Subtask $3$ ($25\%$ số điểm): ݉$m \le n; n \le 100$;
Subtask $4$ ($25\%$ số điểm): ݉$m\le n; n \le 1000$.

Example

Test 1

Input

6 2
1 1 2 3 4 3

Output

5. Xâu con (THTC Vòng Chung kết)

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

Xét xâu $S$ là một xâu chỉ gồm các kí tự in hoa. Một xâu con của xâu $S$ là xâu thu được khi xoá một số kí tự (hoặc có thể là không xóa kí tự nào) khỏi xâu $S$ và giữ nguyên thứ tự các kí tự còn lại. Ví dụ, xâu ABC có các xâu con là A, AC, BC, ABC nhưng BA hay CAB không phải là xâu con của xâu ABC. Dễ thấy, xâu $S$ độ dài $N$ sẽ có $2^N - 1$ xâu con không rỗng.

Để đánh giá độ lặp lại của các xâu con này, Hồng định nghĩa hàm $f$:

\[f(S) = \sum_{s \in w(S)} r(s)^2 \cdot |s|\]

trong đó $w(S)$ là tập các xâu con khác rỗng của $S$, $r(s)$ là số lần lặp của $s$, $|s|$ là độ dài xâu $s$.

Ví dụ xét $S = $ ABAB, các xâu con của $S$ bao gồm A (2 lần), B (2 lần), AB (3 lần) và AA, BB, BA, AAB, ABB, ABA, BAB, ABAB mỗi xâu xuất hiện 1 lần. Khi đó:

\[ \begin{aligned} f(S) &= 2^2 \cdot 1 + 2^2 \cdot 1 + 3^2 \cdot 2 \\ &\quad + 1^2 \cdot 2 + 1^2 \cdot 2 + 1^2 \cdot 2 \\ &\quad + 1^2 \cdot 3 + 1^2 \cdot 3 + 1^2 \cdot 3 + 1^2 \cdot 3 + 1^2 \cdot 4 = 48 \end{aligned} \]

Yêu cầu: Cho xâu $S$, hãy tính $f(S)$. Vì $f(S)$ có thể rất lớn, Hồng cần đưa ra $f(S) \pmod{10^9 + 7}$, trong đó $\%$ là phép chia lấy dư.

Input

Gồm một dòng chứa xâu $S$ chỉ gồm kí tự in hoa có độ dài không quá $200$.

Output

Ghi ra một dòng chứa một số nguyên là giá trị $f(S) \pmod{10^9 + 7}$.

Example

Test 1

Input

ABAB

Output

Ràng buộc

Có $20\%$ số test ứng với $20\%$ số điểm của bài thỏa mãn: $|S| \le 20$.
Có $15\%$ số test khác ứng với $15\%$ số điểm của bài thỏa mãn: $S$ gồm các kí tự giống nhau.
Có $30\%$ số test khác ứng với $30\%$ số điểm của bài thỏa mãn: $s_i \le s_j$ nếu $i < j$.
Có $35\%$ số test còn lại ứng với $35\%$ số điểm của bài thỏa mãn: $|S| \le 200$.

6. Cắt bánh (THTC Vòng Chung kết)

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

Vào ngày nhà giáo Việt Nam 20.11 năm nay, Hồng đã làm một chiếc bánh để chúc mừng mẹ. Chiếc bánh có dạng là một hình đa giác đều gồm $n$ đỉnh, các đỉnh được đánh số từ $1$ đến $n$ theo chiều kim đồng hồ. Sau khi chúc mừng mẹ, em Phúc đề xuất cắt bánh bằng $m$ lần cắt bánh, lần cắt thứ $k$ đi qua hai đỉnh phân biệt $i_k, j_k$ ($1 \le k \le m$) và đố mọi người có bao nhiêu miếng bánh sau khi cắt.

Yêu cầu: Cho biết các lần cắt bánh, hãy đếm số miếng bánh sau khi thực hiện $m$ lần cắt bánh.

Input

Dòng đầu chứa hai số nguyên $n, m$ ($n \le 50$).
Dòng thứ $k$ ($1 \le k \le m$) chứa hai số nguyên $i_k, j_k$ mô tả lần cắt thứ $k$ ($1 \le i_k, j_k \le n$ và $i_k \neq j_k$).

Output

Ghi ra một dòng chứa một số nguyên là số miếng bánh sau khi thực hiện $m$ lần cắt bánh.

Example

Test 1

Input

4 1
1 3

Output

Note

Có $30\%$ số lượng test ứng với $30\%$ số điểm mà ba đường cắt bất kì không cắt nhau tại một điểm bên trong chiếc bánh.