C11DOLL - Búp bê nga
Giới hạn- Thời gian: 0.4s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Búp bê Nga hay Búp bê babushka (Búp bê lồng nhau, Búp bê làm tổ, ...) là một loại búp bê đặc trưng của Nga. Thật ra đó là một bộ gồm những búp bê rỗng ruột có kích thước từ lớn đến nhỏ. Con búp bê nhỏ nhất sẽ được chứa đựng trong lòng con búp bê lớn hơn nó một chút, đến lượt mình con búp bê lớn được chứa trong một con búp bê khác lớn hơn, và cứ thế cho đến con lớn nhất sẽ chứa tất cả những con búp bê còn lại trong bộ.
Hôm nay yenthanh132 mời bạn đến tham quan bố sưu tập búp bê nga của anh ta. Nhưng việc tham quan chỉ là phụ thôi, việc chính là yenthanh132 muốn đố bạn một bài toán liên quan đến những con búp bê nga này.
Đầu tiên yenthanh132 sắp xếp N con búp bê của anh ta từ trái sang phải theo một thứ tự bất kì, con thứ i có kích thước a i (1 ≤ a i ≤ M). Sau đó anh ta yêu cầu bạn tạo khoảng trống ở đầu mút trái, để làm được điều đó, bạn cần xếp những con búp bê có kích thước nhỏ hơn ở bên trái đặt vào những con búp bê có kích thước lớn hơn bên phải, tuy nhiên mỗi con búp bê lớn hơn chỉ chứa đúng 1 con búp bê nhỏ hơn nó. Bạn chỉ được quyền dùng 3 thao tác: Lấy một con búp bê ở bên trái lên, di chuyển nó sang phải và đặt vào bên trong một con búp bê lớn hơn. Bạn cần tìm cách sắp xếp sao cho khoảng trống ở đầu mút trái là lớn nhất.
Nói cách khác, yenthanh132 yêu cầu bạn tìm một số nguyên K lớn nhất (1 ≤ K ≤ N/2) sao cho K con búp bê trái nhất có để đặt vào bên trong K con búp bê ngay sau đó (từ k+1..k*2), mỗi con búp bê chỉ chứa đúng 1 con búp bê, theo một thứ tự nào đó. Lưu ý con búp bê i có thể đặt vào bên trong con búp bê j nếu (a i < a j ).
Dữ liệu vào:
- Dòng đầu tiên có 2 số N, M lần lượt là số lượng con búp bê của yenthanh132 và kích thước giới hạn của N con búp bê đó. N luôn là số chẵn.
- Dòng thứ 2 chứa N số a i , là kích thước của N con búp bê từ trái sang phải. (1 ≤ a i ≤ M).
Dữ liệu ra:
- Xuất ra số K theo yêu cầu của bài. Nếu không có kết quả (không có cách sắp nào để tạo khoảng trống ở đầu mút trái ) thì xuất ra -1.
Giới hạn test:
- 20% test đầu có (1 ≤ N ≤ 100; 1 ≤ M ≤ 1000).
- 20% test tiếp theo có (1 ≤ N ≤ 10000; 1 ≤ M ≤ 1000).
- 60% test còn lại có (1 ≤ N ≤ 10 5 ; 1 ≤ M ≤ 10 5 ).
Ví dụ:
Input: 10 5
2 1 4 2 3 2 4 5 2 3
Output:
4
Giải thích:
Ta có thể đặt 4 con búp bê bên trái vào trong 4 con búp bê bên cạnh theo thứ tự như sau:
1 đặt vào 5, 2 đặt vào 6, 3 đặt vào 8, 4 đặt vào 7.
Input 2:
4 5
2 2 1 1
Output 2:
-1
- Người up: yenthanh132
- Nguồn bài: Lê Yên Thanh