c488: kevin 的大桶子
標籤 : extgcd greedy
通過比率 : 81% (17 人 / 21 人 ) (非即時)
評分方式:
Special

最近更新 : 2018-02-12 10:50

內容

kevin 有兩個水桶

他想用這兩個水桶來裝水喝

但是 kevin 喝水的習慣是把桶子裡的水喝的一滴都不剩

可以請你幫他裝出恰好的水量到其中一個桶子裡嗎

 

kevin 的大水桶容量別為x, y公升

而他想要喝到 k 公升的水

一開始桶子皆為空的

你現在可以執行一些倒水的操作

 

桶子編號 1 容量 x 公升

       編號 2 容量 y 公升

 

操作:

  1 p : 把編號為 p 的桶子裝滿水

  2 p : 把編號為 p 的桶子中的水都倒掉

  3 p q : 把編號 p 中的水倒入 q 中, 若 q 桶裝不下這麼多水, 則多出來裝不下的部份留在 p 桶中

 

另外 kevin 覺得 裝水和倒水很浪費力氣

所以他希望操作1, 2的數量和不超過 x + y

你現在可決定操作的順序

來幫kevin取得 k 公升的水

輸入說明

輸入共一行

第一行有3個數字 x, y, k

分別代表 桶子 1 的容量, 桶子 2 的容量, kevin 想要喝的水量

輸出說明

按照順序輸出你的操作

每個操作後應該換行

輸出完所有操作後應於下一行輸出一個0

所無解則直接輸出 0

 

輸出操作編號 op 應滿足 1 <= op <= 3

而桶子編號應滿足 1 <= p, q <= 2 && p != q

 

操作1, 2的數量和 <= x + y

範例輸入
2 3 1

2 4 1
範例輸出
1 1
3 1 2
1 1
3 1 2
0

0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (6%): 1.0s , <1K
公開 測資點#1 (6%): 1.0s , <1K
公開 測資點#2 (6%): 1.0s , <1K
公開 測資點#3 (6%): 1.0s , <1K
公開 測資點#4 (6%): 1.0s , <1K
公開 測資點#5 (7%): 1.0s , <1K
公開 測資點#6 (7%): 1.0s , <1K
公開 測資點#7 (7%): 1.0s , <1K
公開 測資點#8 (7%): 1.0s , <1K
公開 測資點#9 (7%): 1.0s , <1K
公開 測資點#10 (7%): 1.0s , <1K
公開 測資點#11 (7%): 1.0s , <1K
公開 測資點#12 (7%): 1.0s , <1K
公開 測資點#13 (7%): 1.0s , <1K
公開 測資點#14 (7%): 1.0s , <1K
提示 :

測試資料中

44% x, y <= 200

100% x, y <= 100000

標籤:
extgcd greedy
出處:
妹妹0u0 [編輯:
justinO__o (夜貓)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」