JOI 2024 - White Light 2

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: 1800 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có \(N\) bóng đèn xếp thành một hàng ngang, được đánh số từ \(1\) đến \(N\) từ trái sang phải. Mỗi bóng đèn có màu đỏ, xanh lá hoặc xanh dương. Màu của các bóng đèn được biểu diễn bằng xâu \(S\): bóng đèn \(i\) (\(1 \le i \le N\)) có màu đỏ nếu ký tự thứ \(i\) của \(S\) là R, màu xanh lá nếu là G, và màu xanh dương nếu là B. Ban đầu, tất cả các bóng đèn đều sáng.

Khi vẫn còn ít nhất một bóng đèn sáng, JOI có thể thực hiện ba loại thao tác sau theo thứ tự tùy ý và với số lần tùy ý. JOI cũng có thể không thực hiện thao tác nào.

  • Trả \(A\) yên để tắt bóng đèn ngoài cùng bên trái trong số các bóng đèn đang sáng.
  • Trả \(B\) yên để tắt bóng đèn ngoài cùng bên phải trong số các bóng đèn đang sáng.
  • Trả \(C\) yên để chọn một bóng đèn đang sáng và đổi nó sang màu tùy ý.

JOI muốn khi nhìn hàng đèn từ xa, chúng trông có màu trắng đẹp mắt. Để làm được điều đó, dãy màu của các bóng đèn còn sáng, xét từ trái sang phải, phải là các lần lặp trọn vẹn của RGB (đỏ, xanh lá, xanh dương), có dạng RGBRGB...RGB. Nếu không còn bóng đèn nào sáng thì cũng được xem là một dãy lặp của RGB. Lưu ý rằng các dãy như GBRGBR hoặc RGBRG không thỏa mãn điều kiện.

Cho thông tin về hàng đèn và chi phí các thao tác, hãy viết chương trình tìm số tiền ít nhất cần trả để dãy màu của các bóng đèn còn sáng là một dãy lặp của RGB.

Dữ liệu vào

Dòng thứ nhất chứa số nguyên \(N\).

Dòng thứ hai chứa xâu \(S\).

Dòng thứ ba chứa ba số nguyên \(A, B, C\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra trên một dòng số tiền ít nhất cần trả để dãy màu của các bóng đèn còn sáng là một dãy lặp của RGB, không kèm đơn vị yên.

Ràng buộc

  • \(1 \le N \le 200\,000\).
  • \(S\) là xâu có độ dài \(N\).
  • Mỗi ký tự của \(S\) là R, G hoặc B.
  • \(1 \le A \le 10^9\).
  • \(1 \le B \le 10^9\).
  • \(1 \le C \le 10^9\).
  • \(N, A, B, C\) là các số nguyên.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

  1. (4 điểm) \(N = 3\).
  2. (22 điểm) \(N \le 300\).
  3. (19 điểm) \(N \le 10\,000\).
  4. (9 điểm) \(N\) chia hết cho \(3\), \(A = 10^9\), \(B = 10^9\), \(C = 1\).
  5. (10 điểm) \(A = 10^9\), \(B = 10^9\), \(C = 1\).
  6. (36 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
6
GRBBRG
3 4 5
Output 
16
Giải thích

Chẳng hạn, có thể thực hiện bốn thao tác sau để dãy màu của các bóng đèn còn sáng là một dãy lặp của RGB. Ký hiệu - biểu diễn một bóng đèn đã tắt.

  1. Trả \(3\) yên để tắt bóng đèn \(1\), là bóng ngoài cùng bên trái đang sáng. Trạng thái hàng đèn trở thành -RBBRG.
  2. Trả \(4\) yên để tắt bóng đèn \(6\), là bóng ngoài cùng bên phải đang sáng. Trạng thái hàng đèn trở thành -RBBR-.
  3. Trả \(4\) yên để tắt bóng đèn \(5\), là bóng ngoài cùng bên phải đang sáng. Trạng thái hàng đèn trở thành -RBB--.
  4. Trả \(5\) yên để đổi bóng đèn \(3\) sang màu xanh lá. Trạng thái hàng đèn trở thành -RGB--.

Không thể đạt được yêu cầu với chi phí nhỏ hơn \(16\) yên, nên in ra \(16\).

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

Ví dụ 2

Input 
3
BRG
1000000000 1000000000 1
Output 
3
Giải thích

Chẳng hạn, có thể thực hiện ba thao tác sau để dãy màu của các bóng đèn còn sáng là một dãy lặp của RGB. Ký hiệu - biểu diễn một bóng đèn đã tắt.

  1. Trả \(1\) yên để đổi bóng đèn \(2\) sang màu xanh lá. Trạng thái hàng đèn trở thành BGG.
  2. Trả \(1\) yên để đổi bóng đèn \(3\) sang màu xanh dương. Trạng thái hàng đèn trở thành BGB.
  3. Trả \(1\) yên để đổi bóng đèn \(1\) sang màu đỏ. Trạng thái hàng đèn trở thành RGB.

Không thể đạt được yêu cầu với chi phí nhỏ hơn \(3\) yên, nên in ra \(3\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 3, 4, 5, 6\).

Ví dụ 3

Input 
3
GRB
9 11 14
Output 
27
Giải thích

Chẳng hạn, có thể thực hiện ba thao tác sau để dãy màu của các bóng đèn còn sáng là một dãy lặp của RGB. Ký hiệu - biểu diễn một bóng đèn đã tắt.

  1. Trả \(9\) yên để tắt bóng đèn \(1\), là bóng ngoài cùng bên trái đang sáng. Trạng thái hàng đèn trở thành -RB.
  2. Trả \(9\) yên để tắt bóng đèn \(2\), là bóng ngoài cùng bên trái đang sáng. Trạng thái hàng đèn trở thành --B.
  3. Trả \(9\) yên để tắt bóng đèn \(3\), là bóng ngoài cùng bên trái đang sáng. Trạng thái hàng đèn trở thành ---.

Không thể đạt được yêu cầu với chi phí nhỏ hơn \(27\) yên, nên in ra \(27\). Lưu ý rằng trường hợp không còn bóng đèn nào sáng cũng thỏa mãn điều kiện.

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 3, 6\).

Ví dụ 4

Input 
9
RGBRGBRGB
1000000000 1000000000 1
Output 
0
Giải thích

Dãy màu của hàng đèn đã là một dãy lặp của RGB, nên in ra \(0\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 4, 5, 6\).

Ví dụ 5

Input 
20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1
Output 
2000000008
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 5, 6\).

Ví dụ 6

Input 
23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229
Output 
10107224827
Giải thích

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

Nguồn

Bản dịch tiếng Việt từ đề 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.

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: