[TÁM TƯ] KÌ THI CHỌN ĐỘI TUYỂN DỰ THI THÀNH PHỐ 2023 Problems

AABBN

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 1G Input: AABBN.INP Output: AABBN.OUT

There are two ways to write error-free programs; only the third one works 😈

Cho một số nguyên $N$ $(0 \le N \le 10^{18})$
Đếm xem có bao nhiêu bộ hai số nguyên dương chẵn $a, b$ sao cho $a * a * b * b = N$.

Lưu ý: $a$ và $b$ có vài trò khác nhau. Ví dụ: cặp $(6, 4)$ và $(4, 6)$ được tính là hai cặp khác nhau.

Input: `AABBN.INP`

Dòng đầu tiên gồm số nguyên $N$.

Output: `AABBN.OUT`

In ra một số nguyên là số lượng cặp $a$ và $b$ thỏa mãn đề bài .

Scoring:

Subtask $1$ $(40\%)$: $N \le 10^6$;
Subtask $2$ $(40\%)$: $N \le 10^{12}$;
Subtask $3$ $(20\%)$: $N \le 10^{18}$.

Sample Input

Sample Output

Watching

Nộp bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 1G Input: watching.inp Output: watching.out

There are 10 types of people in this world. Those who understand binary and those who don't 😈

Hôm nay là ngày nghỉ của Ti36, điều đó có nghĩa là sẽ không có gì ngăn cản anh ấy làm điều mình yêu thích - xem phim truyền hình dài tập. Trong suốt cả ngày, kênh A sẽ chiếu phần mới nhất của loạt phim "Avengers" và kênh B sẽ chiếu phần mới nhất của loạt phim "Batman".

Vì Ti36 không muốn chỉ xem một bộ phim duy nhất trong hai bộ phim này nên anh ấy quyết định xem cả hai, anh ấy sẽ chuyển sang kênh khác để xem phim còn lại mỗi khi quảng cáo bắt đầu ở kênh anh ấy đang xem. Vào thời điểm $0$, Ti36 sẽ bật TV và bắt đầu xem loạt phim "Avengers" trên kênh A. Nếu bất cứ lúc nào trên kênh truyền hình mà Ti36 đang xem có quảng cáo bắt đầu, thì Ti36 sẽ chuyển sang kênh kia và xem kênh đó. Nếu Ti36 chuyển kênh và cũng có một quảng cáo đang diễn ra vào lúc này, thì anh ấy sẽ không chuyển kênh với hy vọng rằng quảng cáo sẽ sớm kết thúc trên kênh này. Vào thời điểm $t$, Ti36 sẽ tắt TV và đi ngủ.

Cho biết lịch chiều quảng cáo cụ thể và thời lượng của các quảng cáo trên hai kênh, hãy xác định xem Ti36 sẽ xem mỗi bộ phim bao nhiêu đơn vị thời gian.

Input: `watching.inp`

Dòng đầu tiên chứa bốn số nguyên $n, m, t$ và $k$ $(1 \le n, m \le 10^5, 1 \le t \le 10^{18}, 1 \le k \le 10^9)$, trong đó $n$ là số đoạn quảng cáo trên kênh A, $m$ là số đoạn quảng cáo trên kênh B, $t$ là thời điểm đi ngủ và $k$ là khoảng thời gian được chiếu trên mỗi kênh của mỗi quảng cáo.
Dòng thứ hai chứa $n$ số nguyên $a_i$ $(1 \le a_1 < a_2 < ... < a_n \le 10^{18}, a_i + k < a_{i+1} \forall i \in [1,n — 1])$, là thời điểm bắt đầu chiếu quảng cáo trên kênh A.
Dòng thứ ba chứa $m$ số nguyên $b_j$ $(1 \le b_1 < b_2 < ... < b_m \le 10^{18}, b_j + k < b_{j+1} \forall j \in [1,m — 1])$, là thời điểm bắt đầu chiếu quảng cáo trên kênh B.

Output: `watching.out`

Đưa ra hai số nguyên là tổng thời gian xem phim "Avengers" trên kênh A và tổng thời gian xem phim "Batman" trên kênh B.

Scoring:

Subtask $1$ $(40\%)$: $n \le 1000, k, t, a_i, b_j \le 10^6$;
Subtask $2$ $(60\%)$: không có ràng buộc gì thêm.

Sample Input 1

6 5 10 1
1 3 5 7 9 11
2 4 6 8 10

Sample Output 1

5 5

SMod

Nộp bài

Điểm: 100 Thời gian: 2.0s Bộ nhớ: 1G Input: smod.inp Output: smod.out

It works … on my machine 😈

Cho bốn số nguyên $n, x, y, m$.
Dãy số $A$ có độ dài $n$ được tạo ra theo cách sau:

$a_1 = x$;
$a_i = (a_{i-1}*x+y) \% m$ với $2 \le i \le n$.

Dãy số $B$ là dãy số $A$ sau khi sắp xếp không giảm.

Tính: $\sum_{i=1}^{n} (b_i * i) \% m$

Input: `smod.inp`

Gồm một dòng chứa bốn số nguyên $n, x, y, m$ $(1 \le x, y \le m)$.

Output: `smod.out`

In ra một số nguyên là kết quả của bài toán.

Scoring:

Subtask $1$ $(40\%)$: $n \le 10^5; m \le 10^9$;
Subtask $2$ $(40\%)$: $n \le 3*10^7; m \le 3*10^7$;
Subtask $3$ $(20\%)$: $n \le 10^{18}; m \le 10^6$;

Sample Input

3 2 1 10

Sample Output

Note

Dãy số $A$: $2, 5, 1$;
Dãy số $B$: $1, 2, 5$;
Kết quả: $(1*1+2*2+5*3)\%10=0$.

Tunnel

Nộp bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 1G Input: TUNNEL.INP Output: TUNNEL.OUT

Software and cathedrals are much the same – first we build them, then we pray 😈

Dưới lòng đất của HNA là hệ thống đường ngầm dày đặc gồm $n$ địa điểm đánh số từ $1$ đến $n$. Có $m$ đoạn đường ngầm, đoạn đường ngầm thứ $i$ kết nối địa điểm $u_i$ và $v_i$ có chi phí là $c_i$, nghĩa là muốn kích hoạt sử dụng đoạn đường hầm này phải trả chi phí là $c_i$. LetterC67 và $aúR là đôi bạn thân đang hoạt động dưới lòng đất này.

Buổi sáng, LetterC67 cần đi từ $A$ đến $B$, và tất nhiên cậu chọn tuyến đường sao cho cần trả ít chi phí nhất.

Buổi chiều, $aúR cần đi từ $C$ đến $D$, nhưng may thay, những đoạn đường hầm mà buổi sáng LetterC67 đã trả chi phí để kích hoạt rồi thì $aúR có thể sử dụng mà không cần trả chi phí nữa.

Hãy hãy tính xem $aúR cần trả chi phí ít nhất là bao nhiêu?

Input: `tunnel.inp`

Dòng đầu tiên gồm hai số nguyên $n, m$.
Dòng thứ hai là bốn số nguyên $A, B, C, D$.
$m$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $u_i, v_i, c_i$.
Dữ liệu đảm bảo từ một địa điểm có thể đi đến mọi địa điểm khác, không có hai đoạn đường hầm nối cùng một cặp địa điểm.

Output: `tunnel.out`

In ra một số nguyên là kết quả của bài toán.

Note

Trong mọi test: $A \neq B, C \neq D$, $1 \le u_i < v_i \le n$, $1 \le c_i \le 10^9$.
Subtask 1 ($15\%$ số điểm): $A=C$;
Subtask 2 ($15\%$ số điểm): Có duy nhất một tuyến đường từ $A$ đến $B$ có giá trị nhỏ nhất;
Subtask 3 ($30\%$ số điểm): $n \le 300$;
Subtask 4 ($40\%$ số điểm): $2 \le n \le 10^5, 1 \le m \le 2 \times 10^5$

Ví dụ

Input:

Output:

Giải thích:

Chỉ có duy nhất một đường đi ngắn nhất từ $1$ đến $6$ là $1-2-3-5-6$, nên LetterC67 sẽ sử dụng tuyến đường này.
$aúR sẽ chỉ phải trả chi phí thêm đoạn đường hầm $4-5$ với giá trị $2$ đến di chuyển từ $1$ đến $4$.

Watermelon

