JOI 2023 - Vòng chung kết quốc gia - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2023 - Stone Arranging 2	100 (p)	2.0s	1G
2	JOI 2023 - Advertisement 2	100 (p)	2.0s	1G
3	JOI 2023 - Maze	100 (p)	2.0s	2G
4	JOI 2023 - Cat Exercise	100 (p)	2.0s	1G
5	JOI 2023 - Modern Machine	100 (p)	2.5s	1G

1. JOI 2023 - Stone Arranging 2

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

JOI có \(N\) quân cờ vây, được đánh số từ \(1\) đến \(N\). Màu của mỗi quân cờ được biểu diễn bằng một số nguyên từ \(1\) đến \(10^9\). Ban đầu, quân cờ \(i\) (\(1 \le i \le N\)) có màu \(A_i\).

JOI sẽ thực hiện \(N\) thao tác để xếp các quân cờ thành một hàng trên bàn. Thao tác thứ \(i\) (\(1 \le i \le N\)) được thực hiện theo thứ tự sau:

Đặt quân cờ \(i\) ngay bên phải quân cờ \(i - 1\). Riêng khi \(i = 1\), đặt quân cờ \(1\) lên bàn.
Nếu trong các quân cờ \(1, 2, \ldots, i - 1\) có quân cờ mang màu hiện tại giống với quân cờ \(i\), gọi \(j\) là số hiệu lớn nhất trong số các quân cờ đó. Khi ấy, đổi màu của tất cả các quân cờ \(j + 1, j + 2, \ldots, i - 1\) thành \(A_i\).

Để kiểm tra mình có thực hiện đúng các thao tác hay không, JOI muốn biết trước màu của các quân cờ sau khi thực hiện xong tất cả các thao tác.

Cho thông tin về các quân cờ, hãy tìm màu của từng quân cờ sau \(N\) thao tác.

Dữ liệu vào

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

N
A_1
A_2
...
A_N

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) chứa màu của quân cờ \(i\) sau \(N\) thao tác.

Ràng buộc

\(1 \le N \le 200\,000\).
\(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.

Chấm điểm

\(25\) điểm: \(N \le 2000\).
\(35\) điểm: \(A_i \le 2\) với mọi \(1 \le i \le N\).
\(40\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Các thao tác được thực hiện như trong bảng sau. Màu của các quân cờ trên bàn được liệt kê từ trái sang phải.

Thao tác	Màu của các quân cờ trên bàn	Diễn biến
\(1\)	\(1\)	Đặt quân cờ \(1\) lên bàn.
\(2\)	\(1, 2\)	Đặt quân cờ \(2\) ngay bên phải quân cờ \(1\).
\(3\)	\(1, 2, 1\)	Đặt quân cờ \(3\) ngay bên phải quân cờ \(2\).
\(3\)	\(1, 1, 1\)	Đổi màu quân cờ \(2\) thành \(1\).
\(4\)	\(1, 1, 1, 2\)	Đặt quân cờ \(4\) ngay bên phải quân cờ \(3\).
\(5\)	\(1, 1, 1, 2, 3\)	Đặt quân cờ \(5\) ngay bên phải quân cờ \(4\).
\(6\)	\(1, 1, 1, 2, 3, 2\)	Đặt quân cờ \(6\) ngay bên phải quân cờ \(5\).
\(6\)	\(1, 1, 1, 2, 2, 2\)	Đổi màu quân cờ \(5\) thành \(2\).

Cuối cùng, các quân cờ \(1, 2, 3, 4, 5, 6\) lần lượt có màu \(1, 1, 1, 2, 2, 2\).

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

Ví dụ 2

Input

Output

Giải thích

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

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

2. JOI 2023 - Advertisement 2

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

Vương quốc JOI có \(N\) cư dân, được đánh số từ \(1\) đến \(N\). Cư dân \(i\) (\(1 \le i \le N\)) sống tại tọa độ \(X_i\) trên trục số và có mức ảnh hưởng \(E_i\). Nhiều cư dân có thể sống tại cùng một tọa độ. Cư dân có mức ảnh hưởng càng lớn thì khả năng quảng bá càng cao, nhưng cũng càng thận trọng khi mua sách.

Rie đã xuất bản một cuốn sách về tin học. Để khuyến khích nhiều người mua sách, cô có thể tặng sách cho một số cư dân. Khi Rie tặng sách cho cư dân \(i\) (\(1 \le i \le N\)), người đó sẽ có sách của cô. Ngoài ra, trong số các cư dân chưa có sách, mọi cư dân \(j\) (\(1 \le j \le N\)) thỏa mãn điều kiện sau đều sẽ mua sách và có được một bản:

Khoảng cách trên trục số giữa cư dân \(i\) và cư dân \(j\) không vượt quá \(E_i - E_j\), tức là \(\lvert X_i - X_j \rvert \le E_i - E_j\).

Nếu mọi cư dân đều đọc sách của Rie, các kỳ Olympic Tin học sẽ được biết đến rộng rãi hơn. Hãy tìm số cư dân ít nhất mà Rie cần tặng sách để tất cả cư dân của vương quốc JOI đều có sách của cô.

Dữ liệu vào

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

N
X_1 E_1
X_2 E_2
...
X_N E_N

Dữ liệu ra

In trên một dòng số cư dân ít nhất mà Rie cần tặng sách.

Ràng buộc

\(1 \le N \le 500\,000\).
\(1 \le X_i \le 10^9\) (\(1 \le i \le N\)).
\(1 \le E_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.

Chấm điểm

\(10\) điểm: \(E_1 = E_2 = \cdots = E_N\).
\(23\) điểm: \(N \le 16\).
\(36\) điểm: \(N \le 1000\).
\(31\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Chẳng hạn, Rie có thể tặng sách theo cách sau để tất cả cư dân đều có sách.

Trước tiên, Rie tặng sách cho cư dân \(3\).

Vì \(\lvert X_3 - X_1 \rvert = 1\) và \(E_3 - E_1 = 2\), cư dân \(1\) sẽ mua sách của Rie.

Vì \(\lvert X_3 - X_2 \rvert = 1\) và \(E_3 - E_2 = 1\), cư dân \(2\) sẽ mua sách của Rie.

Vì \(\lvert X_3 - X_4 \rvert = 3\) và \(E_3 - E_4 = -1\), cư dân \(4\) sẽ không mua sách của Rie.

Như vậy, các cư dân \(1, 2, 3\) đã có sách. Tiếp theo, Rie tặng sách cho cư dân \(4\). Vì tất cả cư dân khác đều đã có sách, sau lần tặng này, mọi cư dân của vương quốc JOI đều có sách.

Không thể tặng sách cho ít hơn hai cư dân mà vẫn làm cho tất cả cư dân đều có sách, nên in ra \(2\).

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

Ví dụ 2

Input

Output

Giải thích

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

Ví dụ 3

Input

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019

Output

Giải thích

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

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

3. JOI 2023 - Maze

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

Chủ tịch K thích giải mê cung. Ông tìm thấy một bảng ô vuông có thể dùng để tạo mê cung. Bảng có dạng hình chữ nhật gồm \(R\) hàng và \(C\) cột, mỗi ô được tô màu trắng hoặc đen. Gọi ô ở hàng thứ \(i\) từ trên xuống (\(1 \le i \le R\)), cột thứ \(j\) từ trái sang (\(1 \le j \le C\)) là ô \((i, j)\).

Chủ tịch K quy định chỉ được đi qua các ô trắng, không được đi qua các ô đen. Cụ thể, ông chọn hai ô trắng: ô xuất phát \((S_r, S_c)\) và ô đích \((G_r, G_c)\). Mỗi bước được chuyển sang một ô trắng kề ô hiện tại theo một trong bốn hướng trên, dưới, trái, phải. Mục tiêu là tìm đường từ ô xuất phát đến ô đích bằng cách lặp lại các bước như vậy.

Sau khi đã chọn cố định ô xuất phát và ô đích, chủ tịch K nhận ra rằng, tùy cách tô màu của bảng, có thể không tồn tại đường đi chỉ qua các ô trắng nối hai ô này. Ông có một con dấu kích thước \(N \times N\) ô và muốn thực hiện thao tác sau một số lần để tạo ra một đường đi như vậy.

Trong mỗi thao tác, chọn một vùng hình vuông gồm \(N \times N\) ô nằm trong bảng và tô trắng tất cả các ô thuộc vùng đó. Cụ thể, chọn hai số nguyên \(a, b\) thỏa mãn \(1 \le a \le R - N + 1\) và \(1 \le b \le C - N + 1\). Với mọi cặp số nguyên \((i, j)\) thỏa mãn \(a \le i \le a + N - 1\) và \(b \le j \le b + N - 1\), tô ô \((i, j)\) thành màu trắng.

Vì dùng con dấu có thể làm bẩn tay, chủ tịch K muốn số thao tác ít nhất có thể. Cho màu của các ô, kích thước con dấu, ô xuất phát và ô đích, hãy tìm số thao tác nhỏ nhất cần thực hiện để có đường đi từ ô xuất phát đến ô đích chỉ qua các ô trắng.

Dữ liệu vào

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

R C N
S_r S_c
G_r G_c
A_1
A_2
...
A_R

\(A_i\) (\(1 \le i \le R\)) là xâu có độ dài \(C\), chỉ gồm các ký tự . và #. Ký tự thứ \(j\) (\(1 \le j \le C\)) của \(A_i\) biểu diễn màu của ô \((i, j)\): . là màu trắng, còn # là màu đen.

Dữ liệu ra

In trên một dòng số thao tác nhỏ nhất cần thực hiện để có đường đi từ ô xuất phát đến ô đích chỉ qua các ô trắng.

Ràng buộc

\(1 \le N \le R \le C\).
\(R \times C \le 6\,000\,000\).
\(1 \le S_r \le R\).
\(1 \le S_c \le C\).
\(1 \le G_r \le R\).
\(1 \le G_c \le C\).
\((S_r, S_c) \ne (G_r, G_c)\).
\(A_i\) (\(1 \le i \le R\)) là xâu có độ dài \(C\), chỉ gồm . và #.
Ô \((S_r, S_c)\) có màu trắng.
Ô \((G_r, G_c)\) có màu trắng.
\(R, C, N, S_r, S_c, G_r, G_c\) là các số nguyên.

Chấm điểm

\(8\) điểm: \(N = 1\), \(R \times C \le 1\,500\,000\).
\(19\) điểm: \(R \times C \le 1000\).
\(16\) điểm: Đáp án không vượt quá \(10\) và \(R \times C \le 1\,500\,000\).
\(19\) điểm: \(R \times C \le 60\,000\).
\(5\) điểm: \(R \times C \le 150\,000\).
\(19\) điểm: \(R \times C \le 1\,500\,000\).
\(8\) điểm: \(R \times C \le 3\,000\,000\).
\(6\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

2 4 2
1 1
2 4
.###
###.

Output

Giải thích

Nếu chọn \((a, b) = (1, 2)\) và thực hiện một thao tác, các ô \((1, 2)\), \((1, 3)\), \((2, 2)\), \((2, 3)\) sẽ trở thành màu trắng. Khi đó, có đường đi chỉ qua các ô trắng từ ô xuất phát đến ô đích. Chẳng hạn, đường đi \((1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4)\) thỏa mãn yêu cầu.

Nếu không thực hiện thao tác nào thì không có đường đi như vậy, nên in ra \(1\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 3, 4, 5, 6, 7, 8\).

Ví dụ 2

Input

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###

Output

Giải thích

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

Ví dụ 3

Input

6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 3, 4, 5, 6, 7, 8\).

Ví dụ 4

Input

1 15 1
1 15
1 1
...............

Output

Giải thích

Có thể đã tồn tại đường đi từ ô xuất phát đến ô đích chỉ qua các ô trắng ngay cả khi không thực hiện thao tác nào.

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

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

4. JOI 2023 - Cat Exercise

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

Có \(N\) tháp dành cho mèo, được đánh số từ \(1\) đến \(N\). Tháp \(i\) (\(1 \le i \le N\)) có chiều cao \(P_i\). Chiều cao của các tháp là các số nguyên đôi một khác nhau từ \(1\) đến \(N\).

Có \(N - 1\) cặp tháp kề nhau. Với mỗi \(j\) (\(1 \le j \le N - 1\)), tháp \(A_j\) và tháp \(B_j\) kề nhau. Ban đầu, có thể đi từ bất kỳ tháp nào đến bất kỳ tháp nào khác bằng cách liên tục di chuyển sang một tháp kề.

Ban đầu, một chú mèo ở trên tháp có chiều cao \(N\).

Ta cho mèo tập thể dục bằng cách lặp lại thao tác chọn một tháp và đặt chướng ngại vật lên tháp đó. Không được đặt chướng ngại vật lên tháp đã có chướng ngại vật. Sau mỗi thao tác, các trường hợp sau xảy ra:

Nếu mèo không ở trên tháp được chọn, không có gì xảy ra.
Nếu mèo ở trên tháp được chọn và tất cả các tháp kề với tháp đó đều có chướng ngại vật, buổi tập kết thúc.
Trong trường hợp còn lại, xét các tháp mà mèo có thể đi đến từ tháp hiện tại bằng cách liên tục di chuyển sang một tháp kề không có chướng ngại vật. Trong số đó, bỏ qua tháp hiện tại, mèo sẽ đi đến tháp cao nhất. Mèo chọn đường đi có số lần di chuyển sang tháp kề ít nhất.

Cho chiều cao của các tháp và các cặp tháp kề nhau, hãy tìm tổng số lần di chuyển sang tháp kề lớn nhất mà mèo có thể thực hiện nếu ta đặt các chướng ngại vật một cách phù hợp.

Dữ liệu vào

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

N
P_1 P_2 ... P_N
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}

Dữ liệu ra

In trên một dòng tổng số lần di chuyển sang tháp kề lớn nhất mà mèo có thể thực hiện.

Ràng buộc

\(2 \le N \le 200\,000\).
\(1 \le P_i \le N\) (\(1 \le i \le N\)).
\(P_i \ne P_j\) (\(1 \le i < j \le N\)).
\(1 \le A_j < B_j \le N\) (\(1 \le j \le N - 1\)).
Ban đầu, có thể đi từ bất kỳ tháp nào đến bất kỳ tháp nào khác bằng cách liên tục di chuyển sang một tháp kề.
Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

\(7\) điểm: \(A_i = i\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\); \(N \le 16\).
\(7\) điểm: \(A_i = i\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\); \(N \le 300\).
\(7\) điểm: \(A_i = i\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\); \(N \le 5000\).
\(10\) điểm: \(N \le 5000\).
\(20\) điểm: \(A_i = i\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\).
\(23\) điểm: \(A_i = \left\lfloor \frac{i + 1}{2} \right\rfloor\), \(B_i = i + 1\) với mọi \(1 \le i \le N - 1\).
\(26\) điểm: Không có ràng buộc bổ sung.

Ở đây, \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Nếu cho mèo tập theo cách sau, mèo sẽ di chuyển tổng cộng \(3\) lần.

Đặt chướng ngại vật lên tháp \(1\). Mèo không di chuyển.
Đặt chướng ngại vật lên tháp \(2\). Mèo đi từ tháp \(2\) sang tháp \(3\), rồi từ tháp \(3\) sang tháp \(4\).
Đặt chướng ngại vật lên tháp \(4\). Mèo đi từ tháp \(4\) sang tháp \(3\).
Đặt chướng ngại vật lên tháp \(3\). Buổi tập kết thúc.

Không có cách nào làm cho mèo di chuyển sang tháp kề từ \(4\) lần trở lên, nên in ra \(3\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(1, 2, 3, 4, 5, 7\).

Ví dụ 2

Input

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

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(4, 6, 7\).

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

5. JOI 2023 - Modern Machine

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

Bitaro được tặng một chiếc máy JOI nhân dịp sinh nhật. Máy gồm một quả bóng, \(N\) ô phát sáng và \(M\) nút bấm. Các ô được đánh số từ \(1\) đến \(N\). Khi bật nguồn, ô \(i\) (\(1 \le i \le N\)) phát sáng với màu \(C_i\), là xanh lam (B) hoặc đỏ (R). Các nút bấm được đánh số từ \(1\) đến \(M\).

Khi Bitaro nhấn nút \(j\) (\(1 \le j \le M\)), máy thực hiện theo thứ tự sau:

Đặt quả bóng lên ô \(A_j\).
Đổi màu ô \(A_j\) thành đỏ, bất kể màu trước đó của ô này.
Lặp lại quá trình dưới đây cho đến khi quả bóng được lấy ra khỏi máy.

Gọi \(p\) là số hiệu ô đang chứa quả bóng. Nếu ô \(p\) có màu xanh lam, đổi ô này thành màu đỏ. Sau đó, nếu \(p = 1\), lấy quả bóng ra khỏi máy; nếu không, chuyển quả bóng sang ô \(p - 1\).

Nếu ô \(p\) có màu đỏ, đổi ô này thành màu xanh lam. Sau đó, nếu \(p = N\), lấy quả bóng ra khỏi máy; nếu không, chuyển quả bóng sang ô \(p + 1\).

Thích thú với chiếc máy, Bitaro lên kế hoạch thực hiện \(Q\) thí nghiệm. Trong thí nghiệm thứ \(k\) (\(1 \le k \le Q\)), Bitaro bật nguồn để các ô có lại màu ban đầu \(C_i\), rồi nhấn lần lượt các nút \(L_k, L_k + 1, \ldots, R_k\). Sau mỗi lần nhấn nút, cậu đợi đến khi quả bóng được lấy ra khỏi máy rồi mới nhấn nút tiếp theo.

Cho thông tin về chiếc máy và các thí nghiệm, hãy tìm số ô màu đỏ sau khi mỗi thí nghiệm kết thúc.

Dữ liệu vào

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

N M
C_1C_2...C_N
A_1 A_2 ... A_M
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dòng thứ hai là xâu gồm \(N\) ký tự B hoặc R, không có dấu cách giữa các ký tự.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa số ô màu đỏ sau khi thí nghiệm thứ \(k\) kết thúc.

Ràng buộc

\(3 \le N \le 120\,000\).
\(1 \le M \le 120\,000\).
\(C_i\) là B hoặc R (\(1 \le i \le N\)).
\(1 \le A_j \le N\) (\(1 \le j \le M\)).
\(1 \le Q \le 120\,000\).
\(1 \le L_k \le R_k \le M\) (\(1 \le k \le Q\)).
\(N, M, A_j, Q, L_k, R_k\) là các số nguyên.

Chấm điểm

\(3\) điểm: \(N \le 300\), \(M \le 300\), \(Q = 1\).
\(12\) điểm: \(N \le 7000\), \(M \le 7000\), \(Q = 1\).
\(10\) điểm: \(Q \le 5\).
\(11\) điểm: \(N = 10\) và \(C_i\) là R với mọi \(1 \le i \le N\).
\(26\) điểm: Tồn tại số nguyên \(t\) (\(0 \le t \le N\)) sao cho \(C_i\) là R với mọi \(i \le t\) và là B với mọi \(i > t\).
\(17\) điểm: \(A_j \le 20\) hoặc \(A_j > N - 20\) với mọi \(1 \le j \le M\).
\(21\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

5 1
RBRRB
4
1
1 1

Output

Giải thích

Thí nghiệm thứ nhất diễn ra như sau.

Bitaro nhấn nút \(1\), quả bóng được đặt lên ô \(4\). Ô \(4\) được đổi thành màu đỏ. Vì ô này vốn đã đỏ nên màu không thay đổi.

Sau đó, máy thực hiện các bước sau:

Ô \(4\) đang đỏ, nên đổi thành xanh lam và chuyển quả bóng sang ô \(5\).
Ô \(5\) đang xanh lam, nên đổi thành đỏ và chuyển quả bóng sang ô \(4\).
Ô \(4\) đang xanh lam, nên đổi thành đỏ và chuyển quả bóng sang ô \(3\).
Ô \(3\) đang đỏ, nên đổi thành xanh lam và chuyển quả bóng sang ô \(4\).
Ô \(4\) đang đỏ, nên đổi thành xanh lam và chuyển quả bóng sang ô \(5\).
Ô \(5\) đang đỏ, nên đổi thành xanh lam và lấy quả bóng ra khỏi máy.

Sau thí nghiệm, chỉ có ô \(1\) mang màu đỏ, nên in ra \(1\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(1, 2, 3, 6, 7\).

Ví dụ 2

Input

Output

5
0

Giải thích

Sau thí nghiệm thứ nhất, các ô \(1, 2, 3, 4, 5\) đều có màu đỏ. Có năm ô như vậy, nên in ra \(5\).

Sau thí nghiệm thứ hai, không có ô nào mang màu đỏ, nên in ra \(0\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(3, 6, 7\).

Ví dụ 3

Input

10 3
BBRRBRBRRB
2 10 5
1
1 3

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(1, 2, 3, 6, 7\).

Ví dụ 4

Input

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

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(3, 4, 5, 6, 7\).

Ví dụ 5

Input

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

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(3, 5, 6, 7\).

Ví dụ 6

Input

30 10
RRRBBRBBBRBBBRBRBRRRRRBBBBRBRR
3 28 2 29 1 30 6 14 7 7
10
1 10
2 3
2 5
2 8
3 3
3 6
4 5
4 7
5 9
10 10

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(6, 7\).

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.