p410.ans2
======================
1035

=================
p410.in2
======================
2
2 1025

=================
p410.ans1
======================
3
science mission to the planet 1
flying mission
flying mission

=================
p410.in1
======================
2
1 2

=================
statement.txt
======================
410. Galaxy in danger
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Many years has already passed since the Logos galaxy was attacked by crazy space creatures, called mistkafers. With extreme efforts brave defenders of the galaxy managed to defeat the main forces of the opponent. The remaining enemies have been isolated on N different planets.

Now the Government of a galaxy has a very difficult problem — to get rid from mistkafers in a galaxy as soon as possible. Namely to take them far beyond the galaxy and to dump them into a black hole. To cope with this problem, the Government needs help of winged pferds which can fly through black holes.

By a strange coincidence, there is exactly N pferds available for the Government. Pferds can fly only all together, and each of them can transport to a black hole only one mistkafer per day. Thus, every day pferds take N mistkafers and transport them into a black hole. And every pferd is so logical and consecutive, that will take mistkafers from the same planet every time, and will not fly to a black hole without mistkafer. Therefore, if there is no mistkafers left on some planet, pferds cannot take them out further.

In order to prevent such situations, in the morning of each day the Government can send scientists to some of the planets. These scientists can clone mistkarefs (no matter how they do it, but after cloning the number of mistkafers on the planet is doubled). The cloning of mistkafers on one planet takes exactly one day, so that day pferds do not take off.

Find out the minimal number of days which is required to get rid of mistkafers.

Input
In the first line of the input file the amount of planets N (1 ≤ N ≤ 100000) is given. The second line contains N natural numbers, each of them means the number of mistkafers on a corresponding planet. The quantity of mistkafers on each planet does not exceed one billion.

Output
On the first line of the output file print one number K — the answer to the problem. In case the number of days does not exceed one thousand, in the following K lines output the description of days in the chronological order. If on the i-th day there was a flight of the pferds, output on (i+1)-th line a phrase "flying mission" (without quotes), otherwise output a phrase "science mission to the planet j (without quotes), where j — is the number of a planet on which the cloning was made.

Example(s)
sample input
sample output
2
1 2
3
science mission to the planet 1
flying mission
flying mission

sample input
sample output
2
2 1025
1035

=================
p410.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int64_t> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // The problem asks for the least number of operations of either multiplying
    // by 2, or subtracting 1 from everything, required to make everything zero.
    // First we can notice that we need at least M = max(a) steps of
    // subtracting 1. We can show this is enough. Particularly, say we look at
    // some M/2 < x < M. Then with a single double, we can reach 2x >= M, and
    // there is no point in doubling further. But if we first subtract and then
    // double, we get to 2(x-1), while at that M := M - 1. What's more relevant
    // is the difference between M and x. Subtracting doesn't change it, while
    // doubling will overshoot it into 2(x-s)-(M-s) = 2x-M-s. Ideally we
    // shouldn't overshoot M, as that would create a new maximum. Therefore, we
    // can try to solve for s, or s = 2x-M. One constraint we have is that x >=
    // s >= 0. In other words we might have to first double until we reach a
    // point where we can actually match with M. After that point, we will find
    // s, wait for some subtraction steps (=s), double, and now have the two
    // positions will be equal. The above construction already performs M
    // subtracting steps, but we now need to make sure that doubling is also
    // optimal. This is not hard to notice, as the above approach will do
    // ~log(M/x) doubling steps, and this is the least we need, because we will
    // perform M subtracting steps anyways. We shouldn't forget that the problem
    // also asks for the actual construction if the answer is small enough.

    int64_t M = *max_element(a.begin(), a.end());
    int64_t ans = M;

    vector<vector<int>> ops(min(M, 1024ll));
    vector<int> pre_ops;
    for(int i = 0; i < n; i++) {
        int64_t x = a[i];
        while(x < M) {
            int64_t s = 2 * x - M;
            if(s >= 0 && s <= x) {
                ans++;
                if(0 <= s && s <= 1000) {
                    ops[s].push_back(i + 1);
                }
                break;
            }

            pre_ops.push_back(i + 1);
            ans++;
            x *= 2;
        }
    }

    cout << ans << endl;
    if(ans <= 1000) {
        for(int pos: pre_ops) {
            cout << "science mission to the planet " << pos << endl;
        }
        for(int i = 0; i < M; ++i) {
            for(int pos: ops[i]) {
                cout << "science mission to the planet " << pos << endl;
            }
            cout << "flying mission" << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