Nộp bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 1G Input: watermelon.inp Output: watermelon.out

It's not a bug — it's an undocumented feature 😈

Cho một dãy số nguyên $A$ gồm $n$ phần tử, được đánh số $A_1,A_2,...,A_n$.

Ta có một số định nghĩa như sau:

Trọng số của đoạn con (ở đây là một đoạn con liên tiếp) là tổng các giá trị $A_i$ trong đoạn.
Độ cân bằng của dãy $A$ là trọng số của đoạn con có trọng số lớn nhất trong dãy số.

Bài toán sẽ thật dễ dàng nếu chỉ yêu cầu tính độ cân bằng của dãy $A$ được cho, vậy nên $Watermelon$ - người thầy của muôn quả - đã quyết định tăng độ khó bằng cách sau:

Đầu tiên, thầy đưa ra một dãy số nguyên gồm $n$ phần tử $B_1,B_2,...,B_n$.
Có tối đa $k$ lượt chỉnh sửa, mỗi lượt bạn được chọn một đoạn con các phần tử từ vị trí thứ $l$ đến vị trí thứ $r$ $(1 \le l \le r \le n)$ và thực hiện phép gán $A_i = A_i*B_i$ với $\forall i \in [l,r]$.

Yêu cầu: Đưa ra được độ cân bằng lớn nhất với tối đa $k$ lượt chỉnh sửa.

Hoa Quả Sơn đã phải bó cành trước bài toán mới này, bạn hãy giúp họ tìm kiếm câu trả lời.

Input: `watermelon.inp`

Dòng đầu tiên gồm hai số nguyên $n$ và $k$ $(1 \le n \le 10^5, 0 \le k \le 10)$.
Dòng thứ hai gồm $n$ số nguyên dương miêu tả dãy số nguyên $A_1, A_2, ..., A_n$ $(|A_i| \le 1000)$.
Dòng thứ ba gồm $n$ số nguyên dương miêu tả dãy số nguyên $B_1, B_2, ..., B_n$ $(|B_i| \le 10)$.

Output: `watermelon.out`

In ra một số nguyên duy nhất là độ cân bằng lớn nhất tìm được của dãy $A$ sau
khi sử dụng tối đa $k$ lượt chỉnh sửa.

Scoring:

Subtask $1$ $(15\%)$: $k = 0$.
Subtask $2$ $(15\%)$: $k = 1$ và $n \le 5000$.
Subtask $3$ $(20\%)$: $k = 1$.
Subtask $4$ $(25\%)$: $k = 2$.
Subtask $5$ $(25\%)$: Không ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

Sample Input 2

3 0
-4 -10 -8
2 2 -1

Sample Output 2

-4

Explanation:

Trong ví dụ thứ nhất, cách tối ưu nhất là chọn đoạn $[3, 4]$ để tác động. Như vậy dãy $A$ mới là $[-3, 4, 5, 4, -2]$. Vậy độ cân bằng của dãy này là $13$.
Trong ví dụ thứ $2$, khi $k = 0$, bạn không thực hiện lượt chỉnh sửa nào và đưa ra độ cân bằng của dãy $A$ ban đầu là $-4$.

BlueSky

Nộp bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 1G Input: bluesky.inp Output: bluesky.out

Cho mảng $a$ gồm $n$ phần tử nguyên $a_1,a_2,...,a_n$ và một số nguyên dương $k$.

Hàm $sum(l,r)$ được định nghĩa là tổng của các phần tử $a_i$ trong đoạn con từ $l$ tới $r$.

Hãy chọn ra $x$ đoạn con ($0 \le x \le k$ với $k$ cho trước) $[l_1,r_1], [l_2,r_2], ..., [l_x,r_x]$ thoả mãn $1 \le l_i \le r_i \le n$ với $\forall i \in [1,x]$ và $r_{i-1} < l_i$ với $\forall i \in [2,x]$ sao cho $\sum sum(l_i,r_i) \forall i \in [1,x]$ là lớn nhất. Nói cách khác, hãy chọn ra $x$ đoạn con không giao nhau sao cho tổng của chúng là lớn nhất.

Input: `bluesky.inp`

