Chọn ĐTQG Đại học Sư phạm Hà Nội 2023

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Rút thăm trúng thưởng

Bờm tham gia trò chơi rút thăm trúng thưởng trong đêm hội Trăng rằm. Ban tổ chức chuẩn bị $k$ loại thẻ bài, các loại thẻ bài tương ứng ghi các giá trị từ $1$ đến $k$ , các thẻ được sắp xếp vào trong $2$ chiếc hộp như sau:

Hộp thứ nhất: chỉ chứa các loại thẻ bài có giá trị là số lẻ trong khoảng từ $1$ tới $k$ , số lượng mỗi loại thẻ không giới hạn.

Hộp thứ hai: chứa chứa các thẻ bài có giá trị là số chẵn trong khoảng từ $1$ tới $k$ , số lượng mỗi loại thẻ không giới hạn.

Theo thể lệ của Ban tổ chức, một người chơi sẽ được thực hiện $n$ lần rút thẻ. Các lượt rút thẻ theo thứ tự bắt đầu từ hộp thứ nhất tới hộp thứ hai và lặp lại quá trình đó.

Ví dụ: $k=4$ , $n=3$

Lượt thứ nhất: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị $1$ hoặc $3$ .

Lượt thứ hai: Người chơi rút thẻ trong hộp thứ hai có thể nhận được các thẻ bài có giá trị $2$ hoặc $4$ .

Lượt thứ ba: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị $1$ hoặc $3$ .

Ban tổ chức đưa ra một con số $m$ và người chơi sẽ nhận được quà nếu tổng số thẻ sau $n$ lần rút là một số chia hết cho $m$ .

Yêu cầu: Hãy tính giúp Bờm xem có bao nhiêu cách rút ra các thẻ bài để có thể nhận được thưởng.

Input

Ba số nguyên dương $n, k, m$ $(2 \leq n, k \leq 109, m \leq 100)$ .

Output

Một số nguyên dương là số cách rút thẻ thỏa mãn yêu cầu của Ban tổ chức. Vì kết quả rất lớn nên bạn chỉ cần đưa ra phần dư của đáp án khi chia cho $123456789$ .

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$n, k \leq 1000$
2	$30%$	$m$ lẻ, $n \leq 103$
3	$30%$	$n \leq 103$
4	$20%$	Không có ràng buộc gì thêm

Sample Input 1

3 4 4

Sample Output 1

Sample Input 2

3 2 4

Sample Output 2

Notes

Giải thích test ví dụ 1:

Có tất cả $8$ cách rút tất cả nhưng có $4$ cách rút thẻ có tổng chia hết cho $4$

Cách 1: 1 2 1

Cách 2: 1 4 3

Cách 3: 3 4 1

Cách 4: 3 2 3

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Hành trình du lịch

Sau chuỗi ngày ôn và thi mệt mỏi, Bờm quyết định du lịch đến đất nước Byteland. Đất nước xinh đẹp này có $n$ thành phố, các thành phố kết nối với nhau bởi $n-1$ con đường hai chiều. Con đường thứ $i$ nối từ thành phố $x$ đến thành phố $y$ có độ dài $w$ . Thêm nữa, qua quá trình khảo sát Bờm có lên thang điểm về độ đẹp cho mỗi thành phố. Độ đẹp của thành phố thứ $i$ được đánh giá là $a i$ .

Việc đi lại giữa các thành phố được thực hiện bằng xe buýt. Cách vận hành xe buýt ở đây cũng rất đặc biệt: Giả sử xe buýt đang ở thành phố $u$ , nó sẽ xác định tuyến đi tiếp theo bằng cách chọn một thành phố $v$ (khác $u$ ) có $a v - d(u,v)$ là lớn nhất. Trong đó $d(u,v)$ được định nghĩa là khoảng cách đi từ $u$ đến $v$ (nếu có nhiều thành phố thỏa mãn thì nó sẽ di chuyển đến thành phố có chỉ số nhỏ nhất). Và khi đã chọn được điểm đến là thành phố $v$ thì xe buýt sẽ đi thẳng từ $u$ đến $v$ mà không dừng ở các thành phố trung gian.

