PVHOI 4 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

1. PVHOI 4 - I - MỘT CÚ LỪA

Điểm: 700 (p) Thời gian: 1.25s Bộ nhớ: 512M Input: i.inp Output: i.out

Lúc em chạm môi anh ta em có ngần ngại?

Có ngần ngại không hay miên man nhớ mãi?

Trả lời đi hương nước hoa thơm mùi gì chen giữa chúng ta

Anh trao em con tim, sao em trao cho anh... MỘT CÚ LỪA

La la la la la la LỪA...

(Một Cú Lừa – Bích Phương)

Chắc nhiều bạn chưa biết, ngoài công việc chính là bán trà sữa dạo, GSPVH còn có một trại nuôi LỪA siêu to khổng lồ.

Sở dĩ GSPVH nuôi LỪA là bởi, để có thể hoàn thành tốt công việc ra đề thi và dạy học – thị trường tiêu thụ trà sữa chính của GS, thì ngoài việc nuôi gà, kỹ năng lùa LỪA cũng vô cùng quan trọng. Người ra đề thi phải biết lùa LỪA thì mới có thể đưa thí sinh vào bẫy, để ban giámkhảo có thể có những tràng cười sảng khoái khi chứng kiến bài làm của thí sinh. Hẳn nhiều thế hệ sinh viên Việt Nam không thể quên bài L đề ICPC quốc gia 2017 hay bài G đề ICPC quốc gia 2018 – những cú LỪA đã đi vào lịch sử. Và biết đâu, ngay trong chính mùa PVHOI 4.0 này cũng có một cú LỪA siêu kinh điển như thế...

Trở lại với trang trại LỪA của GSPVH, nhờ chịu khó chăm nuôi, tâm huyết với đàn, giờ đây đàn LỪA của GSPVH đã phát triển đông đảo với $n$ con LỪA béo tốt, con LỪA thứ $i$ có khối lượng là $w_{i}$. Hôm nay, nhân ngày chủ nhật đầy nắng đẹp và gió mát, GSPVH quyết định dẫn đàn LỪA của mình đi chơi. GSPVH muốn dẫn đàn LỪA của mình sang bên kia sông, nơi có vườn hoa thơm ngát và tươi tắn. Nhưng vì kinh phí có hạn, GS chỉ thuê được một chiếc thuyền với tải trọng $c$ (nói cách khác, chiếc thuyền này chỉ có thể chở được khối lượng không quá $c$).

GSPVH sẽ tự tay chèo thuyền từng chuyến để đưa đàn LỪA này qua sông. Với mong muốn đưa đàn LỪA qua sông nhanh nhất có thể, GSPVH sử dụng chiến lược tham lam như sau:

Bước $1$: GSPVH sắp xếp các con LỪA chưa qua sông theo thứ tự giảm dần về khối lượng.
Bước $2$: GSPVH lần lượt xét các con LỪA theo thứ tự vừa sắp xếp. Với mỗi con LỪA, nếu khối lượng của nó cộng với tổng khối lượng các con LỪA đang trên thuyền không quá tải trọng $c$, GSPVH sẽ lập tức đưa con LỪA đó lên thuyền. Nói cách khác, GSPVH luôn ưu tiên đưa lên thuyền con LỪA có khối lượng lớn nhất có thể, đảm bảo rằng tổng khối lượng các con LỪA được đưa lên thuyền không vượt quá giới hạn khối lượng $c$ của thuyền.
Bước $3$: GSPVH lái thuyền qua bên kia bờ sông và đưa các còn LỪA trên thuyền lên bờ.
Bước $4$: Nếu vẫn còn ít nhất một con LỪA chưa được sang sông, GSPVH sẽ chèo thuyền quay lại bờ xuất phát rồi thực hiện lại từ bước $1$ để đưa các con LỪA khác lên thuyền. Quá trình này được lặp đi lặp lại cho tới khi toàn bộ đàn LỪA đều đã qua sông.

Chắc hẳn mọi người đều biết GSPVH là người thon gọn, bo đì đẹp, dáng chuẩn, nên khối lượng của GSPVH là không đáng kể. Lấy ví dụ, giả sử GSPVH có $n = 10$ con LỪA với khối lượng lần lượt là $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ và tải trọng của thuyền là $c = 38$, quá trình đưa đàn LỪA sang sông của GSPVH diễn ra như sau:

GSPVH đưa các con LỪA có khối lượng $29, 7$ và $2$ lên thuyền, lái qua sông rồi quay lại.
GSPVH đưa các con LỪA có khối lượng $23$ và $13$ lên thuyền, lái qua sông rồi quay lại.
GSPVH đưa các con LỪA có khối lượng $19$ và $17$ lên thuyền, lái qua sông rồi quay lại.
GSPVH đưa các con LỪA có khối lượng $11, 5$ và $3$ lên thuyền, lái qua sông. Tới thời điểm này, toàn bộ đàn LỪA $10$ con đều đã được đưa sang sông.

Như vậy, trong trường hợp này, GSPVH cần $4$ lượt chèo thuyền mới có thể đưa được toàn bộ đàn LỪA qua sông.

Do thời gian có hạn, GSPVH muốn đưa toàn bộ đàn LỪA qua sông với không quá $k$ lượt chèo thuyền. Các bạn hãy giúp GSPVH tìm ra tải trọng $c$ nhỏ nhất của thuyền để thực hiện được điều này.

Input

Dòng đầu tiên chứa số nguyên $\theta$ là số bộ dữ liệu. Tiếp sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
- Dòng đầu tiên là một dòng trống.
- Dòng thứ hai chứa hai số nguyên $n$ và $k$ $(1 \leq k \leq n \leq 20000)$ lần lượt là số con LỪA trong đàn LỪA của GSPVH và số lượt chèo thuyền tối đa để GSPVH đưa toàn bộ đàn LỪA sang sông.
- Dòng thứ ba chứa $n$ số nguyên $w_{1}, w_{2}, \ldots, w_{n}$ $(1 \leq w_{i} \leq 3000)$ là khối lượng các con LỪA.
Gọi $N$ là tổng giá trị của $n$ trong các bộ dữ liệu, dữ liệu vào đảm bảo $N \leq 100000$.

