Bài toán quả chuối
Đề bài
Mô tả
Gon đang chơi trò chơi "Những chú khỉ tham ăn".
Trò chơi được thiết lập như sau:
- Có cái thang, đánh số từ đến . Mỗi thang có chiều cao và có bậc ở các độ cao . Ký hiệu là bậc ở độ cao của thang thứ .
- Có sợi dây nằm ngang. Mỗi sợi dây nối hai bậc cùng độ cao của hai thang khác nhau. Các sợi dây được đánh số từ đến , sợi dây thứ có độ dài . Không có sợi dây nào nối vào bậc hay bậc của bất kỳ thang nào. Mỗi bậc của một thang được nối với nhiều nhất một sợi dây.
Có vị trí đặc biệt, đánh số từ đến . Vị trí thứ được mô tả bởi số nguyên , với và . Với mọi số nguyên không âm :
- Tại thời điểm , một quả chuối mới xuất hiện tại vị trí .
- Tại thời điểm , quả chuối này biến mất khỏi vị trí .
Ví dụ, nếu và : một quả chuối xuất hiện lúc và biến mất lúc ; sau đó một quả chuối khác xuất hiện lúc và biến mất lúc , và cứ thế. Đảm bảo không có sợi dây nào nối vào một vị trí đặc biệt, và các vị trí đặc biệt đôi một phân biệt.
Lúc bắt đầu trò chơi có chú khỉ, đánh số từ đến . Chú khỉ thứ đứng ở . Chú khỉ thứ cần giây để leo lên một bậc của bất kỳ thang nào, và giây để di chuyển một đơn vị độ dài dọc theo bất kỳ sợi dây nào.
Một chú khỉ ăn được một quả chuối khi và chỉ khi nó ở cùng vị trí với quả chuối và quả chuối chưa biến mất. Thời gian ăn chuối không đáng kể. Tất nhiên mỗi quả chuối chỉ được ăn một lần. Nếu nhiều chú khỉ cùng ở vị trí của một quả chuối tại cùng một thời điểm, chỉ một chú ăn được quả chuối đó. Tuy nhiên, nếu các chú khỉ tới một vị trí đặc biệt nhiều lần, chúng có thể ăn nhiều hơn một quả chuối ở vị trí này.
Người chơi điều khiển các chú khỉ. Vì Gon là một cậu bé đơn giản, cậu điều khiển các chú khỉ theo một chiến thuật rất đơn giản:
- Nếu một chú khỉ đang ở một bậc thang có nối một sợi dây, và chú khỉ chưa từng đi trên sợi dây này theo bất kỳ chiều nào, nó lập tức đi dọc sợi dây sang đầu bên kia.
- Ngược lại, chú khỉ leo lên trên thang.
- Các chú khỉ luôn di chuyển theo hai quy tắc trên, cho tới khi không thể di chuyển được nữa (điều này chỉ xảy ra khi chúng tới bậc của một thang nào đó).
- Các chú khỉ có thể đi xuyên qua nhau.
Hỏi các chú khỉ ăn được bao nhiêu quả chuối nếu Gon làm theo chiến thuật này?
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (, , ): số thang, chiều cao mỗi thang, số sợi dây và số vị trí đặc biệt.
Trong dòng tiếp theo, dòng thứ chứa số nguyên (, , , ): sợi dây thứ có độ dài và nối hai vị trí và .
Trong dòng tiếp theo, dòng thứ chứa số nguyên và (): số giây để chú khỉ thứ leo lên một bậc thang, và để di chuyển một đơn vị dọc theo một sợi dây.
Trong dòng tiếp theo, dòng thứ chứa số nguyên (, , ): là vị trí đặc biệt thứ , còn là các tham số của nó.
Đảm bảo rằng:
- Mỗi vị trí được nối với nhiều nhất một sợi dây.
- Các vị trí đặc biệt (nơi chuối xuất hiện) đôi một phân biệt.
- Các vị trí đặc biệt không được nối với sợi dây nào.
Dữ liệu ra
In ra một số nguyên là số quả chuối các chú khỉ ăn được khi làm theo chiến thuật của Gon.
Ràng buộc
- , ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 2 0 2 2 1000 1 1 1 2 1 2 2 1 |
1 | Chỉ có thang và không có dây; chú khỉ cần giây để leo một bậc. Vị trí có chuối từ tới , từ tới , ...; vị trí có chuối từ tới , từ tới , ... Chú khỉ tới lúc , khi đó không có chuối; tới lúc và ăn quả chuối. |
| 2 2 1 2 1 1 2 1 1 2 2 1 1 2 3 1 2 2 2 3 |
1 | Dây nối và , dài . Khỉ ở lúc , lúc , lúc . Khỉ ở lúc , lúc , lúc . Vị trí có chuối từ tới , từ tới , ...; vị trí có chuối từ tới , từ tới , ... Khỉ ăn được chuối ở , khỉ không ăn được quả nào. |
Bình luận