Good day!

I invite everyone to take part in the last contest of the series of WCS olympiads for school students which is one of the regular Codeforces rounds at the same time. The start of the contest is on the 12th of December, at 11:00 MSK.

The competition rules are ACM-ICPC rules, the duration of the contest is 3 hours.

Like the previous school individual olympiads, the contest will be rated for all participants (both for school students and others). Rating will be calculated according to the merged result table.

The authors of the problems are me and Dmitry Matov again. Thanks to Gerald Agapov and Artem Rakhov for their help in preparing the problems and to Maria Belova for translating the problem statements.

Good luck everyone!

UPD. The contest is over. The results are available. The winner of School Personal Contest is scottai1, the winner of Codeforces Beta Round is ilyakor. Congratulations to the winners!

The author's problem analysis is posted. Now problems G and H are added to the tutorial, too.

Thanks to everyone who participated in WCS series for school students, officially and unofficially!

_{i}gives bounds (s_{i}+1)/i > alpha >= s_{i}/i_{i}<= Alpha * i < A_{i}+ 1_{i}/ i);_{i}+ 1) / i);const int N = 100010;

long long bk[N];

long long a[N];

int n;

int main()

{

int i, j, k;

scanf("%d",&n);

memset(bk,0,sizeof(bk));

for(i = 1; i<=n;i++)

{

scanf("%lld",&a[i]);

bk[a[i]]++;

}

i=1;

while(i+1<=n&&bk[i]>=bk[i+1])i++;

if(i<n) printf("-1\n");

else{

printf("%lld\n",bk[1]);

printf("%lld",bk[a[1]]--);

for(i = 2; i <=n;i++)

printf(" %lld",bk[a[i]]--);

}

scanf("%d",&i);

return 0;

}

Possibly that's a mistake:

while (i+1<=n && bk[i] >= bk[i+1]) i++;_{i}can be even 10^{5}.yeah

my first code got presentation error on test 5 too.

i had to change my code completely and then got AC.but still i don't know where i made the mistake.

1

5

Correct answer is -1, you print

0

1

http://codepad.org/kS4YaBTk

