|
|
Common BoardPage 1195 13 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ans: 31.513956103964 binsearch + dijkstra works but with naive dijkstra Edited by author 26.05.2024 06:13 These are some of the things I had to overcome: 1)Testing on something like: 6 5 5 1 1 2 2 and 6 5 5 1 1 1 2 2)There cant be 2 out of place pairs in the ascending/descending order 3)Swapping elements across all pairs Hope this helps someone. #include <iostream> #include <iomanip> #include <cmath> using namespace std; int main() { int x1, y1, x2, y2, x0, y0, l; cin >> x1 >> y1 >> x2 >> y2; cin >> x0 >> y0 >> l; cout << fixed << setprecision(2); // <|ENG: Set 2 symbols after dot |> <|RUS: stavim 2 simvola dlia tochki |> //<|ENG: get all sides |> //<|RUS: poluchaem vse storonui |> double firstEdge = sqrt(pow(x1 - x0, 2) + pow(y1 - y0, 2)); double secondEdge = sqrt(pow(x2 - x0, 2) + pow(y2 - y0, 2)); double field = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)); double ans2 = max(firstEdge, secondEdge) - l; // <|ENG: Second answer - max length |> <|RUS: Vtoroi otvet = prosto maximum do krainih tochek |> double ans1; //<|ENG: get the squares of the sides|> //<|RUS: Vosvodim v kvadrat storonui |> double a = firstEdge * firstEdge; double b = secondEdge * secondEdge; double c = field * field; //<|ENG: checking if there are obtuse angles on the side that is the pineapple field |> //<|RUS: Proverka est li typie ygli vosle toi storoni kotoraiy iavliaetsia polem c ananasami |> if (a+c < b || b+c < a) { ans1 = min(firstEdge, secondEdge) - l; } else { //<|ENG: get half the perimeter of triangle|> //<|RUS: poluchaem poly perimetr treygolnika |> double p = (firstEdge + secondEdge + field) / 2; //<|ENG: get square of triangle|> //<|RUS: poluchaem ploshad treygolnika |> double S = sqrt(p * (p - firstEdge) * (p - secondEdge) * (p - field)); //<|ENG: If the area is zero and the field with pineapples does not exist (test: 2 2 2 2 3 3 1)|> //<|RUS: Esli ploshad ravna 0 i polia c ananasami kak bu net (test: 2 2 2 2 3 3 1)|> if (S == 0 && field == 0) { ans1 = min(firstEdge, secondEdge) - l; } //<|ENG: If the area is zero and more than one side is not zero (test: -5 0 5 0 1 0 1)|> //<|RUS: Esli ploshad ravna 0 i ni odna storona ne ravna 0 (test: -5 0 5 0 1 0 1)|> else if (S == 0 && firstEdge != 0 && secondEdge != 0 && field != 0) { ans1 = 0; } else { //<|ENG: Default. We just look for the height using the formula|> //<|RUS: Obichni slychai. Prosto po formule S = a*h/2 (test: -5 0 5 0 1 0 1)|> double d = 2 * S / field; ans1 = d - l; } } //<|ENG: If, after subtracting the rope, the length becomes negative, then do 0|> //<|RUS: Esli sle vichetania verevki otvet stal menihe nylia to delayem 0|> ans1 = ans1 < 0 ? 0 : ans1; ans2 = ans2 < 0 ? 0 : ans2; //<|ENG: Next just cout "round(ans1 * 100) / 100" and "round(ans2 * 100) / 100"|> //<|RUS: Teper prosto vivedi "round(ans1 * 100) / 100" i "round(ans2 * 100) / 100"|> //!!!!!!!!!!!!!!!!!!! //cout << round(ans1 * 100) / 100 << endl; //cout << round(ans2 * 100) / 100; return 0; //<|ENG: Thanks a lot for your time here!|> //<|RUS: Spasibo chto pochitali i uia vam pomog (navernoe)|> // :) } Admins, please increase Memory Limit in this task. It is wrong that solutions with O(Q*log2(10^9)) memory - segment tree on hash table - has not got any chance to pass Memory Limit without additional input queries coordinates compression (because 100000 * 30 * (3*double + char) is obviously > 64 Mb). This data structure is quite complex even without input queries coordinates compression, why not to AC such solutions? Nowadays commonly used ML is 256 Mb, not 64. Edited by author 19.05.2024 12:37 Edited by author 19.05.2024 12:39 There is only one eligible lowered numbered ball at any round. Keeping track of this should result in O(n) solution Write down the sequence, on paper, by hand. Now, right down the index of each digit on the sequence. Do you know prefix sums and binary search? It's kinda useful for many problems btw... Edited by author 15.05.2024 05:54 I solved 1009 and 1012. Now im using new algorithm (log(n)) and program works fast and correct with my tests. Can you give more tests? I solved 1013, my mistake was multiplication of large numbers, i use long arithmetic for multiplication and uint64 for variables and get Accept Page 1194 if the cube is at e2, neighbors are: e1 (near), e3 (far), d2 (left) and f2 (right) for your convenience 24 orientations of cube: 1 2 3 4 5 6 1 2 4 5 6 3 1 2 5 6 3 4 1 2 6 3 4 5 2 1 3 6 5 4 2 1 4 3 6 5 2 1 5 4 3 6 2 1 6 5 4 3 3 5 1 6 2 4 3 5 2 4 1 6 3 5 4 1 6 2 3 5 6 2 4 1 4 6 1 3 2 5 4 6 2 5 1 3 4 6 3 2 5 1 4 6 5 1 3 2 5 3 1 4 2 6 5 3 2 6 1 4 5 3 4 2 6 1 5 3 6 1 4 2 6 4 1 5 2 3 6 4 2 3 1 5 6 4 3 1 5 2 6 4 5 2 3 1 test: 4 1 4 2 3 6 5 1 4 3 6 5 2 1 4 5 2 3 6 1 4 6 5 2 3 ans: 1 1 2 3 4 It would be interesting to solve such a problem on an arbitrary graph (not a tree) or to say that there is no solution for such a graph. it is well known problem. but its hard to implement. You should find a clique of size 5 or complete bipartite subgraph with size (3, 3). There is no solution if and only if there exist such subgraph or topologicaly equal to that(other vertex can adjust 2 dif. vertexes of such subgraph). I took lectures about that a long time ago. Can't find source now. Edited by author 26.05.2024 21:22 For WA12 try this: 9126492316491641269352615215701236589213658621356281376589216562319562396592381659862195621281E-190 100 # Output must be: 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009126 What is test #2? Try this: .234 2 .2 2 # Answers: 0.23 0.20 |
|
|