小明想作賣油的商人。因為家裡太窮,所以他買不起一般人所使用的量器,他只有一個裝他所有的油的大桶子,還有兩個確知容量的杯子 (但上面沒有刻度)。
每當客人要來買油的時候,客人會告訴他想要買多少油,小明雖然沒有正常的量器,但聰明的他,利用這兩個杯子容量的差異,經過若干次注滿與倒空的過程,依然湊出客人所要的量。經過多日的買賣,小明漸漸發現,有些時候,有些要求的量是任憑他怎樣努力都是湊不出來的。你能幫助他找出哪些量湊得出來,哪些量湊不出來嗎?
另外,台灣人的耐性大都不好,如果小明慢吞吞地倒過來倒過去許久,客人會不耐煩的。所以小明不但要確知他能量出那一個量,他還得利用最少的步驟達到這個要求。
下面所列的這些都算是「一個步驟」:
1. 將一個杯子裡的油倒空到大桶子裡。
2. 從大桶子裡取油將一個杯子注滿。
3. 將一個杯子的油倒空到另一個杯子裡(如果倒過去不會溢出來的話)。
4. 用一個杯子裡的油注滿另一個杯子(如果油量夠,注得滿的話)。
5. 將一個杯子裡的油倒給客人。
假設客人來到的時候,兩個杯子都是空的。
輸入檔中有許多組輸入,每組輸入佔一列。每一組輸入裡,會有三個以空白隔開的整數:第一個和第二個代表小明所擁有的兩個杯子的容量,第三個代表客人所要求的量,單位都是公合(這三個整數都是正的,而且不會超過 100)。遇到一行為三個零“0 0 0”為檔案結束,不須處理這組輸入。
對每一組測試資料,你應該輸出一列。如果客人要求的量湊得出來,請輸出最少的步驟數,否則請輸出「No」。
第一組:小明可以用容量為 1 公合的杯子將油量給客人。
第二組:小明可以先用容量為 2 公合的杯子量油給客人 4 次,然後再用容量為 1 公合的杯子量給客人 1 次。
第三組:小明可以先把 5 公合的杯子注滿,然後用這個 5 公合的杯子將 3 公合的杯子注滿,那麼在 5 公合的杯子裡就會剩下 2 公合,將這 2 公合量給客人以後,把 3 公合的杯子倒空,再重覆一次,就可以量給客人總共 4 公合的油了。
原TIOJ1098 / NPSC2006決賽(prob A)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |