If for any participant beforei ≥ 2400 and afteri > beforei, then the answer is "YES", otherwise "NO"
We can simply try every a from 0 to n / 1234567 and b from 0 до n / 123456, and if n - a * 1234567 - b * 123456 is non-negative and divided by 1234, then the answer is "YES".
If there is no such a and b, then the answer is "NO".
Let's solve this problem with greedy approach. Let's apply operations from log in given order.
If current operation is insert x, then add element x to heap.
If current operation is removeMin, then if heap is not empty, then simply remove minimal element, otherwise if heap is empty, add operation insert x, where x can be any number, and then apply removeMin
If current operation is getMin x then do follows:
- While heap is not empty and its minimal element is less than x, apply operation removeMin.
- Now if heap is empty or its minimal element is not equal to x, apply operation insert x.
- Apply operation getMin x.
In order to fit time limit, you need to use data structure, which allows you to apply given operations in O(logN) time, where N is a number of elements in it. For example, std::priority_queue or std::multiset.
Formal statement of the problem:
You have a directed acyclic graph, every vertex has at most one ingoing edge. Vertex A is an ancestor of vertex B if there is a path from A to B in graph. Also every vertex is an ancestor of itself.
Every vertex i has a pair – vertex ai, ai – ancestor of i.
You need to build such sequence of vertex, that for every vertex i the leftmost vertex in the sequence which is ancestor of i must be equal to ai.
Or you need to tell, that such sequence does not exists.
Solution:
Assume sequence ans, which contains every vertex from sequence an by once and only them. Let's order elements of this sequence in such way, that for every i and j if ansi – ancestor of ansj, then i ≥ j.
If this sequecne is the answer, then print it. Otherwise, there is no answer.
Why?
If some vertex ai from sequence a in not present in ans, then a man, who needs to give a gift to a man number ai, will not be able to do it. So every vertex ai must have place in the resulting sequence.
If ai – ancestor of aj and i < j, then a man, who needs to give a gift to a man number aj will not be able to do it.
How can we build this sequence?
Let's sort vertices topologically, than reverse it and remove redundant vertices.
Now we need to check if that this sequence can be the answer.
Let's calculate to whom every man will give his gift. At start for any man we don't know that. Let's iterate through vertices of the resulting sequence.
For every vertex (man) from current vertex subtree (i.e. for vertices whose ancestor is current vertex) such that we still don't know whom will this vertex (man) give a gift to, stays that these vertices would give a gift to current vertex, because it is their first ancestor in the list.
Iterate through that vertices (men) in dfs order and remember for them, to whom they will give their gift.
After we apply this operation to all vertices from resulting sequence, compare for each man to whom he will give his gift and to whom he needs to give his gift. If there is at least one mismatch, then the answer doesn't exist.
At first assume the case when cockroach at the moment 0 is already inside or on the border of some circle. In that case the cockroach will always survive, i. e. the probability is 1.
Otherwise the cockroach will have time to run to every point inside the circle with center of x0, y0 and radius v × t.
Let's iterate through all the shadow circles and figure out how each circle relates to "cockroach circle". We want to find the maximum angle, such that choosing the direction from this angle the cockroach will have enough time to reach current circle and survive.
In general, maximal "surviving" angle, such that choosing the direction from it the cockroach will reach the circle in infinite time – is an angle between two tangents from a start point to the circle. If length of this tangents is not greater than v × t, then this angle is the needed one.
Otherwise we need to find intersections of cockroach circle and current circle. If there is no intersection points or there is only one, then current circle is too far away from cockroach. Otherwise intersection points and start point form the needed angle for this circle.
After we've found all the angles, we can figure out that those angles are segments that cover a segment from 0 to 2π. Sort their ends and find a length of their union. This length divided by 2π will give us the answer.
