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

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)

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.

tleonlinejudge
e

3

tleonlinejudge
le

6

tleonlinejudge
eee

6

Tổng tích (SUMMUL)

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.

3 3
1 2 3
1 2
2 3
3 4

11
16
21
26

5 3
0 0 0 1 1
1 1
2 1
4 0

1
3
6
3

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

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$.

3
1 2 3

14

3
2 3 1

15

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

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.

5
2 4 8 16 32

4

9
1 2 3 4 5 6 7 8 9

4

5
5 10 15 20 25

1

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

Tổng quan đề thi

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 ---

Cặp số nguyên tố tương đồng (CSNNTD)

Bạn An rất yêu thích toán học, đặc biệt là số nguyên tố. Một ngày nọ, trong lúc giải một bài toán về số nguyên tố, An nhận ra có nhiều cặp số nguyên tố có tổng các chữ số của chúng bằng nhau và An gọi những cặp số như thế là cặp số nguyên tố tương đồng. Ví dụ, cặp số $151$ và $601$ là cặp số tương đồng vì cả hai đều có tổng các chữ số là $1+5+1=6+0+1=7$.
Yêu cầu: Cho hai số nguyên dương $L,R$. Hãy giúp An tìm xem cặp số nguyên tố tương đồng có giá trị trong đoạn từ $L$ tới $R$ và hiệu hai số là lớn nhất.

30 100

36

Dãy số (DAYSO)

Cho dãy số gồm N số nguyên $a_1,a_2,…,a_N$ và hai số nguyên không âm $L,R$ $(L≤R)$. Đếm số cặp $(i,j)$ thỏa mãn $1≤i≤j≤N$ và $L≤|a_i+a_{i+1}+⋯+a_j |≤R$.

3 0 1
1 -1 2

4

Ăn trưa (ANTRUA)

Trường mầm non Super Kid có nhiều bé code rất nhanh nhưng ăn rất chậm. Trong giờ ăn trưa, có $N$ bé ngồi quanh một bàn tròn, các bé được đánh số từ 1 tới $N$ theo chiều kim đồng hồ. Xuất phát từ một vị trí của 1 bé, cô giáo phải đi một vòng quanh bàn theo chiều kim đồng hồ để múc đồ ăn cho từng bé. Khi đến vị trí 1 bé, cô chuẩn bị đồ ăn hết $X$ (giây), và bé đó bắt đầu ăn ngay trong khi cô chuyển sang chuẩn bị đồ ăn cho bé kế tiếp theo chiều kim dồng hồ…, thời gian di chuyển của cô coi như không đáng kể.

Do biết rõ tốc độ ăn của từng bé, cô có thể uớc luợng chính xác rằng bé thứ $i$ sau khi được cô chuẩn bị đồ ăn sẽ cần dúng $a_i$ giây để ăn xong phần ăn của mình $(∀i = 1,2,… ,n)$. Vấn đề là cô muốn kết thúc bữa ăn trưa càng sớm càng tốt, muốn vậy, việc chọn bé nào để chuẩn bị đồ ăn đầu tiên phải đuợc tính toán kỹ luỡng.

Yêu cầu: Bạn duợc cho biết số $N$, giá trị $X$, dãy $A = (a_1,a_2,…,a_n)$. Hãy giúp cô giáo chọn vị trí xuất phát sao cho thời gian từ lúc bắt đầu buổi ăn trưa tới khi tất cả các học sinh ăn xong là nhỏ nhất.
Ðể tránh việc phải đọc một luợng dữ liệu quá lớn, dãy $A$ sẽ duợc cho bởi ba số nguyên duong $P,Q,M$ trong dó mỗi phần tử $a_i$ được xác dịnh theo công thức:

5 3
2 1 9

18

Số bộ K (SOBOK)

