Thi thử HSG9 TFL & TK - 2025

Cho một xâu kí tự \(s\) chỉ gồm các kí tự trong bảng mã ASCII. Ta gọi một phép dịch xâu \(s\) qua \(k\) kí tự là chuyển \(k\) kí tự ở cuối của xâu \(s\) lên đầu.

Ví dụ: \(s\) = abbaac, \(k = 3\) thì xâu \(s\) trở thành aacabb.

Yêu cầu: Cho xâu \(s\) và một số nguyên dương \(k\). In ra xâu \(s\) sau khi dịch qua \(k\) kí tự.

Input

• Dòng đầu gồm xâu \(s\).
• Dòng thứ hai gồm số nguyên dương \(k\).
• Dữ liệu đảm bảo \(1 \le k \le |s| \le 300\), với \(|s|\) là độ dài xâu \(s\).

Output

• Một dòng duy nhất là xâu \(s\) sau khi dịch qua \(k\) kí tự.

Example

Npndqtldcphktnh
5

hktnhNpndqtldcp

Scoring

• \(60\%\) số điểm có \(1 \le k \le |s| \le 50\) và xâu \(s\) chỉ gồm các kí tự in thường a, b, c, d, ..., z.
• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Cho số nguyên dương \(n\), hãy kiểm tra xem nó có chia hết cho một số chính phương nào khác \(1\) hay không. Số chính phương là số có thể biểu diễn được dưới dạng bình phương của một số tự nhiên.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(n\) (\(n \le 10^9\)).

Output

• In ra YES nếu \(n\) tồn tại một ước khác \(1\) là số chính phương, ngược lại in ra NO.

Example

7

NO

12

YES

Ràng buộc

• \(40\%\) số điểm có \(n \le 10\)
• \(40\%\) số điểm tiếp theo có \(n \le 10^4\)
• \(20\%\) số điểm còn lại có \(n \le 10^9\)

Cho dãy số \(f_1, f_2, f_3, f_4, f_5, \dots\) được định nghĩa như sau:

• \(f_1 = 2\)
• \(f_i = f_{i-1} + i \cdot (i + 1)\)

Yêu cầu: Tính \(f_n\).

Input

• Một dòng duy nhất gồm số nguyên dương \(n\) (\(n \leq 10^9\)).

Output

• Một dòng duy nhất là giá trị của \(f_n\) sau khi chia lấy dư cho \(10^9 + 7\).

Example

4

40

Scoring

• \(40\%\) số điểm có \(n \leq 10^3\).
• \(40\%\) số điểm có \(n \leq 10^6\).
• \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Chính có một món đồ chơi giải đố cho trẻ em 5 tuổi, đồ chơi có thể được biểu diễn thành một xâu \(s\) gồm \(n\) kí tự latin thường. Một ngày, em họ của Chính đến nhà chơi và đã \(q\) lần nghịch đồ chơi của anh, lần thứ \(i\) em của Chính đã đổi tất cả các kí tự \(u_i\) trong xâu \(s\) thành kí tự \(v_i\). Sau khi phát hiện ra, Chính không chỉ không tức giận mà ngược lại còn rất hứng thú với trò nghịch ngợm của em họ. Chính quay sang đố bạn xác định xâu \(s\) cuối cùng sau \(q\) lần phá của em họ Chính.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, q\) (\(n, q \leq 10^5\)).
• Dòng thứ hai gồm một xâu \(s\), chỉ gồm các kí tự latin thường.
• Trong \(q\) dòng tiếp theo, dòng thứ \(i\) gồm hai kí tự \(u_i, v_i\).

Output

• In ra duy nhất một xâu là đáp án của bài toán.

Example

7 4
contest
et
ta
mo
no

cooaasa

4 3
aaaa
ba
ab
bc

cccc

Ràng buộc

• \(30\%\) số điểm có \(n, q \leq 10^3\).
• \(30\%\) số điểm tiếp theo thỏa mãn xâu \(s\) chỉ có duy nhất một loại kí tự.
• \(20\%\) số điểm tiếp theo thỏa mãn xâu \(s\) chỉ có hai loại kí tự.
• \(20\%\) số điểm còn lại có \(n, q \leq 10^5\).

Cho 2 dãy số \(a_1, a_2, \dots, a_n\) và \(b_1, b_2, \dots, b_m\) và một số nguyên dương \(c\). Gọi \(k\) là số lớn nhất sao cho tồn tại 2 bộ số \((i_1, i_2, \dots, i_k)\) và \((j_1, j_2, \dots, j_k)\) (\(1 \le i_1 < i_2 < \dots < i_k \le n, 1 \le j_1 < j_2 < \dots < j_k \le m\)) thỏa mãn \(a_{i_t} + b_{j_t}\) chia hết cho \(c\) với mọi \(t\) thỏa \(1 \le t \le k\).

Yêu cầu: Tìm \(k\).

Input

• Dòng đầu tiên gồm 3 số nguyên dương \(n, m, c\) (\(1 \le n, m \le 10^3, c \le 10^9\))
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).
• Dòng tiếp theo gồm \(m\) số nguyên dương \(b_1, b_2, \dots, b_m\) (\(1 \le b_i \le 10^9\)).

Output

• Một dòng duy nhất là số \(k\).

Example

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

3

Scoring