When a car is located at station X and you refueled your car K times before (let's say initial moment also counts as refuel, so K >= 1), then the amount of fuel in the tank at station X is equal to [alpha * K - X * 10]. You can easily see that:

- if you had to stop at station X, then [alpha * K - X * 10] < 10 because otherwise you would have reached the next station without refuel

- if you didn't have to stop at station X, then [alpha * K - X * 10] >= 10

So, input values give you a set of less/greater conditions on alpha, so you can calculate alpha_lo and alpha_hi for the input data. Then you have to check a few forward station indices X and see if [alpha_lo, alpha_hi) is non-empty for them using the same algorithm. If you find a single matching value X, then the answer is unique. Otherwise it's not.

So, that gives you linear complexity in respect to the max station index.

_{this is my code(my reply to Narashy appeared below the filix's post!!)}_{#include<iostream>}_{}_{#include<vector>}_{}_{using namespace std;}_{}_{vector<int> per[100010];}_{}_{int a[100010],num[100010],lab[100010];}_{}_{int main(){}_{}_{ int n;}_{}_{ cin>>n;}_{}_{ for(int i=0;i<n;i++)}_{}_{ cin>>a[i];}_{}_{ for(int i=0;i<n;i++)}_{}_{ num[a[i]-1]++;}_{}_{ for(int i=0;i<n;i++)}_{}_{ {}_{}_{ for(int k=0;k<num[i];k++)}_{}_{ {}_{}_{ per[k].push_back(i+1);}_{}_{ if(per[k].size()>1)}_{}_{ {}_{}_{ if(per[k][per[k].size()-1]!=per[k][per[k].size()-1])}_{}_{ {}_{}_{ cout<<"-1";}_{}_{ return 0;}_{}_{ }}_{}_{ }}_{}_{ if(per[k].size()==1&&per[k][0]!=1)}_{}_{ {}_{}_{ cout<<"-1";}_{}_{ return 0;}_{}_{ } }_{}_{ }}_{}_{ }}_{}_{ int l=0;}_{}_{ while(per[l].size()>0)}_{}_{ { }_{}_{ l++;}_{}_{ }}_{}_{ cout<<l<<endl;}_{}_{ for(int i=0;i<n;i++)}_{}_{ {}_{}_{ cout<<++lab[a[i]]<<" ";}_{}_{ }}_{}_{ return 0;}_{}_{}}Why?

it seems large and it is because i don't know how to post a code here!

please tell me!!!thanks

THX

can anyone help me?!

my code gives the correct answer(-1)to the test case below:

1

5

i couldn't find my mistake,its good to put the test case 5 here.

can anyone help me?!

my code gives the correct answer(-1)to the test case below:

1

5

i couldn't find my mistake,its good to put the test case 5 here.

its right too!I'm really wondering !what's wrong with that!

i have posted my code(bud it's a little unreadable!)you can check it your self...thanks

http://pastebin.com/VWkUw2Qj

6

Is this a correct solution?

In case this might be just a coincidence, This is the algorithm I applied;

using a counting sort, count the instances of each number while also storing the numbers in an array. Then, reading the numbers in the array one by one and simply printing its count and then reducing its count by 1.

http://codepad.org/GHUzcb2v this is the code if someone wants to go through it to understand what I have done.

If that is right then perhaps i made a mistake with my limits or something.

n is the number of planets.

problem B,what is it,answer?

Then you iterate over the entire matrix and calculate the sum in the small rectangle which can now be done in O(1) using the above matrix.

I got wrong answer in case no.7 ,,,problem - E -....plz any help

[code]

#include <string.h>

#include <vector>

#include <queue>

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <math.h>

#include <map>

#include <set>

#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()

#define rep_(i,n) for(i=n-1;i>=0;i--)

#define rep(i,n) for(i=0;i<n;i++)

#define forr(i,a,b) for(i=a;i<=b;i++)

#define forr_(i,a,b) for(i=a;i>=b;i--)

#define min(a,b) ( a>b? b : a )

#define max(a,b) ( a>b? a : b )

#define sz size()

#define pb(a) push_back(a)

#define mset(a,v) memset(a,v,sizeof(a))

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef map<int,int> mi;

typedef vi::iterator it;

typedef pair<int,int> pii;

typedef vector<pii> vpii;

typedef vector<string> vs;

typedef pair<string,int> psi;

typedef vector<psi> vpsi;

typedef queue<int> qi;

typedef queue<pii> qpii;

typedef unsigned long long ubig;

typedef long long big;

typedef long double bigd;

template<class T> string tos(T x){stringstream ss; ss<<x; return ss.str();}

int Draw,Ivan,Zmey;

vpii v1,v2;

int i,h,t,r,m,n;

class Substitute

{

public:

};

void solve()

{

queue<pair<pair<int,int>,int> > q;

bool vis[1000][1000];

mset(vis,0);

pair<pair<int,int>,int> start(pair<int,int>(h,t),0),cur;

q.push(start);

int cc,ch,ct;

while(!q.empty())

{

cur=q.front();

cc=cur.second;

ch=cur.first.first;

ct=cur.first.second;

q.pop();

if(vis[ch][ct])

{

Draw=true;

}

else if(ch+ct>r)

{

Zmey=cc;

}

else if(!ch && !ct)

{

Ivan=cc;

return;

}

else

{

vis[ch][ct]=true;

int k,l;

rep( k , min(n,ch) )q.push(pair<pair<int,int>,int>(pair<int,int>(ch-(k+1)+v1[k].first,ct+v1[k].second),cc+1));

rep( l , min(m,ct) )q.push(pair<pair<int,int>,int>(pair<int,int>(ch+v2[l].first,ct-(l+1)+v2[l].second),cc+1));

}

}

}

int main()

{

cin>>h>>t>>r>>n;

v1.resize(n);

rep(i,n)cin>>v1[i].first>>v1[i].second;

cin>>m;

v2.resize(m);

rep(i,m)cin>>v2[i].first>>v2[i].second;

solve();

if(Ivan)cout<<"Ivan\n"<<Ivan<<endl;

else if(Draw)cout<<"Draw\n";

else cout<<"Zmey\n"<<Zmey<<endl;

return 0;

}

[/code]

iam using bfs

Please, edit your post.

Is there anyone know the test 6 for Problem C?thx

B: 5?

C: 8, 9, 17, 19, 25

D: 4, 9, 11

E: 4, 11, 25, 46

H: 9