Steed 2: Cruise Control

Annie là tài xế xe buýt với công việc rất căng thẳng. Cô thử thư giãn bằng một chuyến du thuyền Caribe nhưng chuyến đi cũng đầy áp lực, nên gần đây cô chuyển sang cưỡi ngựa.

Hôm nay Annie cưỡi ngựa về phía đông trên một con đường một chiều dài và hẹp chạy từ tây sang đông. Cô đang ở kilômét 0, đích ở kilômét \(D\); số kilômét tăng dần về phía đông.

Có \(N\) con ngựa khác cũng đi về phía đông, sẽ tiếp tục đi mãi và hiện đều nằm giữa Annie và đích. Ngựa thứ \(i\) ban đầu ở kilômét \(K_i\) và chạy với tốc độ tối đa \(S_i\) km/h.

Ngựa rất lịch sự: một con \(H_1\) không vượt lên trước con \(H_2\) vốn xuất phát phía trước nó. Nhiều ngựa có thể cùng vị trí trong bất kỳ khoảng thời gian nào và có thể coi mỗi con là một điểm. Các ngựa khác Annie chạy tốc độ tối đa, trừ khi một con nhanh \(H_1\) bắt kịp con chậm hơn \(H_2\), lúc đó \(H_1\) giảm tốc để bằng \(H_2\).

Ngựa của Annie không có tốc độ tối đa và có thể chạy ở bất kỳ tốc độ nào cô chọn, miễn không vượt ngựa khác. Để chuyến đi êm ái, Annie muốn dùng một tốc độ “cruise control” không đổi trong toàn bộ hành trình từ vị trí hiện tại tới đích. Tốc độ lớn nhất hợp lệ là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test bắt đầu bằng hai số nguyên \(D,N\), lần lượt là vị trí đích và số ngựa khác trên đường. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa \(K_i,S_i\), vị trí ban đầu và tốc độ tối đa của ngựa thứ \(i\).

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test và y là tốc độ không đổi lớn nhất (km/h) Annie có thể dùng mà không vượt ngựa khác. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(0<K_i<D\le10^9\) với mọi \(i\).
• \(K_i\ne K_j\) với mọi \(i\ne j\); không hai ngựa nào xuất phát cùng vị trí.
• \(1\le S_i\le10000\).

Phân nhóm

• Small Dataset (Test Set 1, hiển thị): \(1\le N\le2\).
• Large Dataset (Test Set 2, ẩn): \(1\le N\le1000\).

Đ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
2525 1
2400 5
300 2
120 60
60 90
100 2
80 100
70 10

Case #1: 101.000000
Case #2: 100.000000
Case #3: 33.333333

Nguồn

Google Code Jam 2018, Vòng luyện tập, bài Steed 2: Cruise Control.

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