410. Galaxy in danger

410. Galaxy in dangerTime limit per test: 2 second(s)
Memory limit: 65536 kilobytesinput: 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 Nmistkafers 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.

InputIn 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. 

OutputOn 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
题目是这个样子的。。
一堆数,两种操作。。一种是所有数-1
一种是一个数*2.。
用最少操作让所有数都变成0.。。。
首先可以发现-1的次数肯定就是最大的那个数。。
然后显然就是每次看看最小的那个数*2是不是比最大的那个大,
不是的话就把它*2.。。
然后答案比较小的话模拟一下。。
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=100000;
using namespace std;
typedef long long ll;
int A[maxn],n,T[maxn];
struct cmp
{
bool operator()(int i,int j)const
{
return A[i]>A[j];
}
};
priority_queue<int,vector<int>,cmp> PQ;
int Solve()
{
int ret=0;
int Max=*max_element(A,A+n);
for(int T=0;T<Max;)
{
for(;;)
{
int t=PQ.top();
if((A[t]-T)*2>(Max-T))
{
int pass=2*(A[t]-T)-(Max-T);
T+=pass;
break;
}
A[t]-=T;A[t]*=2;A[t]+=T;PQ.pop();
PQ.push(t);ret++;
}
}
return ret+Max;
}
void Simulate()
{
while(PQ.size())PQ.pop();
rep(i,n)PQ.push(i);
int Max=*max_element(A,A+n);
rep(T,Max)
{
for(;;)
{
int t=PQ.top();
if((A[t]-T)*2>(Max-T))break;
A[t]-=T;A[t]*=2;A[t]+=T;PQ.pop();
PQ.push(t);
printf("science mission to the planet %dn",t+1);
}
puts("flying mission");
}
}
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);
rep(i,n)scanf("%d",A+i),PQ.push(i);
memcpy(T,A,sizeof A);
int ret=Solve();
cout<<ret<<endl;
if(ret<=1000)
{
memcpy(A,T,sizeof A);
Simulate();
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>