A - Happy Birthday! 4 Editorial by shobonvip


公式解説のように、現在から \(k\) 年後 \((k \ge 0)\) に高橋君の年齢が青木君の年齢のちょうど \(Z\) 倍となるための条件は、

\[X+k = Z(Y+k)\]

となります。

\(k\) が大きすぎると高橋君の年齢と青木君の年齢の比が近くなることに注目します。たとえば、現在高橋君が \(25\) 歳、青木君が \(5\) 歳であるとき、現在では高橋君の年齢は青木君の年齢の \(5\) 倍になっています。しかし、今から \(995\) 年後には、高橋君が \(1020\) 歳、青木君が \(1000\) 歳となり、高橋君の年齢は青木君の年齢の \(1.02\) 倍にしかなりません。

どのくらい \(k\) を大きくすれば高橋君の年齢は青木君の年齢の \(2\) 倍未満になるのでしょうか? \((X+k)/(Y+k) < 2\) を解くと \(k > X-2Y \ge X\) となります。よって、 \(k \ge X + 1\) であれば二人の年齢の比の値は \(2\) 未満になります。したがって、 \(k\) として考慮すべき値は \(k = 0,1,2,\cdots, X\) のみとなります。

制約が \(1 \le X, Y \le 100\) と小さいので、 \(k=0,1,2,\cdots, X\) について \(X+k = Z(Y+k)\) か否かをすべて試しても実行時間に間に合い、正解することができます。

なお、厳密に \(k \le X\) などと評価できなくても、直感的に \(k\) が抑えられることを感じ取れば、 \(k \le 10^6\) などで全探索を行うことで正解することも可能です。(いわゆる未証明AC)

x, y, z = map(int,input().split())
for i in range(x + 1):
	if x + i == (y + i) * z:
		print("Yes")
		exit()
print("No")
#include<bits/stdc++.h>
using namespace std;
int main() {
	int x, y, z;
	cin >> x >> y >> z;
	for (int i=0; i<=x; i++) {
		if (x + i == (y + i) * z) {
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
}

posted:
last update: