JOI 2022 - Giraffes
Xem PDFVườn thú IOI nổi tiếng với hươu cao cổ. Có \(N\) con hươu cao cổ, được đánh số từ \(1\) đến \(N\) theo thứ tự chiều cao tăng dần; chiều cao của chúng đôi một khác nhau. Có \(N\) chuồng xếp thành một hàng, đánh số từ \(1\) đến \(N\) từ trái sang phải. Mỗi chuồng có đúng một con hươu. Con hươu \(P_i\) sống trong chuồng \(i\).
Ông APIO, giám đốc vườn thú, lo lắng vì những đánh giá thấp với lý do "hươu cao cổ lên ảnh không đẹp". Cụ thể, khi chụp ảnh, khách chọn hai số nguyên \(l,r\) \((1 \le l \le r \le N)\) rồi chụp các con hươu trong các chuồng \(l,l+1,\ldots,r\). Bức ảnh không đẹp nếu đồng thời thỏa mãn hai điều kiện:
- Có một con hươu trong ảnh cao hơn cả hai con ở hai đầu ảnh; tức là tồn tại \(k\) với \(l<k<r\) sao cho \(P_l<P_k>P_r\).
- Có một con hươu trong ảnh thấp hơn cả hai con ở hai đầu ảnh; tức là tồn tại \(k\) với \(l<k<r\) sao cho \(P_l>P_k<P_r\).
Ông APIO muốn sắp xếp lại các con hươu sao cho ảnh không bị xấu với bất kỳ cách chọn \(l,r\) nào. Vì chuyển hươu giữa các chuồng rất vất vả, ông muốn số con hươu phải chuyển là nhỏ nhất. Sau khi sắp xếp, mỗi chuồng vẫn phải có đúng một con hươu.
Cho vị trí hiện tại của các con hươu, hãy tính số con ít nhất phải chuyển. Vì cách sắp xếp hiện tại do ông APIO chọn ngẫu nhiên, có thể giả sử các giá trị \(P_i\) được sinh ngẫu nhiên như mô tả ở mục Cách sinh dữ liệu.
Dữ liệu vào
Đọc từ đầu vào chuẩn, tất cả các giá trị đều là số nguyên:
N
P_1 P_2 ... P_N
Dữ liệu ra
In một dòng chứa số con hươu ít nhất phải chuyển.
Ràng buộc
- \(1 \le N \le 8\,000\).
- \(1 \le P_i \le N\) \((1 \le i \le N)\).
- \(P_i \ne P_j\) \((1 \le i<j \le N)\).
- Các giá trị \(P_i\) được sinh ngẫu nhiên theo cách dưới đây.
Chấm điểm
- \(10\) điểm: \(N \le 7\)
- \(22\) điểm: \(N \le 13\)
- \(27\) điểm: \(N \le 300\)
- \(41\) điểm: Không có giới hạn bổ sung.
Cách sinh dữ liệu
Không kể các ví dụ, có \(10\) bộ dữ liệu thỏa mãn cả bốn nhóm; \(10\) bộ chỉ thỏa mãn các nhóm \(2,3,4\); \(10\) bộ chỉ thỏa mãn các nhóm \(3,4\); và \(10\) bộ chỉ thỏa mãn nhóm \(4\). Tính cả ví dụ, có tổng cộng \(44\) bộ dữ liệu dùng để chấm. Cả \(44\) bộ đều được sinh như sau:
- Chọn \(N\) thỏa mãn giới hạn của nhóm tương ứng.
- Chọn ngẫu nhiên đều một hoán vị \((P_1,P_2,\ldots,P_N)\) trong \(N!=1\times2\times\cdots\times N\) hoán vị hợp lệ. Mọi hoán vị có xác suất được chọn như nhau.
Ví dụ
Ví dụ 1
Input
6
5 4 6 1 3 2Output
2Giải thích
Thứ tự từ trái sang phải là \(5,4,6,1,3,2\). Ảnh ứng với \(l=2,r=5\) không đẹp: con trong chuồng \(3\) cao hơn cả hai con trong chuồng \(2\) và \(5\), còn con trong chuồng \(4\) thấp hơn cả hai con đó.
Chuyển con hươu \(1\) từ chuồng \(4\) sang chuồng \(1\) và con hươu \(5\) từ chuồng \(1\) sang chuồng \(4\) thì mọi ảnh đều không bị xấu. Cần chuyển \(2\) con và đây là số nhỏ nhất. Ví dụ thỏa mãn mọi nhóm.
Ví dụ 2
Input
4
4 1 3 2Output
0Giải thích
Với thứ tự \(4,1,3,2\), mọi ảnh đều không bị xấu, nên không cần chuyển con nào. Ví dụ thỏa mãn mọi nhóm.
Ví dụ 3
Input
7
3 1 6 7 4 2 5Output
2Giải thích
Có thể sắp thành \(3,5,6,7,4,2,1\). Khi đó mọi ảnh đều không bị xấu. Cần chuyển \(2\) con và đây là số nhỏ nhất. Ví dụ thỏa mãn mọi nhóm.
Ví dụ 4
Input
13
8 5 6 13 4 2 11 3 9 1 10 7 12Output
6Giải thích
Ví dụ này thỏa mãn các nhóm \(2,3,4\).
Nguồn
JOI Open Contest 2022, JCIOI. Bản dịch tiếng Việt theo CC BY-SA 4.0.
Kỳ thi:
- JOI 2022 - Open Contest (3 Tháng bảy, 2022)
Bình luận