Output

Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là giới hạn khối lượng của thuyền $c$ nhỏ nhất để GSPVH có thể đưa toàn bộ đàn LỪA qua sông trong không quá $k$ lượt.

Scoring

Subtask $1$ ($11$ điểm): $n \leq 3$.
Subtask $2$ ($16$ điểm): $w_{i} \leq 2$.
Subtask $3$ ($18$ điểm): $n \leq 50$ và $N \leq 250$.
Subtask $4$ ($13$ điểm): $n \leq 2000$ và $N \leq 10000$.
Subtask $5$ ($12$ điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

3
7 3
2 2 7 1 9 9 7
6 6
1 1 2 3 5 8
5 1
1 4 9 16 25

Output

14
8
55

Note

Trong bộ dữ liệu thứ nhất:

Với tải trọng thuyền là $c = 14$, GSPVH chỉ cần $3$ lượt là có thể đưa toàn bộ đàn LỪA qua sông. Các con LỪA được đưa qua ở mỗi lượt lần lượt là $(9, 2, 2), (9, 1)$ và $(7, 7)$.
Với tải trọng thuyền là $c = 13$, GSPVH cần tới $4$ lượt mới có thể đưa toàn bộ đàn LỪA qua sông. Các con LỪA được đưa ở mỗi lượt là $(9, 2, 2), (9, 1), (7)$ và $(7)$.

Trong bộ dữ liệu thứ hai, GSPVH có thể đưa mỗi lượt một con LỪA sang sông, nên tải trọng thuyền chỉ cần đủ để chở con LỪA có khối lượng lớn nhất sang sông.

Trong bộ dữ liệu thứ ba, GSPVH cần đưa toàn bộ đàn LỪA sang sông chỉ trong $1$ lượt chèo thuyền, vì vậy tải trọng thuyền tối thiểu cần là tổng khối lượng của đàn LỪA.

2. PVHOI 4 - II - THỨ TỰ TỪ ĐIỂN

Điểm: 700 (p) Thời gian: 3.0s Bộ nhớ: 512M Input: II.INP Output: II.OUT

Cho dãy số $a_{1}, a_{2}, \ldots, a_{n}$ và hai số $k$ và $s$. Bạn cần đếm số dãy số $b_{1}, b_{2}, \ldots, b_{n}$ thoả mãn các điều kiện sau:

$b_{i} \in \{1, 2, \ldots, s\} \ \forall\ 1 \leq i \leq n$.
Có chính xác $k$ cặp chỉ số $(l, r)$ sao cho $1 \leq l \leq r \leq n$ và dãy số $a_{l}, a_{l + 1}, \ldots, a_{r − 1}, a_{r}$ có thứ tự từ điển nhỏ hơn dãy số $b_{l}, b_{l + 1}, \ldots, b_{r − 1}, b_{r}$.

Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số dãy số thoả mãn khi chia cho $20215201314$.

Nhắc lại, dãy số $x_{1}, x_{2}, \ldots, x_{m}$ có thứ tự từ điển nhỏ hơn dãy số $y_{1}, y_{2}, \ldots, y_{m}$ khi và chỉ khi tồn tại chỉ số $\alpha$ sao cho:

$1 \leq \alpha \leq m, x_{\alpha} < y_{\alpha}$, và
$x_{\beta} = y_{\beta} \ \forall \ 1 \leq \beta \leq \alpha − 1$.

Input

Dòng đầu tiên chứa ba số nguyên $n, k$ và $s$ $(1 \leq n \leq 2014, 0 \leq k \leq 9213, 1 \leq s \leq 902535)$.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \ldots, a_{n}$ $(1 \leq a_{i} \leq s)$.

Output

Gồm một số nguyên duy nhất là phần dư của số dãy số tìm được khi chia cho $20215201314$.

Scoring

Subtask $1$ ($10$ điểm): $n \leq 8$ và $s \leq 4$.
Subtask $2$ ($10$ điểm): $n \leq 12$.
Subtask $3$ ($14$ điểm): $n \leq 97$.
Subtask $4$ ($12$ điểm): $k = 0$.
Subtask $5$ ($12$ điểm): $k \leq 5 \times n$ và $a_{1} = a_{2} = \ldots = a_{n} = 1$.
Subtask $6$ ($12$ điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

4 6 3
2 3 2 1

Output

Note

Trong ví dụ trên, có tất cả $7$ dãy số thoả mãn là $(2, 3, 3, 1), (3, 1, 2, 2), (3, 1, 2, 3), (3, 1, 3, 1), (3, 2, 2, 2), (3, 2, 2, 3)$ và $(3, 2, 3, 1)$.
Dãy số $(2, 3, 3, 1)$ thoả mãn vì ở đó có chính xác $6$ cặp chỉ số $(l, r)$ thoả mãn dãy số $a_{l}, a_{l + 1}, \ldots, a_{r − 1}, a_{r}$ có thứ tự từ điển nhỏ hơn dãy số $b_{l}, b_{l + 1}, \ldots, b_{r − 1}, b_{r}$. Đó là các cặp:

$l = 1, r = 3$: $(2, 3, 2) < (2, 3, 3)$.
$l = 1, r = 4$: $(2, 3, 2, 1) < (2, 3, 3, 1)$.
$l = 2, r = 3$: $(3, 2) < (3, 3)$.
$l = 2, r = 4$: $(3, 2, 1) < (3, 3, 1)$.
$l = 3, r = 3$: $(2) < (3)$.
$l = 3, r = 4$: $(2, 1) < (3, 1)$.

Dãy số $(3, 1, 3, 1)$ thoả mãn vì ở đó có chính xác $6$ cặp chỉ số $(l, r)$ thoả mãn các điều kiện ở trên:

$l = 1, r = 1$: $(2) < (3)$.
$l = 1, r = 2$: $(2, 3) < (3, 1)$.
$l = 1, r = 3$: $(2, 3, 2) < (3, 1, 3)$.
$l = 1, r = 4$: $(2, 3, 2, 1) < (3, 1, 3, 1)$.
$l = 3, r = 3$: $(2) < (3)$.
$l = 3, r = 4$: $(2, 1) < (3, 1)$.

3. PVHOI 4 - III - ĐỊNH CHIỀU ĐỒ THỊ

Điểm: 600 (p) Thời gian: 1.5s Bộ nhớ: 512M Input: iii.inp Output: iii.out

Cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Các đỉnh được đánh số từ $1$ đến $n$ và các cạnh được đánh số từ $1$ đến $m$. Cạnh thứ $i$ nối hai đỉnh $u_{i}$ và $v_{i}$.

Bạn cần định chiều đồ thị này để biến từ đồ thị vô hướng thành đồ thị có hướng. Nói cách khác, với cạnh thứ $i$ trong số $m$ cạnh của đồ thị được cho, bạn cần biến nó thành cung có hướng $u_{i} \rightarrow v_{i}$ hoặc cung có hướng $v_{i} \rightarrow u_{i}$.

Sau khi định chiều, bạn muốn số cặp đỉnh $(x, y)$ thoả mãn $1 \leq x, y \leq n, \sqrt{\dfrac{x^{2} + y^{2}}{2}} > \dfrac{2}{\dfrac{1}{x} + \dfrac{1}{y}}$ và trên đồ thị có đường đi từ $x$ đến $y$ là lớn nhất. Lưu ý rằng $(x, y)$ và $(y, x)$ được tính là hai cặp khác nhau, và việc có đường đi từ $x$ đến $y$ không đảm bảo rằng sẽ có đường đi từ $y$ đến $x$.

Hãy tìm số cặp đỉnh $(x, y)$ thoả mãn điều kiện trên lớn nhất có thể và chỉ ra một cách định chiều cho ra số cặp này.

Input

Dòng đầu tiên chứa hai số nguyên $\theta$ và $\tau$ lần lượt là số thứ tự của subtask chứa test này và số bộ dữ liệu có trong file dữ liệu. Sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
- Dòng đầu tiên là một dòng trống.
- Dòng thứ hai chứa hai số nguyên $n$ và $m$ $(1 \leq n \leq 80000, 1 \leq m \leq 350000)$ lần lượt là số đỉnh và số cạnh của đồ thị.
- Trong $m$ dòng còn lại, dòng thứ $i$ chứa hai số nguyên $u_{i}$ và $v_{i}$ $(1 \leq u_{i}, v_{i} \leq n)$ là hai đỉnh được nối bởi cạnh thứ $i$.
Gọi $N$ là tổng giá trị của $n$ trong tất cả các bộ dữ liệu và $M$ là tổng giá trị của $m$ trong tất cả các bộ dữ liệu, dữ liệu vào đảm bảo $N \leq 24 \times 10^{4}$ và $M \leq 105 \times 10^{4}$.

Output

Với mỗi bộ dữ liệu, ghi ra kết quả trên một dòng gồm số nguyên $k$ $(0 \leq k \leq n \times (n − 1))$ thể hiện số cặp đỉnh $(x, y)$ tối đa thoả mãn điều kiện ở trên; theo sau là xâu ký tự $s$ chứa chính xác $m$ ký tự F hoặc B thể hiện một phương án định chiều. Ký tự thứ $i$ của xâu $s$ là F cho biết bạn sẽ định chiều cạnh thứ $i$ theo hướng $u_{i} \rightarrow v_{i}$; ngược lại, nếu bạn định chiều cạnh thứ $i$ theo hướng $v_{i} \rightarrow u_{i}$, ký tự thứ $i$ của xâu $s$ là B.
Nếu có nhiều phương án định chiều tối ưu, bạn được phép in ra một phương án bất kỳ.

Score

Với mỗi test, bạn được $0$ điểm nếu file kết quả vi phạm ít nhất một trong các điều sau:

Có dòng khác rỗng ngoại trừ $\tau$ dòng đầu tiên.
Có ít nhất một trong $\tau$ dòng đầu tiên không có dạng $k$ $s$.
Có ít nhất một giá trị $k$ không thuộc đoạn $[0, n \times (n − 1)]$.
Có ít nhất một xâu $s$ có độ dài khác $m$ hoặc chứa ký tự không phải F hay B.

Ngược lại, gọi $\rho$ là số bộ dữ liệu bạn cho ra chính xác số cặp đỉnh tối đa và đưa ra một phương án định chiều chính xác, $\epsilon$ là số bộ dữ liệu bạn cho ra chính xác số cặp đỉnh tối đa nhưng chưa có phương án định chiều chính xác, và $\Omega$ là số điểm tối đa của test; điểm số của bạn trong test được tính bởi công thức:
$\left(\left(\dfrac{\rho + \epsilon}{\tau}\right)^{\pi} + \left(\dfrac{\rho}{\tau}\right)^{\epsilon}\right) \times \dfrac{\Omega}{2}$

Điểm của bài là tổng điểm đạt được trong tất cả các test. Điểm tối đa của mỗi test là như nhau. Điểm tối đa của bài là $60$.

Scoring

Subtask $1$ ($11$ điểm): $m \leq 16$ và $M \leq 48$.
Subtask $2$ ($12$ điểm): Trong đồ thị ban đầu, mỗi đỉnh kề với tối đa hai đỉnh khác.
Subtask $3$ ($13$ điểm): $m = n − 1$ và $1 \leq u_{i} < v_{i} = i + 1 \forall 1 \leq i \leq m$.
Subtask $4$ ($14$ điểm): $n \leq 5000$ và $N \leq 15000$.
Subtask $5$ ($10$ điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

9 FFBB
6 FBF

Note

Hình vẽ sau mô tả đồ thị trong bộ dữ liệu đầu tiên:
Có $9$ cặp đỉnh $(x, y)$ có đường đi từ $x$ tới $y$ là: $(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)$.
Hình vẽ sau mô tả đồ thị trong bộ dữ liệu thứ hai:
Có $6$ cặp đỉnh $(x, y)$ có đường đi từ $x$ tới $y$ là: $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$.

4. PVHOI 4 - IV - FAKER HỒI SINH – T1 VÔ ĐỊCH CHUNG KẾT THẾ GIỚI

Điểm: 700 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: iv.inp Output: iv.out

Sau khi huỷ diệt Weibo Gaming với tỷ số $3 – 0$, T1 đã chính thức lần thứ tư lên ngôi vô địch chung kết thế giới. $7$ năm mòn mỏi chờ đợi của các Tcon đã khép lại trong quả ngọt, giờ là lúc để chúng ta cùng chia vui và chứng kiến các tình yêu ngự trị trên ngai vàng thế giới. Riêng với Faker, màn hạ đo ván The Shy là lời tuyên bố rõng rạc và đanh thép: chúa chỉ có $1$ mà thôi!

Một trong những yếu tố khiến T1 dễ dàng nghiền nát Weibo Gaming là những màn cấm chọn cân não. Với bể tướng khủng của Gumayusi và Keria, họ sẵn sàng chọn cuối để có những lượt lựa chọn khắc chế mạnh, qua đó khiến đối thủ phải chịu thua dù ván đấu chưa diễn ra phút nào. Nhân ngày T1 đăng quang, chúng ta hãy cùng giải một bài toán về việc cấm chọn này nhé.

Lưu ý rằng bài toán này chỉ được lấy ý tưởng từ việc cấm chọn trong bộ môn Liên Minh Huyền Thoại, chứ hoàn toàn không giống với trò chơi thực. Bởi vậy bạn không cần chơi Liên Minh để làm được bài này, mà có chơi nhiều cũng chưa chắc làm được bài toán này đâu nha. À nhưng mà có một điều chắc chắn là, nếu bạn không chơi Liên Minh mà thay vào đó chơi Liên Quân á, thì bạn sẽ không có giải quốc gia đâu hihi. Vì tương lai có giải quốc gia, hãy nói không với Liên Quân nhé!

Bể tướng của Liên Minh Huyền Thoại có $n$ vị tướng được đánh số từ $1$ đến $n$. Vị tướng thứ $i$ có chỉ số sức mạnh là $s_{i}$. Đội chọn được tướng có chỉ số sức mạnh cao sẽ càng có lợi thế trong ván đấu. Hai đội, gọi là đội xanh và đội đỏ, tham gia loạt cấm chọn. Trước khi loạt cấm chọn bắt đầu, trọng tài công bố thông tin về loạt cấm chọn: sẽ có tất cả $m$ lượt chơi, mỗi lượt sẽ được thực hiện bởi một trong hai đội xanh hoặc đỏ, và lượt đó sẽ hoặc là lượt cấm hoặc là lượt chọn. Mỗi lượt chơi thuộc loại nào và do đội nào thực hiện là cố định và được trọng tài thông báo ngay từ đầu. Sau đó, lần lượt các lượt chơi diễn ra. Tại mỗi lượt, đội thực hiện lượt đó đưa ra quyết định cho mình. Luật chơi cụ thể như sau:

Nếu lượt hiện tại là lượt chọn, đội thực hiện lượt này phải chọn một vị tướng trong $n$ vị tướng thuộc bể tướng của Liên Minh Huyền Thoại. Vị tướng này sẽ được coi là thuộc về đội thực hiện lượt chọn này.
Nếu lượt hiện tại là lượt cấm, đội thực hiện lượt này có thể cấm một trong $n$ vị tướng hoặc không cấm vị tướng nào. Vị tướng bị cấm, nếu có, sẽ không thuộc về bất kỳ đội nào. Việc cấm này chỉ nhằm mục đích ngăn cản đối phương chọn được vị tướng này trong các lượt tiếp theo. Nếu không có vị tướng nào bị cấm, lượt cấm này coi như bị bỏ qua.
Mỗi vị tướng chỉ được xuất hiện tối đa một lần trong suốt cả loạt cấm chọn. Nói cách khác, nếu một vị tướng đã được chọn hay bị cấm đi bởi một đội nào đó, nó chắc chắn sẽ không thể được chọn hay bị cấm đi bởi bất kỳ đội nào trong tương lai.

Để có được lợi thế trong ván đấu, cả hai đội đều muốn đội mình có được những vị tướng mạnh nhất còn đối phương có được những vị tướng yếu nhất. Nói cách khác, gọi $B$ là tổng sức mạnh của những vị tướng thuộc về đội xanh, $R$ là tổng sức mạnh của những vị tướng thuộc về đội đỏ; đội xanh mong muốn giá trị $B − R$ lớn nhất có thể, đội đỏ cực tiểu hoá giá trị $B − R$.

Hãy xác định giá trị $B − R$ sau khi toàn bộ $m$ lượt chơi của loạt cấm chọn kết thúc, biết rằng cả hai đội đều rất thông minh, đều biết đối thủ rất thông minh, đều biết đối thủ biết mình rất thông minh,...

Input

Dòng đầu tiên chứa hai số nguyên $\theta$ và $\tau$ lần lượt là số thứ tự của subtask chứa test này và số bộ dữ liệu có trong file dữ liệu. Sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
- Dòng đầu tiên là một dòng trống.
- Dòng thứ hai chứa hai số nguyên $n$ và $m$ $(1 \leq n \leq 10^{4}, 1 \leq m \leq 22, m \leq n)$ lần lượt số vị tướng trong bể tướng của Liên Minh Huyền Thoại và số lượt chơi trong loạt cấm chọn.
- Dòng thứ ba chứa $n$ số nguyên $s_{1}, s_{2}, \ldots, s_{n}$ $(1 \leq si \leq 10^{8})$ là sức mạnh của các vị tướng.
- Trong $m$ dòng cuối cùng, dòng thứ $i$ mô tả lượt chơi thứ $i$ của loạt cấm chọn bởi một chữ cái là b hoặc p và một số nguyên là $1$ hoặc $2$. Nếu chữ cái là b, lượt thứ $i$ là lượt cấm; nếu chữ cái là p, lượt thứ $i$ là lượt chọn. Nếu số nguyên là $1$, đội xanh sẽ thực hiện lượt này; nếu số nguyên là $2$, đội đỏ sẽ thực hiện lượt này.
- Dữ liệu vào đảm bảo mỗi đội có ít nhất một lượt chọn, số lượt cấm của hai đội bằng nhau và số lượt chọn của hai đội bằng nhau.
Gọi $N$ là tổng giá trị của $n$ trong tất cả các bộ dữ liệu và $M$ là tổng giá trị của $m$ trong tất cả các bộ dữ liệu, dữ liệu vào đảm bảo $N \leq 3 \times 10^{4}$ và $M \leq 50$.

Output

Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là giá trị $B − R$ sau khi loạt cấm chọn kết thúc.

Scoring

Subtask $1$ ($8.4$ điểm): Tất cả các lượt chơi đều là lượt chọn.
Subtask $2$ ($9.8$ điểm): Tất cả $\dfrac{m}{2}$ lượt chơi đầu tiên đều thuộc về đội xanh.
Subtask $3$ ($14$ điểm): $s_{i} \leq 5$.
Subtask $4$ ($12.6$ điểm): $m \leq 4$.
Subtask $5$ ($13.3$ điểm): $m \leq 16$.
Subtask $6$ ($11.9$ điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

3
0

Note

Trong bộ dữ liệu thứ nhất, loạt cấm chọn có $m = 4$ lượt chơi lần lượt là: đội xanh cấm $\rightarrow$ đội đỏ cấm $\rightarrow$ đội xanh chọn $\rightarrow$ đội đỏ chọn.
Do đội xanh được chọn trước, ở lượt thứ hai, đội đỏ bắt buộc phải cấm đi vị tướng có sức mạnh $8$ nhằm ngăn đội xanh chọn nó ở lượt thứ ba. Đội xanh quyết định bỏ qua lượt cấm đầu tiên. Cuối cùng đội xanh chọn vị tướng có sức mạnh $4$, đội đỏ chọn vị tướng có sức mạnh $1$. Ta có $B − R = 4 − 1 = 3$.
Trong bộ dữ liệu thứ hai, mọi lượt chơi đều là lượt chọn. Do đó mỗi đội khi tới lượt của mình đều chọn vị tướng có sức mạnh lớn nhất còn sót lại. Vì vậy $B − R = (13 + 5) − (11 + 7) = 0$.

5. PVHOI 4 - V - CÂY CƠ BẢN

Điểm: 700 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: v.inp Output: v.out

Cho một cây gồm $n$ đỉnh, các đỉnh được đánh số từ $1$ đến $n$. Đỉnh $1$ là gốc của cây. Với các đỉnh còn lại, đỉnh thứ $i$ có cha là đỉnh $p_{i}$. Mỗi đỉnh trên cây có ba loại giá trị; các loại giá trị này của đỉnh thứ $i$ được ký hiệu là $w_{i}, b_{i}$ và $g_{i}$. Bạn được cho một số nguyên $t$.

Bạn cần chọn ra một đỉnh $r$ cùng một dãy các đỉnh $s_{1}, s_{2}, \ldots, s_{k}$ thoả mãn các điều kiện dưới đây:

Các đỉnh $s_{1}, s_{2}, \ldots, s_{k}$ là $k$ đỉnh đôi một phân biệt thuộc cây con gốc $r$ ($k$ đỉnh này có thể chứa hoặc không chứa đỉnh $r$).
$w_{s_{1}} + w_{s_{2}} + \ldots + w_{s_{k}} \leq t$.
Giá trị $b_{r} + k^{2}$ là lớn nhất có thể.
Nếu có nhiều phương án thoả mãn mọi điều kiện trên, ta chọn phương án có $k$ nhỏ nhất.
Nếu có nhiều phương án thoả mãn mọi điều kiện trên, ta chọn phương án có dãy
$(g_{s_{1}}, g_{s_{2}}, \ldots, g_{s_{k}})$ có thứ tự từ điển nhỏ nhất.

Nhắc lại, dãy số $x_{1}, x_{2}, \ldots, x_{m}$ có thứ tự từ điển nhỏ hơn dãy số $y_{1}, y_{2}, \ldots, y_{m}$ khi và chỉ khi tồn tại chỉ số $\alpha$ sao cho:

$1 \leq \alpha \leq m, x_{\alpha} < y_{\alpha}$, và
$x_{\beta} = y_{\beta} \forall 1 \leq \beta \leq \alpha − 1$.

Input

Dòng đầu tiên chứa hai số nguyên $\theta$ và $\tau$ lần lượt là số thứ tự của subtask chứa test này và số bộ dữ liệu có trong file dữ liệu. Sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
- Dòng đầu tiên là một dòng trống.
- Dòng thứ hai chứa hai số nguyên $n$ và $t$ $(1 \leq n \leq 2 \times 10^{5}, 1 \leq t \leq 10^{17})$.
- Dòng thứ ba chứa $n − 1$ số nguyên $p_{2}, p_{3}, \ldots, p_{n}$ $(1 \leq p_{i} < i)$.
- Dòng thứ tư chứa $n$ số nguyên $w_{1}, w_{2}, \ldots, w_{n}$ $(1 \leq w_{i} \leq 10^{7})$.
- Dòng thứ năm chứa $n$ số nguyên $b_{1}, b_{2}, \ldots, b_{n}$ $(1 \leq b_{i} \leq 10^{11})$.
- Dòng thứ sáu chứa $n$ số nguyên $g_{1}, g_{2}, \ldots, g_{n}$ $(1 \leq g_{i} \leq 10^{13})$.
Gọi $N$ là tổng giá trị của $n$ trong tất cả các bộ dữ liệu, dữ liệu vào đảm bảo $N \leq 10_{6}$.

Output

Với mỗi bộ dữ liệu, ghi ra kết quả trên hai dòng:
- Dòng đầu tiên chứa hai số nguyên $b_{r} + k^{2}$ và $k$.
- Dòng thứ hai chứa $k$ số nguyên $g_{s_{1}}, g_{s_{2}}, \ldots, g_{s_{k}}$.

Scoring

Subtask $1$ ($12$ điểm): $n \leq 20$ và $N \leq 10^{2}$.
Subtask $2$ ($10$ điểm): $n \leq 2000$ và $N \leq 10^{4}$.
Subtask $3$ ($8$ điểm): $w_{1} = w_{2} = \ldots = w_{n}$.
Subtask $4$ ($9$ điểm): $b_{1} = b_{2} = \ldots = b_{n}$.
Subtask $5$ ($13$ điểm): $g_{1} = g_{2} = \ldots = g_{n}$.
Subtask $6$ ($11$ điểm): $p_{i} = i − 1$ với mọi $2 \leq i \leq n$.
Subtask $7$ ($7$ điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

1 1

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

Output

15 3
3 4 5

Note

Ta chọn $r = 3, k = 3$ và $s_{1} = 11, s_{2} = 10, s_{3} = 9$. Khi đó:

$9, 10, 11$ đều thuộc cây con gốc $3$.
$w_{9} + w_{10} + w_{11} = 6 \leq 7 = t$.
$b_{3} + 3^{2} = 15$.
$(g_{11}, g_{10}, g_{9}) = (3, 4, 5)$.Cho một cây gồm $n$ đỉnh, các đỉnh được đánh số từ $1$ đến $n$. Đỉnh $1$ là gốc của cây. Với các đỉnh còn lại, đỉnh thứ $i$ có cha là đỉnh $p_{i}$. Mỗi đỉnh trên cây có ba loại giá trị; các loại giá trị này của đỉnh thứ $i$ được ký hiệu là $w_{i}, b_{i}$ và $g_{i}$. Bạn được cho một số nguyên $t$.

Bạn cần chọn ra một đỉnh $r$ cùng một dãy các đỉnh $s_{1}, s_{2}, \ldots, s_{k}$ thoả mãn các điều kiện dưới đây:

Các đỉnh $s_{1}, s_{2}, \ldots, s_{k}$ là $k$ đỉnh đôi một phân biệt thuộc cây con gốc $r$ ($k$ đỉnh này có thể chứa hoặc không chứa đỉnh $r$).
$w_{s_{1}} + w_{s_{2}} + \ldots + w_{s_{k}} \leq t$.
Giá trị $b_{r} + k^{2}$ là lớn nhất có thể.
Nếu có nhiều phương án thoả mãn mọi điều kiện trên, ta chọn phương án có $k$ nhỏ nhất.
Nếu có nhiều phương án thoả mãn mọi điều kiện trên, ta chọn phương án có dãy
$(g_{s_{1}}, g_{s_{2}}, \ldots, g_{s_{k}})$ có thứ tự từ điển nhỏ nhất.

Nhắc lại, dãy số $x_{1}, x_{2}, \ldots, x_{m}$ có thứ tự từ điển nhỏ hơn dãy số $y_{1}, y_{2}, \ldots, y_{m}$ khi và chỉ khi tồn tại chỉ số $\alpha$ sao cho:

$1 \leq \alpha \leq m, x_{\alpha} < y_{\alpha}$, và
$x_{\beta} = y_{\beta} \forall 1 \leq \beta \leq \alpha − 1$.

Input

Dòng đầu tiên chứa hai số nguyên $\theta$ và $\tau$ lần lượt là số thứ tự của subtask chứa test này và số bộ dữ liệu có trong file dữ liệu. Sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
- Dòng đầu tiên là một dòng trống.
- Dòng thứ hai chứa hai số nguyên $n$ và $t$ $(1 \leq n \leq 2 \times 10^{5}, 1 \leq t \leq 10^{17})$.
- Dòng thứ ba chứa $n − 1$ số nguyên $p_{2}, p_{3}, \ldots, p_{n}$ $(1 \leq p_{i} < i)$.
- Dòng thứ tư chứa $n$ số nguyên $w_{1}, w_{2}, \ldots, w_{n}$ $(1 \leq w_{i} \leq 10^{7})$.
- Dòng thứ năm chứa $n$ số nguyên $b_{1}, b_{2}, \ldots, b_{n}$ $(1 \leq b_{i} \leq 10^{11})$.
- Dòng thứ sáu chứa $n$ số nguyên $g_{1}, g_{2}, \ldots, g_{n}$ $(1 \leq g_{i} \leq 10^{13})$.
Gọi $N$ là tổng giá trị của $n$ trong tất cả các bộ dữ liệu, dữ liệu vào đảm bảo $N \leq 10_{6}$.

Output

Với mỗi bộ dữ liệu, ghi ra kết quả trên hai dòng:
- Dòng đầu tiên chứa hai số nguyên $b_{r} + k^{2}$ và $k$.
- Dòng thứ hai chứa $k$ số nguyên $g_{s_{1}}, g_{s_{2}}, \ldots, g_{s_{k}}$.

Scoring

Subtask $1$ ($12$ điểm): $n \leq 20$ và $N \leq 10^{2}$.
Subtask $2$ ($10$ điểm): $n \leq 2000$ và $N$ \leq $10^{4}$.
Subtask $3$ ($8$ điểm): $w_{1} = w_{2} = \ldots = w_{n}$.
Subtask $4$ ($9$ điểm): $b_{1} = b_{2} = \ldots = b_{n}$.
Subtask $5$ ($13$ điểm): $g_{1} = g_{2} = \ldots = g_{n}$.
Subtask $6$ ($11$ điểm): $p_{i} = i − 1$ với mọi $2 \leq i \leq n$.
Subtask $7$ ($7$ điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

1 1

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

Output

15 3
3 4 5

Note

Ta chọn $r = 3, k = 3$ và $s_{1} = 11, s_{2} = 10, s_{3} = 9$. Khi đó:

$9, 10, 11$ đều thuộc cây con gốc $3$.
$w_{9} + w_{10} + w_{11} = 6 \leq 7 = t$.
$b_{3} + 3^{2} = 15$.
$(g_{11}, g_{10}, g_{9}) = (3, 4, 5)$.

6. PVHOI 4 - VI - PHAO CHUỐI

Điểm: 600 (p) Thời gian: 3.5s Bộ nhớ: 512M Input: vi.inp Output: vi.out

Các bạn đã tham gia trại hè Tin học Miền Trung – Tây Nguyên tại Quy Nhơn vừa qua hẳn không thể quên Phao Chuối – trò chơi mạo hiểm thử thách sự không sợ sóng biển làm khiếp sợ vị giáo sư đáng kính của chúng ta. Nhưng nay GSPVH đã khôn lớn, trưởng thành, không còn là đứa con nít $9475$ ngày tuổi hôm nào, nên GSPVH quyết định cùng các bạn học sinh Quảng Ngãi đi trải nghiệm phao chuối một lần nữa.

Chiếc phao chuối tại Lý Sơn lần này có $n$ vị trí ngồi, các vị trí ngồi được đánh số từ $1$ đến $n$ theo thứ tự từ đầu tới đuôi: vị trí thứ $1$ ở đầu chuối, vị trí thứ $n$ ở đuôi chuối và với mọi $1 \leq i \leq n − 1$, vị trí thứ $i$ và thứ $i + 1% ở cạnh nhau.

Do đã tìm hiểu rất kỹ chiếc phao chuối trước chuyến đi, GSPVH nhận ra rằng, mỗi vị trí ngồi có một độ an toàn nhất định và không có hai vị trí ngồi nào có cùng độ an toàn. Nhờ đó, độ an toàn của $n$ vị trí ngồi có thể được biểu diễn bởi một hoán vị $p_{1}, p_{2}, \ldots, p_{n}$ của các số nguyên từ $1$ đến $n$. Vị trí ngồi thứ $i$ an toàn hơn vị trí ngồi thứ $j$ khi và chỉ khi $p_{i} < p_{j}$; vị trí $b$ có $p_{b} = 1$ là vị trí ngồi an toàn nhất, vị trí $w$ có $p_{w} = n$ là vị trí kém an toàn nhất. Cũng vì rất am hiểu về phao chuối, GSPVH tìm ra vị trí ngồi ưa thích của mình là vị trí $f$.

GSPVH dẫn theo $n − 1$ bạn học sinh của trường chuyên Lê Khiết đi chơi phao chuối. Coi GSPVH là người số $1$ và $n − 1$ bạn còn lại được đánh số từ $2$ đến $n$. Toàn bộ $n$ người sẽ lần lượt bước lên phao chuối và ngồi vào một vị trí nào đó, quy trình chọn vị trí ngồi của nhóm người như sau:

Trước hết, toàn bộ $n$ vị trí trên phao chuối đều trống.
Đầu tiên, GSPVH (người thứ $1$) ngồi vào vị trí ưa thích của mình là vị trí thứ $f$.
Tiếp theo, lần lượt các bạn từ bạn thứ $2$ đến bạn thứ $n$ chọn cho mình một vị trí trên phao chuối để ngồi. Tất cả các bạn đều chọn vị trí ngồi theo chiến lược sau:
- Mỗi bạn luôn ngồi vào một vị trí còn trống tại thời điểm đó.
- Mỗi bạn luôn ngồi vào một vị trí bên cạnh một vị trí đã có người ngồi trước đó.
- Mỗi bạn luôn ngồi vào vị trí an toàn nhất trong các vị trí thoả mãn hai điều kiện trên.

Có thể thấy, sau cú lật thuyền xưa kia, ngay cả những bạn sinh ra từ biển cũng còn rén, luôn chọn cho mình chỗ an toàn nhất và phải bên cạnh một người để có thể ôm chặt khi thuyền chao đảo. Lấy ví dụ, giả sử phao chuối có $n = 7$ vị trí ngồi với dãy biểu diễn độ an toàn của các vị trí là $(7, 2, 5, 1, 4, 6, 3)$ và vị trí ưa thích của GSPVH là $f = 3$. Khi đó, mọi người sẽ lựa chọn chỗ ngồi như sau:

Trước hết, toàn bộ n vị trí trên phao chuối đều trống: _ _ _ _ _ _ _
Đầu tiên, GSPVH (người thứ $1$) ngồi vào vị trí ưa thích $f = 3$: _ _ 1 _ _ _ _
Bạn thứ $2$ ngồi vào vị trí $4$: _ _ 1 2 _ _ _
Bạn thứ $3$ ngồi vào vị trí $2$: _ 3 1 2 _ _ _
Bạn thứ $4$ ngồi vào vị trí $5$: _ 3 1 2 4 _ _
Bạn thứ $5$ ngồi vào vị trí $6$: _ 3 1 2 4 5 _
Bạn thứ $6$ ngồi vào vị trí $7$: _ 3 1 2 4 5 6
Bạn thứ $7$ ngồi vào vị trí $1$: 7 3 1 2 4 5 6

Tuy nhiên, cuộc sống không ngừng biến đổi đi lên, và phao chuối cũng ngày càng được cải tiến. Gần đây, GSPVH phát hiện nhiều công trình khoa học đã ra đời nhằm nâng cấp độ an toàn của các vị trí ngồi trên phao chuối. Mỗi công trình nghiên cứu được biểu diễn bởi hai con số $k$ và $c$ $(1 \leq k, c \leq n)$ với ý nghĩa: vị trí ngồi thứ $k$ được nâng cấp và giờ trở thành vị trí có độ an toàn thứ $c$. Lưu ý rằng ở mọi thời điểm, sau mọi sự nâng cấp, độ an toàn của các vị trí ngồi luôn đôi một phân biệt. Cụ thể, giả sử $p_{1}, p_{2}, \ldots, p_{n}$ là hoán vị biểu diễn độ an toàn của các vị trí ngồi trước sự nâng cấp, cách xác định hoán vị $p'_{1}, p'_{2}, \ldots, p'_{n}$ biểu diễn độ an toàn của các vị trí ngồi sau sự nâng cấp như sau:

Đặt $o = p_{k}$. Chú ý rằng, do vị trí ngồi thứ k được nâng cấp nên chắc chắn vị trí này có độ an toàn cao hơn trước. Vì vậy, dữ liệu vào luôn đảm bảo $c < o$.
$p'_{k} = c$
Với mọi vị trí $i$ có $1 \leq i \leq n$ và $c \leq p_{i} \leq o − 1$, ta có $p'_{i} = p_{i} + 1$.
Với mọi vị trí $i$ có $1 \leq i \leq n$ và $1 \leq p_{i} \leq c − 1$, ta có $p'_{i} = p_{i}$.
Với mọi vị trí $i$ có $1 \leq i \leq n$ và $o + 1 \leq p_{i} \leq n$, ta có $p'_{i} = p_{i}$.

Việc có quá nhiều cải tiến khoa học về phao chuối khiến cho GSPVH rất khó quản lý độ an toàn của các vị trí ngồi, vì vậy GSPVH muốn nhờ bạn viết chương trình xử lý $q$ sự kiện, mỗi sự kiện thuộc một trong hai dạng sau:

U $k$ $c$: Có công trình khoa học nâng cao độ an toàn của vị trí thứ $k$ lên mức $c$ (như định nghĩa ở trên)
G $x$: Cho biết với độ an toàn của các vị trí như ở thời điểm hiện tại, ai sẽ ngồi vào vị trí thứ $x$, biết rằng GSPVH cùng những học sinh đi cùng vẫn chọn chỗ ngồi theo chiến lược ở trên.

Các bạn hãy giúp GSPVH nhé.

Input

Dòng đầu tiên chứa số nguyên $\theta$ là số thứ tự của subtask chứa test này.
Dòng thứ hai chứa ba số nguyên $n, q$ và $f$ $(1 \leq f \leq n \leq 666^{2}, 1 \leq q \leq 777^{2})$ lần lượt là số vị trí ngồi trên phao chuối, số thao tác cần được xử lý và vị trí ưa thích của GSPVH.
Dòng thứ ba chứa $n$ số nguyên $v_{1}, v_{2}, \ldots, v_{n}$ $(1 \leq v_{i} \leq n)$ là một hoán vị của các số nguyên từ $1$ đến $n$ biểu diễn độ an toàn của $n$ vị trí ngồi ở thời điểm ban đầu.
Trong $q$ dòng cuối cùng, mỗi dòng mô tả một thao tác thuộc một trong hai dạng sau:
- U $k$ $c$ $(1 \leq k, c \leq n)$ mô tả một sự cải tiến độ an toàn. Dữ liệu vào đảm bảo nếu $p_{1}, p_{2}, \ldots, p_{n}$ là hoán vị biểu diễn độ an toàn của n vị trí trước thao tác này, $c < p_{k}$.
- G $x$ $(1 \leq x \leq n)$ yêu cầu tìm người sẽ ngồi vào vị trí thứ $x$.

Output

Với mỗi thao tác dạng G $x$, in ra một số nguyên trên một dòng thể hiện kết quả.

Scoring

Subtask $1$ ($3$ điểm): $n \leq 66^{2}$ và $q \leq 77^{2}$.
Subtask $2$ ($9$ điểm): Có tối đa $66$ thao tác dạng U $k$ $c$.
Subtask $3$ ($13$ điểm): Mọi thao tác dạng U $k$ $c$ đều xuất hiện trước mọi thao tác dạng G $x$.
Subtask $4$ ($13$ điểm): Mọi thao tác dạng U $k$ $c$ đều thoả mãn $c \leq 11$.
Subtask $5$ ($12$ điểm): $n \leq 222^{2}$.
Subtask $6$ ($10$ điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

1
7 15 3
7 2 5 1 4 6 3
G 1
G 2
G 3
G 4
G 5
G 6
G 7
U 1 4
G 1
G 2
G 4
U 5 2
G 5
G 6
G 7

Output

Note

Ban đầu, khi dãy biểu diễn độ an toàn của các vị trí là $(7, 2, 5, 1, 4, 6, 3)$, những người sẽ ngồi vào các vị trí là $(7, 3, 1, 2, 4, 5, 6)$ (ví dụ này đã trình bày ở trên).
Sau thao tác U $1$ $4$, dãy biểu diễn độ an toàn của các vị trí trở thành $(4, 2, 6, 1, 5, 7, 3)$, những người sẽ ngồi vào các vị trí là $(4, 3, 1, 2, 5, 6, 7)$.
Sau thao tác U $5$ $2$, dãy biểu diễn độ an toàn của các vị trí trở thành $(5, 3, 6, 1, 2, 7, 4)$, những người sẽ ngồi vào các vị trí là $(5, 4, 1, 2, 3, 6, 7)$.