I'm glad to welcome all fans of programming!

The second qualifying round Yandex.Algorithm will take place today, and it was prepared for you by Artem Rakhov, Michael Mirzayanov and me.

Please pay attention that as well as during the previous qualifying round Codeforces's functionality will be a little cut down for the period of the competition. Don't worry, all will return into place after the round termination.

I remind the best 500 participants pass in Yandex. Algorithm 2011 Round 1 which will take place on May, 20th at 19.00

Good luck!

**UPD: the contest is over, congratulations to the winner - **tourist!

**I recall this competition was a qualifying round, and the best 500 will take part in Yandex.Algorithm Round 1!**

**Today two participants were the most lucky - **Hossein_Hima and ss.nurboolean, - **they have taken 499-500 places together with result 978 scores.**

With the first 500 people per race?

EDIT: but my contributions may increase...

EDIT: Sorry I thought it was posted before the end of contest. Really sorry...База для k=0 очевидно.

Пусть пришли еще не все потомки, тогда из какого-то поддерева пришли не все потомки, тогда в вершину поддереве там пришло не меньше (k-1) за k-1 ход+1 была. Значит там что-то есть=> Оттуда что-то приедет.

Let d be the maximum distance from the capital to a people. Let x be the number of people whose distance from the capital is d. "x + d" is initially at most n, and each day this value always decreases.

<move follow qestion>

In case n > 2 a[i][j] = n-1 if and only if i and j were from one set. Find a for all 1 <= i, j <= 200, and you can find answer easy!

FIRST - input line in which was first occurence of this number

SECOND - input line in which second occurence of this number

two number belong to one answer where they have equal FIRST,SECOND pair

simple :)

1. u have not used points used[1..200] all set to 0//not used

2. read n - amount of sets,set must out sets o=n;

3 while readind n*(n-1)/2 pairs of sets do this:{ line number is j

set setA=empty; setB= empty;

read k-amount of points

for all k points p in this line j do {

if used[p]<0 continue;

if used[p] ==0 {is notused mark used[p]=j//it means that number p fist time in j line}

else if used [p]>0 {it means that in j line we get set

with p points in 2nd time so we can solve what set has p point

if (A.empty||used[A.top]==used[p])A.push(p) else B.push(p)

}//end for k points in j line

if(not empty A){out(A);mark all p in A used[p]*=-1;o--}

if(not empty B){out(B);mark all p in B used[p]*=-1;o--}

}//end for j lines of n*(n-1)/2 lines of pairs sets

test if (o>0){//o==2

cose we have last readed line like k a1 a2 .... ak

we make hand made out like

line1: 2

line2: 1 a1

line3: k-1 a2 ... ak

}

thats all

loose time cose this solution solv not only problem B but problems where not all pairs n*(n-1)/2, but that where each sets no less 2 times so this can solv:

4

4 1 11 2 22

4 1 11 3 33

4 2 22 4 44

4 4 44 5 55

4 5 55 6 66

4 6 66 3 33

Read the first of n*(n-1)/2 union. Remember the first element of it -

.FThen read all other unions and save only containing this

.FWe will get

unionsn-1U, ...,_{1}U._{n}Then intersect

Uand_{1}U, we will get_{2}A, that contains_{0}.FAfter that subtracting

Afrom every_{0}U, we will get_{i}A._{i}And

A, ...,_{0}Aare the answers. :)_{n-1}If I'm not mistaking, it could be realized with complexity O(n*m) where m is the number of different elements, so about const*200*200 solution.

And don't forget about 2.

Mverticies (up to 200 verticies). Where each vertex is assigned an unique value ofA._{i}(u, v)of such graph we should count its weight as the number of times the valuesuandvappeared in one union. If this number is smaller thanN - 1we should ignore this edge in our further solution. And than it's very simple to find all the connected components. Solution requiresO(Mtime and^{2})O(Mmemory.^{2})N= 2 again.For the first part, note that you may count each window (and both lightbulbs) separately, and each window gives a trapezoid shadow.

For the second part, you will each time only need to intersect two such trapezoids -- one from the upper bulb and one from the lower. It may look even easier if noticed that you may intersect triangles, not trapezoids.

However, the origin set in B could be 19900, and I announced 200....