[AGC026] B - rng_10s
[Q] https://atcoder.jp/contests/agc026/tasks/agc026_b
循環するからなんかのmodをとると思うと、とても嫌な気持ちになるけど、この問題は大丈夫なやつ。
知識がない状態でも、ループを見つけて法則を探れば分かる。
1. とりあえず、A<Bなら最初でNo
2. とりあえず、B>Dなら、いつか追い込まれるのでNo
3. シミュレートして法則を見つける
4. 収入Dと支出Bだけ変動するので、gcd(B, D)の変動を網羅することになるだろうと思う。
5. あと1回Bしたら、C以下になるような在庫数xを考える。
6. ありうるxの最小値がBに満たないならNo
Q. シミュレート？
・ex1
9 7 5 9
9 →昼 2 →夜 11 →昼 4 →夜 13 →昼 6 →夜 6 →昼 x
4. 永遠に回すので、収入と支出の最大公約数だけループするのがわかる。
ll g = gcd(B,D) = gcd(7,9) = 1
5. あと1回とったらC以下になる在庫数を抽出すると、
9,11,6,xとなっているようだ。
~
gcd が 1なので、あと1回とったらC以下になる在庫数として取りうる値は、
6,7,8,9,10,11,12
の7種類が全部出るんだろうと思う。
low = 6
6. そして、low = 6 < 7(B) なので、Bを満たせずNo
・ex2
9 7 6 9
9 →昼 2 →夜 11 →昼 4 →夜 13 →昼 6 →夜 15 →昼 8 →夜 8 →昼 1 →夜 10 →昼 3 →夜 12 →昼 5 →夜 14 →昼 7 →夜 7 →昼 0 →夜 9
gcd = 1
5. あと1回とったらC以下になる在庫数は、
9,11,13,8,10,12,7
つまり
7,8,9,10,11,12,13
これはgcd=1だから網羅する。
low = 7 >= Bなので、Yes。実装
bool solve() {
ll A, B, C, D;
cin >> A >> B >> C >> D;
if (A < B) return false;
if (B > D) return false;
ll g = gcd(B, D);
ll high = A % B;
// highは±gを任意に変動しうる。
// high < C である限りgを足す
high += ((C - high + g - 1) / g) * g;
// ぴったりならもう1回
if (high <= C) high += g;
if (high < B) return false;
return true;
}
int main() {
cincout();
ll T;
cin >> T;
rep(i, T) {
if (solve()) {
cout << "Yes" << endl;
} else
cout << "No" << endl;
}
}