Pre TS10 2024 - TLEOI 2.0 - Ngày thi thứ nhất

Điểm: 0

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Thời gian làm bài: $120$ phút, $20$ giờ $00$ đến $22$ giờ $00$ ngày $23$ tháng $12$ năm $2023$ .

Nộp bài từ $21$ giờ $55$ đến $22$ giờ $05$ tại đây.

Tổng quan đề thi

STT	Tên bài	Mã bài	Thời gian	Bộ nhớ	Điểm
1	Ghép xâu	`MAKESTR`	$1$ giây	$256$ MB	$5$
2	Tổng tích	`SUMMUL`	$1$ giây	$256$ MB	$5$
3	Tổng các số lớn nhất	`SUMMAX`	$1$ giây	$256$ MB	$5$
4	Tích chính phương	`SQRPRO`	$1$ giây	$256$ MB	$5$

Lưu ý:

Các đội nộp bài trên hệ thống TLEOJ. Contest sẽ được mở lúc $22$ giờ $00$ của ngày thi và sẽ kết thúc vào lúc $22$ giờ $05$ cùng ngày.
Với mỗi bài tập, các bạn được nộp tối đa một lần.
Tất cả các bài đều nhập xuất qua file. File dữ liệu đầu vào có tên là <mã bài>.inp và file dữ liệu đầu ra có tên là <mã bài>.out, ví dụ như bài có mã là EQSTR thì sẽ có các file là EQSTR.inp và EQSTR.out.
Bài thi chỉ được chấm bởi một trong ba ngôn ngữ: C++ (C++11), Pascal và Python (Python 3).
Tất cả các bài nộp đều không được phép dùng các từ khóa như #pragma, optimize.

--- Happy coding ---

Ghép xâu (MAKESTR)

Thời gian	Bộ nhớ	Input	Output
$1$ giây	$256$ megabytes	`MAKESTR.inp`	`MAKESTR.out`

Quang có hai xâu $s$ và $t$ . Quang muốn chọn một bộ số $(a_1, a_2, ..., a_k)$ , các số trong bộ đôi một khác nhau sao cho khi ghép lần lượt các ký tự $a_1,a_2,…,a_k$ của xâu $s$ ta được xâu $t$ . Ví dụ, với xâu $s=$ "danghuyhau" và $t=$ "huh" thì một bộ hợp lệ là $(8,10,5)$ vì các ký tự thứ $8, 10, 5$ trong xâu s lần lượt là h, u, h.

Input, Output và Subtask

Input: Nhập từ file MAKESTR.inp

Dòng đầu tiên gồm một xâu $s$ gồm các ký tự Latin tiếng Anh in thường.
Dòng đầu tiên gồm một xâu $t$ gồm các ký tự Latin tiếng Anh in thường.
Độ dài hai xâu không vượt quá $10^5$ .

Output: Xuất ra file MAKESTR.out

Một dòng duy nhất gồm số cách Quang có thể thực hiện. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của kết quả khi chia cho $10^9+7$ .

Subtask

Subtask 1 $(20\%)$ : Độ dài xâu $t$ là $1$ .
Subtask 2 $(20\%)$ : Độ dài xâu $t$ là $2$ và độ dài xâu $s$ không vượt quá $5000$ .
Subtask 3 $(20\%)$ : Xâu $t$ chỉ gồm các ký tự khác nhau.
Subtask 4 $(20\%)$ : Xâu $t$ chỉ gồm một loại ký tự.
Subtask 5 $(20\%)$ : Không có giới hạn gì thêm.

Sample

Sample 1

Input (MAKESTR.inp)

tleonlinejudge
e

Output (MAKESTR.out)

Notes

Các bộ số thỏa mãn là $(3),(9)$ và $(14)$ .

Sample 2

Input (MAKESTR.inp)

tleonlinejudge
le

Output (MAKESTR.out)

Notes

Các bộ số thỏa mãn là $(2,3),(2,9),(2,14),(3,3),(3,9),(3,14)$ .

Sample 3

Input (MAKESTR.inp)

tleonlinejudge
eee

Output (MAKESTR.out)

Notes

Các bộ số thỏa mãn là $(3,9,14),(3,14,9),(9,3,14),(9,14,3),(14,3,9)$ và $(14,9,3)$ .

Tổng tích (SUMMUL)

Thời gian	Bộ nhớ	Input	Output
$1$ giây	$256$ megabytes	`SUMMUL.inp`	`SUMMUL.out`

Cho một dãy $a_1,a_2,…,a_n$ . Bạn cần tính tổng tất cả các giá trị $a_i×a_j$ với mọi $1≤i<j≤n$ .

Nhận thấy bài toán này quá dễ đối với các bạn học sinh chuyên Tin, Quang quyết định tăng độ khó cho nó bằng cách áp dụng các truy vấn, mỗi truy vấn gồm hai số $u,v$ , yêu cầu bạn thay đổi giá trị $a_u=v$ , sau đó tính lại tổng các giá trị như trên.

Input, Output và Subtask

Input: Nhập từ file SUMMUL.inp

Dòng đầu tiên gồm hai số nguyên duơng n,q – lần lượt là số lượng số trong dãy $a$ và số lượng truy vấn $(1≤n,q≤3×10^5 )$ .
Dòng tiếp theo gồm n số nguyên mô tả dãy $a$ ban đầu $(0≤a_i≤10^9 )$ .
$q$ dòng tiếp theo mỗi dòng gồm hai số nguyên dương u,v mô tả một truy vấn yêu cầu gán lại $a_u=v$ $(1≤u≤n,0≤v≤10^9 )$ .

