AGC 017 B - Moderate Differences
Nこのマスがあり、左端にAが、右端にBが書かれている
隣接する全てのマスで、整数の差がC以上D以下に出来るか判定せよ
3 <= N 50000
A 10^9
B 10 ^9
0 <= c <= D <= 10 ^9
自分の解法
一マスごとに足した場合の区間と引いた場合の二通りの区間があるため、答えに近い方を選択する。
想定解
足し引きの順番は関係なく、それらの回数により、結果が一意に定まるため、全探索。
public static void main(String[] args) { N = sc.nextInt(); A = sc.nextInt(); B = sc.nextInt(); C = sc.nextInt(); D = sc.nextInt(); long l = A,r=A; for (int d = 1; d < N; d++) { long mid = (l+r)/2; if(mid<B){ l+=C; r+=D; } else{ l-=D; r-=C; } } if(l<=B&&B <= r){ System.out.println("YES"); } else{ System.out.println("NO"); } }