JOI 2022 - Vòng loại 2 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2022 - Library 2	100 (p)	2.0s	1G
2	JOI 2022 - Carpet	100 (p)	2.0s	1G
3	JOI 2022 - Land Division	100 (p)	1.0s	1G
4	JOI 2022 - Candies 2	100 (p)	2.0s	1G
5	JOI 2022 - Trade Plan	100 (p)	4.0s	1G

1. JOI 2022 - Library 2

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bitaro thích đọc sách và quyết định mượn sách ở thư viện. Nhà của Bitaro khá chật, nên trên sàn chỉ có một khoảng trống đủ đặt một quyển sách. Tuy nhiên, phía trên có đủ chỗ, vì vậy Bitaro quyết định xếp các quyển sách chồng lên nhau tại khoảng trống này.

Bitaro sẽ thực hiện \(Q\) hành động. Hành động thứ \(i\) (\(1 \le i \le Q\)) được biểu diễn bởi xâu \(S_i\). Xâu \(S_i\) chỉ gồm các chữ cái tiếng Anh viết thường hoặc là READ, với ý nghĩa như sau:

Nếu \(S_i\) chỉ gồm các chữ cái tiếng Anh viết thường, Bitaro mượn quyển sách có tên \(S_i\) từ thư viện và đặt lên trên cùng của chồng sách.
Nếu \(S_i\) là READ, Bitaro đọc quyển sách trên cùng của chồng sách rồi trả quyển đó cho thư viện.

Bạn muốn biết Bitaro đã đọc những quyển sách nào và theo thứ tự nào. Cho thông tin về \(Q\) hành động, hãy in ra tên các quyển sách mà Bitaro đã đọc, theo đúng thứ tự đọc.

Dữ liệu vào

Dữ liệu vào có dạng:

Q
S_1
S_2
...
S_Q

Dữ liệu ra

Với mỗi hành động có \(S_i\) là READ, in ra tên quyển sách mà Bitaro đọc trong hành động đó. In các tên theo đúng thứ tự đọc, mỗi tên trên một dòng.

Ràng buộc

\(2 \le Q \le 200\,000\).
\(Q\) là số nguyên.
\(S_i\) là xâu có độ dài từ \(1\) đến \(10\) (\(1 \le i \le Q\)).
\(S_i\) chỉ gồm các chữ cái tiếng Anh viết thường hoặc là READ (\(1 \le i \le Q\)).
Có ít nhất một chỉ số \(i\) (\(1 \le i \le Q\)) mà \(S_i\) là READ.
Mỗi khi \(S_i\) là READ, chồng sách luôn có ít nhất một quyển (\(1 \le i \le Q\)).

Phân nhóm

40 điểm: \(Q \le 2000\).
60 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

7
joi
joig
ioi
READ
egoi
READ
READ

Output

ioi
egoi
joig

Note

Bitaro thực hiện các hành động như sau:

Đặt quyển sách joi vào khoảng trống. Chồng sách lúc này chỉ có joi.
Đặt quyển sách joig lên trên. Các quyển sách từ trên xuống là joig, joi.
Đặt quyển sách ioi lên trên. Các quyển sách từ trên xuống là ioi, joig, joi.
Đọc và trả quyển sách ioi. Các quyển sách từ trên xuống còn lại là joig, joi.
Đặt quyển sách egoi lên trên. Các quyển sách từ trên xuống là egoi, joig, joi.
Đọc và trả quyển sách egoi. Các quyển sách từ trên xuống còn lại là joig, joi.
Đọc và trả quyển sách joig. Chồng sách chỉ còn joi.

Vì vậy, in ra các tên sách ioi, egoi, joig theo thứ tự này, mỗi tên trên một dòng.

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 2

Input

20
one
READ
two
three
four
five
six
seven
READ
eight
nine
READ
ten
eleven
READ
READ
twelve
READ
READ
READ

Output

one
seven
nine
eleven
ten
twelve
eight
six

Note

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Nguồn

Đề bài Library 2, JOI 2021/2022, vòng loại thứ hai, bài 1 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.

2. JOI 2022 - Carpet

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bitaro thích những đồ vật đẹp và vừa mua một tấm thảm mới. Tấm thảm có hình chữ nhật, được chia thành \(H\) hàng và \(W\) cột ô vuông. Mỗi ô được tô màu trắng hoặc đen. Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang (\(1 \le i \le H\), \(1 \le j \le W\)) có màu trắng nếu ký tự thứ \(j\) của xâu \(S_i\) là ., và có màu đen nếu ký tự đó là #.

