Google Code Jam Round 1A Numbers

This problem simply asks about the three digits before decimal points for .
can be very large.

The idea is very simple. Since the required number is in surd form, its power is also in surd form, namely . Consider it's conjucate , it is not difficult to verify that it's power is also in surd form, namely . Note that and since , that means the sum should be nearly itself. The final answer is just to consider the round off by 1, and giving the answer by considering is enough.

Remember can be calculated by:

Google Code Jam Qualification Round Problem C

Problem C: Fly Swatter

To summarize, the problem asks about the probability that a circle have intersection with the racquet as described in the page.

Please read the problem statement before reading the solution.

To deal with this question, first of all we can observe the following fact:

1. As the racquet is a circle, we know that the required probability in every quadrant is the same. Therefore we need to find out the probability in one single quadrant , and the result is given by
2. Revision of probability . How do we quantify for the "Number"? Of course in terms of area. But calculating the total area that the circle intersects the racquet is nearly impossible. Thanks god, we know the existence of complementary law in probability, therefore we can think in this way:.
3. Note that is to find the area that the circle does not intersect the racquet. Considering the structure of the racquet... You've got it. We can concerning the area of free space that a circle would stay in without intersecting the racquet.
4. The free space can be described by discrete polygons. They must be convex.
5. For a complete square inside the racquet, the possible covering area is given by if is non-negative.

At this point, the question remain is: How to calculate the area if the square is not complete? Basically we can reach the idea from the what we achieved for complete square. In complete square case, we find out the extreme positions such that circle cannot move further from either x or y directions i.e. the four corners. Using that idea, we are going to locate all the extreme positions of the circles in a general polygon. Suppose we are doing this in the first quadrant, if we know that there exists free space for the circle inside that polygon, we can always place it in the lower left corner of it, which is always a right angle. We then treat that polygon as a square, and do binary search to locate the next placible point for that circle. Note that we can find at most 4 distinct extra places. The next step is to calculate the placible area given these extreme points. One may think of convex hull polygon area of those vertices but it is certainly wrong. Note that the polygon bounding the free space can have curved sides. The task is more difficult: how to know the curved area? Well, the answer is simple: given that the curved side is always following the track of the inner rim of the racquet, the curve is always units from the inner rim. It concludes that the curve is from a perfect circle, and concentric with the racquet. Therefore the area is given by the total convex hull area and chord area. If you forget the way to calculate the chord area, let me remind you that for the circle centred at with radius , the chord area between the two vectors and which point at the side of the circle is given by . The last thing to do is summing up all the free spaces in that quadrant, and divide it by quarter of the total racquet area. The final result is the probability complement of it.

The diagram below illustrates the idea of the algorithm, note that the red arrow indicates the order of binary searching the extreme points.