Codeforces #712 Div.2 C. Memory and De-Evolution
要約
正三角形2つが与えられる.
それぞれの辺の長さは, [tex:x, y (y
やること
非縮退三角形とは, 以下の条件を満たす三角形(つまり普通の三角形) 三角形の辺の長さを とすると,
少し変形して, 辺に着目すると, 以下のような式になる
辺の長さを減らしていく方向に考えると, 他の辺を減らす量が減ってしまうことがあり, 貪欲に考えることができない.
しかし, 辺の長さを増やしていく方向に考えると, 増やせば増やすほど他の辺もいっぱい増やせるので貪欲に増やすことができる
不等号が含まない不等号なのに注意して,
となるようにする.
同様に, をから初めて順に大きくしていってになった時点で終了
SourceCode
void solve() { //y -> x int x, y; cin >> x >> y; vector<int> vx(3, y); vector<int> vy(3, x); ull cnt = 0; ull ok = 0; for (ull i = 0;; ++i) { int tar = i % 3; if (vx[tar] != x) { vx[tar] = min(vx[(tar + 1) % 3] + vx[(tar + 2) % 3] - 1, x); ++cnt; } else ok |= 1 << tar; if (ok == (1 << 3) - 1) break; } cout << cnt << endl; }