Hello everybody!

Is there a predefined data structure in C++ that allows you to insert numbers (maybe even dublicate keys) and effectively count the amount of numbers greater or less than a given value?

Now I'm using a recursive implementation of Red Black Tree — Here in original (Java) and Here translated to C++ with count_greater implemented.

One idea would be using std::lower_bound in std::map and then std::distance from map.begin() to the result iterator.

Suppose you have a triangle(x1,y1,x2,y2,x3,y3) and another one (x11,y11,x22,y22,x33,y33) . Coordinates don't come in a specific order.

The question: Can you draw the second triangle by just moving or rotating the first one? You can't detach the triangle from the board. EX: Therefore, using any of this two triangles you can't draw the other one.

So, one way is to compare the area and the angles, but still can't figure out how to deal with the case given above (where the area and the angles are equal, but the answer is still "NO". Maybe it's a special use of signed area formula?

UPD!!! Thanks everyone! Here's how I solved it.

1. Read coords of the first triangle

2. Compute d1 (between point 1 and 2), d2 (2-3), d3 (1-3).

3. Put them in a separate vector. (We suppose that the direction is clockwise)

4. Compute the signed area, if it's less than zero, swap vector[0] with vector[2]. (we took the wrong direction, switch to counter-clockwise).

5. Repeat 1-2-3-4 for the second triangle.

6. Compare all the shifts (either to left or right) of the first vector with the second vector (to check for matches). If it matches — the answer is YES and NO otherwise.

Howdy! I have an idea for a problem.

Cody studies in a special school. Teachers there value children's work with integer marks from 1 to 10. Soon the teachers will start to calculate the final mark. Cody is a principled boy, so he wants his final mark to be equal to M. He already looked in the mark-book and he knows that he has N marks and their values. Cody doesn't want to work much so he wants to get as few marks, as possible. Help Cody by telling him how many marks should he recieve and list the exact values.

The final mark is calculated this way: the teacher sums all the marks and divides them with the number of marks. Ex: The final mark of : 1 2 3 4 5 will be 3.

Input: First line contains numbers N and M, the number of marks already in the list and the final mark he wants. The second line containts N integer numbers — the marks in the list.

Output: First line must contain the number X of integer marks he should work at and on the second line you must list them. If the solution doesn't exist — print -1.

Test 1. Input

 5 5
 1 5 9 7 2

Output

 1
 6

Test 2. Input

 3 8
 1 2 3

Output

 9
 10 10 10 10 10 10 10 10 10

Suggest your ideas of solving and, the most important, suggest the maximum value of N, for the solution to be within 1 and 3 seconds. Almost sure in the test examples, but if you see a mistake — feel free to write about it in the comments. In my opinion, this problem with relatively small N's could be in a Div.2 contest as A or B problem.

Hello.

Suppose we have a undirected graph V. We certainly know that any vertex u can be reached from any vertex v.

If we delete vertex K and it's edges and, therefore, any vertex u losses connection with any vertex v, then K is considered to be important.

So we need to find the number of this important vertexes.

First that comes to mind is DFS, but I think there are other faster ways to solve this problem.