2025 · HSG THPT · Quảng Trị

Trong trò chơi điện tử Zentric, nhân vật được điều khiển di chuyển trên một ô lưới (giả sử số ô không hạn chế).

Khởi đầu trò chơi, nhân vật được đặt tại một ô bất kì. Tại mỗi bước, nhân vật có thể di chuyển đến ô liền kề là một trong các ô: bên trái, bên phải, phía trên, phía dưới của ô hiện tại.

Để hướng dẫn nhân vật di chuyển, cần một chuỗi lệnh ~S~ gồm các kí tự ~'L'~ (Left - sang trái), ~'R'~ (Right - sang phải), ~'U'~ (Up - lên trên) và ~'D'~ (Down - xuống dưới).

Cho trước một chuỗi lệnh ~S~, để hoàn thành màn chơi, bạn cần chỉnh sửa lại chuỗi lệnh ~S~ sao cho có thể hướng dẫn nhân vật di chuyển qua các ô, mỗi ô được phép đi qua không quá một lần và phải trở về đúng ô xuất phát. Việc chỉnh sửa lại chuỗi lệnh ~S~ có thể được thực hiện bằng cách:

• Xóa đi một số kí tự (có thể không xóa kí tự nào) trong chuỗi lệnh ~S~.
• Thay đổi vị trí các kí tự trong chuỗi lệnh ~S~ theo ý muốn.

Yêu cầu: Hãy xác định độ dài lớn nhất của chuỗi lệnh ~S~ sau khi thực hiện việc chỉnh sửa.

Input

Vào từ file văn bản GAME.INP:

• Gồm một dòng chứa chuỗi lệnh ~S~ (độ dài không vượt quá ~10^6~).

Output

Ghi ra file văn bản GAME.OUT:

• Gồm một dòng ghi một số nguyên ~t~ là kết quả bài toán. Trường hợp không thể chỉnh sửa chuỗi lệnh ~S~ để hoàn thành màn chơi thì in ~-1~.

Scoring

• Subtask ~1~ ~(60\%)~: Độ dài xâu không quá ~255~ kí tự.
• Subtask ~2~ ~(40\%)~: Không còn ràng buộc gì thêm.

Example input 1

LURD

Example output 1

4

Note 1

• Không cần xóa kí tự nào.

Example input 2

LDLDURURL

Example output 2

8

Note 2

• Phải xóa đi một kí tự ~'L'~.

Example input 3

LLLLU

Example output 3

-1

Note 3

• Không có phương án chỉnh sửa chuỗi để hoàn thành màn chơi.

Alice và Peter là đôi bạn thân có cùng đam mê mãnh liệt với việc sưu tầm các thẻ bài Magic: The Gathering.

Hiện tại, Alice đang sở hữu ~N~ lá bài với các giá trị tương ứng là: ~A_{1}, A_{2}, ..., A_{N}~. Tương tự Peter cũng sở hữu ~N~ lá bài với các giá trị tương ứng là: ~B_{1}, B_{2}, ..., B_{N}~.

Alice muốn biết tập hợp ~x~ thẻ bài đầu tiên của mình có giống tập hợp ~y~ thẻ bài đầu tiên của Peter hay không. Hai tập hợp được coi là giống nhau nếu mọi loại thẻ bài của Alice cũng trùng với Peter và ngược lại.

Yêu cầu: Hãy giúp Alice trả lời câu hỏi của mình.

Input

Vào từ file văn bản MAGIC.INP:

• Dòng ~1~: Chứa số nguyên dương ~N~ ~(1 \leq N \leq 2 \times 10^5)~, là số lượng thẻ bài của mỗi bạn;
• Dòng ~2~: Chứa ~N~ số nguyên dương ~A_{1}, A_{2}, ..., A_{N}~ ~(1 \leq A_{i} \leq 10^9, 1 \leq i \leq N)~, là danh sách giá trị các thẻ bài của Alice;
• Dòng ~3~: Chứa ~N~ số nguyên dương ~B_{1}, B_{2}, ..., B_{N}~ ~(1 \leq B_{i} \leq 10^9, 1 \leq i \leq N)~, là danh sách giá trị các thẻ bài của Peter;
• Dòng ~4~: Chứa số nguyên dương ~Q~ ~(Q \leq 2 \times 10^5)~, là số lượng cã truy vấn;
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương: ~x, y~ ~(1 \leq x, y \leq N)~ tương ứng với việc xét tập hợp ~x~ thẻ bài đầu tiên của Alice và ~y~ thẻ bài đầu tiên của Peter.

