[AtCoder] AGC 041 A – Table Tennis Training

2019年12月29日2020年12月17日

問題

方針

両者の距離が \( 2 \) の倍数のとき、向かい合うように進む事が最適です。また、卓 \( 1 \) または \( N \) に留まり続けることは最適ではありません。

\( (B – A) \bmod 2 = 0 \) のとき

このとき、両者は向かい合うように進めばいいので、\( \dfrac{B – A}{2}\) となります。

\( (B – A) \bmod 2 \neq 0 \) のとき

\( 2 \) 通り考えます。一つ目は、卓 \( A \) にいた選手が卓 \( 1 \) に向かって進み、卓 \( 1 \) で一回勝利したあと負け続けます。このとき、卓 \( B \) にいた選手は勝ち続けます。二つ目は、卓 \( B \) にいた選手が卓 \( N \) に向かって進み、卓 \( N \) で一回敗北したあと勝ち続けます。このとき、卓 \( A \) にいた選手は負け続けます。

したがって、

\[ \min \left( A + \dfrac{B – A – 1}{2}, \ N – B + 1 + \dfrac{B – A – 1}{2} \right)\]

が答えとなります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll N, A, B;
    cin >> N >> A >> B;
    if ((B - A) % 2 == 0) {
        cout << (B - A) / 2 << "\n";
    } else {
        cout << min(A + (B - A - 1) / 2, N - B + 1 + (B - A - 1) / 2) << "\n"; 
    }
    return 0;
}