| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 4000 | Airplane Parking |
|
| 4001 | Incircles Again |
|
| 4002 | Rating Hazard |
|
| 4003 | Your Ways |
|
| 4004 | Hexagonal Sticks |
|
Description
During this economic crisis time, Jack has started an incredible new business related to air travel, a parking-lot for airplane. He bought a very large land to park airplanes. However the land is very narrow, so that the only way airplanes can go in or go out of the parking lot must be in the Last-In First-Out fashion (see picture below). He only has spaces in the parking lot so he cannot take some airplane at the end out so that other airplanes can move.
In this case, it is possible to accommodate airplane 1, 2, and 4. But it is not possible to accommodate both airplanes 2 and 3.
It is possible that different planes plan to arrive or depart the parking lot at the same time. Jack has the best crews working with him, so that they will manage to arrange the plane to the parking lot in the best way that if it is possible to park and take out the planes they will be able to do it. Consider another example.
Although airplane 5 and 6 arrive at the same time, Jack's crews know that airplane 5 will have to be out before airplane 6, so when both airplanes arrive they put airplane 6 in first, following by airplane 5.
Given a list of parking requests, you want to find the maximum number of airplanes that can be parked in this parking lot, provided that they can only depart in the Last-In First-Out fashion.
Input
The first line contains an integer T, the number of test cases (1 < T < 5). Each test case is in the following format.
The first line starts with an integer N (1 < N < 300) denoting the number of airplanes. The next N lines describe the request table. Each line 1 + i, for 1 < i < N, contains two integer Si and Ti , (0 < Si < Ti < 1,000,000,000) which are the planned arrival time and planned departing time for airplane i.
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the figure below you can see triangle ABC and its incircle (Circle that touches all the sides of a triangle internally). The radius of this in circle is r. Three other circles are drawn. Each of them touches two sides of this triangle and the in circle of ABC. The radiuses of these circles are r1, r2 and r3.
Given the values of r, r1, r2 and r3 you will have to find the area of triangle ABC.
Input
The input file can contain up to 1000 lines of inputs. Each line contains four positive floating point numbers which denotes the values of r, r1, r2 and r3 respectively.
Input is terminated by a line containing four negative integers.
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A very important aspect of web portals is customer reviews. The customers can rate any product in the web portal. Generally, a customer can rate a product from one star to five star. Based on the rating of all the customers the average customer rating for a product is shown. Look at the figure on the left to get a clear idea. For example if three customers rate a product as 3 star, 4 star and 4 star respectively then the average rating will be (3+4+4)/3 = 3.67 (Rounded to two digits after the decimal point). In the figure on the left 847 customers have rated a product and 597, 189, 26, 11 and 24 customers have rated the product as 5 star, 4 star, 3 star, 2 star and 1 star respectively. So the average rating is: (597x5+189x4+11x2+24)/847=456316411(Rounded to eight digits after the decimal point).
Input
The input file can contain up to 2000 lines of inputs. Each line contains a nonnegative floating point number v (1 ≤ v ≤ 5). This number will have minimum one digit and maximum eight digits after the decimal point. If this number has n digits after the decimal point then you have to assume that the value of the average is given rounded to n digits after the decimal point.
Input is terminated by a line containing a negative number.
Output
For each line of input produce one line of output. This line contains the serial of output followed by an integer T which denotes the minimum number of voter that is required for this average rating.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You live in a small well-planned rectangular town in Phuket. The size of the central area of the town is H kilometers x W kilometers. The central area is divided into HW unit blocks, each of size 1 x 1 km2. There are H + 1 streets going in the West to East direction, and there are W + 1 avenue going in the North-South direction. The central area can be seen as a rectangle on the plane, as shown below.
We can identify each intersection by its co-ordinate on the plane. For example, on the Figure above the bottom-left corner is intersection (0,0), and the top-right corner is intersection (6,3).
Your house is at the bottom-left corner (i.e., intersection (0,0)) and you want to go to the university at the top-right corner (i.e., intersection (W,H)). More over, you only want to go to the university with wasting any efforts; therefore, you only want to walk from West-to-East and South-to-North directions. Walking this way, in the example above there are 84 ways to reach the university.
You want to go to the university for K days. Things get more complicated when each morning, the city blocks parts of streets and avenues to do some cleaning. The blocking is done in such a way that it is not possible to reach parts of the streets or avenues which is blocked from some other part which is blocked as well through any paths containing only West-to-East and South-to-North walks.
You still want to go to the university using the same West-to-East and South-to-North strategy. You want to find out for each day, how many ways you can reach the university by only walking West-to-East and South-to-North. Since the number can be very big, we only want the result modulo 2552.
Input
The first line contains an integer T, the number of test cases (1 < T < 5). Each test case is in the following format.
The first line of each test case contains 3 integers: W, H, and K (1 < W < 1,000; 1 < H < 1,000; 1 < K < 10,000). W and H specify the size of the central area. K denotes the number of days you want to go to the university.
The next K lines describe the information on broken parts of streets and avenues. More specifically, line 1 + i, for 1 < i < K, starts with an integer Qi (1 < Qi < 100) denoting the number of parts which are blocked. Then Qi sets of 4 integers describing the blocked parts follow. Each part is described with 4 integers, A, B, C, and D (0 < A < C < W; 0 < B < D < H) meaning that the parts connecting intersection (A,B) and (C,D) is blocked. It is guaranteed that that part is a valid part of the streets or avenues, also C - A < 1, and D - B < 1, i.e., the part is 1 km long.
Output
For each test case, for each day, your program must output the number of ways to go to the university modulo 2552 on a separate line. i.e., the output for each test case must contains K lines.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In this problem, we will consider an infinite hexagonal grid. The grid consists of equal regular hexagonal cells arranged in the fashion shown below. The figure also elucidates the coordinate system used to identify each cell. Each cell of the grid can be empty or blocked.
There are few sticks placed randomly on this grid. The length of each stick is one ‘hexagonal unit’. This means, the end points of a stick lies on the centers of neighboring cells. Your job is to move the sticks so that a closed regular hexagonal figure is formed.
The diagrams below show some closed hexagonal figures made of sticks.
You will be given the initial coordinates of the sticks that are placed on the grid. You will also be given the coordinates of the cells that are blocked. In each move you can do one of the followings:
- Select one stick and throw it out
- Select one stick and rotate it 60 degrees clockwise/anti-clockwise about one of the end points
- Select one stick and push it along the length of the stick
The sticks can never occupy a cell that is blocked. However, two sticks can occupy the same cells at the same time.
Consider the scenario shown above. We have an obstacle situated at coordinate (1, 1) and a stick at coordinate (0, 0) > (1, 0). The four possible moves that can be made are depicted below
After all the moves are made, you have to ensure a closed regular hexagonal shape is formed with no other sticks lying around. This means the grid should contain exactly 6*x sticks where x is positive integer. Can you do this in minimum number of moves?
Input
The first line of input is an integer T(T<50) that indicates the number of test cases. Each case starts with a nonnegative integer S(S<9) that gives you the number of sticks available.
The next S lines give you the coordinates of the sticks. The coordinates of the sticks will be of the format x1 y1 x2 y2, which means there is a stick from (x1, y1) to (x2, y2). The coordinates will be valid and the length of each stick will be one hexagonal unit as mentioned above.
The next line will give you a nonnegative integer B(B<20) that indicates the number of obstacles.
Each of the next B lines will give you the coordinates of the obstacles. The coordinate will be of the format x1 y1. It is guaranteed that the given blocks will not overlap with any given sticks.
All the coordinates (sticks and blocks) will have values in the range [4, 4].
Note: Remember that we are dealing with infinite grids. So in the optimal result, it could be possible that the hexagonal sticks lie outside [4, 4].
Output
For each case, output the case number first followed by the minimum number of moves required. If it is impossible to form a hexagonal grid, output “impossible” instead. Adhere to the sample input/output for exact format.