POJ 3862 Business Center

問題

エレベータがm台あり、各エレベータには昇降用のボタンが2つだけついている。エレベータiの上昇ボタンを押すとu[i]階上がり、下降ボタンを押すとd[i]階下がる。階数は無限にあるが、0階より下の階はない。m台のエレベータのうちのいずれか一台のエレベータを選んで、n回昇降ボタンを押した上で到達することができるもっとも低層の階（ただし1階以上）を求めよ。

やりかた

上昇ボタンをx回、下降ボタンをn-x回押してp階にたどり着けるとするととなる。xについて解くと xは整数であるから分子は分母で割り切れる必要があり、これを満たすようなpは になる。すべてのエレベータでpを計算して最小値を求めればいい。

以下ソース。

int main(){
  int n, m, u, d;
  scanf("%d %d", &n, &m);

  int ans = INF;
  for(int i = 0; i < m; i++){
    scanf("%d %d", &u, &d);
    ans = min(ans, u + d - (d * n) % (u + d));
  }
  printf("%d\n", ans);
  return 0;
}