*a*

_{c}- amount of occurrences of letter

*c*in first and second strings in input,

*b*

_{c}- amount of occurrences of letter

*c*in third string in input. If the answer is "YES" else "NO".

*i*≤ 10

^{6}, in which assumedly the stone could hit. Let’s find the minimal number of square on this level. Then we can understand, how many squares there are on this level: one or two. Then we check with one or two ifs (if on this level two squares) if the stone is in corresponding square or not. If the stone is inside then output the answer. If we didn't find any square, where the stone is, output "-1".

*name*

_{i},

*a*

_{i}) by ascending of

*a*

_{i}. If there is an index i: 0 ≤

*i*<

*n*that

*a*

_{i}>

*i*, then answer is "-1". Otherwise the answer exists. We will iterate through the array of sorted pairs from left to right with supporting of vector of results

*res*. Let on the current iteration

*a*

_{i}=

*n*-

*i*, then we must transfer the current man in the position

*a*

_{i}. It can be done in C++ with one line: res.insert(res.begin() + a[i], man);

Let's generate the weighted directed graph of all ramps. The graphs' vertexes are the important points on the line *Ox*, there are points: 0, *L*, *x*_{i} - *p*_{i}, *x*_{i} + *d*_{i}. The graphs' edges are the possible ramp jumps: transfer from point *x*_{i} - *p*_{i} to point *x*_{i} + *d*_{i} or transfer from vertex in neighboring vertexes (neighboring means that we get the next and previous important points on the line). The weights of these edges are correspondingly *p*_{i} + *t*_{i} and *x*_{v + 1} - *x*_{v}, *x*_{v} - *x*_{v - 1}. We must note that in the transfers we can't get in the negative part of *Ox*, and we must delete this transfers.

Then we must find and output the shortest path in this graph from vertex 0 to *L*. This can be done, for example, with Dijkstra's algorithm for the sparse graphs.

In this problem we must find the minimum spanning tree, in which the half of edges are marked with letter 'S'.

There are *n* - 1 edges in this tree, because of it if *n* is even then the answer is "-1".

Let's delete from the given graph all S-edges. And there are *cnt* components in obtained graph. For making this graph be connected we must add *cnt* - 1 edges or more, that's why if *cnt* - 1 > (*n* - 1) / 2 the answer is "-1". Then we find *cnt* - 1 S-edges, that we must add to the graph, so that it become connected. If *cnt* - 1 < (*n* - 1) / 2 then we will try to add in this set of edges another S-edges, so that the S-edges don't make circle. We must do all of this analogically to Kruskal's algorithm of finding a minimum spanning tree. If we could get a set of S-edges of (*n* - 1) / 2 elements, that there are exactly *cnt* - 1 edges and no S-circles, then the answer exists, Then we must add to this set (*n* - 1) / 2 M-edges, that forms with our set of edges the minimum spanning tree, it must be done analogically with Kruskal's algorithm.

cntcomponents, then you addcnt- 1 edges of second type, then you just add remaining second type edges (all counted as ), that all second type edges doesn't make a cycle.OK, lets do it in English.

q, where we will place people in right order, that will be an answer. Sort input people by decreasing ofa, give them heightfrom n to 0, place them in arraymand go from begining of this array to the end. When m[i].a=0, just place them in vector q by decreasing of h. Notice, that they are the highest people. It means, that if we place some element in vector q on place ai, before him will be ai people, higher than he, that meets the problem.There are n - 1 edges in this tree, because of it if n is even then the answer is "-1".That would normally be correct, but here we can have roads that start and end at the same hut, so we can add such a road without changing the connectivity, can't we?

2 2

1 2 S

1 1 M

For this case, isn't the solution to clear both roads?

~~"between any two huts should exist exactly one simple path along the cleared roads". That case results in 2 paths from 1 to 2. Hence, we can't clear roads which connect the same hut.~~UPD: I misunderstood it. Your opinion seems correct based on the problem statement.

I think the roads which begin and end in the same hut are useful to adjust one nearly right answer to a right one.

for example, if I got S=10 M=9, and one road 2->2 is M, I can choose this road so that S=M=10.

and the rule above is satisfied, too. because 2->2 is never used, for when it's used nd 2 appeared twice. so whether to choose 2->2 is not important.

To conclude, the solution for problem E is wrong || the problem statement needs change.