Bitaro nghĩ ra một trò chơi: đặt một quân cờ ở ô trên cùng bên trái của tấm thảm, rồi thực hiện thao tác sau một số lần để đưa quân cờ đến ô dưới cùng bên phải:

Chọn một ô có màu khác với ô quân cờ đang đứng và kề với ô đó theo một trong bốn hướng trên, dưới, trái, phải; sau đó chuyển quân cờ sang ô đã chọn.

Bitaro muốn thực hiện ít thao tác nhất có thể. Tuy nhiên, tùy theo hoa văn của tấm thảm, có thể không đưa được quân cờ đến đích.

Cho hoa văn của tấm thảm, hãy xác định liệu có thể đưa quân cờ từ ô trên cùng bên trái đến ô dưới cùng bên phải bằng cách lặp lại thao tác trên hay không. Nếu có thể, hãy tìm số thao tác ít nhất.

Dữ liệu vào

Dữ liệu vào có dạng:

H W
S_1
S_2
...
S_H

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất nếu có thể đưa quân cờ từ ô trên cùng bên trái đến ô dưới cùng bên phải. Nếu không thể, in ra \(-1\).

Ràng buộc

\(1 \le H \le 500\).
\(1 \le W \le 500\).
\((H,W) \ne (1,1)\).
\(S_i\) là xâu có độ dài \(W\) (\(1 \le i \le H\)).
Mỗi ký tự của \(S_i\) là . hoặc # (\(1 \le i \le H\)).
\(H,W\) là các số nguyên.

Phân nhóm

4 điểm: \(H=1\).
14 điểm: \(H \le 5\), \(W \le 5\).
24 điểm: \(H \le 30\), \(W \le 30\).
58 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

4 5
...#.
#####
...#.
#.###

Output

Note

Chẳng hạn, có thể di chuyển quân cờ theo hai cách trong hình sau:

Cách bên trái đưa quân cờ từ ô trên cùng bên trái đến ô dưới cùng bên phải sau \(9\) thao tác, còn cách bên phải cần \(13\) thao tác. Không thể đến đích với ít hơn \(9\) thao tác, nên in ra \(9\).

Ví dụ này thỏa mãn ràng buộc của các subtasks \(2,3,4\).

Ví dụ 2

Input

3 3
...
...
...

Output

-1

Note

Có trường hợp không thể thực hiện thao tác nào ngay từ đầu. Trong ví dụ này, không thể đưa quân cờ đến ô dưới cùng bên phải, nên in ra \(-1\).

Ví dụ này thỏa mãn ràng buộc của các subtasks \(2,3,4\).

Ví dụ 3

Input

1 5
.#.#.

Output

Note

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 4

Input

5 5
###.#
.#...
.#..#
.####
##..#

Output

Note

Ví dụ này thỏa mãn ràng buộc của các subtasks \(2,3,4\).

Ví dụ 5

Input

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

Output

Note

Ví dụ này thỏa mãn ràng buộc của các subtasks \(3,4\).

Nguồn

Đề bài Carpet, JOI 2021/2022, vòng loại thứ hai, bài 2 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.

3. JOI 2022 - Land Division

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Đất nước JOI có hình chữ nhật, được chia thành \(H\) hàng và \(W\) cột ô vuông. Chiều dọc của đất nước song song với hướng bắc–nam, còn chiều ngang song song với hướng đông–tây. Ô ở hàng thứ \(i\) tính từ phía bắc (\(1 \le i \le H\)) và cột thứ \(j\) tính từ phía tây (\(1 \le j \le W\)) có dân số là \(A_{i,j}\) người.

Để việc quản lý hiệu quả hơn, đất nước JOI quyết định chia toàn bộ lãnh thổ thành ít nhất hai khu vực bằng cách kẻ ít nhất một đường ranh giới. Mỗi đường ranh giới phải thỏa mãn cả hai điều kiện sau:

Nằm trên các đường phân cách giữa các ô.
Là một đoạn thẳng nối từ biên phía bắc đến biên phía nam của đất nước, hoặc nối từ biên phía đông đến biên phía tây của đất nước.

Cho dân số của từng ô, hãy đếm số cách chia sao cho tất cả các khu vực đều có dân số bằng nhau.

Dữ liệu vào

Dữ liệu vào có dạng:

H W
A_1,1 A_1,2 ... A_1,W
A_2,1 A_2,2 ... A_2,W
...
A_H,1 A_H,2 ... A_H,W

