Mã bài:
threejug
Điểm:
2,3 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Có ~3~ bình dung tích ~A, B, C~ (lít) với lượng nước ban đầu tương ứng là ~a, b, c~ (lít). Mỗi bước được phép đổ đúng ~d~ lít từ một bình ~i~ sang một bình ~j~ khác với điều kiện lượng nước hiện có trong bình ~i~ lớn hơn hoặc bằng ~d~ và sau khi đổ hết ~d~ lít từ bình ~i~ sang bình ~j~ thì nước trong bình ~j~ không bị tràn ra ngoài. Hãy tìm dãy ít nhất các bước đổ nước sao cho lượng nước còn lại ở 1 trong 3 bình đúng bằng ~T~.
Dữ liệu đầu vào
Bao gồm ~1~ dòng ghi số ~8~ số nguyên dương ~A, B, C, a, b, c, d, T (0 ≤ A, B, C, a, b, c, d, T ≤ 10^5)~.
Dữ liệu đầu ra
Dòng duy nhất ghi số ít nhất các bước đổ nước thỏa mãn yêu cầu đặt ra hoặc ghi ra số -1 nếu không có cách thực hiện nào.
Sample Input 1
20 20 20 3 6 6 3 12
Sample Output 1
2
Sample Input 2
20 20 20 2 4 5 3 10
Sample Output 2
-1
Sample Input 3
45 45 45 5 10 8 4 21
Sample Output 3
4
Hạn chế
- ~25%~ số test với ~0 ≤ A, B, C ≤ 100~.
- ~35%~ số test với ~100 < A, B, C ≤ 1000~.
- ~40%~ test còn lại không có ràng buộc gì thêm.
Nguồn: Trại đông Bảo Lộc 2021 - thầy Đỗ Phan Thuận
Bình luận