Jeff và Furik

Điểm: 6,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Jeff và Furik chơi một trò chơi trên một hoán vị $p_{1}, p_{2}, \dots, p_{n}$ của các số $1, 2, \dots, n$ . Hai người chơi lần lượt đi, Jeff đi trước.

Lượt của Jeff: Jeff chọn một cặp phần tử kề nhau bất kỳ và đổi chỗ chúng.
Lượt của Furik: Furik tung một đồng xu (xác suất "ngửa" và "sấp" bằng nhau là 50%).
- Nếu ra ngửa: Furik chọn ngẫu nhiên đều một cặp chỉ số $(i, i + 1)$ thỏa $p_{i} > p_{i + 1}$ rồi đổi chỗ chúng.
- Nếu ra sấp: Furik chọn ngẫu nhiên đều một cặp chỉ số $(i, i + 1)$ thỏa $p_{i} < p_{i + 1}$ rồi đổi chỗ chúng.
- Nếu Furik không có cặp nào phù hợp với mặt vừa tung, Furik phải tung lại đồng xu (và việc tung lại không tính là một lượt).

Trò chơi kết thúc khi hoán vị trở thành dãy tăng dần $1, 2, \dots, n$ .

Jeff muốn trò chơi kết thúc càng nhanh càng tốt, tức là tổng số lượt đi của cả hai người nhỏ nhất có thể (theo nghĩa kỳ vọng). Hãy tính kỳ vọng tối thiểu của tổng số lượt đi khi Jeff chơi tối ưu.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên phân biệt $p_{1}, p_{2}, \dots, p_{n}$ — hoán vị.

Dữ liệu ra

In ra một số thực — kỳ vọng tối thiểu của tổng số lượt đi. Kết quả được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{- 6}$ .

Ràng buộc

$1 \leq n \leq 3000$
$1 \leq p_{i} \leq n$ , các $p_{i}$ phân biệt.

Ví dụ

Input	Output	Giải thích
2 1 2	0	Hoán vị đã được sắp xếp nên trò chơi kết thúc ngay.
5 3 5 2 4 1	13	Số nghịch thế là $7$ . Kỳ vọng tối thiểu bằng $13$ .
2 2 1	1	Jeff chỉ cần một lượt đổi để sắp xếp dãy.

Bình luận

Không có bình luận tại thời điểm này.