Dữ liệu ra

In ra một dòng chứa số cách chia sao cho tất cả các khu vực đều có dân số bằng nhau.

Ràng buộc

\(1 \le H \le 50\).
\(1 \le W \le 50\).
\(1 \le A_{i,j} \le 100\,000\) (\(1 \le i \le H\), \(1 \le j \le W\)).
Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

12 điểm: \(H=1\).
26 điểm: \(H \le 6\), \(W \le 6\).
62 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

2 3
10 10 20
10 10 20

Output

Note

Có \(3\) cách chia để tất cả các khu vực có dân số bằng nhau, như các hình sau, nên in ra \(3\).

Ví dụ này thỏa mãn ràng buộc của các subtasks \(2,3\).

Ví dụ 2

Input

1 4
2 1 1 2

Output

Note

Có \(2\) cách chia để tất cả các khu vực có dân số bằng nhau, như các hình sau, nên in ra \(2\).

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 3

Input

Output

Note

Có \(2\) cách chia để tất cả các khu vực có dân số bằng nhau, như các hình sau, nên in ra \(2\).

Ví dụ này thỏa mãn ràng buộc của các subtasks \(2,3\).

Ví dụ 4

Input

1 1
10000

Output

Note

Không có cách chia nào để tất cả các khu vực có dân số bằng nhau, nên in ra \(0\).

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Nguồn

Đề bài Land Division, JOI 2021/2022, vòng loại thứ hai, bài 3 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.

4. JOI 2022 - Candies 2

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Trên bàn có \(N\) viên kẹo xếp thành một hàng ngang, được đánh số từ \(1\) đến \(N\) theo thứ tự từ trái sang phải. Viên kẹo \(i\) (\(1 \le i \le N\)) có độ ngon là \(A_i\).

JOI quyết định chọn một số viên trong \(N\) viên kẹo để ăn. Tuy nhiên, để không ăn quá nhiều, trong bất kỳ \(K\) viên kẹo liên tiếp nào, JOI chỉ được ăn nhiều nhất \(2\) viên. Cụ thể, với mọi \(j\) (\(1 \le j \le N-K+1\)), số viên được ăn trong các viên từ \(j\) đến \(j+K-1\) phải không vượt quá \(2\).

Với điều kiện đó, JOI muốn tổng độ ngon của các viên kẹo được ăn lớn nhất có thể. Cho độ ngon của \(N\) viên kẹo và giá trị \(K\), hãy tìm tổng độ ngon lớn nhất mà JOI có thể đạt được.

Dữ liệu vào

Dữ liệu vào có dạng:

N K
A_1 A_2 ... A_N

Dữ liệu ra

In ra một dòng chứa tổng độ ngon lớn nhất của các viên kẹo mà JOI có thể ăn.

Ràng buộc

