How should I approach the following problem?I thought of finding the shortest distance by projecting the cube in 2D but I am getting nowhere.

A solid cube of 10 cm x 10cm x 10 cm rests on the ground. It has a beetle on it, and some sweet honey spots at various locations on the surface of the cube. The beetle starts at a point on the surface of the cube and goes to the honey spots in order along the surface of the cube.

If it goes from a point to another point on the same face (say X to Y), it goes in an arc of a circle that subtends an angle of 60 degrees at the center of the circle If it goes from one point to another on a different face, it goes by the shortest path on the surface of the cube, except that it never travels along the bottom of the cube The beetle is a student of cartesian geometry and knows the coordinates (x, y, z) of all the points it needs to go to. The origin of coordinates it uses is one corner of the cube on the ground, and the z-axis points up. Hence, the bottom surface (on which it does not crawl) is z=0, and the top surface is z=10. The beetle keeps track of all the distances traveled, and rounds the distance traveled to two decimal places once it reaches the next spot so that the final distance is a sum of the rounded distances from spot to spot.

Input Format: The first line gives an integer N, the total number of points (including the starting point) the beetle visits

The second line is a set of 3N comma separated non-negative numbers, with up to two decimal places each. These are to be interpreted in groups of three as the x, y, z coordinates of the points the beetle needs to visit in the given order.

Output Format: One line with a number giving the total distance traveled by the beetle accurate to two decimal places. Even if the distance traveled is an integer, the output should have two decimal places.

Constraints: None of the points the beetle visits is on the bottom face (z=0) or on any of the edges of the cube (the lines where two faces meet)

2<=N<=10

Sample Input-Output:

Input 3 1,1,10,2,1,10,0,5,9 Output 6.05 Input 3 1,1,10,2,1,10,0,1,9 Output 4.05

Should this problem be solved with union or something simpler ? Please give some ideas.

There are N rectangular boxes(Bi) and each has a special value(Power) Pi. These rectangular boxes are placed in the first quadrants of the x-y plane.

These boxes are represented by two coordinates,bottom-left and top-right.

Example:

Below rectangle(highlighted with yellow) is represented as (1,1) i.e. bottom-left and (3,6) i.e. top-right

If two boxes(B1 & B2 with special value P1 & P2 respectively) overlap each other, then the special value of the common area is P1+P2.

Find the total area with maximum Power.

Constraints 1<=N<=10^5

0<=x,y <= 10^4 i.e.the lowest co-ordinate of bottom-left corner is (0,0) and the highest coordinate of top-right corner is (10000,10000)

1<=P<=100

Input Format The first line contains the number of boxes N

In next N lines, each line contains five integers where

The first two integers represent the (x, y) coordinates of bottom-left corner

Next two integers represent the (x, y) coordinates of top-right corner respectively

The last integer represents the special value or power, P

Output Total area with maximum power

Test Case

Explanation Example 1

2

1 1 3 6 5

2 2 4 4 8

Sample output #1

2

Explanation #1

The area highlighted with red has the highest value of P and its area is 2

Example 2

5

21 46 38 56 13

26 28 47 38 8

18 32 38 38 5

31 35 42 51 8

39 31 45 38 5

output

65

Explanation #1

Total Area with P=21 is 65.

Can anybody provide me any hint on how to solve this problem? The problem is as follows.

The contest in which it was asked is over.

Mr. X is teaching number theory in his class. He is discussing about factors and permutations in his class. A factor of a positive integer N is a positive integer that divides n precisely (without leaving a remainder). The set of factors always includes 1 and N.

Mr. X likes combinatorics a lot. He asked his students find out all the factors of the number Y, and sort them in an ascending order. He asks them to list all permutations of the factors. They then need to cross out all permutations where two adjacent numbers are adjacent in the same order in the original list. The number of uncrossed (valid) permutations are to be given to him.

Illustration:

Integer 9 has 3 factors [1,3,9].

The permutations of these factors of number 9 are [1,3,9],[1,9,3],[3,9,1],[3,1,9],[9,1,3],[9,3,1].

Of these 6 permutations, we need to cross out [1,3,9] (1 3 adjacent in same order), [3,9,1] (3 9 in same order) and[9,1,3] (1 3 in same order)

The remaining (valid) permutations are:

[1,9,3] ,[9,3,1],[3,1,9]

Hence the number of valid permutations =3, which is the answer.

Constraints 1<= N<=120000

1<=T <= 100

Input Format The first line contains T, the number of testcases

Next T lines contain the integer N

Output T lines containing number of valid permutations satisfying conditions mentioned in the problem statement for given input.

Test Case

Explanation Example 1

Input

1

10

Output

11

Explanation

T=1 (there is 1 test case)

N=10.

10 has 4 factors [1,2,5,10]. There are 24 permutations of these four factors. The 11 valid permutations are [1,5,2,10],[1,10,5,2], [2,1,10,5],[2,10,1,5], [2,10,5,1], [5,1,10,2], [5,2,1,10], [5,2,10,1], [10,1,5,2], [10,2,1,5], [10,5,2,1]. Hence the output is 11

Example 2

Input

2

6

9

Output

11

3

Explanation

T=2 (there are 2 test cases).

In the first test case, N=6. 6 has four factors [1,2,3,6]. As in the previous example, there are 11 valid permutations for these. Hence the output for the first test case is 11. This is the first line of the output

In the second test case, N=9. As was shown in the Illustration in the problem statement, thenumber of valid permutations is 3. Hence the output for the second test case (the second line of the output) is 3.