题解归档 - cf2228B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2228B
• 本地来源：problems/cf2228B/idea.md
• 题目链接：https://codeforces.com/contest/2228/problem/B
• 原始标题：cf2228B

思路

cf2228B

pattern: pursuit on a cycle with limited evasion moves.

claim: If n<=3, every different position is adjacent to Reimu, so she catches in one second.

For n>=4, let d be the initial shorter circular distance. Without Remilia moving, Reimu catches in d seconds. Each adjacent move by Remilia can be made away from Reimu and delays capture by exactly one second; after those k moves are spent, Reimu closes the remaining distance.

answer: 1 for n<=3, otherwise min(|x1-x2|, n-|x1-x2|)+k.

edge: n=2,3 are special because there is no safe away move.

代码

来源：problems/cf2228B/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ll t,n,x1,x2,k,d;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld%lld",&n,&x1,&x2,&k);
        if(n<=3){
            printf("1\n");
            continue;
        }
        d=llabs(x1-x2);
        d=min(d,n-d);
        printf("%lld\n",d+k);
    }
    return 0;
}