TCS CodeVita Season 9, 2020

Elections

Problem Description

Elections are going on, and there are two candidates A and B, contesting with each other. There is a queue of voters and in this queue some of them are supporters of A and some of them are supporters of B. Many of them are neutral. The fate of the election will be decided on which side the neutral voters vote. Supporters of A and supporters of B make attempt to win the votes of neutral voters.

The way this can be done is explained below:

1. The voter queue is denoted by three characters, viz {-, A, B}. The – denotes neutral candidate, A denotes supporter of candidate A and B denotes supporter of candidate B.

2. Supporters of A can only move towards the left side of the queue.

3. Supporters of B can only move towards the right side of the queue.

4. Since time is critical, supporters of both A and B will move simultaneously.

5. They both will try and influence the neutral voters by moving in their direction in the queue. If supporter of A reaches the neutral voter before supporter of B reaches him, then that neutral voter will become a supporter of candidate A.

6. Similarly, if supporter of B reaches the neutral voter before supporter of A reaches him, then that neutral voter will become a supporter of candidate B.

7. Finally, if both reach at the same time, the voter will remain neutral. A neutral vote cannot decide the outcome of the election.

8. If finally, the queue has more votes for candidate A, then A wins the election. If B has more votes, then B wins that election. If both have equal votes, then it will be a coalition government.

Refer Examples section for understanding the dynamics of how the supporters influence the neutral voters.

Your task is to find the outcome of the election.

Note: There are no test cases where all votes are neutral.

Constraints

1 <= length of queue <= 10 ^ 5

Input

First line contains an integer which is length of queue of voters.

Second line contains characters {-, A, B}, in which denotes

· A = voter who is supporter of candidate A

· B = voter who is supporter of candidate B

· – = neutral voter

Output

Print candidate with maximum number of votes. If they have equal number of votes, print “Coalition government“.

Time Limit

1

Examples

Example 1

Input

14

–AB–AB—A–

Output

A

Explanation:

For starting positions where there is no opposition from supporter of B, supporter of A can promote in left side of the queue. The voting queue will then look like below:

A A A B – – A B – – – A – –

From 4^th place (in voting queue) B supporter is moving towards the right side, simultaneously 7^th placed A supporter is also moving towards the left side. Then the voting queue will look like below:

A A A B B A A B – – – A – –

From 8^th place B supporter is moving towards the right side, simultaneously 12^th placed A supporter is also moving towards the left side. Then the voting queue will look like below:

A A A B B A A B B – A A – –

Since supporters of both A and B will reach the 10^th voter at the same time, 10^th voter will remain neutral.

Since supporter of A at 12^th place cannot move towards right, last 2 voters will not be influenced and remain neutral. Then the voting queue will look like below:

A A A B B A A B B – A A – –

Since all voter have now cast their votes, election results can now be declared.

So final result is: A A A B B A A B B – A A – –

A has 7 votes, B has 4 votes hence, A wins the election.

Example 2

Input

4

A—

Output

A

Explanation:

Since supporter of A at 1^st place cannot move towards right, last 3 voters will not be influenced and will remain neutral. Then the voting queue will look like below:

A – – –

Since all voter have now cast their votes, election results can now be declared.

So final result is: A – – –

A has 1 vote, B has 0 votes hence, A wins the election.

Example 3

Input

5

A—B

Output

Coalition government

Explanation:

Since supporter of A at 1^st place cannot move towards right, supporter of B at 5^th cannot move towards left, middle 3 voters will not be influenced and will remain neutral. Then the voting queue will look like below:

A – – – B

So final result is: A – – – B

A has 1 vote, B has 1 vote hence, output will be “Coalition government“.

Single Lane Highway

Certain number of cars are passing a single lane road. Speeds of all cars vary. It is easy to see, that depending on the speeds of the cars various groups will be formed.

Problem Description

Certain number of cars are passing a single lane road. Speeds of all cars vary. It is easy to see, that depending on the speeds of the cars various groups will be formed.

Being a single lane road passing/overtaking is not allowed. Given speeds of cars, calculate how many groups can be formed if all possible permutations are taken into account. Refer example1 for better understanding.

Print number of groups divided by the number of permutations.

Constraints

0 <= N < 10 ^ 5

0 <= speed of individual vehicle < 10 ^ 9

Input

First line contains an integer N, which denotes the number of vehicles

Second line contains N space separated integers which denotes the speed of individual vehicle.

Output

Print number of groups divided by the number of permutations rounded upto 6 decimal places.

Time Limit

1

Examples

Example 1

Input

3

10 20 30

Output

1.833333

Explanation:

So all possible permutations are:

{10 20 30}

{10 30 20}

{20} {10 30}

{20 30} {10}

{30} {10 20}

{30 20} {10}

So here there are total 6 permutations, and total number of groups are 11.

So, output is 11/6 = 1.833333

Example 2

Input

4

56 78 13 92

Output

2.083333

Explanation:

So here there are total 24 permutations,

For example:

{56 78 13 92}

{92} {13 78 56}

{56} {13 92 78}

{78 92} {13 56}

.

So on and so forth. The total number of groups are 50.

So, the output is 50/24 = 2.083333

Jogging Ground

There are 4 circular grounds of equal sizes. Their circumferences do not intersect. The radius and the distance of the center of each circle from the leftmost circle’s center are given.

Problem Description

There are 4 circular grounds of equal sizes. Their circumferences do not intersect. The radius and the distance of the center of each circle from the leftmost circle’s center are given.

There are 4 joggers who can start at the same time from any of the points designated as { a, b, c, d } on the circumference of all the four circles as shown in the diagram below. All 4 joggers jog in different grounds along the circumference of that ground. They could jog in either clockwise (left to right) or anticlockwise (right to left) direction. Finally they may also jog at different speeds.

Given starting position, direction of jogging and speed of jogging of all the 4 joggers, find the summation of length of 3 segments between the four joggers at a given point in time since the start of the jog.

Note: All the computation has to be accurate up to 6 digits after the decimal point.

Constraints

1 <= N < 10^9

Input

First line contains 4 integers each denoting the following

• R denotes the radius of all four circles
• D1 denotes the distance centre of the second circle from left to the centre of the leftmost circle
• D2 denotes the distance centre of the third circle from left to the centre of the leftmost circle
• D3 denotes the distance centre of the last circle from left to the centre of the leftmost circle

Second line contains 4 space separated integers denoting the angle with point a of each of the 4 circles where 0 degree indicates point a itself, 90 degree indicates point b, 180 degree indicates point c and 270 degree indicates point d.

Third line contains 4 space separated integers denoting the velocity in degrees per second.

Fourth line contains 4 space separated integers denoting the direction of running for joggers (0=clockwise and 1=anticlockwise).

Fifth Line contains integer N denoting the time in seconds since the start of the jog.

Output

Print the summation of length of 3 segments between the four joggers after N seconds, rounded to the nearest integer.

Time Limit

1

Examples

Example 1

Input

10 25 50 75

0 0 0 0

1 1 1 1

1 1 1 1

90

Output

75

Explanation

Here every jogger is starting from point a and all have speed of 1 degree per second. So they will be at 90 degree after 90 seconds. After connecting these points we get segment lengths as (25 +25 +25) = 75

Example 2

Input

10 25 50 75

0 0 0 0

1 2 3 4

0 0 0 0

90

Output

91

Explanation

Here every jogger is starting from point a. They are jogging at the speed of 1, 2, 3 and 4 degrees per second respectively in clockwise direction. Hence after 90 seconds they will reach points where the segment length between them is (18.027800+36.400500+36.400500) = 90.8288. Hence, output is 91

Largest Gold Ingot

Ramesh is a goldsmith, who brought a large number of gold ingot each of different length(L) but equal breadth(B) and height(H). He wanted to wield the ingots of same length with each other.

Problem Description

Ramesh is a goldsmith, who brought a large number of gold ingot each of different length(L) but equal breadth(B) and height(H). He wants to weld the ingots of same length with each other. He tasks his new employee, Akash, to weld the ingots of same length with each other. But Akash forgot that he had to weld the ingots of same length, instead he welded the ingots in a random manner.

Later Ramesh found out what he had done. He then ordered Akash to cut the welded ingot such that a cuboid with the largest volume from the welded gold ingot is obtained.

Find the volume of summation of gold ingots minus volume of the largest cuboid.

Constraints

0 < G < 10^5

Input

First Line contains one integer G, denoting number of gold ingots

Second line contains two space separated integers B and H, where B denotes the breadth and H denotes the height of individual ingot

Third line contains G space separated integers, denoting the length of the individual gold ingots that are welded together in adjacent manner

Output

An integer corresponding to the volume of summation of gold ingots minus volume of the largest cuboid, mod 10^9+7.

Time Limit

1

Examples

Example 1

Input

7

1 1

6 7 3 4 5 1 3

Output

14

Explanation

Total volume of shaded region is 15 and the total volume is 29. So the volume of summation of gold ingots minus largest cuboid obtained is 14, since the height is 1 and breadth is 1.

Example 2

Input

7

1 2

1 2 6 4 5 3 4

Output

20

Explanation

The volume of summation of gold ingots minus largest cuboid obtained is 20, since the height is 2 and breadth is 1.

Zoo Design

Aman is a rich businessman who want to build a zoo. He wants to make enclosures for terrestrial and aquatic animals. Terrestrial animals will be of two types, namely herbivorous and carnivorous animals.

Problem Description

Aman is a rich businessman who want to build a zoo. He wants to make enclosures for terrestrial and aquatic animals. Terrestrial animals will be of two types, namely herbivorous and carnivorous animals. So there will be three different enclosures.

Herbivores like Elephant, Deer are prime attractions. Similarly, Lion and Tiger are prime attractions amongst carnivores. Finally, Dolphins and Shark are prime attractions amongst aquatics for tourists.

Aman being a savvy businessman realizes that in order to minimize the cost of building the zoo without compromising on the attractions, he has to decide how much area to allocate to each animal type. Each animal type requires a certain area to thrive in. This in turn impacts the area allocation, which in turn has cost implications.

Your task is to help Aman workout the mathematics such that the zoo building cost is minimized subject to the following constraints:

• Zoo needs to have minimum of X herbivores, Y carnivores and Z aquatic animals
• Different types of animals will need different minimum area to thrive in
• For animals of a given type, the minimum area required is the same
• There is also a maximum limit for the overall area allocated for each animal type
• Cost of fencing etc. is included in cost of enclosure
• Exclude the essentials like pathways for tourists, from area and cost calculations

Consider all areas in square meters and cost in Rupees. 

Constraints

0 < number of animals of each type <= 20

0 < max area for each animal type <= 500

0 < total area of land on which zoo is to be built <= 1000

0 < min area required by individual animals <= 15

0 < price of each type of enclosure <= 10000

Area of each type of enclosure should be rounded off to the nearest integer

Input

First line contains three space separated integers denoting the cost per square meter of building the enclosure for each type of animals viz. herbivorous, carnivorous and aquatic respectively

Second line contains three space separated integers denoting the maximum area that can be allocated to each type of animal viz. herbivorous, carnivorous and aquatic respectively

Next three lines, each will contain two space separated integers M and N, for each type of animal viz. herbivorous, carnivorous and aquatic respectively, where M denotes minimum number of animals of that type and N denotes minimum area required for that animal type

Last line contains an integer which represents the total area of land on which the zoo needs to be built

Output

Single integer containing the minimum cost required to build the zoo

Time Limit

1

Examples

Example 1

Input

10000 1000 1500

250 250 300

5 5

15 5

10 10

500

Output

837500

Explanation

·The cost of constructing the enclosure for herbivores is high. However, since we need to accommodate 5 herbivores as per given constraints, a 25 sq. meter land will need to allocated for the herbivores.

·Since the cost of constructing the enclosure for carnivores is cheapest we are able to allocate them the maximum limit that we can allocate. Thus we are allocating 250 sq. meters for carnivores.

·The remaining 225 sq. meters can thus be allocated to aquatics without violating any constraint.

·Thus the minimum cost of constructing the zoo adhering to all constraints is (25 * 10000 + 250 * 1000 + 225 * 1500) = 837500

Example 2

Input

100 1000 1500

250 250 300

5 5

15 5

10 10

500

Output

325000

Explanation

·Since the cost of constructing the enclosure for herbivores is cheapest we are able to allocate them the maximum limit that we can allocate. Thus we are allocating 250 sq. meters for herbivores.

·The cost of constructing the enclosure for aquatics is high. However, since we need to accommodate 10 aquatics as per given constraints, a 100 sq. meter land will need to allocated for the aquatic animals.

·The remaining 150 sq. meters can thus be allocated to carnivores without violating any constraint.

·Thus the minimum cost of constructing the zoo adhering to all constraints is (250 * 100 + 150 * 1000 + 100 * 1500) = 325000

