Contest giao lưu Tin học trẻ 2024 - Lần thứ Ba (Bảng C1) - Bộ đề bài

1. Giao lưu THT 2024 lần 3 - Bài C bảng B1 & C2, Bài A bảng C1

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

Cho hai số nguyên dương $n, k$. Hãy tính giá trị của biểu thức:

$S = \lceil \frac{n}{1} \rceil + \lceil \frac{n}{2} \rceil + \lceil \frac{n}{3} \rceil + \cdots + \lceil \frac{n}{k-1} \rceil + \lceil \frac{n}{k} \rceil$

Ở đây, $\lceil x \rceil$ là số nguyên nhỏ nhất không nhỏ hơn $x$.

Input

Một dòng chứa $2$ số nguyên dương $n, k$ $(1 \le k \le n \le 10^{12})$

Output

Giá trị của biểu thức $S$.

Scoring

Subtask $1$ ($50\%$ số điểm): $n \le 10^6$.
Subtask $2$ ($50\%$ số điểm): $n \le 10^{12}$.

Example

Test 1

Input

2 2

Output

Giải thích

$S=\lceil \frac{2}{1} \rceil + \lceil \frac{2}{2} \rceil = 2 + 1 = 3$.

Test 2

Input

5 3

Output

Giải thích

$S = \lceil \frac{5}{1} \rceil + \lceil \frac{5}{2} \rceil + \lceil \frac{5}{3} \rceil=5+3+2=10.$

2. Giao lưu THT 2024 lần 3 - Bài D bảng B1 & C2, Bài B bảng C1

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

Cho bàn cờ vua $n \times m$ ô. Đếm số cách đặt các quân mã (số lượng tùy ý) lên bàn cờ sao cho chúng đôi một không ăn nhau. Hai cách được coi là khác nhau nếu tồn tại một ô được đặt trong cách này không được đặt trong cách kia.

Input

Chỉ một dòng duy nhất chứa số tự nhiên $n$, $m$ ($n \times m \le 10000$).

Output

Gồm một số nguyên duy nhất là số cách đặt chia lấy dư cho $ 1000000007 $.

Constraints

Subtask 1 ($ 30\% $ test): $n \times m \le 4$
Subtask 2 ($ 70\% $ test): Không có ràng buộc thêm

Example

Test 1

Input

2 3

Output

Note

Không đặt quân nào được tính là 1 cách

3. Giao lưu THT 2024 lần 3 - Bài G bảng B1 & C2, Bài D bảng C1

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

Cho số nguyên dương $n$. Đếm số hoán vị ($p_1, p_2, p_3,..., p_{2n}$) của ($1, 2, 3, ..., 2n$) sao cho tồn tại $1 ≤ i ≤ 2n - 1$ thỏa mãn |$p_i - p_{i+1}$| = $n$.

Input

Gồm một số nguyên dương $n$ ($n ≤ 10^5$).

Output

In ra kết quả bài toán chia lấy dư cho $10^9 + 7$.

Scoring

Có $10\%$ số điểm ứng với $n ≤ 5$.
Có $90\%$ số điểm ứng với $n ≤ 10^5$.

Example

Test 1

Input

Output

Test 2

Input

Output

4. Giao lưu THT 2024 lần 3 - Bài D bảng C1

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

Cho dãy $a_1, a_2, ..., a_n$. Bạn cần thực hiện hai loại truy vấn sau:

$!\ u\ v$: Gán $a_u = v$ $(1 \le u \le n, 1 \le v \le 10^9)$.
$?\ l\ r$: Giả sử mỗi thao tác bạn có thể chọn một phần tử bắt kỳ và tăng giá trị của nó lên $1$. Tính số lượng thao tác tối thiểu để dãy $a_l, a_{l + 1}, ..., a_r$ là dãy không giảm.

Input, Output và Scoring

Input

Dòng đầu tiên gồm hai số nguyên dương $n, q$ - số phần tử của dãy và số truy vấn cần xử lý. $(1 \le n, q \le 10^5)$.
Dòng tiếp theo gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$.
$q$ dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng trên.

Output

Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.

Scoring

$20\%$ số điểm có $n, q \le 2000$.
$30\%$ số điểm khác không có truy vấn loại 1.
$30\%$ số điểm khác có $l = 1, r = n$ với mọi truy vấn loại 2.
$20\%$ số điểm còn lại không có giới hạn gì thêm.

Sample

Input

Output

3
3

Notes

Input	Output	Note
`4 3`		$n = 4$, $q = 3$
`2 4 1 4`		$a = (2, 4, 1, 4)$
`? 2 4`	`3`	Cần 3 thao tác để biến dãy $a_2, a_3, a_4$ thành $(4, 4, 4)$
`! 1 4`		$a = (4, 4, 1, 4)$
`? 1 4`	`1`	Cần 3 thao tác để biến dãy $a$ thành $(4, 4, 4, 4)$

Input	Output	Note
`4 3`		\(n = 4\), \(q = 3\)
`2 4 1 4`		\(a = (2, 4, 1, 4)\)
`? 2 4`	`3`	Cần 3 thao tác để biến dãy \(a_2, a_3, a_4\) thành \((4, 4, 4)\)
`! 1 4`		\(a = (4, 4, 1, 4)\)
`? 1 4`	`1`	Cần 3 thao tác để biến dãy \(a\) thành \((4, 4, 4, 4)\)