[Codeforces][Round #667][Div.3] C : Yet Another Array Restoration (C++)

https://codeforces.com/contest/1409/problem/C

Problem - C - Codeforces

 

 

[난이도] Div.3
[유형] 구현

[풀이]
a2−a1=a3−a2=…=an−an−1=k 를 등차 k가 가장 적게하면서 만족할수록
max(a1,a2,…,an)의 값은 작아지게 된다. k=1부터 체크하면서 조건을 만족하는
수열을 만들 수 있는지 확인해보자

 

#include <cstdio>
using namespace std;
int n,x,y,tc;
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&n,&x,&y);
        int s,e,j;
        for(int i=1;;i++){
            int cnt=1;
            j=i;
            if((y-x)%i) continue;
            s=x,e=y;
            cnt+=(y-x)/i;
            if(cnt > n) continue;
            if(cnt == n) break;
            s -= ((x-1)/i)*i;
            if((x-1)/i+cnt>=n) {
                cnt+=(x-1)/i;
                s+=(cnt-n)*i;
                break;
            }
            cnt+=(x-1)/i;
            e+=(n-cnt)*i;
            break;
        }
        for(int i=s;i<=e;i+=j) printf("%d ",i);
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/C.cpp