681.md (5486B)
1 Source: https://codeforces.com/blog/entry/45425 2 3 [681A - A Good Contest](/contest/681/problem/A "Codeforces Round 357 (Div. 2)") 4 5 If for any participant *before**i* ≥ 2400 and *after**i* > *before**i*, then the answer is "YES", otherwise "NO" 6 7 [Code](https://ideone.com/kzMYfl) 8 9 [681B - Economy Game](/contest/681/problem/B "Codeforces Round 357 (Div. 2)") 10 11 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". 12 13 If there is no such *a* and *b*, then the answer is "NO". 14 15 [Code](https://ideone.com/zbPSkF) 16 17 [681C - Heap Operations](/contest/681/problem/C "Codeforces Round 357 (Div. 2)") 18 19 Let's solve this problem with greedy approach. Let's apply operations from log in given order. 20 21 If current operation is *insert* *x*, then add element *x* to heap. 22 23 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* 24 25 If current operation is *getMin* *x* then do follows: 26 27 1. While heap is not empty and its minimal element is less than *x*, apply operation *removeMin*. 28 2. Now if heap is empty or its minimal element is not equal to *x*, apply operation *insert* *x*. 29 3. Apply operation *getMin* *x*. 30 31 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`. 32 33 [Code](https://ideone.com/1iyHy8) 34 35 [681D - Gifts by the List](/contest/681/problem/D "Codeforces Round 357 (Div. 2)") 36 37 Formal statement of the problem: 38 39 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. 40 41 Every vertex *i* has a pair – vertex *a**i*, *a**i* – ancestor of *i*. 42 43 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 *a**i*. 44 45 Or you need to tell, that such sequence does not exists. 46 47 Solution: 48 49 Assume sequence *ans*, which contains every vertex from sequence *a**n* by once and only them. Let's order elements of this sequence in such way, that for every *i* and *j* if *ans**i* – ancestor of *ans**j*, then *i* ≥ *j*. 50 51 If this sequecne is the answer, then print it. Otherwise, there is no answer. 52 53 Why? 54 55 1. If some vertex *a**i* from sequence *a* in not present in *ans*, then a man, who needs to give a gift to a man number *a**i*, will not be able to do it. So every vertex *a**i* must have place in the resulting sequence. 56 2. If *a**i* – ancestor of *a**j* and *i* < *j*, then a man, who needs to give a gift to a man number *a**j* will not be able to do it. 57 58 How can we build this sequence? 59 60 Let's sort vertices topologically, than reverse it and remove redundant vertices. 61 62 Now we need to check if that this sequence can be the answer. 63 64 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. 65 66 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. 67 68 Iterate through that vertices (men) in dfs order and remember for them, to whom they will give their gift. 69 70 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. 71 72 [Code](https://ideone.com/Nwydx2) 73 74 [681E - Runaway to a Shadow](/contest/681/problem/E "Codeforces Round 357 (Div. 2)") 75 76 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. 77 78 Otherwise the cockroach will have time to run to every point inside the circle with center of *x*0, *y*0 and radius *v* × *t*. 79 80 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. 81 82 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. 83 84 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. 85 86 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. 87 88 [Code](https://ideone.com/knTyd5)