Dòng đầu tiên chứa hai số nguyên dương $n$ và $k$ $(1 \le k \le n \le 3\times 10^5)$
Dòng thứ hai gồm $n$ số nguyên: $a_1,a_2,...,a_n$ $(|a_i| \le 10^9)$.

Output: `bluesky.out`

In ra tổng lớn nhất tìm được.

Subtasks

Có $5\%$ số test ứng với $a_i \ge 0$.
Có $10\%$ số test ứng với chỉ có duy nhất một vị trí mà $a_i < 0$.
Có $15\%$ số test ứng với $k = 1$.
Có $15\%$ số test ứng với $1 \le k \le n \le 80$.
Có $15\%$ số test ứng với $1 \le k \le n \le 300$.
Có $20\%$ số test ứng với $1 \le k \le n \le 2000$.
$20\%$ số test còn lại không có điều kiện gì thêm.

Sample Input 1

6 1
1 -2 3 -1 5 -6

Sample Output 1

Sample Input 2

6 2
1 2 3 -10 5 6

Sample Output 2

Sample Input 3

6 4
-1 -2 -1 0 -5 -1

Sample Output 3

Con cáo và chùm nho

Nộp bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 1G Input: dincpath.inp Output: dincpath.out

Tiếp tục là Châu và câu chuyện hành trình trở thành thợ code của anh ấy. MrTee sau khi thấy Châu đã quá thợ nên đã gửi anh ấy cho thầy Hưng Cao dạy. Thử thách đầu tiên thầy Hưng giao cho Châu là Con cáo và chùm nho (không phải bài nhạc mà các bạn biết). Thử thách có nội dung như sau:

Cho chùm nho có $N$ quả và $M$ cành cây, mỗi cành cây nối 2 quả nào đó với nhau. Giữa 2 quả bất kì có thể có nhiều cành cây nối chúng (cây bị down). Cũng có thể có những quả có cành cây nối với chính nó. Đơn giản thì chùm nho là mô hình đồ thị $N$ đỉnh, $M$ cạnh.

Các quả nho được đánh số từ $1$ đến $N$. Quả thứ $i$ có độ cao là $A_i$. Độ dốc giữa cành cây nối giữa 2 quả được tính bằng giá trị tuyệt đối chênh lệch chiều cao giữa 2 quả nho. Ví dụ cành cây nối giữa 2 quả $x$ và $y$ sẽ có độ dốc là $|A_x - A_y|$.

Dù trong nhiều câu chuyện, cáo luôn là phản diện nhưng chúng là loài động vật thông minh. Ai cũng thích động vật thông minh và Châu và thầy Hưng cũng vậy. Để giúp con cáo lấy được chuỗi các quả nho xịn và nhiều nhất, Châu phải thiết kế 1 con đường leo cây siêu nhanh. Xuất phát từ 1 quả nho nào đó, đi đến các quả nho khác với điều kiện các quả nhỏ sau cao hơn quả nho trước, không những thế, độ dốc của cành cây sau cũng phải lớn hơn độ dốc của cành cây trước đó. Nghĩa là, nếu như Châu quyết định chọn một hành trình đi qua các quả nho theo thứ tự $P_1, P_2, ..., P_k$ thì hành trình đó sẽ phải thỏa mãn tính chất:

$0 < A_{P_2}-A_{P_1} < A_{P_3}-A_{P_2} < ... < A_{P_k}-A_{P_{k-1}}$

Như đã nói, để giúp con cáo, hành trình này cũng phải thỏa mãn việc nó có đi qua nhiều quả nho nhất. Ngoài ra thầy Hưng cũng muốn biết thêm có bao nhiêu cách đi như vậy để còn giật dây hành trình của con cáo.

Vì là thợ đặc cấp nên Châu dễ dàng vượt qua thử thách này và được dạy cho nhiều câu punchline như một phần thưởng.

Liệu bạn có thợ như Châu?

Yêu cầu:

Tìm đường đi qua nhiều quả nho nhất và thỏa mãn yêu cầu đề bài. Đồng thời tìm xem có bao nhiêu đường đi khác nhau đi qua nhiều quả nho nhất.

Input: `dincpath.inp`

