小 X 又在玩水瓶了。
小 X 有 2 个水瓶,第 1 个水瓶的容积为 L1,第 2 个水瓶的容积为 L2,现要测量容积为 K 的水,问是否能通过若干次操作(或者不进行)使得能够测量出容积为 K 的水。
以下记 l1 为第 1 个水瓶的当前载水量,l2 为第 2 个水瓶的当前载水量。
对于每次操作,你可以选择以下之一:
- 将水瓶 1 装满水(l1=L1)
- 将水瓶 2 装满水(l2=L2)
- 将水瓶 1 的水全部倒出(l1=0)
- 将水瓶 2 的水全部倒出(l2=0)
- 将水瓶 1 的水全部倒入水瓶 2,将满出的倒回水瓶 1(l1=max(0,l1−(L2−l2))modL1,l2=(l1+l2)modL2)
- 将水瓶 2 的水全部倒入水瓶 1,将满出的倒回水瓶 2(l1=(l1+l2)modL1,l2=max(0,l2−(L1−l1))modL2)
蒟蒻求助