• \(50\%\) số điểm có \(1 \le n, m \le 5\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.

Vương quốc dưới sự lãnh đạo của nhà vua gồm có \(n\) thành phố nằm cạnh nhau. Mỗi thành phố sẽ có cho mình \(a_i\) trạm phát điện. Với mỗi trạm điện ở thành phố thứ \(i\) nó có thể phát điện được cho các thành phố \(j\) sao cho \(|i - j| \le r\). Ta có năng lượng mà thành phố \(i\) sở hữu là số lượng trạm phát điện có thể phát được tới thành phố \(i\). Gọi độ phát triển của vương quốc là giá trị nhỏ nhất của năng lượng mà các thành phố sở hữu. Vì nhận thấy sự phát triển chưa mạnh mẽ nên nhà vua dự định sẽ cho lắp đặt thêm \(k\) trạm phát điện ở các thành phố bất kì. Hãy giúp nhà vua tính độ phát triển lớn nhất mà vương quốc có thể đạt được.

Input

• Dòng đầu chứa ba số nguyên \(n\), \(r\) và \(k\) (\(1 \le n \le 5 \cdot 10^5\); \(0 \le r \le n\); \(0 \le k \le 10^{18}\)) – Lần lượt là số thành phố, khoảng cách mà các trạm điện có thể phát tới, số trạm phát điện dự tính lắp đặt thêm.
• Dòng thứ hai gồm \(n\) số nguyên \(a_i\) (\(0 \le a_i \le 10^9\)) – Số trạm phát điện ban đầu ở các thành phố.

Output

• In ra một số nguyên duy nhất – Độ phát triển tối đa mà vương quốc có thể đạt được.

Example

5 0 6
4 1 3 2 5

4

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

11

Scoring

• \(40\%\) số điểm có \(r = 0\).
• \(30\%\) số điểm tiếp theo có \(k = 0\).
• \(20\%\) số điểm tiếp theo có \(n, k \le 2 \cdot 10^3\).
• \(10\%\) số điểm còn lại có \(n \le 5 \cdot 10^5\), \(k \le 10^{18}\).

Cho dãy \(a_1, a_2, a_3, a_4, \dots, a_n\) (\(a_i \le 10^5\)), các phần tử không nhất thiết. Ngoài ra, bạn còn được cho một số \(t\) (\(t = 2\) hoặc \(t = 3\)) và số nguyên dương \(k\).

• Với \(t = 2\), gọi \(S\) là tập gồm các tổng \(a_x + a_y\) (\(1 \le x < y \le n\)) được sắp xếp tăng dần.
• Với \(t = 3\), gọi \(S\) là tập gồm các tổng \(a_x + a_y + a_z\) (\(1 \le x < y < z \le n\)) được sắp xếp tăng dần.

Yêu cầu: In ra phần tử nhỏ thứ \(k\) của \(S\).

Input

• Dòng đầu tiên gồm 3 số nguyên dương \(n, t, k\) (\(3 \le n \le 10^5, t = 2\) hoặc \(t = 3\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^8\)).

Dữ liệu đảm bảo \(k\) không lớn hơn số lượng phần tử trong tập \(S\).

Output

• Một dòng duy nhất là phần tử nhỏ thứ \(k\) của tập \(S\).

Example

4 2 5
1 5 5 11

16

4 3 1
1 5 5 11

11

Scoring

• \(20\%\) số điểm có \(t = 2, n \le 1000\).
• \(30\%\) số điểm tiếp theo có \(t = 3, n \le 100\).
• \(20\%\) số điểm tiếp theo có \(t = 2, a_i \le 300\).
• \(20\%\) số điểm tiếp theo có \(t = 3, n \le 1000, a_i \le 10^4\).
• \(10\%\) số điểm còn lại có \(t = 3, k \le 10^5\).

Sau nhiều năm cày cuốc, Chính đã mua được cho mình một căn biệt thự to bự. Hôm nay là ngày họp mặt đại gia đình, họ hàng; vì biệt thự của Chính vô cùng rộng rãi, thoáng mát và thư giãn nên mọi người đã chốt địa điểm họp ở đó. Nhưng vì chính quá béo nên đã ngủ quên tới chiều, trong lúc mọi người đang đứng chờ ở trước cổng biệt thự. Quá bức xúc, mọi người quyết định tự mình tìm cách mở cổng thay vì chờ Chính.

Cổng biệt thự bị khóa bằng một loại ổ khóa đặc biệt, mật khẩu là một số nguyên dương \(x\). Trên cổng vô tình có một tờ giấy gợi ý ghi: \(F(x) = a\) với \(a\) là một số nguyên dương cho trước. Trên tờ giấy đó cũng có định nghĩa \(F(x)\) là tổng các ước số nguyên dương \(k\) của \(x\) thỏa mãn điều kiện \(k\) và \(\frac{x}{k}\) nguyên tố cùng nhau. Bạn hãy giúp người thân của Chính xác định được mật khẩu \(x\) để mở khóa cổng biệt thự, do có thể có nhiều hơn một giá trị thỏa mãn \(F(x) = a\), mật khẩu chính là giá trị \(x\) nhỏ nhất.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(a\) (\(a \le 10^{10}\)).
• Dữ liệu vào đảm bảo luôn tồn tại mật khẩu \(x\).

Output

• Gồm một dòng duy nhất chứa kết quả của bài toán.

Example

3

2

12

6

Scoring

• \(30\%\) số điểm có \(a \le 100\).
• \(30\%\) số điểm khác có \(a \le 10^4\).
• \(40\%\) số điểm còn lại có \(a \le 10^{10}\).