백준 31749 - 조작

 

 

step 1

$N$이 홀수일 때는 답이 0입니다.

1. $a_1, a_2$를 조작하여 $a_1$을 $0$으로 만듭니다.
2. $a_2, a_3$를 조작하여 $a_2$을 $0$으로 만듭니다.
3. 이런 식으로 $a_{n-1}$까지 $0$으로 만듭니다. 그럼 $a_n$에만 값이 들어있을 것입니다. 이제부터 나머지 숫자들을 $a_n$에 맞출 것입니다.
4. $a_{n-2}, a_{n-1}$을 조작하여 두 숫자를 $a_n$로 만듭니다.
5. $a_{n-4}, a_{n-3}$을 조작하여 두 숫자를 $a_n$로 만듭니다.
6. 이런 식으로 $a_1, a_2$까지 조작해서 모든 숫자를 $a_n$으로 만듭니다.

step 2

위의 3번 과정까지 따라 하면 마찬가지로 $a_n$에만 값이 들어 있습니다. 백준 예제입력에 위 과정을 적용하면

 

0 0 0 0 0 14

 

가 됩니다. 이 값은 홀수일 때와 달리 없어지지 않습니다. 이 값을 $a_2, a_4, ..., a_n$에 골고루 나누어 줄 것입니다. 위 수열을 예로 들면

 

0 4 0 5 0 5

 

로 만들 것입니다. 이 뒤로는 예시를 이용해 설명하겠습니다.

 

1. $a_5, a_6$에 $-9$를 더해줍니다.  (0 0 0 0 -9 5)
2. $a_4, a_5$에 $9$를 더해줍니다.  (0 0 0 9 0 5)
3. $a_3, a_4$에 $-4$를 더해줍니다.  (0 0 -4 5 0 5)
4. $a_2, a_3$에 $4$를 더해줍니다.  (0 4 0 5 0 5)

코드

#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#include <cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
ll b[200000],cnt=0;
struct data {
    ll x, y;
}d[2000000];
int main() {
    ll n, i;
    scanf("%lld", &n);
    for (i = 1;i <= n;i++) {
        scanf("%lld", &b[i]);
    }
    if (n % 2 == 1) {
        printf("0\n");
        for (i = 1;i < n;i++) {
            cnt++;
            d[cnt].x = i;
            d[cnt].y = b[i] * -1;
            b[i + 1] -= b[i];
            b[i] = 0;
        }
        for (i = n - 2;i >= 1;i-=2) {
            cnt++;
            d[cnt].x = i;
            d[cnt].y = b[n] - b[i];
        }
    }
    else {
        for (i = 1;i < n;i++) {
            cnt++;
            d[cnt].x = i;
            d[cnt].y = b[i] * -1;
            b[i + 1] -= b[i];
            b[i] = 0;
        }
        ll dd = (abs(b[n]) % (n / 2) == 0 ? abs(b[n]) / (n / 2) : abs(b[n]) / (n / 2) + 1);
        printf("%lld\n", dd);
        ll r = abs(b[n]) % (n / 2);
        if (r == 0) r = n / 2;
        for (i = n - 1;i >= 2;i-=2) {
            cnt++;
            d[cnt].x = i;
            if (b[i + 1] < 0) {
                d[cnt].y = (b[i + 1] * -1) - (r >= 1 ? dd : dd - 1);
            }
            else {
                d[cnt].y = (b[i + 1] * -1) + (r >= 1 ? dd : dd - 1);
            }
            b[i] += d[cnt].y;
            b[i+1] += d[cnt].y;
            r--;
            cnt++;
            d[cnt].x = i-1;
            d[cnt].y = b[i] * -1;
            b[i - 1] += d[cnt].y;
            b[i] += d[cnt].y;
        }
    }
    printf("%lld\n", cnt);
    for (i = 1;i <= cnt;i++) {
        printf("%lld %lld\n", d[i].x, d[i].y);
    }
    return 0;
}