Output: Xuất ra file SUMMUL.out

Dòng đầu tiên gồm một số là tổng các tích hai số với dãy ban đầu.
$q$ dòng tiếp theo, dòng thứ $i$ trong số $q$ dòng này gồm một số là tổng các tích hai số với dãy sau khi thực hiện truy vấn thứ $i$ .
Vì các kết quả có thể rất lớn, bạn chỉ cần in ra 9 chữ số cuối của nó.

Subtask

Subtask 1 $(25\%)$ : $n, q \le 500$ .
Subtask 2 $(25\%)$ : $n, q \le 5000$ .
Subtask 3 $(25\%)$ : $a_i \le 1$ và $v \le 1$ ở mọi truy vấn.
Subtask 4 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Sample 1

Input (SUMMUL.inp)

Output (SUMMUL.out)

Notes

Ban đầu tổng các tích là $1×2+2×3+1×3=11$ .
Sau truy vấn 1, tổng các tích là $2×2+2×3+2×3=16$ .
Sau truy vấn 2, tổng các tích là $3×2+2×3+3×3=21$ .
Sau truy vấn 3, tổng các tích là $3×2+2×4+3×4=26$ .

Sample 2

Input (SUMMUL.inp)

Output (SUMMUL.out)

Tổng các số lớn nhất (SUMMAX)

Thời gian	Bộ nhớ	Input	Output
$1$ giây	$256$ megabytes	`SUMMAX.inp`	`SUMMAX.out`

Bạn được cho một dãy số $a_1,a_2,…,a_n$ . Bạn hãy tính tổng các giá trị $max⁡(a_l,a_{l+1},…,a_r )$ với mọi cặp $(l,r)$ mà $1≤l≤r≤n$ .
$max⁡(a_l,a_{l+1},…,a_r )$ là số lớn nhất trong đoạn từ $a_l$ đến $a_r$ .

Input, Output và Subtask

Input: Nhập từ file SUMMAX.inp

Dòng đầu tiên gồm một số nguyên dương $n$ – số phần tử của dãy $a$ $(1≤n≤10^6 )$ .
Dòng tiếp theo gồm n số nguyên dương $a_1, a_2, ..., a_n$ $(0≤a_i≤10^9 )$ .

Output: Xuất ra file SUMMAX.out

Một dòng duy nhất gồm kết quả bài toán. Vì kết quả có thể rất lớn nên chỉ cần in ra 9 chữ số cuối của kết quả.

Subtask

Subtask 1 $(25\%)$ : $n \le 500$ .
Subtask 2 $(25\%)$ : $n \le 5000$ .
Subtask 3 $(25\%)$ : Dãy $a$ được sắp xếp không giảm.
Subtask 4 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Sample 1

Input (SUMMAX.inp)

3
1 2 3

Output (SUMMAX.out)

Notes

Cặp $(1,1)$ có số lớn nhất là 1.
Các cặp $(1,2),(2,2)$ có số lớn nhất là 2.
Các cặp $(1,3),(2,3),(3,3)$ có số lớn nhất là 3.

Sample 2

Input (SUMMAX.inp)

3
2 3 1

Output (SUMMAX.out)

Notes

Cặp $(3, 3)$ có số lớn nhất là 1.
Cặp $(1, 1)$ có số lớn nhất là 2.
Các cặp còn lại có số lớn nhất là 3.

Tích chính phương (SQRPRO)

Thời gian	Bộ nhớ	Input	Output
$1$ giây	$256$ megabytes	`SQRPRO.inp`	`SQRPRO.out`

Bạn được cho một dãy $a_1,a_2,…,a_n$ . Bạn cần đếm xem có bao nhiêu cặp $(i,j)$ mà $1≤i<j≤n$ và $a_i×a_j$ là số chính phương.

Input, Output và Subtask

Input: Nhập từ file SQRPRO.inp

Dòng đầu tiên gồm một số nguyên dương $n$ – số phần tử của dãy $a$ $(1≤n≤10^5 )$ .
Dòng tiếp theo gồm n số nguyên dương $a_1, a_2, ..., a_n$ $(1≤a_i≤10^9 )$ .

Output: Xuất ra file SQRPRO.out

Một dòng duy nhất gồm số cặp thỏa mãn.

Subtask

Subtask 1 $(20\%)$ : $n \le 1000$ .
Subtask 2 $(20\%)$ : $a_1 = a_2 = ... = a_n$ .
Subtask 3 $(20\%)$ : $a_i \le 10^6$ .
Subtask 4 $(20\%)$ : $a_i \le 2\times 10^7$ .
Subtask 5 $(20\%)$ : Không có giới hạn gì thêm.

Sample

Sample 1

Input (SQRPRO.inp)

5
2 4 8 16 32

Output (SQRPRO.out)

Notes

Các cặp số thỏa mãn là: $2×8=16,2×32=64,8×32=256,4×16=64$ .

Sample 2

Input (SQRPRO.inp)

9
1 2 3 4 5 6 7 8 9

Output (SQRPRO.out)

Notes

Các cặp số thỏa mãn là: $1×4=4,1×9=9,4×9=36,2×8=16$ .

Sample 3

Input (SQRPRO.inp)

5
5 10 15 20 25

Output (SQRPRO.out)

Notes

Cặp số duy nhất thỏa mãn là $5×20=100$ .

Bình luận

Không có bình luận nào.