Dòng đầu tiên chứa 2 số nguyên $N$ và $M$ $(1 \le N \le 3 * 10 ^ 5, 1 \le M \le 5 * 10^5)$.
Dòng thứ hai chứa độ cao của $N$ quả nho là $N$ số nguyên dương $A_1, A_2, ..., A_n$ $(1 \le A_i \le 10^9)$.
Dòng thứ $i$ trong số $M$ dòng tiếp theo chứa cặp số nguyên dương $(U_i, V_i)$ là chỉ số hai quả nho và là
hai đầu của cành cây thứ $i$ $(1 \le U_i, V_i \le N)$.

Output: `dincpath.out`

Dòng đầu tiên ghi ra một số nguyên là số lượng quả nho của hành trình tìm được.
Dòng thứ hai ghi ra một số nguyên là phần dư trong phép chia số lượng hành trình khác nhau tìm được cho $10^9 + 7$.

Subtasks

Có $20\%$ số test ứng với $N \le 20$.
Có $20\%$ số test khác ứng với $N \le 500$.
Có $20\%$ số test khác ứng với đồ thị tương ứng là một mạch thẳng (đồ thị dạng cây nhưng mỗi đỉnh chỉ có tối đa 2 cạnh).
Có $20\%$ số test khác ứng với $M = N - 1$, và các đỉnh trong đồ thị liên thông với nhau.
$20\%$ còn lại không có giới hạn gì thêm.

Sample Input 1

Sample Output 1

3
1

MarisaChain

Nộp bài

Điểm: 100 Thời gian: 1.5s Bộ nhớ: 1G Input: marisachain.inp Output: marisachain.out

Vào năn 2042, Crypto đã len lỏi vào mọi ngõ ngách của Ảo Tưởng Hương, lùa gà, úp bô, bơm thổi đầy đủ cả. Để theo kịp xu thế, Marisa đã tạo ra blockchain MarisaChain của riêng mình và phát hành token MarisaCoin. Mỗi người sẽ sở hữu cho mình một địa chỉ ví là một dãy các kí tự thập lục phân (các chữ cái từ a đến f và toàn bộ các chữ số). Khi muốn gửi token cho một người khác, cần biết được địa chỉ ví của đối phương. Ví dụ một địa chỉ ví là 2153e00f23fb927a94a49e29df0aaa57.

Địa chỉ ví có thể rất dài, gồm các kí tự không có quy luật, nên việc nhớ được toàn bộ địa chỉ ví là điều rất khó khăn. Vì thế, mọi người thường có xu hướng nhớ một tiền tố và một hậu tố của địa chỉ. Tuy nhiên, có thể có nhiều hơn một địa chỉ có tiến tố và hậu tố như vậy, dẫn đến việc gửi sai địa chỉ.

Trên MarisaChain hiện nay có $n$ địa chỉ đang hoạt động. Nhiệm vụ của bạn là xử lí $q$ truy vấn của người dùng, mỗi truy vấn gồm một xâu $S$ và $T$, hãy đếm số lượng địa chỉ có tiền tố là $S$ và hậu tố $T$ để giúp họ không chuyển token nhầm địa chỉ.

Input: Nhập vào từ file `marisachain.inp`

Dòng đầu tiên gồm hai số nguyên $n,q$.
$n$ dòng tiếp theo, mỗi dòng gồm một xâu $A$ là một địa chỉ ví trên MarisaChain.
$q$ dòng tiếp theo, mỗi dòng gồm hai xâu $S$ và $T$, là truy vấn của người dùng.

Output: Xuất ra file `marisachain.out`

In ra $q$ dòng, dòng thứ $i$ là đáp án cho truy vấn thứ $i$.

Điều kiện

Trong mọi test: $1 \le \sum |S|, \sum|T|, \sum|A| \le 10^6, 1 \le n,m,|S|,|T|,|A| \le 10^5$.
Subtask 1 ($10\%$ số điểm): $1 \le n,q, \sum |S|, \sum|T|, \sum|A| \le 100$.
Subtask 2 ($15\%$ số điểm): $1 \le n,q \le 5000$.
Subtask 3 ($25\%$ số điểm): $|S| = |T|$ trong mọi truy vấn.
Subtask 4 ($25\%$ số điểm): $1 \le n,q, \sum |S|, \sum|T|, \sum|A| \le 10^5$.
Subtask 5 ($25\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ

Input:

3 3
0000
abcd
a02d
a d
a cd
00 00

Output:

2
1
1