Ưóc số và bội số là một trong những khái niệm quen thuộc trong Số học. Với hai số nguyên $A,B$ bất kỳ nếu $A$ chia hết cho $B$ ta gọi $B$ là ước số của $A$ và $A$ là bội số của $B$. Với một bộ $k$ số nguyên dương $a_1,a_2,…,a_k$ bất kỳ, ước số chung lớn nhất của chúng là số nguyên dương $X$ lớn nhất thòa mãn mọi $a_i$ là bội của $X$. Tương tự, bội số chung nhỏ nhất của chúng là số nguyên dương nhỏ nhất $Y$ sao cho $Y$ chia hết cho mọi số $a_i$.

Cho hai số nguyên $P$ và $Q$ được viết dưới dạng tích các số nguyên dương $(P=p_1×p_2×…×p_N,Q=q_1×q_2,…,q_M )$. Đếm số bộ K số nguyên dương có ước chung lớn nhất là $P$ và bội chung nhỏ nhất là $Q$.

1 2 2
1
2 3

4

1 2 10
2
2 3

1022

2 1 5060162
22 7
1997

0

Bocchi là một cô gái hướng nội, mẹ của cô bé – cô Michiyo Gotoh không thích điều này. Vì vậy, mỗi ngày mẹ của cô bé đều bắt cô bé chạy quanh khu phố qua ít nhất k con đường trong khu phố sau đó trở về điểm bắt đầu (lưu ý là trên đường đi và về chỉ cần có ít nhất k con đường, hay nói cách khác cô có thể đi lại trên một con đường nhiều lần), khu phố của Bocchi có dạng một lưới các nhà dân có kích thước n x m, với một khu nhà ($i_1$, $j_1$) sẽ có đường nối tới khu nhà ($i_2$, $j_2$) nếu |$i_1$ – $i_2$| + |$j_1$ – $j_2$| $=$ $1$. Dù các con đường có chiều dài bằng nhau nhưng để đi hết mỗi con đường sẽ tiêu tốn một khoảng thời gian có thể khác nhau vì có thể các con đường trên có chó dữ, đông người hay Oppenheimer đang thử bom nguyên tử,…
Tuy nhiên, Bocchi được quyền chọn một điểm bắt đầu cho chặng đường của cô, và cô muốn tối thiểu thời gian chạy nhất có thể, Bocchi sẽ hỏi bạn $q$ lần dạng câu hỏi nếu bắt đầu chạy từ khu nhà ($i$, $j$) thì cần tối thiểu bao nhiêu thời gian, nhiệm vụ của bạn là trả lời cho Bocchi để giúp tay rock của chúng ta có thời gian chạy ít nhất có thể.

3 3 10
1 1 
1 1
1 1
1 1 1
1 1 1
1
1 1

10

2 2 4
1
3
3 2
1
1 2

4

Lại là $1$ bài toán khác về cờ vua.

Hôm nay là một ngày đẹp trời, flo, Noobcoder và mondellbit009 quyết định đến nhà của flo để chơi cờ vua $4$ người bởi cả $3$ rất thích chơi cờ vua.

Sau khi chơi $69420$ ván cờ vua, cả $3$ đã bắt đầu thấy chán chơi cờ vua thông thường. Thế là flo quyết định lấy bàn cờ vua với kích thước $n \times m$ mà mondellbit009 tặng cậu vào sinh nhật cùng với những con mã của Noobcoder. Trong lúc suy nghĩ nên chơi gì với những món này thì bỗng một bài toán khá thú vị xuất hiện trong đầu của flo.

Bài toán trên quá dễ nên flo, Noobcoder và mondellbit009 đã giải nó chỉ trong $69420ms$. Vậy nên bạn hãy thử sức với bài toán trên nhé.

3
1 1
4 2
6 8

1
0
4

Cho 2 số nguyên dương $n,k$, nhiệm vụ của bạn là tính tổng $XOR$ của tất cả các số nguyên dương có giá trị nhỏ hơn $2^n$ mà có $k$ bit là $1$.

2
2 1
4 2

3
15

À không, bài toán trên quá dễ. Thế nên tôi quyết định đem đến cho $1$ bài toán khó hơn với nội dung tương tự như sau.