Lưu ý: Các giá trị trên cùng một dòng được ghi cách nhau một dấu cách.

Output

Ghi ra file văn bản MAGIC.OUT:

• Gồm ~Q~ dòng tương ứng với ~Q~ truy vấn, mỗi dòng ghi ra "~Yes~" nếu tập hợp các loại thẻ bài của hai bạn giống hệt nhau, ngược lại ghi ra "~No~".

Scoring

• Subtask ~1~ ~(50\%)~: ~1 \leq N, Q \leq 200~; ~x = y~; các giá trị ~A_{i}~ đôi một khác nhau; các giá trị ~B_{i}~ đôi một khác nhau.
• Subtask ~2~ ~(25\%)~: ~1 \leq N, Q \leq 2000~.
• Subtask ~3~ ~(25\%)~: Không còn ràng buộc gì thêm.

Example input 1

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

Example output 1

Yes
Yes
No

Alice là một học sinh có đam mê làm việc với các con số. Cậu sưu tầm và lưu lại danh sách các số nguyên dương mà mình thích và gọi đó là những số nguyên dương "đẹp".

Hiện tại, Alice đang sở hữu một danh sách ~A~ gồm ~N~ số nguyên dương đẹp: ~A_1, A_2,..., A_N,~các giá trị đôi một khác nhau và được sắp xếp tăng dần: ~(A_1 < A_2 < ... < A_N)~. Các số nguyên dương không xuất hiện trong danh sách ~A~ được gọi là các "phần tử thiếu".

Alice cần trả lời ~Q~ truy vấn độc lập, mỗi truy vấn cho một số nguyên dương ~k~. Hãy xác định giá trị phần tử thiếu thứ ~k~ khi liệt kê các phần tử thiếu của danh sách ~A~ theo thứ tự tăng dần.

Yêu cầu: Bạn hãy giúp Alice trả lời ~Q~ truy vấn trên.

Input

Vào từ file văn bản MISS.INP:

• Dòng ~1~: Chứa hai số nguyên dương ~N, Q~ ~(1 \leq N, Q \leq 10^5)~.
• Dòng ~2~: Chứa các số nguyên dương ~A_1, A_2,..., A_N~ ~(1 \leq A_i \leq 10^{18})~. Mỗi số cách nhau một dấu cách. Dãy số đảm bảo tăng nghiêm ngặt.
• ~Q~ dòng tiếp theo chứa một số nguyên ~k_i~ ~(1 \leq k_i \leq 10^{18}, 1 \leq i \leq Q)~ tương ứng với câu hỏi thứ ~i~.

Output

Ghi ra file văn bản MISS.OUT:

• Gồm ~Q~ dòng: Dòng thứ ~i~ ghi một số nguyên ~t~ là phần tử bị thiếu thứ ~k_i~.

Scoring

• Subtask ~1~ ~(40\%)~: ~1 \leq N, Q \leq 2 \times 10^3~;
• Subtask ~2~ ~(30\%)~: ~1 \leq A_i \leq 10^6~ ~(1 \leq i \leq N)~;
• Subtask ~3~ ~(30\%)~: Không còn ràng buộc gì thêm.

Example input 1

5 3
1 3 9 12 17
2
9
19

Example output 1

4
13
24

Note 1

• Phần tử bị thiếu thứ ~2~ là ~4~
• Phần tử bị thiếu thứ ~9~ là ~13~
• Phần tử bị thiếu thứ ~19~ là ~24~