Yêu cầu: Cho $Q$ truy vấn, mỗi truy vấn có hai tham số $s, k$ ứng với việc Bờm xuất phát từ thành phố $s$ và di chuyển qua $k$ tuyến đường bằng xe buýt theo cách mô tả ở trên. Hãy cho biết, với mỗi truy vấn thì Bờm sẽ kết thúc chuyến đi ở thành phố nào?

Input

Dòng đầu chứa hai số nguyên dương $n, Q$ $(n, Q \leq 2 \times 105)$ là số thành phố và số truy vấn.

Dòng hai chứa $n$ số nguyên $a 1, a 2, \dots a n$ là vẻ đẹp của $n$ thành phố $(|a i | \leq 109)$ .

$n-1$ dòng tiếp theo dạng $x y w$ mô tả $n-1$ con đường $(1 \leq x, y \leq n, 0 < w \leq 109)$ .

$Q$ dòng tiếp là truy vấn dạng $s k$ : điểm xuất phát và số tuyến đường sẽ đi.

Output

Gồm $Q$ dòng, mỗi dòng in ra chỉ số thành phố Bờm sẽ kết thúc ở mỗi truy vấn.

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$n, Q \leq 200, k \leq 200$
2	$25%$	$n, Q \leq 2000$
3	$25%$	$k = 1$
4	$30%$	Không có ràng buộc gì thêm

Sample Input 1

Sample Output 1

Notes

Hành trình của tour của Bờm:

$1 \to 5$

$2 \to 3 \to 4 \to 5$

$3 \to 4 \to 5$

$5 \to 1$

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Tô màu cây

Cho một cây có $n$ đỉnh. Các đỉnh được đánh số từ $1$ đến $n$ và gốc của cây là đỉnh $1$ . Một số đỉnh của cây đã được tô màu đen, một số khác thì chưa được tô màu. Ta sẽ tìm cách tô màu cho tất cả các đỉnh.

Thao tác tô màu sẽ được thực hiện như sau: Chọn một đỉnh $u$ và tô tất cả các đỉnh $v$ thành màu đen nếu các điều kiện sau thỏa mãn:

Đỉnh $v$ nằm trong cây con gốc $u$ .

Khoảng cách giữa hai đỉnh chính xác là $i$ . Trong đó khoảng cách giữa hai đỉnh $u$ và $v$ là số cạnh nhỏ nhất để đi từ $u$ đến $v$ .

Chi phí để tô màu một đỉnh có khoảng cách $i$ là $c i$ . Tại một thao tác tô màu, nếu chọn đỉnh $u$ mà có nhiều hơn một đỉnh $v$ cùng có khoảng cách với đỉnh $u$ bằng $i$ thì các đỉnh này sẽ được tô màu cùng lúc với chi phí là $c i$ .

Yêu cầu : Tìm cách tô sao cho tất cả các đỉnh đều được tô thành màu đen với chi phí là nhỏ nhất.

Input

Dòng đầu chứa $n$ $(1 \leq n \leq 106)$ .

Dòng tiếp theo gồm $n$ số $c 0,c 1, \dots,c n-1$ $(c i \leq 109)$ , với $c i$ là chi phí để tô màu ở khoảng cách $i$ .

Dòng tiếp theo gồm $n$ số $a 1,a 2, \dots,a n$ . Trong đó $a i =0/1$ . Nếu $a i =0$ tương ứng là đỉnh $i$ chưa được tô màu, $a i =1$ là đỉnh đã được tô màu.

$n-1$ dòng tiếp theo, mỗi dòng gồm hai số $u,v$ thể hiện một cạnh của cây.

Output

Một dòng ghi một số là tổng chi phí để tô tất cả các nút thành màu đen.

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$n \leq 20$
2	$30%$	$n \leq 200$
3	$30%$	$n \leq 2000$
4	Còn lại	Không có ràng buộc gì thêm

Sample Input 1

Sample Output 1

Notes

Chọn đỉnh $1$ làm gốc, tô màu đỉnh $3$ và $4$ với khoảng cách $2$ , chi phí $1$ .