Chúc bạn may mắn nhé.

3 2
2 3 1

11

4 3
2 3 4 5

154

chinhhoangmanutd có $1$ mảng $A$ gồm các $n$ xâu $S$ có độ dài bất kì và số nguyên không âm $k$. Với mỗi xâu $S$ ta có thể:

• Hoán đổi vị trí giữa hai kí tự liền kề nhau.
• Sau tối đa $k$ thao tác xâu $S$ phải là xâu có thứ tự từ điển lớn nhất.

Sau các thao tác trên hãy in ra xâu có thứ tự từ điển lớn nhất trong mảng $A$.

5 4
hoang
haudz
bngoc
cuong
dviet

zhaud

Bạn được cho $1$ số nguyên dương $n$ và tại mỗi thao tác, bạn có thể trừ $n$ cho $\left \lfloor \sqrt n \right \rfloor$. Nhiệm vụ của bạn là xác định số lượng thao tác cần thực hiện để $n = 0$.

Ta có $\left \lfloor n \right \rfloor$ là phép làm tròn xuống. Ví dụ như $\left \lfloor 6.9 \right \rfloor=6,\left \lfloor 4.20 \right \rfloor=4$.

5
6
9
4
2
0

4
5
3
2
0

Một bài toán rất thú vị về tổng chữ số

huyhau6a2 rất thích những tính chất thú vị về tổng chữ số nên cậu đã tự đặt bài toán cho mình như sau:

• Đầu tiên huyhau6a2 sẽ cho bạn 2 số $l,r$.
• Ta định nghĩa $f(x)=|d(x)-d(x-1)|$. Trong đó $d(x)$ là tổng chữ số của $x$.
• Nhiệm vụ của bạn là hãy tính $\sum_{i=l}^r f(i)$.

5
9 9
10 10
13 21
90 100
1 1000000000000000000

1
8
16
34
1799999999999999999

