けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 041 A - Table Tennis Training (灰色, 300 点)

若干注意力ゲーだった。端で折り返してこれることに注意。

問題概要

正の整数  N, A, B が与えられる。2 つの整数  A, B に対して毎回以下のような操作を行う。2 つの整数が一致させられるまでの最小回数を求めよ。

  • 整数  x 1 でも  N でもないとき、 x-1 x+1 のいずれかに置き換える
  •  x = 1 のとき、1 か 2 のいずれかに置き換える
  •  x = N のとき、 N-1 N のいずれかに置き換える

制約

  •  2 \le N \le 10^{18}
  •  1 \le A \lt B \le N

考えたこと

まず  B-A が偶数ならば、お互いに中点で出会うことができるので、 \frac{B-A}{2} 回となる。

そうでない場合は、

  •  A がマス 1 に行って、一回だけ待機して、折り返して  B と合流する
    •  ((A-1) + (B-1) + 1) / 2 回になる
  •  B がマス  N に行って、一回だけ待機して、折り返して  A と合流する
    •  ((N-A) + (N-B) + 1) / 2 回になる

のうちの小さい方を採用すれば OK。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long N, A, B;
  cin >> N >> A >> B;
  if (abs(A-B)%2 == 0) cout << abs(A-B) / 2 << endl;
  else {
    cout << min((A+B-1)/2, (N*2-A-B+1)/2) << endl;
  }
}