CS Academy 084 DIV1 C - Split the Sticks

これは楽しい

問題へのリンク

問題概要

個の整数 が与えられる。

• 今ある整数の中から 1 個 ( とする) を選んで、好きな整数 を選んで、 を と に分裂させる

という操作を繰り返して、最終的に得られる整数の集合が、まったく同一の 2 つの集合に分けられるような状態にせよ。ただし操作の回数が を超えてはならない。(具体的な操作も復元せよ、できないときは -1 をリターンせよ)

制約

• 

例

{} のとき、

• 6 を 2 と 4 に分けて、{2, 2, 4, 8}
• 8 を 4 と 4 に分けて、{2, 2, 4, 4, 4}
• 4 を 2 と 2 に分けて、{2, 2, 4, 4, 2, 2} (これで {2, 2, 4} × 2 になる)

考えたこと

まず、 の総和が奇数ならばダメ
の総和が偶数のときは必ずできることを示せる。

以下のようにすればよい。priority_queue がいい感じに使える。

• のうちの小さい順に 2 個を選んで として、
  • なら両方 pop
  • そうでないなら を と に分裂させ、 と を pop する
• の中身が 1 個だけになったとき、それが必ず偶数になることが示せる (後述) ので、それを半分ずつに分裂させる

この操作をよく考えてみると、pop 操作を行ったとしても、 の総和の偶奇は不変である。よって最後に残るやつは必ず偶数になる。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
deque<long long> L;

typedef pair<long long,long long> pll;

int main() {
    while (cin >> N) {
        long long sum = 0;
        L.resize(N);
        for (int i = 0; i < N; ++i) {
            cin >> L[i];
            sum += L[i];
        }
        if (sum & 1) cout << -1 << endl;
        else {
            vector<pll> res;
            priority_queue<long long, vector<long long>, greater<long long> > que;
            for (int i = 0; i < N; ++i) que.push(L[i]);
            
            while (que.size() > 1) {
                long long p = que.top(); que.pop();
                long long q = que.top(); que.pop();
                if (p == q) continue;
                res.push_back({q, p});
                que.push(q-p);
            }
            if (que.size() == 1) {
                long long rem = que.top();
                res.push_back({rem, rem/2});
            }
            
            cout << (int)res.size() << endl;
            for (int i = 0; i < res.size(); ++i) {
                cout << res[i].first << " " << res[i].second << endl;
            }
        }
    }
}