JOI 2025 - Just Long Neckties 2
Xem PDFCông ty Just Odd Inventions nổi tiếng với những phát minh kỳ lạ. Trong bài toán này, ta gọi tắt công ty là JOI.
Nhân dịp kỷ niệm \(5\) năm ra mắt sản phẩm chủ lực "Cà vạt chỉ dài", công ty JOI đã phát triển sản phẩm mới "Cà vạt chỉ có thể dài thêm". Đúng như tên gọi, loại cà vạt mới này có đặc điểm là có thể kéo dài tùy ý, không có giới hạn.
Để quảng bá sản phẩm mới, công ty JOI quyết định tổ chức một buổi giới thiệu và chọn bạn làm người dẫn chương trình. Đầu tiên, một số người mẫu đeo loại cà vạt mới sẽ bước lên sân khấu. Ban đầu, cà vạt của tất cả người mẫu đều có độ dài bằng \(1\).
Sau đó, bạn thực hiện tổng cộng \(N\) màn trình diễn để khán giả thấy được khả năng kéo dài của cà vạt. Trong mỗi màn trình diễn, trước tiên bạn mời khán giả hô lên một số tùy ý, gọi số đó là \(x\). Tiếp theo, bạn chọn đáp lại hoặc bỏ qua số vừa được hô lên.
Nếu chọn đáp lại, bạn phải chọn một người mẫu trên sân khấu có cà vạt với độ dài hiện tại không vượt quá \(x\), rồi đặt độ dài cà vạt của người đó thành đúng \(x\). Bạn cũng được phép chọn người mẫu có cà vạt vốn đã dài đúng \(x\). Tuy nhiên, nếu không có người mẫu nào có thể được chọn thì buổi giới thiệu thất bại. Nếu chọn bỏ qua, bạn không làm gì cả.
Tuy nhiên, nếu bạn bỏ qua số khán giả hô lên từ hai lần liên tiếp trở lên, khán giả sẽ tức giận và buổi giới thiệu cũng thất bại.
Số người mẫu xuất hiện trên sân khấu, ký hiệu là \(k\) (\(k \ge 1\)), vẫn chưa được quyết định. Vì việc thuê người mẫu tốn nhiều tiền, công ty muốn \(k\) nhỏ nhất có thể. Số người mẫu tối thiểu cần có để buổi giới thiệu không thất bại phụ thuộc vào các số mà khán giả hô lên trong từng màn trình diễn. May mắn thay, bạn có khả năng tiên tri và biết trước rằng ở màn trình diễn thứ \(i\) (\(1 \le i \le N\)), khán giả sẽ hô lên số \(A_i\).
Cho thông tin về các số khán giả sẽ hô lên, hãy tìm số người mẫu \(k\) nhỏ nhất cần có để buổi giới thiệu không thất bại.
Dữ liệu vào
Dữ liệu vào có dạng:
N
A_1 A_2 ... A_N
Dữ liệu ra
In trên một dòng số người mẫu \(k\) nhỏ nhất cần có để buổi giới thiệu không thất bại.
Ràng buộc
- \(2 \le N \le 5\,000\,000\).
- \(1 \le A_i \le 21\) (\(1 \le i \le N\)).
- Tất cả các giá trị trong dữ liệu vào đều là số nguyên.
Chấm điểm
- \(10\) điểm: \(N \le 15\).
- \(6\) điểm: \(N \le 500\), \(A_i \le 2\) với mọi \(1 \le i \le N\).
- \(12\) điểm: \(N \le 500\), \(A_i \le 5\) với mọi \(1 \le i \le N\).
- \(18\) điểm: \(N \le 500\), \(A_i \le 15\) với mọi \(1 \le i \le N\).
- \(26\) điểm: \(N \le 500\,000\), \(A_i \le 15\) với mọi \(1 \le i \le N\).
- \(10\) điểm: \(N \le 500\,000\).
- \(18\) điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
5
5 3 4 2 1Output
2Giải thích
Khi \(k = 2\), chẳng hạn, bạn có thể tổ chức buổi giới thiệu như sau.
Ban đầu, hai người mẫu đeo cà vạt mới bước lên sân khấu. Cà vạt của mỗi người đều có độ dài bằng \(1\).
-
Ở màn trình diễn thứ \(1\), khán giả hô lên số \(5\) và bạn bỏ qua.
-
Ở màn trình diễn thứ \(2\), khán giả hô lên số \(3\). Bạn đáp lại bằng cách chọn người mẫu thứ nhất và đặt độ dài cà vạt của người đó thành \(3\). Độ dài cà vạt của hai người mẫu lúc này lần lượt là \(3\) và \(1\).
-
Ở màn trình diễn thứ \(3\), khán giả hô lên số \(4\). Bạn đáp lại bằng cách chọn người mẫu thứ nhất và đặt độ dài cà vạt của người đó thành \(4\). Độ dài cà vạt của hai người mẫu lúc này lần lượt là \(4\) và \(1\).
-
Ở màn trình diễn thứ \(4\), khán giả hô lên số \(2\). Bạn đáp lại bằng cách chọn người mẫu thứ hai và đặt độ dài cà vạt của người đó thành \(2\). Độ dài cà vạt của hai người mẫu lúc này lần lượt là \(4\) và \(2\).
-
Ở màn trình diễn thứ \(5\), khán giả hô lên số \(1\) và bạn bỏ qua.
Khi \(k = 1\), buổi giới thiệu luôn thất bại. Chẳng hạn, nếu bạn chọn đáp lại ở các màn trình diễn thứ \(2, 3, 4\) như cách trên, sau màn trình diễn thứ \(3\), cà vạt của người mẫu duy nhất đã có độ dài bằng \(4\). Do đó, ở màn trình diễn thứ \(4\), bạn không thể chọn người mẫu có cà vạt dài không quá \(2\), khiến buổi giới thiệu thất bại.
Vì vậy, số người mẫu \(k\) nhỏ nhất cần có để buổi giới thiệu không thất bại là \(2\), nên in ra \(2\).
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(1, 3, 4, 5, 6, 7\).
Ví dụ 2
Input
6
2 1 1 2 2 1Output
1Giải thích
Khi \(k = 1\), chẳng hạn, bạn có thể tổ chức buổi giới thiệu như sau.
Ban đầu, một người mẫu đeo cà vạt mới bước lên sân khấu. Cà vạt của người đó có độ dài bằng \(1\).
-
Ở màn trình diễn thứ \(1\), khán giả hô lên số \(2\) và bạn bỏ qua.
-
Ở màn trình diễn thứ \(2\), khán giả hô lên số \(1\). Bạn đáp lại bằng cách chọn người mẫu duy nhất trên sân khấu và đặt độ dài cà vạt của người đó thành \(1\).
-
Ở màn trình diễn thứ \(3\), khán giả hô lên số \(1\). Bạn đáp lại bằng cách chọn người mẫu duy nhất trên sân khấu và đặt độ dài cà vạt của người đó thành \(1\).
-
Ở màn trình diễn thứ \(4\), khán giả hô lên số \(2\). Bạn đáp lại bằng cách chọn người mẫu duy nhất trên sân khấu và đặt độ dài cà vạt của người đó thành \(2\).
-
Ở màn trình diễn thứ \(5\), khán giả hô lên số \(2\). Bạn đáp lại bằng cách chọn người mẫu duy nhất trên sân khấu và đặt độ dài cà vạt của người đó thành \(2\).
-
Ở màn trình diễn thứ \(6\), khán giả hô lên số \(1\) và bạn bỏ qua.
Lưu ý rằng ở các màn trình diễn thứ \(2\) và \(3\) trong cách trên, bạn chọn người mẫu có cà vạt vốn đã dài \(1\) và đặt độ dài cà vạt thành \(1\) một lần nữa. Việc chọn người mẫu mà không làm thay đổi độ dài cà vạt như vậy cũng được phép.
Vì vậy, số người mẫu \(k\) nhỏ nhất cần có để buổi giới thiệu không thất bại là \(1\), nên in ra \(1\).
Ví dụ này thỏa mãn ràng buộc của tất cả các bài toán con.
Ví dụ 3
Input
10
2 4 6 7 4 5 5 3 4 1Output
3Giải thích
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(1, 4, 5, 6, 7\).
Nguồn
Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề 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.
Kỳ thi:
- JOI 2025 - Vòng chung kết quốc gia (2 Tháng 2., 2025)
Bình luận