Giả sử đến năm ~2045~, giữa những vùng không gian vũ trụ, công nghệ dịch chuyển tức thời đã đạt đến một tầm cao mới. Những con tàu thám hiểm giờ đây có thể thực hiện những bước nhảy không gian chỉ trong nháy mắt, miễn là tuyến đường chúng chọn không quá nguy hiểm.

Bạn được giao nhiệm vụ điều khiển một con tàu thám hiểm di chuyển trong không gian được biểu thị bởi một bản đồ dạng lưới hình chữ nhật có kích thước ~N \times M~. Các hàng được đánh số thứ tự từ ~1~ đến ~N~, các cột được đánh số thứ tự từ ~1~ đến ~M~.

Ô ~(i, j)~ là ô ở hàng thứ ~i~ ~(1 \le i \le N)~ từ trên xuống dưới và cột thứ ~j~ ~(1 \le j \le M)~ từ trái sang phải trên bản đồ. Mỗi ô ~(i, j)~ biểu thị một vùng không gian, trong đó:

• Chứa giá trị ~0~ thì đó là vùng an toàn.
• Chứa giá trị ~1~ thì đó là vùng không an toàn. Tàu thám hiểm của bạn bắt đầu xuất phát tại ô ~(1, 1)~ và cần di chuyển đến đích là ô ~(N, M)~. Cơ chế di chuyển của con tàu tuân theo ~2~ quy định như sau:
• Hướng di chuyển hợp lệ: Từ vị trí ở ô ~(x, y)~ hiện tại, con tàu có thể thực hiện một bước nhảy đến vị trí mới ở ô ~(u, v)~ theo hai hướng: hướng xuống dưới ~(u > x, v = y)~ hoặc hướng sang phải ~(u = x, v > y)~.
• Bước nhảy hợp lệ: Trong một bước nhảy của con tàu từ ô ~(x, y)~ đến ô ~(u, v)~ thì tổng số vùng không an toàn nằm trên đường đi (bao gồm cả ô ~(x, y)~) không vượt quá giới hạn ~D~, lúc này bước nhảy là hợp lệ. Nếu vượt quá giới hạn này thì con tàu sẽ bị xé vụn.

Yêu cầu: Hãy đếm số cách khác nhau để tàu có thể di chuyển từ ô ~(1, 1)~ đến ô ~(N, M)~ theo cơ chế trên. Hai cách đi được xem là khác nhau nếu như có ít nhất một ô xuất hiện ở cách đi này nhưng không xuất hiện ở cách đi kia. Vì kết quả có thể rất lớn, hãy lấy phần dư của nó khi chia cho ~10^9 + 7~.

Input

Vào từ file văn bản JUMP.INP:

• Dòng 1: Chứa ba số nguyên ~N, M, D~ ~(1 \le N \times M \le 10^6, D \ge 0)~, tương ứng lần lượt là số hàng, số cột của bản đồ và giới hạn ~D~; các giá trị được ghi cách nhau một dấu cách.
• ~N~ dòng tiếp theo: mỗi dòng chứa một xâu gồm ~M~ kí tự '~0~' hoặc '~1~' mô tả bản đồ lưới.

Output

Ghi ra file văn bản JUMP.OUT: Một dòng ghi số nguyên ~t~ là kết quả bài toán.

Scoring

• Subtask ~1~ ~(40\%)~: ~1 \leq N, M \leq 5 \times 10^3~;
• Subtask ~2~ ~(30\%)~: ~D = 0~;
• Subtask ~3~ ~(30\%)~: Không còn ràng buộc gì thêm.

Example input 1

2 3 1
101
010

Example output 1

4

Note 1

Các cách di chuyển từ ô (1,1) đến ô (2,3):

• Cách ~1~: ~(1,1) \to (2,1) \to (2,2) \to (2,3)~.
• Cách ~2~: ~(1,1) \to (2,1) \to (2,3)~.
• Cách ~3~: ~(1,1) \to (1,2) \to (2,2) \to (2,3)~.
• Cách ~4~: ~(1,1) \to (1,2) \to (1,3) \to (2,3)~.