CF 986 problem B 풀이 정리

버츄얼을 돌던 중 만난 문제이다.

 

발상이 조금 특이해 블로그에 기록한다.

 

1. permutation 만드는 것이 가능한 경우

 

일단 permutation을 만들 수 있는 경우만 생각해 보면

 

$b$가 0 이상이면 다 된다.

 

모든 원소가 unique하기 때문에 $[0,n-1]$을 만들 수 있다.

 

이때 원소 중 $0\leq x<n$인 원소는 바꾸지 않아도 되므로

 

$0\leq x<n$의 개수를 $n$에서 빼주면 된다.

 

2. 불가능한 경우

버츄얼 때에는 $b=0\;and\;c=0$으로 잡아서 틀렸다. (\앞으로 더 신중하게 반례를 생각해볼 필요가 있을 것 같다.\)

 

불가능한 경우는 $b=0$일 때를 주목하면 된다.

 

$b=0$일 때 모든 원소는 $c$로 구성되어있다.

 

이들에 대해 연산을 진행하다보면 순환을 만나게 되는데

 

바로 $c+1\rightarrow c+2\;\;c+2\rightarrow c+1$에서 계속 순환해 $c+1$번째 원소에서

 

더 이상 진행을 할 수 없다.

 

따라서 $c+1<n-1$ 통과할 수 없으므로 이 조건까지 해결해야 했다.

 

$b=0$인 다른 경우는 가능 경우와 같은 방식으로 처리했다.

 

코드는 다음과 같다.

 

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int main(){

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int t;

    cin >> t;

    while(t--){

        ll n,b,c;

        cin >> n >> b >> c;

        if(b==0 && c<n-2){

            cout << "-1\n";

            continue;

        }

        if(b==0){

            cout << n-(c<n) << '\n';

            continue;

        }

        ll cnt=(n-c)/b;

        if(n-c>b*cnt) cnt++;

        if(c>=n) cnt=0;

        cout << n-cnt << '\n';

    }

    return 0;

}