JOI 2023 - Chorus

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2700 (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 
2
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ỗ:

  1. Đổi chỗ chú thứ \(3\) và thứ \(4\). Xâu trở thành \(\mathrm{AA}\underline{\mathrm{AB}}\mathrm{BABBAB}\), tức AAABBABBAB.
  2. Đổ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 
0
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 
9
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 
37
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.

Tệp

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: