Hi all!
On September 13, a qualification contest for ACM ICPC was held in Samara SAU. We always put our contests to Codeforces Gyms, so this Saturday, November 14, 11.00 MSK everyone will be able to enjoy it.
The contest will be held at Codeforces Gyms, it will be unrated and will last for 5 hours. The problems were prepared by craus and Shlakoblock.
And here is the full list of our previous contests:
- 2012, V Samara Regional Intercollegiate Programming Contest
- 2012, Samara SAU ACM ICPC Quarterfinal Qualification Contest
- 2013, VI Samara Regional Intercollegiate Programming Contest
- 2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest
- 2014, VII Samara Regional Intercollegiate Programming Contest
- 2014, Samara SAU ACM ICPC Quarterfinal Qualification Contest
- 2015, VIII Samara Regional Intercollegiate Programming Contest
ummmm..... gym contest :D
tnx dalex :D
Reminder: the contest starts in 10 minutes.
your dress color still blue-black )
Are you dalek? :v
you write solutions on C++ it regularly happens than input reading through std::cin appears to be slow because of the large input size. Certainly is more correct in such cases to write data reading more effectively — at least using scanf. But if the testing system uses GNU C++ (checked on MinGW 4.4.1, but I think it works on other versions too), and you don't want to rewrite input reading, it is possible to improve performance by only one line placed in the beginning of the program: ios_base::sync_with_stdio(0).
On my example where it was required to find the sum of one million integers, it has accelerated the program in 4.5 times. Tried to do the same test on MS Visual C ++ 9.0 — but it hasn't accelerated the reading.
How to solve A and H?
In H, my team were thinking of drawing all lines connecting points P1, P2 and origin. Then, the original circle is divided into 6 arcs and then applying ternary search on each arc about where the new circle should touch the arc. For evaluating maximum radius if new circle is touching at certain point on the arc, we can apply binary search on the radius of new circle.
H: Show that the largest circle always touches the boundary of the garden. Binary search the radius. Now for a fixed radius
rwe know that the answer lies on the circumference of the circle with center (0, 0) and radiusR - r, whereRis the radius of the garden.So we are only interested in the polar angle of the answer. Notice that if this angle is
atan2(y1, x1) + PI, we get the most distant point from (x1, y1) we can get. Find suchdeltathat angles fromatan2(y1, x1) + PI - deltatoatan2(y1, x1) + PI + deltaare distant enough from (x1, y1), and the rest of the angles are not. You can do it with another binary search or with acos, but don't forget that sometimes the whole circle is good anddelta = PI, and sometimes evenatan2(y1, x1) + PIis not good enough.Now we have two ranges of angles. Those that are good for (x1, y1) and those that are good for (x2, y2). If the ranges have at least one common angle, this radius is good, else it isn't.
A: For each guy, calculate how much he owes minus how much he is owed. For some guys the number will be positive, for some guys negative. The sum is, of course, zero. Greedily connect the positive guys with the negative ones.
I finally upsolved H, and it turned out to be very easy. Solution above is written on drugs, so this is the normal solution.
I denote input radius as R, input points as A and B, and the answer's center as O.
I will also post data you can paste to https://csacademy.com/app/geometry_widget/.
There are two cases:
1) The resulting circle touches one point A. If this is really the answer, the direction of the vector AO is the same as the direction from A to (0, 0). So the answer's diameter has length R + distance((0, 0), A), divide it by two and get the answer.
2) The resulting circle touches both points. Then the answer's center O lies on the ray which is emitted from the AB's center and is perpendicular to AB. Try both directions of this ray and use binary search how far O should be moved from AB. In binary search, you find the candidate center C, its radius is CA (or CB), and check if this circle intersects the input circle.
I'm surprised many high rated people couldn't solve it. People should learn that "geometry" doesn't mean "hard".
How to G?
In Rev. 1
thx :)
how To solve problem K?
In Rev. 1
what's rev1 ?
push on arrow near voting)
How to solve C?
How to solve problem B? Thanks you :D
Use map to keep how many times each pattern appears.
Make sure you ignore the judge who includes more than 15 or less than 8 tasks
How to solve J and L ?
How can I solve problem C, please?
how to solve A?
How to slove B and L ?
The problem L can be solved using extended euclidean. You will divide it into 3 cases.
$$$n*x = m*y$$$ -> answer is $$$LCM(n, m)$$$
$$$n*x + 1 = m*y$$$ -> solve: $$$m*y - n*x = 1$$$
$$$n*x = m*y + 1$$$ -> solve: $$$n*x - m*y = 1$$$
You need to treat individually when $$$n = 1$$$ or $$$m = 1$$$.
Problem L solution