1637 - 날카로운 눈

문제 링크

---

https://www.acmicpc.net/problem/1637

문제 요약

---

정수가 여러개 모여있는 정수더미가 있다. 이 때 정수더미 안에서 홀수개 들어있는 특정 정수를 찾는 문제다. 홀수개 들어있는 정수의 수는 최대 한개이며 없을수도 있다.

문제 풀이

---

이 문제는 정수가 직접 주어지는게 아니라 정수더미 안에 들어있는 수들의 규칙이 주어지고 이를 통해 홀수개 들어있는 정수를 찾아야 하기 때문에 단순 시뮬레이션으로는 풀수가 없다. 그렇다면 어떻게 접근해야 할까?

우선 예제의 수들을 한번 직접 계산해보자.

직접 계산해 본다면 숫자 4가 3개 들어있어서 답이 됨을 알 수 있다. 이것만으로 일정한 규칙을 찾을수가 없다. 하지만 이들 수의 누적합을 계산해 본다면 특정 규칙을 찾을 수 있다.

위 표를 잘 살펴보면 숫자 4이후로 누적합은 홀수가 되는것을 알 수 있다. 홀수개 존재하는 정수는 최대 하나니까 한번 누적합이 홀수가 된 이후는 다시 짝수로 바뀌는 일은 없다. 이러한 특징을 이용해 \(binary\ search\)를 이용해 풀 수 있다.

이 문제는 \(func(x)\)라는 함수를 정의해서 쉽게 풀 수 있다. 함수의 의미는 \(x\)보다 작거나 같은 수들 중 정수더미에 들어있는 수의 개수라고 정의한다. 이 함수는 마지막에 답을 출력할 때도 도움이 된다. 만약 홀수개 들어있는 정수를  \(ans\)라고 했을 때 \(ans\)는 정수더미에 몇개 존재하는지 출력을 해야 한다. 이는 \(func(ans)-func(ans-1)\)로 쉽게 계산할 수 있다.

소스 코드

---

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll INF = 1LL << 32;
const int MAX = 20010;
int n;
ll A[MAX], B[MAX], C[MAX];

ll func(ll mid) {
  ll ret = 0;
  for (int i = 0 ; i < n ; ++i) {
    if (mid >= A[i]) {
      ret += (min(mid, C[i]) - A[i]) / B[i] + 1;
    }
  }
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 0 ; i < n ; ++i) {
    scanf("%lld%lld%lld", &A[i], &C[i], &B[i]);
  }
  
  ll lo = 0, hi = INF;
  while (lo <  hi) {
    ll mid = (lo + hi) >> 1;
    if (func(mid) & 1) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  
  if (lo == INF) {
    puts("NOTHING");
  } else {
    printf("%lld %lld\n", lo, func(lo) - func(lo - 1));
  }
}