#10037. TIMDUONG - Tìm bước nhảy tàu vũ trụ

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Nguyễn Văn Đạt

Đề bài

Khi còn nhỏ, Hùng tin rằng sẽ có một tương lai mà con người có tìm thấy các hành tinh có sự sống khác ngoài trái đất. Và giờ đây, anh đang chờ đợi giây phút vinh quang để đặt chân đến thế giới mới với tư cách là phi hành gia VINASAT.

Vì con tàu vũ trụ mà anh ta sẽ lên được trang bị một hệ thống hỗ trợ sự sống quy mô lớn để tiên phong xây dựng một ngôi nhà mới của con người có tên là Dream House, hệ sao gần nhất và hệ hành tinh gần nhất với hệ mặt trời của trái đất ở 4,37 năm ánh sáng từ mặt trời, nó được trang bị một thiết bị di chuyển trong không gian được phát triển bằng cách ứng dụng các công nghệ mới nhất nhằm hỗ trợ kích thước và khối lượng khổng lồ của nó.
Tuy nhiên, thiết bị di chuyển không gian này có nhược điểm là gây ra các ảnh hưởng xấu nghiêm trọng cho máy khi quãng đường di chuyển tăng nhanh. Ví dụ: khi thiết bị được kích hoạt lần đầu, về mặt lý thuyết nó có thể di chuyển -1 hoặc 0 hoặc 1 năm ánh sáng, nhưng trên thực tế, nó có thể di chuyển tối thiểu 1 năm ánh sáng, vì khoảng cách âm hoặc 0 là vô nghĩa. Tức là tàu vũ trụ chỉ nên giữ nguyên tốc độ hoặc tăng hoặc giảm 1 năm ánh sáng cho mỗi đoạn di chuyển. Hùng nhận thấy rằng hoạt động của thiết bị di chuyển trong không gian tiêu tốn rất nhiều năng lượng, vì vậy anh cố gắng di chuyển từ điểm x đến điểm y với số lần hoạt động tối thiểu. Tuy nhiên, ngay cả sau khi đến điểm y , để đảm bảo an toàn cho thiết bị di chuyển trong không gian, khoảng cách di chuyển ngay trước khi đến điểm y phải được đặt thành 1 năm ánh sáng. Hình minh họa:

Viết một chương trình giúp Hùng tìm số lần hoạt động tối thiểu của thiết bị di chuyển trong không gian cần thiết để di chuyển chính xác từ điểm x đến điểm y .

Dữ liệu:

  • Dòng đầu là số trường hợp thử nghiệm;
  • Các dòng tiếp theo là giá trị nguyên của vị trí hiện tại x và vị trí đích y\ (0 ≤ x< y < 2^{31}) .

Kết quả:

  • Ghi số lần hoạt động tối thiểu của thiết bị di chuyển trong không gian cần thiết để đạt được chính xác điểm từ x đến y tương ứng với mỗi trường hợp thử nghiệm.

Ví dụ:

Dữ liệu:

3
0 4
2 10
41 53

Kết quả:

3
5
6