Dòng chảy trong ống
Đề bài
Mô tả
Thị trấn của bạn đã thuê một số nhà thầu, trong đó có bạn, để quản lý mạng lưới đường ống của thành phố. Họ đã xây dựng mạng lưới này với chi phí rất lớn để cung cấp Flubber tới mọi ngôi nhà trong thị trấn. Đáng tiếc là chưa ai tìm ra công dụng của Flubber, nhưng không sao. Thị trấn phải chọn giữa một mạng lưới Flubber và một đội cứu hỏa, và thật lòng mà nói, nhà cửa hiếm khi cháy đến mức đội cứu hỏa gần như chẳng cần thiết.
Phòng khi có ai đó ở đâu đó muốn dùng Flubber, người ta muốn biết Flubber chảy trong ống nhanh như thế nào. Đo tốc độ chảy là công việc của bạn.
Bạn được tiếp cận một đường ống nối vào mạng lưới. Ống dài mét, và bạn có thể cho Flubber bắt đầu chảy vào ống tại thời điểm bạn chọn. Bạn biết Flubber chảy với một tốc độ không đổi (là một số thực), tốc độ này ít nhất là mét/giây và nhiều nhất là mét/giây. Bạn muốn ước lượng tốc độ này với sai số tuyệt đối không quá mét/giây.
Đáng tiếc là ống không trong suốt, nên việc duy nhất bạn làm được là gõ vào ống tại một điểm bất kỳ dọc theo chiều dài ống, tức là tại một vị trí thực trong đoạn đóng . Nghe tiếng gõ, bạn biết được Flubber đã tới điểm đó hay chưa.
Bạn không nhanh vô hạn. Lần gõ đầu tiên phải cách thời điểm bắt đầu cho Flubber chảy ít nhất giây, và giữa hai lần gõ liên tiếp phải cách nhau ít nhất giây.
Hãy tìm một chiến lược sao cho số lần gõ trong trường hợp xấu nhất là ít nhất để ước lượng được tốc độ chảy của Flubber. Lưu ý rằng trong một số trường hợp việc ước lượng với độ chính xác mong muốn là không thể (chẳng hạn khi Flubber tới cuối ống quá nhanh).
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên , số bộ test. Mỗi dòng trong dòng tiếp theo mô tả một bộ test, gồm năm số nguyên , , , và như mô tả ở trên.
Dữ liệu ra
Với mỗi bộ test, in ra số lần gõ ít nhất cần có trong trường hợp xấu nhất để ước lượng được tốc độ chảy. Nếu có thể xảy ra trường hợp không đo được tốc độ chảy đủ chính xác, in ra impossible.
Ràng buộc
- .
- và .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1000 1 30 1 1 60 2 10 2 5 59 2 10 2 5 |
5 3 impossible |
Bộ test 1: ống đủ dài để tìm kiếm nhị phân trên đoạn tốc độ cho tới khi mỗi đoạn còn dài không quá , cần lần gõ. Bộ test 2 và 3 chỉ khác nhau ở độ dài ống: với thì không có chiến lược nào luôn đo được. |
| 3 10 3 4 1 7 100 1 9 2 10 100 1 9 2 11 |
0 3 impossible |
Bộ test 1: đoán là đủ, không cần gõ. Bộ test 2: lần gõ thứ diễn ra lúc giây nên chỉ kiểm tra được tốc độ không quá . Lần gõ 1 tại vị trí (tốc độ hay không), nếu chưa thì lần gõ 2 tại vị trí (tốc độ hay không), nếu vẫn chưa thì lần gõ 3 tại vị trí (tốc độ hay không). Mỗi khả năng còn lại là một đoạn dài . Bộ test 3: các lần gõ đến muộn hơn một chút và không đủ nữa. |
Bình luận