Một hàm $f(x)$ được gọi là hàm chẵn khi và chi khi $f(x) = f(-x)$ với mọi $x$, và được gọi là hàm lẻ khi và chỉ khi $f(x) = -f(-x)$ với mọi $x$.
Viết chương trình kiêm tra một hàm $f(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n$ có phải hàm chẵn và/hoặc hàm lẻ hay không.

2
2
3 2 1
0
1

None
Even

Bài đầu tiên của flo và đây là phiên bản reupload :D

Sau một ngày dài mệt mỏi, flo quyết định chơi cờ vua với bạn cậu là huyhau6a2 để xả stress.

Sau khi chơi $69420$ ván cờ, flo và huyhau6a2 đã bắt đầu chán chơi cờ theo kiểu bình thường. Thế là cả hai quyết định dùng bàn cờ $n\times m$ vừa mua ở Ohio ra chơi. Nhà của flo có rất nhiều quân mã nên cả hai lấy ra để nghịch. Sau đó, flo vô tình phát hiện ra một bài toán vô cùng thú vị và độc đáo như sau.

Bài toán như vậy thì khá là dễ nên flo đã giải chỉ trong vòng $1$ nốt nhạc. Vậy là cậu đã nghĩ ra phiên bản khó hơn như sau.

Cả flo và huyhau6a2 rất muốn biết đáp án. Tuy nhiên, cả hai đang rất là mệt mỏi. Là một con người tốt bụng, bạn hãy giúp flo và huyhau6a2 tìm đáp án nhé.

2
10 12
5 9

390
74

Trong tiết toán ngày hôm nay, huyhau6a2 đã được học về phân số. Theo cậu biết, phân số là sự biểu diễn số hữu tỷ dưới dạng tỷ lệ của hai số nguyên với số ở trên là tử số, còn số ở dưới là mẫu số khác $0$. Và như bao như tiết học khác, huyhau6a2 lại được giao một đống bài tập về phân số.

Buổi tối hôm đó, huyhau6a2 đang ngồi hoàn thành đống bài tập trên. Các bài này vô cùng dễ nhưng có một số bài lại khiến cậu sợ bởi cậu không chắc chắn về kết quả của mình. Ví dụ như là bài sau.

Bài trên khá đơn giản nhưng huyhau6a2 lại không chắc chắn vể kết quả mà cậu tính ra được. Bạn có thể kiểm tra giúp huyhau6a2 chứ.

3
4 2
3 4
6 9

No
Yes
No

Hôm nay là một ngày mưa to gió lớn nên huyhau6a2 được nghỉ ở nhà. Hằng ngày cậu có thể đi chơi với bạn gái nhưng do điều kiện thời tiết như này nên cậu chỉ có thể lựa chọn ở nhà. Quá chán, huyhau6a2 bỗng nghĩ ra một trò chơi như sau.

• Cậu có hai số nguyên $n$ và $m$. Ban đầu, $m$ bằng $0$.
• Tạo tất cả các số $n$ khác nhau bằng cách hoán đổi vị trí của $2$ chữ số bất kỳ của $n$.
• Với mỗi số $n$ tạo được, cộng nó vào $m$.

huyhau6a2 thắc mắc với số nguyên dương $n$ cậu chọn thì khi trò chơi kết thúc, $m$ sẽ có giá trị là bao nhiêu. Vì số cậu chọn quá lớn nên cậu không thể tính được. Bạn hãy tính giúp huyhau6a2 nhé.

3
69
133
420

165
777
1332

Đây mới là bản dễ.

Sau một ngày dài đi học mệt mỏi, huyhau6a2 quyết định chơi trò chơi điện tử yêu thích của cậu ấy. Trò chơi khá đơn giản, chỉ cần điều khiển nhân vật vượt qua các chương ngại vật của mỗi màng chơi.

Sau khoảng $69420s$ chơi, huyhau6a2 cuối cùng đã đến được màng cuối cùng. Ở màng chơi này, cậu cần phải điều khiển nhân vật của mình vượt qua $1$ cây cầu. Cây cầu này có tất cả là $n$ ô và ô thứ $i$ sẽ có $a_i$ điểm. Tại mỗi bước đi, huyhau6a2 có thể nhảy sang bất kì ô nào miễn vị trí của ô đó lớn hơn vị trí của ô mà cậu bắt đầu nhảy. Khi vượt qua cây cầu, tích số điểm trên những ô mà huyhau6a2 đã điều khiển nhân vật của mình nhảy lên phải là $1$ số chính phương thì huyhau6a2 mới chiến thắng.

huyhau6a2 thắc mắc có bao nhiêu cách để điều khiển nhân vật của cậu vượt qua cây cầu để cậu giành được chiến thắng. Bạn hãy tính giúp huyhau6a2 nhé.

4
2 4 2 1

7

Đây là bài đầu tiên nên tôi cũng không muốn thêm tình huống hay làm đề bài dài hơn để làm rối bạn hết cả. Vì thế, nội dung bài này tôi viết khá là ngắn gọn, cụ thể là như sau.

Đấy, tôi đã nói rồi. Đề bài chỉ ngắn gọn thế thôi, chúc bạn may mắn và đừng bị vấn đề kĩ năng nhé.

5 2
1 2 4 3 2
2 5 6
1 3 10

3
2

TLE CHAMPIONS LEAGUE là giải đấu danh giá và lâu đời. Nhiều năm về trước, TLE CHAMPIONS LEAGUE được tổ chức lần đầu vào những năm $20$ của thế kỉ $XXI$. Mùa giải đầu tiên với sự đăng cai của Sunlight đã chứng kiến những cuộc lội ngược dòng ngoại mục. Năm đó, đội bóng $Pre-MU$ không tham dự vì lí do chưa mua được bản quyền. Năm nay, dưới sự chèo lái của huấn luyện viên đại tài tourist với các cầu thủ như Maguire, Ohaha,... sẽ mang đến bất ngờ cho giải đấu năm tới nhưng $Pre-MU$ đang gặp phải $1$ vấn đề như sau.

Đội bóng $Pre-MU$ của tourist làm huấn luyện viên có $n$ cầu thủ, cầu thủ thứ $i$ có chiều cao là $A_i$. Trong quá trình chuẩn bị cho giải TLE CHAMPIONS LEAGUE tổ chức vào năm sau, tourist nhận thấy:

• Trình độ huấn luyện của mình là $S$.
• Khả năng tấu hài của đội bóng sẽ là $S\times |A_i-A_{i-1}|$ với mọi $2\le i\le n$.

Vì tourist không kịp chuẩn bị cầu thủ mới để khả năng tấu hài là nhỏ nhất nên đến nhờ jiangly. Biết vậy, jiangly đã mang ra lọ Calcium gia truyền tinh khiết $69\%$ để buff chiều cao cho các cầu thủ:

• Nếu cầu thủ cao thêm $k$ đơn vị thì khả năng tấu hài của cả đội sẽ tăng thêm $k^2$ đơn vị.

Được lọ thuốc gia truyền này, tourist về để dùng cho các cầu thủ của mình. Hãy giúp tourist sử dụng thuốc như thế nào để khả năng tấu hài là nhỏ nhất. Và tất nhiên mỗi cầu thủ chỉ được dùng loại thuốc $1$ lần.

6 3
2 4 6 3 1 7

35

Ông $A$ là một địa chủ ở một vùng đất tên là $ACP$. Ông A có một mảnh đất rộng lớn và ông $A$ quyết định trồng $n$ cây. Các cây được đánh số từ $1$ đến $n$. Cây thứ $i$ có chiều cao là $A_i$.

Sau khi trồng $n$ cây xong, ông $A$ có một máy cắt cây, máy cắt cây của ông $A$ rất lạ kì. Trên máy cắt cây đó sẽ nhận vào một giá trị $x(1≤x≤10^9)$ mà ông A nhập trên màn hình của máy, máy cắt cây đó chỉ cắt những cây nào có độ dài lớn hơn hoặc bằng $x$, nó cứ cắt cho đến khi độ dài cây bé hơn $x$ thì không cắt nữa.

Một cây được gọi là được cắt hết khi và chỉ khi độ dài sau khi cắt bằng $0$, độ cao cây bằng $0$ không có nghĩa là không có cây.
Ví dụ : $A=[8,5,4,7,6]$ và $x=3$. Khi sử dụng máy cắt đó để cắt cây thứ $1$ và thứ $5$ thì độ cao của $n$ sau khi cắt là $A=[2,5,4,7,0]$.
Ông $B$ thấy mảnh đất của ông $A$ và chiếc máy cắt cây kì lạ nên hiếu kì đến chơi, sau khi ông $B$ quan sát thì ông $B$ đố ông $A$ một câu đố như sau:

• Chọn ra $k$ cây, sau đó sử dụng máy cắt cây lạ kì đó cắt $k$ cây này.
• $k$ cây sau khi cắt phải được cắt hết (nghĩa là độ dài của $k$ cây sau khi cắt phải bằng $0$)
• Ông $A$ sẽ nhập trên màn hình máy cắt cây một giá trị $x$, máy cắt sẽ thực hiện cắt cây với mô tả trên.
• Máy cắt sẽ không nhận giá trị khác khi đang cắt $k$ cây đó, nghĩa là ông $A$ sẽ phải sử dụng máy cắt với giá trị $x$ để cắt $k$ cây đó.
• Với những tiêu chí trên thì ông $B$ muốn hỏi giá trị $x$ tối đa có thể có được sau khi chọn $k$ cây là bao nhiều ?

Ông $B$ sẽ hỏi $Q$ câu hỏi, mỗi câu hỏi là một giá trị $k$

Yêu cầu: Hãy giúp ông $A$ trả lời $Q$ câu hỏi này nhé !

6 3
2 4 6 3 1 7
1
2
3

7
3
2