TopCoder

Thumb
Posen
樂觀 樂觀 要樂觀

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

93.8% (15/16)

Description

小明想作賣油的商人。因為家裡太窮,所以他買不起一般人所使用的量器,他只有一個裝他所有的油的大桶子,還有兩個確知容量的杯子 (但上面沒有刻度)。

每當客人要來買油的時候,客人會告訴他想要買多少油,小明雖然沒有正常的量器,但聰明的他,利用這兩個杯子容量的差異,經過若干次注滿與倒空的過程,依然湊出客人所要的量。經過多日的買賣,小明漸漸發現,有些時候,有些要求的量是任憑他怎樣努力都是湊不出來的。你能幫助他找出哪些量湊得出來,哪些量湊不出來嗎?

另外,台灣人的耐性大都不好,如果小明慢吞吞地倒過來倒過去許久,客人會不耐煩的。所以小明不但要確知他能量出那一個量,他還得利用最少的步驟達到這個要求。

下面所列的這些都算是「一個步驟」:
1. 將一個杯子裡的油倒空到大桶子裡。
2. 從大桶子裡取油將一個杯子注滿。
3. 將一個杯子的油倒空到另一個杯子裡(如果倒過去不會溢出來的話)。
4. 用一個杯子裡的油注滿另一個杯子(如果油量夠,注得滿的話)。
5. 將一個杯子裡的油倒給客人。

假設客人來到的時候,兩個杯子都是空的。

Input Format

輸入檔中有許多組輸入,每組輸入佔一列。每一組輸入裡,會有三個以空白隔開的整數:第一個和第二個代表小明所擁有的兩個杯子的容量,第三個代表客人所要求的量,單位都是公合(這三個整數都是正的,而且不會超過 100)。遇到一行為三個零“0 0 0”為檔案結束,不須處理這組輸入。

Output Format

對每一組測試資料,你應該輸出一列。如果客人要求的量湊得出來,請輸出最少的步驟數,否則請輸出「No」。

Sample Input

1 2 1
1 2 9
3 5 4
3 6 8
0 0 0

Sample Output

2
10
7
No

Hints

第一組:小明可以用容量為 1 公合的杯子將油量給客人。

第二組:小明可以先用容量為 2 公合的杯子量油給客人 4 次,然後再用容量為 1 公合的杯子量給客人 1 次。

第三組:小明可以先把 5 公合的杯子注滿,然後用這個 5 公合的杯子將 3 公合的杯子注滿,那麼在 5 公合的杯子裡就會剩下 2 公合,將這 2 公合量給客人以後,把 3 公合的杯子倒空,再重覆一次,就可以量給客人總共 4 公合的油了。

Problem Source

原TIOJ1098 / NPSC2006決賽(prob A)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536