날카로운 눈
1. 힌트
1) 정수 더미에 들어있는 정수의 최대 개수는 N×(231−1)이기 때문에 당연히 완전 탐색으로는 불가능하다.
2) 정수 더미에 들어있는 전체 정수의 개수는 짝수 + 홀수 이기 때문에 홀수가 된다.
3) f(x)를 정수 더미 내의 x이하의 정수의 개수로 정의하면 f(x)는 짝수에서 홀수로 바뀌는 지점이 존재한다, 그 x의 값이 홀수개 존재하는 수이다.
2. 구현
public class Main {
static int N; static int[][] S;
static long f(long x) {
long sum = 0;
for (int i = 0; i < N; i++)
sum += cnt((int)x, S[i][0], S[i][1], S[i][2]);
return sum;
}
static int cnt(int x, int A, int C, int B) {
if (A > C || x < A) return 0;
C = Math.min(C, x);
return (C - A) / B + 1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
S = new int[N][3];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < 3; j++) S[i][j] = Integer.parseInt(st.nextToken());
}
long lo = 0; long hi = Integer.MAX_VALUE;
if (f(hi) % 2 == 0) { System.out.println("NOTHING"); System.exit(0); }
while (lo + 1 < hi) {
long mid = (lo + hi) / 2;
if (f(mid) % 2 == 1) hi = mid;
else lo = mid;
}
System.out.println(String.format("%d %d", hi, (f(hi) - f(hi - 1))));
}
}
1) 시간 복잡도
2) 테스트 케이스