JOI 2023 - Tuyển chọn mùa xuân - Ngày 3 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2023 - Chorus	100 (p)	6.0s	1G
2	JOI 2023 - Cookies	100 (p)	1.0s	1G
3	JOI 2023 - Tourism	100 (p)	4.0s	1G

1. JOI 2023 - Chorus

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

Có \(2N\) chú hải ly thuộc một dàn hợp xướng đang đứng thành một hàng ngang trên sân khấu. Mỗi chú đảm nhận bè alto hoặc bè bass. Thông tin này được cho bởi xâu \(S\): chú thứ \(i\) tính từ cánh phải của sân khấu, tức từ trái sang phải khi nhìn từ phía khán giả, hát bè alto nếu ký tự thứ \(i\) của \(S\) là A, và hát bè bass nếu ký tự đó là B. Có đúng \(N\) chú hát bè alto và \(N\) chú hát bè bass.

Dàn hợp xướng sắp hát \(K\) bài. Vì các bài đều rất khó, mỗi chú hải ly chỉ hát đúng một bài, không hát các bài khác. Để tiếng hát hòa quyện, mỗi bài phải thỏa mãn tất cả các điều kiện sau:

Có ít nhất một chú hải ly hát bài đó.
Số chú hát bè alto bằng số chú hát bè bass trong bài đó.
Chỉ xét những chú hát bài đó: tất cả các chú hát bè alto phải đứng trước tất cả các chú hát bè bass theo thứ tự từ trái sang phải khi nhìn từ phía khán giả.

Nhạc trưởng Bitaro muốn phân công bài hát thỏa mãn các điều kiện, nhưng nhận ra có thể chưa tồn tại cách phân công nào. Vì vậy, trước khi phân công, Bitaro có thể thực hiện nhiều lần thao tác đổi chỗ hai chú hải ly đứng cạnh nhau.

Bitaro muốn thực hiện ít thao tác nhất và nhờ bạn giúp đỡ. Cho thông tin dàn hợp xướng và số bài hát \(K\), hãy tìm số thao tác nhỏ nhất để tồn tại cách phân công hợp lệ. Với các ràng buộc của bài, luôn có thể thực hiện các thao tác để đạt được điều này.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N K
S

Dữ liệu ra

In một dòng chứa số thao tác nhỏ nhất Bitaro cần thực hiện.

Ràng buộc

\(1\le N\le 1\,000\,000\).
\(1\le K\le N\).
\(S\) có độ dài \(2N\), gồm đúng \(N\) ký tự A và \(N\) ký tự B.
\(N,K\) là các số nguyên.

Phân nhóm

Nhóm 1 (16 điểm): \(N\le 10\).
Nhóm 2 (24 điểm): \(N\le 500\).
Nhóm 3 (21 điểm): \(N\le 5000\).
Nhóm 4 (26 điểm): \(N\le 100\,000\).
Nhóm 5 (13 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

5 2
AABABABBAB

Output

Giải thích

Trong toàn bộ ví dụ, vị trí được tính từ trái sang phải khi nhìn từ phía khán giả. Bitaro có thể làm như sau; hai ký tự gạch chân là vị trí vừa được đổi chỗ:

Đổi chỗ chú thứ \(3\) và thứ \(4\). Xâu trở thành \(\mathrm{AA}\underline{\mathrm{AB}}\mathrm{BABBAB}\), tức AAABBABBAB.
Đổi chỗ chú thứ \(8\) và thứ \(9\). Xâu trở thành \(\mathrm{AAABBAB}\underline{\mathrm{AB}}\mathrm{B}\), tức AAABBABABB.

Sau đó, phân công các chú ở vị trí \(1,2,3,4,5,7\) hát bài thứ nhất; các chú ở vị trí \(6,8,9,10\) hát bài thứ hai. Cách phân công này thỏa mãn mọi điều kiện.

Không thể đạt được một cách phân công hợp lệ với ít hơn \(2\) thao tác, nên kết quả là \(2\). Ví dụ thỏa mãn tất cả các nhóm.

Ví dụ 2

Input

5 3
AABABABBAB

Output

Giải thích

Không cần đổi chỗ, Bitaro có thể phân công theo vị trí từ trái sang phải khi nhìn từ phía khán giả:

Các chú ở vị trí \(1,2,3,5\) hát bài thứ nhất.
Các chú ở vị trí \(4,6,7,8\) hát bài thứ hai.
Các chú ở vị trí \(9,10\) hát bài thứ ba.

Mọi điều kiện đều được thỏa mãn, nên kết quả là \(0\). Ví dụ thỏa mãn tất cả các nhóm.

Ví dụ 3

Input

3 1
BBBAAA

Output

Giải thích

Ví dụ thỏa mãn tất cả các nhóm.

Ví dụ 4

Input

10 3
ABABBBBABBABABABAAAA

Output

Giải thích

Ví dụ thỏa mãn tất cả các nhóm.

Nguồn

JOI 2022/2023 Spring Training, Contest 3, 21/03/2023. Đề gốc của JCIOI; bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.

2. JOI 2023 - Cookies

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

Rie rất thích làm bánh quy. Cô đã làm \(N\) loại bánh, trong đó có \(A_i\) chiếc thuộc loại \(i\) với \(1\le i\le N\). Để bán bánh, Rie muốn đóng tất cả bánh vào các hộp, thỏa mãn hai điều kiện:

Các chiếc bánh trong cùng một hộp phải thuộc những loại khác nhau.
Số chiếc bánh trong mỗi hộp phải bằng một trong \(M\) số \(B_1,B_2,\ldots,B_M\).

Cho số lượng bánh từng loại và các kích thước hộp được phép, hãy xác định có thể đóng tất cả bánh vào hộp hay không. Nếu có thể, hãy đưa ra một cách đóng sử dụng ít hộp nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N
A_1 A_2 ... A_N
M
B_1 B_2 ... B_M

Dữ liệu ra

Nếu có thể đóng tất cả bánh hợp lệ, gọi \(x\) là số hộp sử dụng. Hộp thứ \(k\) có \(c_k\) chiếc, mỗi chiếc thuộc một trong các loại \(v_{k,1},v_{k,2},\ldots,v_{k,c_k}\), mỗi loại đúng một chiếc. In ra đầu ra chuẩn theo định dạng:

x
c_1 v_1,1 v_1,2 ... v_1,c_1
c_2 v_2,1 v_2,2 ... v_2,c_2
...
c_x v_x,1 v_x,2 ... v_x,c_x

\(x\) phải là số hộp nhỏ nhất có thể. Nếu có nhiều cách đóng hợp lệ với số hộp nhỏ nhất, có thể in bất kỳ cách nào.

Nếu không thể đóng tất cả bánh thỏa mãn các điều kiện, in -1.

Ràng buộc

\(1\le N\le 15\,000\).
\(A_i\ge 1\) với mọi \(1\le i\le N\).
\(A_1+A_2+\cdots+A_N\le 15\,000\).
\(1\le M\le N\).
\(1\le B_j\le N\) với mọi \(1\le j\le M\).
\(B_j<B_{j+1}\) với mọi \(1\le j<M\).
Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

Nhóm 1 (6 điểm): \(N\le 500\) và \(A_i=1\) với mọi \(1\le i\le N\).
Nhóm 2 (7 điểm): \(N\le 500\) và \(M=1\).
Nhóm 3 (12 điểm): \(A_1+A_2+\cdots+A_N\le 15\).
Nhóm 4 (45 điểm): \(A_1+A_2+\cdots+A_N\le 500\).
Nhóm 5 (15 điểm): \(A_1+A_2+\cdots+A_N\le 3000\).
Nhóm 6 (15 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

7
1 1 1 1 1 1 1
3
1 2 3

Output

Giải thích

Có thể đóng \(7\) chiếc bánh vào \(3\) hộp như sau:

Hộp thứ nhất chứa một chiếc loại \(1\) và một chiếc loại \(7\).
Hộp thứ hai chứa một chiếc loại \(2\) và một chiếc loại \(6\).
Hộp thứ ba chứa một chiếc mỗi loại \(3,4,5\).

Không thể đóng hợp lệ cả \(7\) chiếc vào nhiều nhất \(2\) hộp, nên cách trên được chấp nhận. Ngoài cách này còn có các kết quả khác được chấp nhận. Ví dụ thỏa mãn các nhóm \(1,3,4,5,6\).

Ví dụ 2

Input

Output

-1

Giải thích

Không tồn tại cách đóng hợp lệ cả \(15\) chiếc bánh, nên in -1. Ví dụ thỏa mãn các nhóm \(2,3,4,5,6\).

Ví dụ 3

Input

7
5 4 4 2 1 1 1
2
2 6

Output

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

Giải thích

Ví dụ thỏa mãn các nhóm \(4,5,6\).

Nguồn

JOI 2022/2023 Spring Training, Contest 3, 21/03/2023. Đề gốc của JCIOI; bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.

3. JOI 2023 - Tourism

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

Vương quốc JOI gồm \(N\) hòn đảo, đánh số từ \(1\) đến \(N\). Có \(N-1\) cây cầu, đánh số từ \(1\) đến \(N-1\). Cầu \(i\) nối hai đảo \(A_i\) và \(B_i\) theo cả hai chiều. Từ bất kỳ đảo nào cũng có thể đi đến bất kỳ đảo khác bằng cách qua một số cây cầu.

Vương quốc có \(M\) địa điểm tham quan, đánh số từ \(1\) đến \(M\). Địa điểm \(j\) nằm trên đảo \(C_j\).

Có \(Q\) du khách, đánh số từ \(1\) đến \(Q\), dự định đến tham quan. Mỗi người thực hiện chuyến đi như sau:

Chọn một đảo \(x\) với \(1\le x\le N\) và đáp máy bay xuống đảo đó.
Thực hiện nhiều lần các hành động sau, với loại hành động và thứ tự tùy ý: chọn một địa điểm tham quan trên đảo hiện tại để ghé thăm; hoặc đi qua một cây cầu đến đảo khác.
Từ đảo hiện tại, đáp máy bay rời vương quốc.

Du khách \(k\) muốn ghé thăm tất cả các địa điểm \(L_k,L_k+1,\ldots,R_k\). Vì ngân sách có hạn, người đó muốn giảm thiểu số đảo khác nhau đã đặt chân đến ít nhất một lần, kể cả các đảo chỉ đi qua.

Cho thông tin vương quốc và yêu cầu của các du khách, hãy tìm số đảo nhỏ nhất có thể cho từng người.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N M Q
A_1 B_1
A_2 B_2
...
A_(N-1) B_(N-1)
C_1 C_2 ... C_M
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dữ liệu ra

In \(Q\) dòng. Dòng \(k\) chứa số đảo khác nhau ít nhất mà du khách \(k\) cần đặt chân đến để ghé thăm mọi địa điểm yêu cầu.

Ràng buộc

\(1\le N\le 100\,000\).
\(1\le M\le 100\,000\).
\(1\le Q\le 100\,000\).
\(1\le A_i,B_i\le N\) với \(1\le i<N\).
Từ bất kỳ đảo nào cũng có thể đi đến bất kỳ đảo khác qua các cây cầu.
\(1\le C_j\le N\) với \(1\le j\le M\).
\(1\le L_k\le R_k\le M\) với \(1\le k\le Q\).
Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

Nhóm 1 (5 điểm): \(N\le 300\), \(M\le 300\), \(Q\le 300\).
Nhóm 2 (5 điểm): \(N\le 2000\), \(M\le 2000\), \(Q\le 2000\).
Nhóm 3 (7 điểm): \(A_i=i\), \(B_i=i+1\) với mọi \(1\le i<N\).
Nhóm 4 (18 điểm): \(L_1=1\), \(R_k+1=L_{k+1}\) với mọi \(1\le k<Q\), và \(R_Q=M\).
Nhóm 5 (24 điểm): \(A_i=\lfloor(i+1)/2\rfloor\), \(B_i=i+1\) với mọi \(1\le i<N\). Ký hiệu \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).
Nhóm 6 (41 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

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

Output

4
6

Giải thích

Du khách thứ nhất có thể ghé thăm đủ các địa điểm \(1,2,3\) theo hành trình:

Đáp máy bay xuống đảo \(2\).
Ghé địa điểm \(1\) trên đảo \(2\).
Qua cầu \(1\) từ đảo \(2\) đến đảo \(1\).
Qua cầu \(2\) từ đảo \(1\) đến đảo \(3\).
Ghé địa điểm \(2\) trên đảo \(3\).
Qua cầu \(5\) từ đảo \(3\) đến đảo \(6\).
Ghé địa điểm \(3\) trên đảo \(6\).
Rời vương quốc bằng máy bay từ đảo \(6\).

Người này đặt chân đến bốn đảo \(1,2,3,6\). Không thể ghé đủ các địa điểm \(1,2,3\) mà chỉ đến nhiều nhất ba đảo, nên dòng đầu là \(4\).

Du khách thứ hai có thể ghé thăm đủ các địa điểm \(4,5,6\) theo hành trình:

Đáp máy bay xuống đảo \(3\).
Qua cầu \(6\) từ đảo \(3\) đến đảo \(7\).
Ghé địa điểm \(6\) trên đảo \(7\).
Qua cầu \(6\) từ đảo \(7\) trở về đảo \(3\).
Qua cầu \(2\) từ đảo \(3\) đến đảo \(1\).
Qua cầu \(1\) từ đảo \(1\) đến đảo \(2\).
Qua cầu \(3\) từ đảo \(2\) đến đảo \(4\).
Ghé địa điểm \(4\) trên đảo \(4\).
Qua cầu \(3\) từ đảo \(4\) trở về đảo \(2\).
Qua cầu \(4\) từ đảo \(2\) đến đảo \(5\).
Ghé địa điểm \(5\) trên đảo \(5\).
Rời vương quốc bằng máy bay từ đảo \(5\).

Người này đặt chân đến sáu đảo \(1,2,3,4,5,7\). Mỗi đảo chỉ được tính một lần dù được ghé lại. Không thể ghé đủ các địa điểm \(4,5,6\) mà chỉ đến nhiều nhất năm đảo, nên dòng thứ hai là \(6\).

Ví dụ thỏa mãn các nhóm \(1,2,4,5,6\).

Ví dụ 2

Input

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

Output

Giải thích

Ví dụ thỏa mãn các nhóm \(1,2,3,6\).

Ví dụ 3

Input

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

Output

Giải thích

Ví dụ thỏa mãn các nhóm \(1,2,6\).

Nguồn

JOI 2022/2023 Spring Training, Contest 3, 21/03/2023. Đề gốc của JCIOI; bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.