Sau đó tô đỉnh $1$ với khoảng cách $0$ , chi phí $10$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Hoán vị trộn

Cho hai dãy số nguyên dương độ dài $n$ : $a=(a 1,a 2, \dots,a n)$ và $b=(b 1,b 2, \dots,b n)$ . Biết rằng các phần tử của hai dãy số là các số nguyên dương, không nhất thiết là phân biệt, được lấy từ tập ${1,2, \dots,n}$ .

Đối với hai dãy đã cho, ta có thể thực hiện phép biến đổi sau đây: chọn hai chỉ số $i$ và $j$ với $1 \leq i \leq j \leq n$ , sau đó hoán đổi hai dãy con $a i,a i+1, \dots,a j$ và $b i,b i+1, \dots,b j$ của hai dãy cho nhau, ta thu được hai dãy mới:

$(a 1,a 2, \dots,a i-1,b i,b i+1, \dots,b j,a j+1,a j+2, \dots,a n)$

và:

$(b 1,b 2, \dots,b i-1,a i,a i+1, \dots,a j,b j+1,b j+2, \dots,b n)$ .

Như vậy, phép biến đổi nêu trên được xác định bởi cặp hai chỉ số $(i,j)$ .

Nếu sau khi thực hiện phép biến đổi như vậy có ít nhất một trong hai dãy thu được là hoán vị của ${1,2, \dots,n}$ , thì ta thu được một hoán vị trộn.

Yêu cầu : Hãy xác định xem có thể thu được hoán vị trộn bởi bao nhiêu cách.

Input

Dữ liệu gồm nhiều test có cấu trúc như sau:

Dòng đầu tiên là số $t$ $(t \leq 5)$ là số test. Sau đó là các test, mỗi test gồm:Dòng thứ nhất chứa số nguyên $n$ $(1 \leq n \leq 2 \cdot 105)$ .Dòng thứ hai chứa dãy số $a 1,a 2, \dots,a n$ $(a i \leq n)$ .Dòng thứ ba chứa dãy số $b 1,b 2, \dots,b n$ $(b i \leq n)$ .

Output

Gồm $t$ số nguyên tương ứng là số cách khác nhau có thể thu được hoán vị trộn nhờ thực hiện phép biến đổi đã nêu đối với hai dãy tương ứng trong dữ liệu vào.

Scoring

Subtask	Điểm	Ràng buộc
1	$30%$	$n \leq 100$
2	$30%$	$n \leq 5000$
3	Còn lại	$n \leq 200000$

Sample Input 1

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

Sample Output 1

8
3

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. Dãy đặc biệt

Cho hai dãy số nguyên cùng có $n$ phần tử $A=(a 1,a 2, \dots,a n)$ , $B=(b 1,b 2, \dots,b n)$ và một số nguyên dương $d$ . Gọi dãy số $i 1,i 2, \dots,i k$ là đặc biệt nếu:

$1 \leq i 1 < i 2 < \dots < i k \leq n$ ;

$|a i j -a i j-1 | \leq d$ với mọi $j=2, \dots,k$ ;

$|b i j -b i j-1 | \leq d$ với mọi $j=2, \dots,k$ .

Yêu cầu : Bạn hãy tìm dãy đặc biệt có nhiều phần tử nhất.

Input

Dòng đầu chứa hai số nguyên dương $n,d$ $(n \leq 105, d \leq 109)$ .

Dòng thứ hai chứa $n$ số nguyên $a 1,a 2, \dots,a n$ $(|a i | \leq 109)$ mô tả dãy $a$ .

Dòng thứ ba chứa $n$ số nguyên $b 1,b 2, \dots,b n$ $(|b i | \leq 109)$ mô tả dãy $b$ .

Output

Một số nguyên duy nhất là kích thước của dãy đặc biệt tìm được.

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$n \leq 20$
2	$20%$	$n \leq 2000$
3	$20%$	$n \leq 30000$
4	$20%$	$b 1 =b 2 = \dots =b n$
5	Còn lại	Không có điều kiện gì thêm

Sample Input 1

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

Sample Output 1

Sample Input 2

10 187
110 -187 554 -722 811 -930 346 24 933 132
113 72 -962 77 -242 -118 256 -759 -756 368