\(2 \le K \le N \le 3000\).
\(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

4 điểm: \(N \le 20\).
19 điểm: \(K \le 10\).
47 điểm: \(N \le 300\).
30 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

5 4
1 3 2 4 3

Output

Note

Nếu JOI ăn các viên kẹo \(1,4,5\), tổng độ ngon là \(8\).

Không có cách chọn nào vừa bảo đảm trong bất kỳ \(4\) viên kẹo liên tiếp nào cũng ăn nhiều nhất \(2\) viên, vừa có tổng độ ngon từ \(9\) trở lên. Vì vậy, in ra \(8\).

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 2

Input

6 3
3 7 1 5 6 4

Output

Note

Nếu JOI ăn các viên kẹo \(1,2,4,5\), tổng độ ngon là \(21\).

Không có cách chọn nào vừa bảo đảm trong bất kỳ \(3\) viên kẹo liên tiếp nào cũng ăn nhiều nhất \(2\) viên, vừa có tổng độ ngon từ \(22\) trở lên. Vì vậy, in ra \(21\).

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 3

Input

5 2
3 3 2 2 1

Output

Note

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 4

Input

12 5
864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728

Output

4427122428

Note

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Nguồn

Đề bài Candies 2, JOI 2021/2022, vòng loại thứ hai, bài 4 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.

5. JOI 2022 - Trade Plan

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Hợp chúng quốc JOI có \(N\) thành phố được đánh số từ \(1\) đến \(N\) và \(M\) con đường được đánh số từ \(1\) đến \(M\). Đường \(i\) (\(1 \le i \le M\)) nối hai chiều giữa thành phố \(U_i\) và thành phố \(V_i\).

Quốc gia này gồm \(K\) bang, được đánh số từ \(1\) đến \(K\). Thành phố \(j\) (\(1 \le j \le N\)) thuộc bang \(S_j\). Mỗi bang có ít nhất một thành phố.

Chủ tịch K, Bộ trưởng Công nghiệp của Hợp chúng quốc JOI, muốn thực hiện \(Q\) chuyến giao thương. Trong chuyến thứ \(k\) (\(1 \le k \le Q\)), đặc sản được vận chuyển từ thành phố \(A_k\) đến thành phố \(B_k\) qua một số con đường và thành phố. Tuy nhiên, chỉ bang \(S_{A_k}\) và bang \(S_{B_k}\) đồng ý hợp tác; nếu \(S_{A_k}=S_{B_k}\) thì chỉ có bang đó hợp tác. Nếu đi qua một thành phố không thuộc các bang hợp tác, đặc sản sẽ bị đánh cắp.

Chủ tịch K muốn biết có lộ trình nào để thực hiện chuyến giao thương mà không bị đánh cắp đặc sản hay không. Cho thông tin về các thành phố, đường đi, bang và các chuyến giao thương, hãy xác định với từng chuyến liệu có thể vận chuyển đặc sản đến nơi an toàn hay không.

Dữ liệu vào

Dữ liệu vào có dạng:

N M K
U_1 V_1
U_2 V_2
...
U_M V_M
S_1 S_2 ... S_N
Q
A_1 B_1
A_2 B_2
...
A_Q B_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa \(1\) nếu có thể vận chuyển đặc sản đến nơi an toàn trong chuyến giao thương thứ \(k\), hoặc \(0\) nếu không thể.

Ràng buộc

\(2 \le N \le 400\,000\).
\(1 \le M \le 400\,000\).
\(1 \le K \le N\).
\(1 \le U_i<V_i \le N\) (\(1 \le i \le M\)).
\((U_i,V_i) \ne (U_j,V_j)\) (\(1 \le i<j \le M\)).
\(1 \le S_j \le K\) (\(1 \le j \le N\)).
Với mọi \(l\) (\(1 \le l \le K\)), tồn tại ít nhất một \(j\) (\(1 \le j \le N\)) sao cho \(S_j=l\).
\(1 \le Q \le 400\,000\).
\(1 \le A_k \le N\) (\(1 \le k \le Q\)).
\(1 \le B_k \le N\) (\(1 \le k \le Q\)).
\(A_k \ne B_k\) (\(1 \le k \le Q\)).
Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

5 điểm: \(N \le 1000\), \(M \le 1000\), \(Q \le 1000\).
11 điểm: Với mỗi bang \(l\) (\(1 \le l \le K\)), mọi cặp thành phố thuộc bang \(l\) đều có thể đi đến nhau bằng các con đường và chỉ qua các thành phố thuộc bang \(l\).
42 điểm: \(N \le 80\,000\), \(M \le 80\,000\), \(Q \le 80\,000\).
42 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

1
0
1

Note

Trong chuyến thứ \(1\), đặc sản cần được vận chuyển từ thành phố \(1\) đến thành phố \(2\), chỉ qua các thành phố thuộc bang \(1\) hoặc bang \(2\). Lộ trình \(1 \to 2\) thỏa mãn điều kiện, nên in ra \(1\).

Trong chuyến thứ \(2\), đặc sản cần được vận chuyển từ thành phố \(1\) đến thành phố \(3\), chỉ qua các thành phố thuộc bang \(1\). Không có lộ trình nào thỏa mãn điều kiện, nên in ra \(0\).

Trong chuyến thứ \(3\), đặc sản cần được vận chuyển từ thành phố \(1\) đến thành phố \(4\), chỉ qua các thành phố thuộc bang \(1\) hoặc bang \(2\). Lộ trình \(1 \to 2 \to 3 \to 4\) thỏa mãn điều kiện, nên in ra \(1\).

Ví dụ này thỏa mãn ràng buộc của các subtasks \(1,3,4\).

Ví dụ 2

Input

Output

Note

Ví dụ này thỏa mãn ràng buộc của các subtasks \(1,3,4\).

Ví dụ 3

Input

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

Output

Note

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 4

Input

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

Output

Note

Ví dụ này thỏa mãn ràng buộc của các subtasks \(1,3,4\).

Nguồn

Đề bài Trade Plan, JOI 2021/2022, vòng loại thứ hai, bài 5 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.