SRM620 Div1 Easy "PairGame"
問題
TopCoder Statistics - Problem Statement
訳
この問題では、正の整数のペアについて考える。ペアが与えられたとき、あなたはそこに任意の回数だけ操作を行える。1回の操作で、あなたは片方の数値に、もう片方の数値を足して、新たなペアに変化させることが出来る。もし現在のペアが(x, y)だとすると、次のペアは(x+y, y)もしくは(x, x+y)とすることができる。
例えば、(1, 2)が最初のペアだとすると、(3, 2)に変化させることができ、それを(3, 5)、さらに(3, 8)と変化させることが出来る。
あなたは4つのint a, b, c, dが与えられる。以下のような(x, y)を見つけよ。
(x, y)から始めて(a, b)へと変化させることが出来る。 同じく(x, y)から始めて(c, d)へと変化させることが出来る。
(a, b)へと変化させるための操作回数と(c, d)へと変化させるための操作回数は違っていても構わない。
そのような(x, y)が1つでもあるのなら、その中でx+yが最も大きいものを選び、その値を返せ。
制約
1 <= a, b, c, d <= 10^6
考えたこと
やばい全然分からん・・
~30分後~
逆から考えると実は1パターンしかないやーん!!
x < yの場合
(x, y) -> (x, y-x)
x > yの場合
(x, y) -> (x-y, y)
ぐぬぬ・・
ソースコード
vector<pair<int, int>> v; class PairGame { public: int maxSum(int a, int b, int c, int d) { while (a > 0 && b > 0) { v.push_back(make_pair(a, b)); if (a < b) { b -= a; } else{ a -= b; } } sort(v.begin(), v.end()); while (c > 0 && d > 0) { if (binary_search(v.begin(), v.end(), make_pair(c, d))) { return c + d; } if (c < d) { d -= c; } else{ c -= d; } } return -1; } };