Sample Output 2

Notes

Rõ ràng, $(2,3,4,5)$ là dãy đặc biệt.

Trong ví dụ thứ hai, không tìm được cặp giá trị $(i,j)$ nào thỏa mãn được các điều kiện đề bài. Đáp số là $1$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 6. Đi tìm kho báu

Băng Mũ Rơm của Luffy đã đặt chân đến hòn đảo Laugh Tale, nơi chứa kho báu ONE PIECE. Luffy tìm thấy $n$ chiếc hộp, chiếc hộp thứ $i$ chứa các đồ có giá trị $c i$ . Trong tay Luffy có $k$ chiếc chìa khóa được đánh số từ $1$ đến $k$ . Chìa khóa thứ $i$ có thể được dùng để mở một trong hai chiếc hộp $a i$ hoặc $b i$ .

Mỗi chiếc hộp chỉ có thể được mở khóa một lần và không cần thiết phải dùng tất cả các chìa khóa.

Luffy chỉ được thực hiện $Q$ truy vấn, truy vấn thứ $i$ là yêu cầu thuộc một trong hai loại:

Bỏ đi chiếc chìa khóa thứ $p i$ ; các chìa khóa còn lại không được đánh số lại sau các truy vấn.

Thêm lại chiếc chìa khóa $p i$ đã bị bỏ đi trước đó; các chìa khóa còn lại không cần đánh số lại.

Yêu cầu : Hãy cho biết, sau khi thực hiện mỗi truy vấn, dùng các chìa khóa còn lại để mở hộp, với cách mở khóa hộp luôn tối ưu, tổng giá trị kho báu lớn nhất thu được từ các hộp được mở là bao nhiêu.

Input

Dòng đầu tiên chứa ba số nguyên dương $n,k,Q$ $(2 \leq n \leq 2 \cdot 105, 1 \leq k,Q \leq 2 \cdot 105)$ là số hộp kho báu, số chìa khóa và số truy vấn.

Dòng tiếp theo gồm $n$ số nguyên dương $c 1,c 2, \dots,c n$ $(c i \leq 109)$ , là giá trị của các hộp kho báu.

$k$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên dương $a i,b i$ $(1 \leq a i,b i \leq n, a i \neq b i)$ , mô tả chiếc chìa khóa thứ $i$ mở được hộp $a i,b i$ .

$Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả các truy vấn:1 p_i: Cho biết đây là truy vấn loại $1$ với chìa khóa bị bỏ đi là $p i$ $(1 \leq p i \leq n)$ .2 p_i: Cho biết đây là truy vấn loại $2$ với chìa khóa được thêm là $p i$ . Dữ liệu đảm bảo chìa khóa này đã được bỏ đi trước đó.

Output

Gồm $k$ dòng, dòng thứ $i$ gồm một số nguyên là tổng giá trị kho báu lớn nhất thu được sau khi thực hiện truy vấn thứ $i$ .

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$N,M,Q \leq 16$
2	$30%$	$N,M,Q \leq 2000$
3	$50%$	Không có ràng buộc gì thêm

Sample Input 1

Sample Output 1

Notes

Sau truy vấn thứ nhất, còn lại các chìa khóa $1,2,3$ . Ta có thể dùng chìa $1$ để mở hộp $2$ , chìa $2$ để mở hộp $3$ và chìa $3$ để mở hộp $1$ . Tổng giá trị của các hộp được mở là $9+5+7=21$ .

Sau truy vấn thứ hai, còn lại chìa khóa $2$ và $3$ . Ta có thể dùng chìa $2$ để mở hộp $3$ , chìa $3$ để mở hộp $1$ . Tổng giá trị của các hộp được mở là $9+7=16$ .

Sau truy vấn thứ ba, còn lại các chìa khóa $1,2,3$ . Giống truy vấn một, tổng giá trị của các hộp được mở là $9+5+7=21$ .

Sau truy vấn thứ tư, chỉ còn lại chìa khóa $1$ và $3$ . Tổng giá trị các hộp mở được là $9+7=16$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Cấu trúc đề và tiến độ