Một đàn gà con chạy về phía đông trên đường thẳng hẹp, mỗi con có vận tốc không đổi. Khi bắt kịp con trước, nó phải chậm lại theo vận tốc con đó. Bạn lái cần cẩu phía sau; có thể nhấc tạm một con để con ngay sau vượt qua rồi đặt lại. Thao tác tức thời, chỉ áp dụng cho hai con kề nhau; dù nhiều con cùng vị trí, mỗi lần đổi chỗ chỉ cho một con vượt.

Biết vị trí đầu \(X_i\), vận tốc tự nhiên \(V_i\), vị trí chuồng \(B\) và hạn \(T\), hãy tìm số lần đổi chỗ ít nhất để ít nhất \(K\) trong \(N\) con tới chuồng không muộn hơn \(T\).

Dữ liệu vào

Dòng đầu là \(C\). Mỗi test gồm \(N,K,B,T\); dòng sau là \(N\) vị trí \(X_i\) tăng nghiêm ngặt; dòng cuối là \(N\) vận tốc \(V_i\). Đơn vị lần lượt là mét, mét/giây và giây.

Dữ liệu ra

In Case #x: S, với \(S\) nhỏ nhất, hoặc IMPOSSIBLE.

Ràng buộc

• \(1\le C\le100\), \(1\le B\le10^9\), \(1\le T\le1000\).
• \(0\le X_i<B\), \(1\le V_i\le100\); các \(X_i\) khác nhau và tăng.
• Thời gian 30 giây mỗi bộ; bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(1\le N\le10\), \(0\le K\le\min(3,N)\).
• Lớn: \(1\le N\le50\), \(0\le K\le N\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
5 3 10 5
0 2 5 6 7
1 1 1 1 4
5 3 10 5
0 2 3 5 7
2 1 1 1 4
5 3 10 5
0 2 3 4 7
2 1 1 1 4

Case #1: 0
Case #2: 2
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2010, Vòng 1B, bài Picking Up Chicks.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.