Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Bạn được cho một hoán vị $P = (P_1, P_2, \dots, P_N)$ của $(1, 2, \dots, N)$.

Đối với một dãy số nguyên dương $T = (T_1, T_2, \dots, T_{N-1})$ có độ dài $N - 1$, giá trị $f(T)$ được định nghĩa là giá trị trả về của thủ tục sau:

Thủ tục $f(T)$

  1. $t \leftarrow 0$.
  2. Trong khi $P$ chưa được sắp xếp theo thứ tự tăng dần:
    • (a) $t \leftarrow t + 1$.
    • (b) Gọi $S = (s_1, s_2, \dots, s_k)$ là dãy tất cả các chỉ số $i \in \{1, \dots, N - 1\}$ sao cho $T_i \le t$, được sắp xếp theo thứ tự tăng dần ($s_1 < s_2 < \dots < s_k$).
    • (c) Với $j = 1$ đến $k$:
      • Đặt $i \leftarrow s_j$. Sau đó hoán đổi $P_i$ và $P_{i+1}$.
    • (d) Nếu $t \ge 10^{100}$, trả về $10^{100}$.
  3. Trả về $t$.

Hãy tìm giá trị nhỏ nhất có thể của $f(T)$ trên tất cả các dãy số nguyên dương $T$. Đảm bảo rằng tồn tại một dãy $T$ sao cho $f(T) < 10^{100}$.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

N
P_1 P_2 ... P_N
  • Tất cả các giá trị đầu vào đều là số nguyên.
  • $2 \le N \le 5000$.
  • $1 \le P_i \le N$.
  • $P_i \neq P_j$ với $i \neq j$.

Dữ liệu ra

In ra đáp án.

Ví dụ 1

4
4 2 1 3
2

Ví dụ 2

20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39

Ghi chú

Trong ví dụ thứ nhất, đặt $T = (2, 1, 2)$. Tại $t = 1$, với $S = (2)$, $P$ trở thành $(4, 1, 2, 3)$. Tại $t = 2$, với $S = (1, 2, 3)$, các phép hoán đổi tuần tự làm thay đổi $P$ như sau: $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Do đó $f(T) = 2$. Vì không có dãy $T$ nào cho $f(T) < 2$, nên đáp án là $2$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.