BOI 2022 - Boarding Passes - LQDOJ: Le Quy Don Online Judge

BOI 2022 - Boarding Passes

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

Sau khi vượt qua được những truyền thống địa phương, bạn đến kịp chuyến phà ngay trước giờ khởi hành. Tuy nhiên, bạn không ngờ lại có nhiều người đi Lübeck đến thế! Vì không muốn muộn lễ trao giải — bạn còn cần thời gian cất toàn bộ tác phẩm nghệ thuật lấy được vào nhà trọ — bạn muốn đẩy nhanh việc lên phà.

Phà có một hàng gồm \(N\) ghế, được đặt kín bởi \(N\) hành khách. Vé của mỗi người ghi ghế được chỉ định và một trong \(G\) nhóm lên phà. Các nhóm lần lượt được gọi lên phà. Những người trong cùng một nhóm lên theo thứ tự ngẫu nhiên, với mọi thứ tự có xác suất như nhau. Mỗi hành khách có thể lên từ đầu hoặc cuối hàng ghế, rồi đi đến ghế của mình trước khi người tiếp theo lên.

Bạn nhận thấy việc tốn thời gian nhất là khi một hành khách phải đi ngang qua người đã ngồi trên ghế: hành lý chứa tất cả những chiếc cà vạt ấy là một chướng ngại đáng kể trên lối đi. May thay, bạn tìm thấy một bộ đồng phục nhân viên trong tủ gần đó, nên có thể quyết định thứ tự các nhóm lên phà và thông báo cho từng hành khách, trước khi bắt đầu lên phà, rằng họ phải lên từ đầu hay cuối hàng ghế.

Hãy viết chương trình dùng thông tin trên vé để tính kỳ vọng nhỏ nhất của tổng số lần một hành khách đi ngang qua người đã ngồi, khi bạn chọn tối ưu cả thứ tự các nhóm và hướng lên phà của từng hành khách.

Chú thích

Với một thứ tự các nhóm và một cách chỉ định hướng lên phà cho từng hành khách, kỳ vọng của số lần đi ngang qua được định nghĩa là

\[ 1\cdot p_1+2\cdot p_2+3\cdot p_3+\cdots, \]

trong đó \(p_k\) là xác suất có đúng \(k\) lần đi ngang qua người đã ngồi trong quá trình lên phà. Nói cách khác, đây là số lần đi ngang qua trung bình khi xét mọi thứ tự có thể của các hành khách trong từng nhóm.

Dữ liệu vào

Dữ liệu vào gồm một chuỗi \(N\) ký tự \(s_1\ldots s_N\). Ký tự \(s_i\) là một trong \(G\) chữ cái in hoa đầu tiên của bảng chữ cái tiếng Anh, biểu thị nhóm lên phà của hành khách được chỉ định ngồi ở ghế thứ \(i\). Ghế ở đầu hàng được đánh số \(1\).

Dữ liệu ra

In một số duy nhất: kỳ vọng nhỏ nhất của số lần đi ngang qua người đã ngồi, khi chọn tối ưu thứ tự các nhóm và hướng lên phà của từng hành khách. Đáp án được chấp nhận nếu sai số tuyệt đối không vượt quá \(0.001\).

Ràng buộc

\(1\le G\le15\).
\(1\le N\le100\,000\).
Giới hạn thời gian: \(2\) giây.
Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

\(5\) điểm: \(G=1\), tức là chỉ có một nhóm lên phà.
\(25\) điểm: \(G\le7\) và \(N\le100\).
\(30\) điểm: \(G\le10\) và \(N\le10\,000\).
\(40\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

AACCAA

Output

Giải thích

Nhóm C nên lên trước nhóm A. Các hành khách ở ghế \(1\), \(2\) và \(3\) nên lên từ đầu hàng; những người còn lại lên từ cuối hàng.

Hai hành khách nhóm C không thể đi ngang qua nhau, và cũng không đi ngang qua hành khách nhóm A nào vì nhóm C lên trước. Những hành khách nhóm A cũng không đi ngang qua hành khách nhóm C: mọi người nhóm A lên từ đầu hàng đều ngồi trước các ghế của nhóm C, còn mọi người nhóm A lên từ cuối hàng đều ngồi sau các ghế của nhóm C.

Vì vậy, chỉ có hai khả năng đi ngang qua: người ở ghế \(2\) đi ngang qua người ở ghế \(1\), chỉ xảy ra nếu người ở ghế \(1\) lên trước người ở ghế \(2\); tương tự đối với hai người ở ghế \(5\) và \(6\). Mỗi khả năng xảy ra với xác suất \(50\%\), nên kỳ vọng của tổng số lần đi ngang qua bằng \(1\).

Ví dụ 2

Input

HEHEHEHIHILOL

Output

7.5

Ví dụ 3

Input

ONMLKJIHGFEDCBAABCDEFGHIJKLMNO

Output

Ví dụ 4

Input

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Output

100800.5

Giải thích

Dữ liệu vào gồm đúng \(899\) ký tự A. Đề PDF viết tắt chuỗi này bằng dấu ba chấm; ở đây chuỗi được ghi đầy đủ. Tất cả dữ liệu vào mẫu có trong gói đính kèm của bài trên CMS chính thức.

Bình luận

Tải bình luận...

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

Kỳ thi:

BOI 2022 - Ngày 2 (1 Tháng năm, 2022)