TCS CodeVita S9 Pre-Qualifier Round Qestion Paper and Solution 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 4th place (in voting queue) B supporter is moving towards the right side, simultaneously 7th 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 8th place B supporter is moving towards the right side, simultaneously 12th 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 10th voter at the same time, 10th voter will remain neutral.
Since supporter of A at 12th 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 1st 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 1st place cannot move towards right, supporter of B at 5th 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
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
Corona Virus
Problem Description
A city is represented as two-dimensional rectangular matrix. The outer wall of the given matrix denotes the boundaries of the city. Citizens are dispersed in the city at different locations. They are either depicted by {a, c}. Corona Virus has already infected the city.
The Corona Virus enters the city from coordinate (0, 0) and traverses along a diagonal path until it encounters a human. If it encounters a human, designated as a , its trajectory rotates anti clockwise (right to left) by 90 degrees. Similarly, if it encounters a human, designated as c , its trajectory rotates clockwise (left to right) by 90 degrees. After infecting the person, the virus continues to move along its diagonal path.
During its traversal if it hits the boundary of the city for the first time, it rotates 90 degrees to reenter the city. However if it hits any of the boundary wall, the second time, the virus gets destroyed.
You have to calculate the trajectory taken by the virus, print the city map where infected citizens can be found and finally report the number of safe and infected citizens.
Input
An input matrix of 9 rows and 20 columns comprising of {*, a, c, . } characters where
· * denotes an element on the boundaries of the city
· a denotes citizen after encountering whom the virus trajectory changes by 90 degrees (anti clockwise direction)
· c denotes citizen after encountering whom the virus trajectory changes by 90 degrees (clockwise direction)
· . (dot) denotes empty location within the city
Output
Random number of lines each denoting the coordinates of the trajectory of the virus.
From next line an output matrix of 9 rows and 20 columns comprising of {*, a, c, ., - } characters where
· * denotes an element on the boundaries of the city
· a denotes citizen after encountering whom the virus trajectory changes by 90 degrees (anti clockwise direction)
· c denotes citizen after encountering whom the virus trajectory changes by 90 degrees (clockwise direction)
· . (dot) denotes empty location within the city
· - denotes the location of the infected citizen
And the next two lines print the number of safe and infected citizens in the city
Refer Examples section for better understanding.
Constraints
0 <= x <= 20
0 <= y <= 8
The virus cannot hit the three corners (20, 8) (20, 0) (0, 8)
Time Limit
1
Examples
Example 1
Input
********************
*....c.............*
*...c..............*
*c.................*
*.............a....*
*c.c...............*
*.a................*
*...........c......*
********************
Output
0 0
1 1
2 2
1 3
2 4
3 5
4 6
5 5
6 4
7 3
8 2
9 1
10 0
11 1
12 2
13 3
14 4
13 5
12 6
11 7
10 8
********************
*....c.............*
*...-..............*
*c.................*
*.............-....*
*-.c...............*
*.-................*
*...........c......*
********************
safe=4
infected=4
Explanation
The virus trajectory starts from (0,0) and crosses (1,1) (2,2). At (2,2) we have a citizen of type a causing the virus trajectory to be rotated by 90 degrees anti clockwise. It moves until the next citizen in its path is encountered at (1, 3) of type c causing the virus trajectory to be rotated by 90 degree clockwise. It continues on its path till it reaches the next human in its path at (4,6) of type c Virus trajectory is again rotated by 90 degrees clockwise until it hits the boundary at (10,0). Since this is the first time that the virus hits the boundary, it rotates by 90 degrees anticlockwise to reenter the city. The trajectory then continues towards (11,1) (12,2) (13,3) and finally a citizen at (14,4) of type a rotating the trajectory to 90 degree anticlockwise. From there it continues its trajectory and hits the boundary at (10,8).
Since this is the second time the virus hits the boundary, the virus is destroyed.
So, along its trajectory starting from (0,0) it has infected 4 citizens at location (2,2) (1,3) (4,6) (14,4). The other 4 citizens who did not come in the virus trajectory are deemed to be safe.
Example 2
Input
********************
*..................*
*..c...............*
*....c.............*
*.........a........*
*..................*
*.......a......c...*
*..................*
********************
Output
0 0
1 1
2 2
3 3
4 4
5 5
6 4
7 3
8 2
9 3
10 4
9 5
8 6
7 7
6 8
5 7
4 6
3 5
2 4
1 3
0 2
********************
*..................*
*..c...............*
*....-.............*
*.........-........*
*..................*
*.......-......c...*
*..................*
********************
safe=2
infected=3
Explanation
The virus trajectory starts from (0,0) and crosses (1,1) (2,2) (5,5). At (5,5) we have a citizen of type c causing the virus trajectory to be rotated by 90 degrees clockwise. It moves until the next citizen in its path is encountered at (8,2) of type a causing the virus trajectory to be rotated by 90 degree anti clockwise. It continues on its path till it reaches the next human in its path at (10,4) of type a Virus trajectory is again rotated by 90 degrees clockwise until it hits the boundary at (6,8). Since this is the first time that the virus hits the boundary, it rotates by 90 degrees anticlockwise to reenter the city. The trajectory then continues towards (9,5) (8,6) (7,7) (6,8) and renters the city by rotating the trajectory by 90 degrees anti clockwise to follow the trajectory (5,7) (4,6) (3,5) (2,4) (1,3) (0,2).
At (0,2) it again hits the boundary and since this is the second time the virus hits the boundary, the virus is destroyed. So along its trajectory starting from (0,0) it has infected 3 citizens at location (5,5) (10,4) (8,2). The other 2 citizens who did not come in the virus trajectory are deemed to be safe.
String Pair
Problem Description
One person hands over the list of digits to Mr. String, But Mr. String understands only strings. Within strings also he understands only vowels. Mr. String needs your help to find the total number of pairs which add up to a certain digit D.
The rules to calculate digit D are as follow
Take all digits and convert them into their textual representation
Next, sum up the number of vowels i.e. {a, e, i, o, u} from all textual representation
This sum is digit D
Now, once digit D is known find out all unordered pairs of numbers in input whose sum is equal to D. Refer example section for better understanding.
Constraints
1 <= N <= 100
1 <= value of each element in second line of input <= 100
Number 100, if and when it appears in input should be converted to textual representation as hundred and not as one hundred. Hence number of vowels in number 100 should be 2 and not 4
Input
First line contains an integer N which represents number of elements to be processed as input
Second line contains N numbers separated by space
Output
Lower case representation of textual representation of number of pairs in input that sum up to digit D
Note: - (If the count exceeds 100 print "greater 100")
Time Limit
1
Examples
Example 1
Input
5
1 2 3 4 5
Output
one
Explanation
1 -> one -> o, e
2 -> two -> o
3 -> three -> e, e
4 -> four -> o, u
5 -> five - > i, e
Thus, count of vowels in textual representation of numbers in input = {2 + 1 + 2 + 2 + 2} = 9. Number 9 is the digit D referred to in section above.
Now from given list of number {1,2,3,4,5} -> find all pairs that sum up to 9.
Upon processing this we know that only a single unordered pair {4, 5} sum up to 9. Hence the answer is 1. However, output specification requires you to print textual representation of number 1 which is one. Hence output is one.
Note: - Pairs {4, 5} or {5, 4} both sum up to 9. But since we are asking to count only unordered pair, the number of unordered pair is this combination is only one.
Example 2
Input
3
7 4 2
Output
zero
Explanation
7 -> seven -> e, e
4 -> four -> o, u
2 -> two -> o
Thus, count of vowels in textual representation of numbers in input = {2 + 2 + 1} = 5. Number 5 is the digit D referred to in section above.
Since no pairs add up to 5, the answer is 0. Textual representation of 0 is zero. Hence output is zero.
Zoo Design
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
3 Palindrome
Problem Description
Given an input string word, split the string into exactly 3 palindromic substrings.
Working from left to right, choose the smallest split for the first substring that still allows the remaining word to be split into 2 palindromes.
Similarly, choose the smallest second palindromic substring that leaves a third palindromic substring.
If there is no way to split the word into exactly three palindromic substrings, print "Impossible" (without quotes). Every character of the string needs to be consumed.
Cases not allowed -
After finding 3 palindromes using above instructions, if any character of the original string remains unconsumed.
No character may be shared in forming 3 palindromes.
Constraints
1 <= the length of input sting <= 1000
Input
First line contains the input string consisting of characters between [a-z].
Output
Print 3 substrings one on each line.
Time Limit
1
Examples
Example 1
Input
nayannamantenet
Output
nayan
naman
tenet
Explanation
The original string can be split into 3 palindromes as mentioned in the output.
However, if the input was nayanamantenet, then the answer would be "Impossible".
Example 2
Input
aaaaa
Output
a
a
aaa
Explanation
The other ways to split the given string into 3 palindromes are as follows -
[a, aaa, a], [aaa, a, a], [aa, aa, a], etc.
Since we want to minimize the length of the first palindromic substring using left to right processing, the correct way to split is [a, a, aaa].
Example 3
Input
aaaabaaaa
Output
a
aaabaaa
a
Explanation
The other ways to split the given string into 3 palindromes are as follows -
[aaaa, b, aaaa], [aa, aabaa, aa], etc.
Since we want to minimize the length of the first palindromic substring using left to right processing, the correct way to split is [a, aaabaaa, a].
Elections Problem Solution In C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin>>n>>s;
//we have to do a bfs for all A and store when A and B are reaching a particular point
vector<pair<int,int>> checker(n,{INT_MAX,INT_MAX});
for(int i=0;i<n;i++)
{
//see if we got A/B
if(s[i]=='A')
{
int t=0; //A moves towards the left
int j=i-1;
if(j>=0)
{
for(j;j>=0;j--)
{
if(s[j]=='-')
{
checker[j].first=min(checker[j].first,t);
}
else if(s[j]=='A'||s[j]=='B')
{
break;
}
++t;
}
}
}
else if(s[i]=='B')
{//B moves towards the right
int t=0;
int j=i+1;
if(j<n)
{
for(j;j<n;j++)
{
if(s[j]=='-')
{
checker[j].second = min(checker[j].second,t);
}
else if(s[j]=='B'||s[j]=='A')
{
break;
}
t++;
}
}
}
}
int a_count=0;
int b_count=0;
//we got our checker array filled
for(int i=0;i<n;i++)
{
int x = checker[i].first;
int y = checker[i].second;
if(s[i]=='A')
{
a_count++;
}
else if(s[i]=='B')
{
b_count++;
}
if(s[i]=='-')
{
//we need to check checker
if(x>y)
{
//this means y reached earlier
b_count++;
}
else if(x<y)
{
a_count++;
}
}
}
//cout<<a_count<<" "<<b_count<<" ";
if(a_count>b_count)
{
cout<<"A";
}
else if(b_count>a_count)
{
cout<<"B";
}
else
{
cout<<"Coalition government";
}
}
3 Palindrome Problem Solution In Python
def is_pallindrome(si):
n = len(si)
if n==1:
return True
for i in range(n//2):
if si[i] != si[-i-1]:
return False
return True
si = input()
def f(si):
for k in range(1,len(si)-2):
if is_pallindrome(si[:k]):
for j in range(k+1,len(si)):
if is_pallindrome(si[k:j]) and is_pallindrome(si[j:]):
print(si[:k])
print(si[k:j])
print(si[j:])
return
print("not possible")
f(si)
TCS MOCKVITA 2 2020 QUESTION PAPER
Swayamvar
Problem Description
A ceremony where a Bride chooses her Groom from an array of eligible bachelors is called Swayamvar. But this is a Swayamvar with difference. An array of Bride-to-be will choose from an array of Groom-to-be.
The arrangement at this Swayamvar is as follows
· Brides-to-be are organized such that the most eligible bachelorette will get first chance to choose her Groom. Only then, the next most eligible bachelorette will get a chance to choose her Groom
· If the initial most eligible bachelorette does not get a Groom of her choice, none of the Brides-to-be have any chance at all to get married. So unless a senior bachelorette is out of the “queue”, the junior bachelorette does not get a chance to select her Groom-to-be
· Inital state of Grooms-to-be is such that most eligible bachelor is at the head of the “queue”. The next most eligible bachelor is next in the queue. So on and so forth.
· Now everything hinges on the choice of the bachelorette. The most eligible bachelorette will now meet the most eligible bachelor.
· If bachelorette selects the bachelor, both, the bachelorette and the bachelor are now Bride and Groom respectively and will no longer be a part of the Swayamvar activity. Now, the next most eligible bachelorette will get a chance to choose her Groom. Her first option is the next most eligible bachelor (relative to initial state)
· If the most eligible bachelorette passes the most eligible bachelor, the most eligible bachelor now moves to the end of the queue. The next most eligible bachelor is now considered by the most eligible bachelorette. Selection or Passing over will have the same consequences as explained earlier.
· If most eligible bachelorette reaches the end of bachelor queue, then the Swayamvar is over. Nobody can get married.
· Given a mix of Selection or Passing over, different pairs will get formed.
The selection criteria is as follows
1. Each person either drinks rum or mojito. Bride will choose groom only if he drinks the same drink as her.
Note : There are equal number of brides and grooms for the swayamvar.
Tyrion as the hand of the king wants to know how many pairs will be left unmatched. Can you help Tyrion?
Constraints
1<= N <= 10^4
Input Format
First line contains one integer N, which denotes the number of brides and grooms taking part in the swayamvar. Second line contains a string in lowercase, of length N containing initial state of brides-to-be. Third line contains a string in lowercase, of length N containing initial state of grooms-to-be. Each string contains only lowercase 'r' and 'm' stating person at that index drinks "rum"(for 'r') or mojito(for 'm').
Output
Output a single integer denoting the number of pairs left unmatched.
Timeout
1
Explanation
Example 1
Input
4
rrmm mrmr
Output
0
Explanation
The bride at first place will only marry groom who drinks rum. So the groom at first place will join the end of the queue. Updated groom's queue is "rmrm".
Now the bride at first place will marry the groom at first place. Updated bride's queue is "rmm" and groom's queue is "mrm".
The process continues and at last there are no pairs left. So answer is 0.
Example 2
Input
4 rmrm mmmr
Output
2
Explanation
Following the above process 2 pairs will be left unmatched. Remember that bride will not move until she gets a groom of her choice.
Digit Pairs
Problem Description
Given N three-digit numbers, your task is to find bit score of all N numbers and then print the number of pairs possible based on these calculated bit score.1. Rule for calculating bit score from three digit number:
From the 3-digit number,
- extract largest digit and multiply by 11 then
- extract smallest digit multiply by 7 then
Note: - Bit score should be of 2-digits, if above results in a 3-digit bit score, simply ignore most significant digit.
Consider following examples:
Say, number is 286
Largest digit is 8 and smallest digit is 2
So, 8*11+2*7 =102 so ignore most significant bit , So bit score = 02.
Say, Number is 123
Largest digit is 3 and smallest digit is 1
So, 3*11+7*1=40, so bit score is 40.
2. Rules for making pairs from above calculated bit scores
Condition for making pairs are
· Both bit scores should be in either odd position or even position to be eligible to form a pair.
· Pairs can be only made if most significant digit are same and at most two pair can be made for a given significant digit.
Constraints
N<=500Input Format
First line contains an integer N, denoting the count of numbers.Second line contains N 3-digit integers delimited by space
Output
One integer value denoting the number of bit pairs.Timeout
1Explanation
Example 1Input
8 234 567 321 345 123 110 767 111
Output
3
Explanation
After getting the most and least significant digits of the numbers and applying the formula given in Rule 1 we get the bit scores of the numbers as:
58 12 40 76 40 11 19 18
No. of pair possible are 3:
40 appears twice at odd-indices 3 and 5 respectively. Hence, this is one pair.
12, 11, 18 are at even-indices. Hence, two pairs are possible from these three-bit scores.
Hence total pairs possible is 3
Dole Out Cadbury
Problem Description
You are a teacher in reputed school. During Celebration Day you were assigned a task to distribute Cadbury such that maximum children get the chocolate. You have a box full of Cadbury with different width and height. You can only distribute largest square shape Cadbury. So if you have a Cadbury of length 10 and width 5, then you need to break Cadbury in 5X5 square and distribute to first child and then remaining 5X5 to next in queueConstraints
0<P<Q<15010<R<S<1501
Input Format
First line contains an integer P that denotes minimum length of Cadbury in the boxSecond line contains an integer Q that denotes maximum length of Cadbury in the box
Third line contains an integer R that denotes minimum width of Cadbury in the box
Fourth line contains an integer S that denotes maximum width of Cadbury in the box
Output
Print total number of children who will get chocolate.Timeout
1Explanation
Example 1Input
5
7
3
4
Output
24
Explanation
Length is in between 5 to 7 and width is in between 3 to 4.
So we have 5X3,5X4,6X3,6X4,7X3,7X4 type of Cadbury in the box.
If we take 5X3 :
First, we can give 3X3 square Cadbury to 1st child .Then we are left with 3X2. Now largest square is 2X2 which will be given to next child. Next, we are left with two 1X1 part of Cadbury which will be given to another two children.
And so on
Petrol Pump
Problem Description
A big group of students, starting a long journey on different set of vehicles need to fill petrol in their vehicles.As group leader you are required to minimize the time they spend at the petrol pump to start the journey at the earliest. You will be given the quantity of petrol (in litres) that can be filled in each vehicle. There are two petrol vending machines at the petrol pump. You need to arrange the vehicles in such a way that they take shortest possible time to fill all the vehicles and provide the time taken in seconds as output. Machine vends petrol @ 1litre/second.
Assume that there is no time lost between switching vehicles to start filling petrol.
Constraints
1<= Number of vehicles < 50.0 <= Quantity of petrol required in any vehicle <= 200
Input Format
First line will provide the quantity of petrol (separated by space) that can be filled in each vehicle.Output
Shortest possible time to fill petrol in all the vehicles.Timeout
1Explanation
Example 1Input
1 2 3 4 5 10 11 3 6 16
Output
31
Explanation
First Petrol vending machine will cater to vehicles taking - 16, 6, 4, 3, 2 litres of petrol (Total 31 sec)
Second machine will cater to vehicles taking - 11, 10, 5, 3, 1 litres of petrol (Total 30 sec)
Example 2
Input
25 30 35 20 90 110 45 70 80 12 30 35 85
Output
335
Explanation
First Petrol vending machine will cater to vehicles taking - 80, 45, 35, 30, 25, 12, 85, 20 litres of petrol.
Second machine will cater to vehicles taking - 90, 70, 35, 30, 110 litres of petrol. Since second machine will take more time, total time to fill petrol in all vehicles will be 335 seconds.
Grooving Monkeys
Problem Description
N monkeys are invited to a party where they start dancing. They dance in a circular formation, very similar to a Gujarati Garba or a Drum Circle. The dance requires the monkeys to constantly change positions after every 1 second.The change of position is not random & you, in the audience, observe a pattern. Monkeys are very disciplined & follow a specific pattern while dancing.
Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.
This array (1-indexed) is the dancing pattern. The value at monkeys[i], indicates the new of position of the monkey who is standing at the ith position.
Given N & the array monkeys[ ], find the time after which all monkeys are in the initial positions for the 1st time.
Constraints
1<=t<=10 (test cases)1<=N<=10000 (Number of monkeys)
Input Format
First line contains single integer t, denoting the number of test cases.Each test case is as follows -
Integer N denoting the number of monkeys.
Next line contains N integer denoting the dancing pattern array, monkeys[].
Output
t lines,Each line must contain a single integer T, where T is the minimum number of seconds after which all the monkeys are in their initial position.
Timeout
1Explanation
Example 1Input
1
6
3 6 5 4 1 2
Output
6
Explanation
Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.
Suppose monkeys are a,b,c,d,e,f, & Initial position (at t = 0) -> a,b,c,d,e,f
At t = 1 -> e,f,a,d,c,b
a will move to 3rd position, b will move to 6th position, c will move to 5th position, d will move to 4th position, e will move to 1st position and f will move to 2nd position. Thus from a,b,c,d,e,f at t =0, we get e,f,a,d,c,b at t =1. Recursively applying same transpositions, we get following positions for different values of t.
At t = 2 -> c,b,e,d,a,f
At t = 3 -> a,f,c,d,e,b
At t = 4 -> e,b,a,d,c,f
At t = 5 -> c,f,e,d,a,b
At t = 6 -> a,b,c,d,e,f
Since at t = 6, we got the original position, therefore the answer is 6.
Death Battle
Problem Description
In a crossover fantasy universe, Houin Kyoma is up in a battle against a powerful monster Nomu that can kill him in a single blow. However being a brilliant scientist Kyoma found a way to pause time for exactly M seconds. Each second, Kyoma attacks Nomu with certain power, which will reduce his health points by that exact power. Initially Nomu has H Health Points. Nomu dies when his Health Points reach 0. Normally Kyoma performs Normal Attack with power A. Besides from Kyoma’s brilliance, luck plays a major role in events of this universe. Kyoma’s Luck L is defined as probability of performing a super attack. A super attack increases power of Normal Attack by C. Given this information calculate and print the probability that Kyoma kills Nomu and survives. If Kyoma dies print “RIP”.Constraints
0 < T <= 501 <= A, H, C, L1, L2 <= 1000
1 <= M <= 20.
L1<=L2
Input Format
First line is integer T denoting number of test cases.Each test case consist of single line with space separated numbers A H L1 L2 M C. Where luck L is defined as L1/L2. Other numbers are, as described above.
Output
Print probability that Kyoma kills Nomu in form P1/P2 where P1<=P2 and gcd(P1,P2)=1. If impossible, print “RIP” without quotes.Timeout
1Explanation
Example 1Input
2
10 33 7 10 3 2
10 999 7 10 3 2
Output
98/125
RIP
TCS MOCKVITA 2 2020 QUESTION PAPER SOLUTION
Swayamvar
n=int(input())
bride=list(input())
groom=list(input())
for i in bride:
if i in groom:
groom.remove(i)
else:
break
print (len(groom),end="")
Digit Pairs
#include<iostream>
using namespace std;
int bit_score(int x) {
int m, n, o, largest, smallest;
int score;
m = x%10; x/=10;
n = x%10; x/=10;
o = x%10; x/=10;
largest = (m>n)?m:n;
largest = (o>largest)?o:largest;
smallest = (m<n)?m:n;
smallest = (o<smallest)?o:smallest;
score = largest*11 + smallest*7;
score = score % 100;
return score;
}
int findPairs (int score_array[], int N) {
int sig_dig[10], i, pairs = 0, msb;
for(i=0; i<10; i++) {
sig_dig[i] = 0;
}
for(i=0; i<N; i=i+2) {
msb = score_array[i] / 10;
for(int j =i+2; j<N; j=j+2){
if(msb == score_array[j]/10){
if(sig_dig[msb] < 2) {
sig_dig[msb]++;
}
}
}
}
for(i=1; i<N; i=i+2) {
msb = score_array[i] / 10;
for(int j =i+2; j<N; j=j+2){
if(msb == score_array[j]/10){
if(sig_dig[msb] < 2) {
sig_dig[msb]++;
}
}
}
}
for(i=0; i<10; i++) {
pairs = pairs + sig_dig[i];
}
return pairs;
}
int main() {
int N, i;
int ip_array[501];
int score_array[501];
int pairs;
cin>>N;
for(i=0; i<N; i++) {
cin>>ip_array[i];
}
for(i=0; i<N; i++) {
score_array[i] = bit_score(ip_array[i]);
}
pairs = findPairs(score_array, N);
cout<<pairs;
return 0;
}
Dole Out Cadbury
#include<stdio.h>int no_of_children(int row, int col)
{
int count=0; int total = row * col;
while(row && col)
{
count++;
if(row>col) row = row - col;
else
col = col - row;
}
return count;
}
int main()
{
int sum=0;
int minlen,maxlen,minwid,maxwid;
scanf("%d\n%d\n%d\n%d",&minlen,&maxlen,&minwid,&maxwid);
if(0<minlen<1501 && 0<maxlen<1501 && 0<minwid<1501 && 0<maxwid<1501)
{
for(int i=minlen;i<=maxlen;i++)
{
for(int j=minwid;j<=maxwid;j++)
{
sum = sum + no_of_children(i,j);
}
}
printf("%d",sum);
}
return 0;
}
Petrol Pump
#include <stdio.h>int main(void) {
int n=0, x, i, j, sum = 0;
int ar[51];
while((scanf("%d",&x))!=-1)
{
ar[n++]=x;
sum += x;
}
int dp[n+1][sum+1];
for(i=0 ; i<=n ; ++i)
dp[i][0] = 1;
for(i=1 ; i<=sum ; ++i)
dp[0][i] = 0;
for(i=1 ; i<=n ; ++i)
for(j=1 ; j<=sum ; ++j)
{
dp[i][j] = dp[i-1][j];
if(ar[i-1] <= j)
dp[i][j] = dp[i][j] | dp[i-1][j - ar[i-1]];
}
int ans = sum;
for(i=sum/2 ; i>=0 ; --i)
if(dp[n][i])
{
ans = sum - i;
break;
}
printf("%d",ans);
return 0;
}
Grooving Monkeys
#include<stdio.h>long long int gcd(long long int a,long long int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
int main()
{
long long int t,n,i,res,c,temp,temp1;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
long long int a[n];
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
i=0;
res=1;
c=0;
while(i<=n-1)
{
temp1=i;
c=0;
while(a[i]!=0)
{
temp=i;//4
i=a[i]-1;//0
a[temp]=0;//0
c+=1;//3
}
i=temp1+1;
if(c!=0)
res=res*c/gcd(res,c);
}
printf("%lld\n",res);
}
return 0;
}
Death Battle
from math import gcd,factorialdef ncr(n,r):
return factorial(n)/(factorial(n-r)*(factorial(r)))
for i in range(int(input())):
a,h,l1,l2,m,c = [int(i) for i in input().split()]
num = 0
den = pow(l2,m)
if m*(a+c) < h:
print("RIP")
else:
k,z = 0,m*a
while z < h:
z += c
k += 1
for i in range(k,m+1):
if i == 0:
num += pow(l2 - l1,m)
elif i == m:
num += pow(l1,i)
else:
num += (pow(l1,i)*pow(l2-l1,m-i)*ncr(m,i))
x = gcd(int(num),den)
print(str(int(num/x))+"/"+str(int(den/x)))
Posts
petrol puump was not working i tested it.
ReplyDelete