きままにものづくり

日々の気付いたことなんかを書いてます。

SRM620Div1Easy

問題

(a, b)と(c, d)の2組の数字のペアが与えられる。任意のペア(x, y)を考える。可能な操作は(x+y, y)または(x, x+y)である。(a, b)と(c, d)が作れる(x, y)のペアを求め、その中でx+yが最大となるペアを求めよ。作れない場合は-1を返す。

解法

(a, b)または(c, d)となるペアの一覧は、それぞれのペアから一意に求まる。 a>bとすれば(a-b, b)となり、[tex: a

計算量

 O(N)
N: a,b,c,dの最大値

コード