Subnetting

Given blocks of IPV4 CIDR addresses mapped to region name. Find which region does a given IP belongs to.

Problem Description

Given blocks of IPV4 CIDR addresses mapped to region name. Find which region does a given IP belongs to.

CIDR denotes a range of IP addresses. In our problem a region will be assigned a range of CIDRs. All such IP addresses falling in all such CIDR ranges, thus belongs to this given region. Consider an example below.

Example:

Range: 255.1.255.0/23 255.1.255.0/24 India

The CIDR 255.1.255.0/23 can have 512 hosts, and CIDR 255.1.255.0/24 can have 256 hosts. These are the individual ranges denoted by the first and the second CIDRs respectively. Similarly, in between these two ranges of CIDRs there will be other CIDR ranges like

255.1.255.1/23, 255.1.255.2/23 ……………. 255.1.254.253/24, 255.1.254.254/24, 255.1.255.0/24

If the number of hosts in each such CIDR range mentioned above is calculated, then the total number of hosts in this overall range exceeds one billion. Now, your task is to find if the given IP address falls in this range.

Consider IP addresses:    255.1.254.123 and 255.1.250.23

Upon performing CIDR expansion, we realize that address 255.1.254.123 falls in this range and hence belongs to India region. However, address 255.1.250.23 does not fall in this region and hence does not belong to India region.

Give R IPv4 CIDR ranges, each belonging to a given region and N IP addresses, your task is to find out the region that a given IP address belongs to.

Constraints

1 < = R <= 100
1 <= N <= 5*10 ^ 4

Input

First line contains 2 space separated integers R and N, where R denotes number of IPv4 CIDR ranges and N denotes number of IP addresses
Next R lines contains two CIDR ranges (from range and to range) and region name. All three inputs are space separated
Next N lines, each contain a single IPV4 address

Output

For each IPV4 address, print the respective region name it belongs to. If it belongs to no region, then print “None” as output.

Time Limit

2

Examples

Example 1

Input

1 3
201.100.255.0/20 207.105.25.0/24 Bangladesh
202.251.245.56
202.255.245.230
207.106.245.230

Output

Bangladesh
Bangladesh
None

Explanation

Given R = 1, N = 3

The CIDR 201.100.255.0/20 can have 4096 hosts, and CIDR 207.105.25.0/24 can have 256 hosts. These are the individual ranges denoted by the first and the second CIDRs respectively. Similarly, in between these two ranges of CIDRs there will other CIDR ranges like

201.100.255.1/20, 201.100.255.2/20 ……………. 207.105.24.253/24, 207.105.24.254/24, 207.105.25.0/24

Address 202.251.245.56 and 202.255.245.230 belong to this region. However, 207.106.245.230 does not belongs to this region.

So, output will be:
Bangladesh
Bangladesh
None

Example 2

Input

2 5
7.25.255.0/20 12.175.25.0/24 Taiwan
13.25.255.0/20 19.175.25.0/24 Japan
14.30.2.0
20.30.2.0
13.25.240.0
8.30.2.0
19.175.25.255

Output

Japan
None
Japan
Taiwan
Japan

Explanation

Given R = 2, N = 4

The CIDR 7.25.255.0/20 can have 4096 hosts, and 12.175.25.0/24 can have 256 hosts. These are the individual ranges denoted by the first and the second CIDRs respectively for Taiwan region. Similarly, in between these two ranges of CIDRs there will other CIDR ranges like

7.25.255.1/20, 7.25.255.2/20 ……………. 12.175.24.254/24, 12.175.24.255/24, 12.175.25.0/24

Similarly for Japan region,

The CIDR 13.25.255.0/20 can have 4096 hosts, and 19.175.25.0/24 can have 256 hosts. These are the individual ranges denoted by the first and the second CIDRs respectively for Japan region. Similarly, in between these two ranges of CIDRs there will other CIDR ranges like

13.25.255.1/20, 13.25.255.2/20 ……………. 19.175.24.254/24, 19.175.24.255/24, 19.175.25.0

Upon computation, we realize that addresses 14.30.2.0, 13.25.240.0 and 19.175.25.255 belong to Japan region and address 8.30.2.0 belongs to Taiwan region, while address 20.30.2.0 belongs to neither of the two regions.

Hence the output is,

Japan
None
Japan
Taiwan
Japan