Please Note- Solution, if not present will be added soon
Microsoft Virtual Internship - https://youtu.be/p-hk5_2Y0UM
Click Here Please Subscribe to YT Channel Link For Amazon & Google Hiring is Posted There (More will be posted)
(please note Solution Video Explanation will be added, Subscribe and wait)
Largest Gold Ingot
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.
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
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
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.
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.
SOLUTION- https://bit.ly/3fMeL4r
CODE-
#include <bits/stdc++.h>#include <iostream>using namespace std;int main(){ long long int n, sum = 0; cin >> n; long long int a, b, m = pow(10, 9) + 7; cin >> a >> b; int arr[n]; for (int i = 0; i < n; i++) { cin >> arr[i]; sum = sum + arr[i]; } long long int res = 0, ans = 0; stack<int> s; for (int i = 0; i < n; i++) { while (s.empty() == false and arr[i] <= arr[s.top()]) { long long int tp = s.top(); s.pop(); res = arr[tp] * (s.empty() ? i : (i - s.top() - 1)); ans = max(ans % m, res); } s.push(i); } while (s.empty() == false) { long long int tp = s.top(); s.pop(); res = arr[tp] * (s.empty() ? n : (n - s.top() - 1)); ans = max(ans % m, res); } cout << ((sum % m - ans % m) % m * a % m * b % m) % m;}
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main()
{
long long int n, sum = 0;
cin >> n;
long long int a, b, m = pow(10, 9) + 7;
cin >> a >> b;
int arr[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
sum = sum + arr[i];
}
long long int res = 0, ans = 0;
stack<int> s;
for (int i = 0; i < n; i++)
{
while (s.empty() == false and arr[i] <= arr[s.top()])
{
long long int tp = s.top();
s.pop();
res = arr[tp] * (s.empty() ? i : (i - s.top() - 1));
ans = max(ans % m, res);
}
s.push(i);
}
while (s.empty() == false)
{
long long int tp = s.top();
s.pop();
res = arr[tp] * (s.empty() ? n : (n - s.top() - 1));
ans = max(ans % m, res);
}
cout << ((sum % m - ans % m) % m * a % m * b % m) % m;
}
Click Here Please Subscribe to YT Channel Link For Amazon & Google Hiring is Posted There (More will be posted)
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.
SOLUTION- https://bit.ly/3fMeL4r
Click Here Please Subscribe to YT Channel Link For Amazon & Google Hiring is Posted There (More will be posted)
Path Through Graph
Problem Description
You are given two natural numbers. Imagine these natural numbers as nodes on a graph. On this graph, a number is connected to its largest factor other than itself. You have to find the shortest path between them and print the number of edges on that path.
If the two numbers do not have any common factor, then construct a path through 1. For better understanding refer to the examples below:
Example 1:
Input numbers: 2 4
The numbers are directly connected as follows on the graph. 2 is the largest factor of 4, other than itself.
We can also see that there is only on edge between them.
4 <--> 2
Hence the number of edges in shortest path is 1.
Output: 1
Example 2:
Input numbers: 18 19
The graph for number 18 and 19 will look like this. Here we have 4 edges in the path.
18 <--> 9 <--> 3 <--> 1 <--> 19Output: 4
Example 3:
Input numbers: 9 9
The number of edges in shortest path is zero since the numbers correspond to the same node.
Output: 0
Constraints
0 < M, N <= 10 ^ 9
Input
Single line containing two space separated integers M, N
Output
Number of edges in the shortest path.
Time Limit
1
Examples
Example 1Input
15689 28
Output
5Explanation :
The graph for number 15689 and 28 will look like this.
Since we know that largest factor of 15689 other than itself is 541.
Since 541 is a prime number, it’s largest factor other than itself is 1.
For number 28, it’s largest factor other than itself is 14.
Largest factor of 14, other than itself is 7.
Since 7 is a prime number, it’s largest factor other than itself is 1.
So, the graph will look like this:
15689 <--> 541 <--> 1 <--> 7 <--> 14 <--> 28
Since there are 5 edges in this graph, output will be 5.
Example 2
Input
16 4
Output
2
Explanation :
The graph for number 16 and 4 will look like this.
Since we know that largest factor of 16 other than itself is 8.
Largest factor of 8 other than itself is 4. That’s the other input number, so we will stop here.
So, the graph will look like this:
16<-->8<-->4
Since there are 2 edges in this graph, output will be 2.
SOLUTION- https://bit.ly/3fMeL4r
CODE-
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int get(int x)
{
for (int i = 2; i * i <= x; i++)
{
if (x % i == 0)
return x / i;
}
return 1;
}
void sol()
{
int x, y;
cin >> x >> y;
if (x < y)
swap(x, y);
if (x == y)
{
cout << 0;
return;
}
map<int, int> m;
int c = 0;
while (x != 1)
{
c++;
x = get(x);
m[x] = c;
}
c = 0;
while (!m.count(y))
{
c++;
y = get(y);
}
cout << c + m[y];
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
Click Here Please Subscribe to YT Channel Link For Amazon & Google Hiring is Posted There (More will be posted)
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 vehiclesSecond 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
SOLUTION - https://bit.ly/3fMeL4r
CODE-
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int speed[n];
for (int i = 0; i < n; i++)
cin >> speed[i];
double per = 1, group = 0;
for (int i = 1; i <= n; i++)
{
per *= i;
for (int j = 1, mult = 1; j <= i; mult *= ++j)
{
group += (per / mult);
}
}
if (n % 2 == 0)
group--;
group -= n;
printf("%0.6f", group / per);
}
Click Here Please Subscribe to YT Channel Link For Amazon & Google Hiring is Posted There (More will be posted)
Secret Word
Problem Description
A computer scientist has developed an encryption algorithm. This algorithm takes two inputs - one plain word and another, a key. Characteristics of inputs are as below.
Plain word: It is a string consisting of lowercase alphabets only.
Key: It is a set of pairs of strings consisting of lowercase alphabets only. For each pair, first string is the plain word and second string is its secret word. The characters of these secret words are jumbled but lengths of Plain Word and Secret Word are equal.
This algorithm finds the secret characters for each character in the inputted plain word by using the key. Then it combines all the secret characters in the same order to form a string called the secret word. Finally output this secret word. Below table shows how secret characters can be obtained from the key.
Examples
Your task is to help him in implementing the algorithm as a computer program.
Note: It is guaranteed that all characters in the given plain word can be converted to secret characters by using the given key.
Note: It is guaranteed that one plain text can be converted to only one encrypted text.
Constraints
1 <= P <= 52000
1 <= N <= 26
1 <= Length of a plain word in pair <= 50000
1 <= Length of a secret word in pair <= 50000
Length (plain word) == Length (secret word)
Input
First line contains string P denoting the plain text.
Second line contains an integer N denoting number of key pairs.
Next N lines, each contain two space separated strings denoting plain text and key.
Output
Print the encrypted word.
Time Limit
1
Examples
Example 1
Input
load
3
app lol
old tip
odd itt
Output
piot
Explanation
"load" is the plain word to be encrypted. Given Key contains 3 pairs of Plain word and Secret word combination. They are <"app", "lol">, <"old", "tip"> and <"odd", "itt">. From first pair, it's clear that the secret character of 'p' is 'l' and that of 'a' is 'o'. From third pair, it's clear that the secret character of 'd' is 't' and that of 'o' is 'i'. By using above findings, from second pair, it is clear that the secret character of 'l' is 'p'. Now we can build the secret word by replacing the characters of plain word by its corresponding secret characters as "piot".
Example 2
Input
a
1
a b
Output
b
Explanation
The word "a" is the plain word to be converted to secret word. The given key consists of only one plain word - secret word pair. i.e., <"a", "b">. From this, it is clear that the secret character of 'a' is 'b', since there is only one character in both secret and plain words. So, the final output is "b".
SOLUTION- https://bit.ly/3fMeL4r
Click Here Please Subscribe to YT Channel Link For Amazon & Google Hiring is Posted There (More will be posted)
7X7
Problem Description
CODU is solving a 7x7 sudoku. Help him in solving the unique Sudoku.
Rules are as follows
1. There are 7 regions coloured differently. Each region must have a single occurrence of numbers between range [1, 7].
2. Regions don't have a fix shape and it can change from input to input.
3. Each row must have a single occurrence of numbers between range [1, 7] across all input.
4. Each column must have a single occurrence of numbers between range [1, 7] across all input.
Some numbers in some rows, columns and regions will be given. These will be between [1, 7].
Zero (0) denotes that the number is covered. Uncovering it will give a number between [1, 7].
Your task is to fill the numbers [1,7] where there is a 0 such that the 7x7 Sudoku is solved.
7x7 Sudoku is said to be solved when every region, every column, every row has exactly one occurrence of numbers [1,7].
Constraints
7 < Known/Given numbers in Entire Sudoku < 14
Input
Input consists of 14 lines.
First 7 lines denote the positions of numbers [1,7] in respective row and column.
Next 7 lines denote the shape of the regions inside the Sudoku. These will be denoted by 7 unique characters between alphabets [a-z].
Output
Print the solved Sudoku.
7 lines, each line containing 7 space separated integers honoring all the conditions.
Time Limit
1
Examples
Example 1
Input
0 0 0 0 0 6 0
0 0 0 0 0 0 0
2 6 5 1 7 4 3
0 0 0 3 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
a a a b b b b
a a a a b b c
d d d e e b c
d d d d e e c
f f f h e e c
f f h h e c c
f f h h h h c
The above input can be visualized as follows-
Output
1 2 4 5 3 6 7
3 5 6 7 1 2 4
2 6 5 1 7 4 3
4 7 1 3 2 5 6
7 1 2 6 4 3 5
5 4 3 2 6 7 1
6 3 7 4 5 1 2
Explanation
There could be many different solutions. Producing any solution as output is acceptable.
Example 2
Input
0 0 0 0 0 0 0
0 0 0 0 4 0 0
3 0 0 6 0 0 0
0 0 0 0 6 0 1
5 0 0 0 0 0 3
0 0 1 0 0 0 2
2 0 0 0 0 0 5
r r r b b b b
g r r r r b o
g g g g b b o
p p g o o o o
p p g d o l l
p p p d l l l
d d d d d l l
The above input can be visualized as follows-
Note that the shape of the regions in both the inputs are different.
Output
7 1 3 4 5 2 6
1 6 5 2 4 3 7
3 5 2 6 1 7 4
4 2 7 3 6 5 1
5 7 4 1 2 6 3
6 3 1 5 7 4 2
2 4 6 7 3 1 5
Explanation
There could be many different solutions. Producing any solution as output is acceptable.
SOLUTION- https://bit.ly/3fMeL4r
Fill The Cube
Problem Description
A company manufactures walls which can be directly implanted at the site. The company uses small square bricks of material C and material D which have similar looks but have huge difference in quality. The company manufactures walls of square shapes only to optimize their costs.
A novice employee created a square wall using bricks of material C and D. However, the client had asked the wall to be made of only high-quality material - material C.
To solve this problem, they will place the wall in a special furnace and heat it such that the material D melts and only material C remains. Material C brick will move down due to gravity if a material D brick below it melts. The new empty space created will be filled by new material C square walls. They also want to use biggest possible C square wall while building the final wall. For this they will position the wall in the furnace in an optimal way i.e. rotate by 90-degrees any number of times, if required, such that the biggest space possible for new material C wall is created. No rotations are possible when the furnace starts heating.
Given the structure of the original wall created by the novice employee, you need to find out the size of the new C square wall which can be fitted in the final wall which will be delivered to the client.
Constraints
1 < N < 100
Input
First Line will provide the size of the original wall N.
Next N lines will provide the type of material (C and D) used for each brick by the novice employee.
Output
Size of the biggest possible C square wall which can be fitted in the final wall.
Time Limit
1
Examples
Example 1
Input
4
C D C D
C C D C
D D D D
C D D D
Output
3
Explanation
If the wall is placed with its left side at the bottom, space for a new C wall of size 2x2 can be created. This can be visualized as follows
D C D D
C D D D
D C D D
C C D C
The melted bricks can be visualized as follows
- - - -
- C - -
C C - -
C C - C
Hence, the maximum wall size that can be replaced is 2x2.
If the wall is placed as it is with its original bottom side at the bottom, space for a new C wall of size 3x3 can be created. Post melting, this can be visualized as follows.
- - - -
C - - -
C - - -
C C C C
Hence, the maximum wall size that can be replaced is 3x3 in this approach.
Since no rotations followed by heating is going to a yield a space greater than 3x3, the output is 3.
Example 2
Input
7
C D D C D D D
C D D C D D D
D D D D D D C
D C D C D D D
D D D C D C D
C D D C D C C
C D C D C C C
Output
5
Explanation
If the wall is placed with its left side at the bottom, a space for new C wall of size 5x5 can be created. This can be visualized as follows
D D C D D C C
D D D D C C C
D D D D D D C
C C D C C C D
D D D D D D C
D D D C D D D
C C D D D C C
When this orientation of the wall is heated, a space for new C wall of size 5x5 is created after the D bricks melt
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ _ _ _C
_ _ _ _ _ _ C
_ _ _ _ _ C C
C C _ C C C C
C C C C C C C
Whereas, if the rotation was not done, the wall formed after the D bricks melt will be as follows
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ C _ _ _
C _ _ C _ _ _
C _ _ C _ _ C
C _ _ C _ C C
C C C C C C C
When this orientation of the wall is heated, a space for new C wall of size 3x3 only is created after the D bricks melt
Hence rotation is important and correct answer is 5x5
Since no rotations followed by heating is going to a yield a space greater than 5x5, the output is 5.
SOLUTION- https://bit.ly/3fMeL4r
CODE-
#include<bits/stdc++.h>
using namespace std;
bool isPerfectSquare(int n)
{
for (int i = 1; i * i <= n; i++) {
// If (i * i = n)
if ((n % i == 0) && (n / i == i)) {
return true;
}
}
return false;
}
int getMaxArea(int hist[], int n)
{
// Create an empty stack. The stack holds indexes
// of hist[] array. The bars stored in stack are
// always in increasing order of their heights.
stack<int> s;
int max_area = 0; // Initialize max area
int tp; // To store top of stack
int area_with_top; // To store area with top bar
// as the smallest bar
// Run through all bars of given histogram
int i = 0;
while (i < n)
{
// If this bar is higher than the bar on top
// stack, push it to stack
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
// If this bar is lower than top of stack,
// then calculate area of rectangle with stack
// top as the smallest (or minimum height) bar.
// 'i' is 'right index' for the top and element
// before top in stack is 'left index'
else
{
tp = s.top(); // store the top index
s.pop(); // pop the top
// Calculate the area with hist[tp] stack
// as smallest bar
area_with_top = hist[tp] * (s.empty() ? i :
i - s.top() - 1);
// update max area, if needed
if (max_area < area_with_top)
max_area = area_with_top;
}
}
// Now pop the remaining bars from stack and calculate
// area with every popped bar as the smallest bar
while (s.empty() == false)
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i :
i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
return max_area;
}
int main()
{
int n;
cin>>n;
char arr[100][100];
int arr2[100][100];
int row[100], col[100];
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>arr[i][j];
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(arr[i][j]=='D')
arr2[i][j] =0;
else
arr2[i][j] = 1;
}
}
for(i=0;i<n;i++)
{ int sum=0;
for(j=0;j<n;j++)
{
sum = sum+ arr2[i][j];
}
row[i] =n - sum;
}
for(i=0;i<n;i++)
{ int sum=0;
for(j=0;j<n;j++)
{
sum = sum+ arr2[j][i];
}
col[i] =n - sum;
}
int count = 0;
for(i=0;i<n;i++)
{
if(row[i]!=0)
{
break;
}
else
count++;
}
int count2 = 0;
for(i=0;i<n;i++)
{
if(col[i]!=0)
{
break;
}
else
count2++;
}
if( count == n && count2 ==n)
cout<<"0";
else
{
int area1 , area2;
area1 = getMaxArea(row , n) ;
area2 = getMaxArea(col , n);
if (isPerfectSquare(area1) && isPerfectSquare(area2) )
{
int max1 = max(sqrt(area1), sqrt(area2));
cout<<max1;
}
else if(isPerfectSquare(area1) && !isPerfectSquare(area2) )
cout<<sqrt(area1);
else if(isPerfectSquare(area2) && !isPerfectSquare(area1) )
cout<<sqrt(area2);
else
cout<<"1";
}
}
Even Odd
Problem Description
Given a range [low, high] (both inclusive), select K numbers from the range (a number can be chosen multiple times) such that sum of those K numbers is even.
Calculate the number of all such permutations.
As this number can be large, print it modulo (1e9 +7).
Constraints
0 <= low <= high <= 10^9
K <= 10^6.
Input
First line contains two space separated integers denoting low and high respectively
Second line contains a single integer K.
Output
Print a single integer denoting the number of all such permutations
Time Limit
1
Examples
Example 1
Input
4 5
3
Output
4
Explanation
There are 4 valid permutations viz. {4, 4, 4}, {4, 5, 5}, {5, 4, 5} and {5, 5, 4} which sum up to an even number
Example 2
Input
1 10
2
Output
50
Explanation
There are 50 valid permutations viz. {1,1}, {1, 3},.. {1, 9} {2,2}, {2, 4},... {2, 10} . . . {10, 2}, {10, 4},... {10, 10}. These 50 permutations, each sum up to an even number.
4 Particles
Problem DescriptionThere is a cube of height H, and there are 4 moving particles on the vertical edges of the cube. Initially particles are at some height A, B, C and D respectively. These particles are moving in different direction (Only upward or downward, no sideways movement) with different speed.
If the particle is moving upward or downward reaches the tip of the cube then it remain at the tip only and will not move further. If other particles have not reach the tip they continue to move along their respective edges in their respective direction till the last particle reaches the tip.
These 4 particles will make two triangles in a 3-D plane. Since the particles are moving, sum of the area of these two triangles will change every moment.
Find out the maximum and minimum of the sum of the areas of these two triangles.
Refer the Examples section for better understanding.
Constraints
1 <= H <= 100
0 <= A, B, C, D <= H
0 <= V1, V2, V3, V4 <= 100
Input
First line contains an integer H which denotes the length of the side of cube.
Second line contains 4 space separated integers denoting the initial position of all 4 particles on the 4 vertical edges, say A, B, C and D respectively.
Third line contains 4 space separated integers denoting the speed of all particles, say V1, V2, V3, and V4 per time unit respectively.
Fourth line contains 4 space separated characters U or D denoting the direction of movement of particles. U denotes the upward direction and D denotes the downward direction.
CODE-
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>
using namespace std;
float dist(float x1, float x2, float y1, float y2, float z1, float z2)
{
float d = 0;
d = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2) + pow(z2 - z1, 2) * 1.0);
return d;
}
float area(float side1, float side2, float side3)
{
float s = (side1 + side2 + side3) / 2;
float are = sqrt(s * (s - side1) * (s - side2) * (s - side3));
return are;
}
int main()
{
float h, a, b, c, d, va, vb, vc, vd;
cin >> h >> a >> b >> c >> d >> va >> vb >> vc >> vd;
char da, db, dc, dd;
cin >> da >> db >> dc >> dd;
if (da == 'D')
{
va = va * (-1);
}
if (db == 'D')
{
vb = vb * (-1);
}
if (dc == 'D')
{
vc = vc * (-1);
}
if (dd == 'D')
{
vd = vd * (-1);
}
float xa = 0, ya = h * (-1);
float xb = h, yb = h * (-1);
float xc = h, yc = 0;
float xd = 0, yd = 0;
float z[100][4];
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 4; j++)
{
z[i][j] = 0;
}
}
z[0][0] = a;
z[0][1] = b;
z[0][2] = c;
z[0][3] = d;
for (int i = 1; i < 100; i++)
{
z[i][0] = z[i - 1][0] + va;
z[i][1] = z[i - 1][1] + vb;
z[i][2] = z[i - 1][2] + vc;
z[i][3] = z[i - 1][3] + vd;
if (z[i][0] > h)
{
z[i][0] = h;
}
if (z[i][0] < 0)
{
z[i][0] = 0;
}
if (z[i][1] > h)
{
z[i][1] = h;
}
if (z[i][1] < 0)
{
z[i][1] = 0;
}
if (z[i][2] > h)
{
z[i][2] = h;
}
if (z[i][2] < 0)
{
z[i][2] = 0;
}
if (z[i][3] > h)
{
z[i][3] = h;
}
if (z[i][3] < 0)
{
z[i][3] = 0;
}
}
float ab[100];
for (int i = 0; i < 100; i++)
{
ab[i] = dist(xa, xb, ya, yb, z[i][0], z[i][1]);
}
float bc[100];
for (int i = 0; i < 100; i++)
{
bc[i] = dist(xb, xc, yb, yc, z[i][1], z[i][2]);
}
float ac[100];
for (int i = 0; i < 100; i++)
{
ac[i] = dist(xa, xc, ya, yc, z[i][0], z[i][2]);
}
float ad[100];
for (int i = 0; i < 100; i++)
{
ad[i] = dist(xa, xd, ya, yd, z[i][0], z[i][3]);
}
float bd[100];
for (int i = 0; i < 100; i++)
{
bd[i] = dist(xb, xd, yb, yd, z[i][1], z[i][3]);
}
float cd[100];
for (int i = 0; i < 100; i++)
{
cd[i] = dist(xc, xd, yc, yd, z[i][2], z[i][3]);
}
float abc[100];
for (int i = 0; i < 100; i++)
{
abc[i] = area(ab[i], bc[i], ac[i]);
}
float adc[100];
for (int i = 0; i < 100; i++)
{
adc[i] = area(ad[i], cd[i], ac[i]);
}
float abd[100];
for (int i = 0; i < 100; i++)
{
abd[i] = area(ab[i], ad[i], bd[i]);
}
float bcd[100];
for (int i = 0; i < 100; i++)
{
bcd[i] = area(bc[i], cd[i], bd[i]);
}
float maxabc = abc[0];
for (int i = 0; i < 100; i++)
{
if (maxabc < abc[i])
maxabc = abc[i];
}
float minabc = abc[0];
for (int i = 0; i < 100; i++)
{
if (minabc > abc[i])
minabc = abc[i];
}
float maxadc = adc[0];
for (int i = 0; i < 100; i++)
{
if (maxadc < adc[i])
maxadc = adc[i];
}
float minadc = adc[0];
for (int i = 0; i < 100; i++)
{
if (minadc > adc[i])
minadc = adc[i];
}
float ans1 = 4 * pow((maxabc + maxadc), 2);
float ans2 = 4 * pow((minabc + minadc), 2);
cout << round(ans1) << " " << round(ans2) << endl;
return 0;
}
Click Here Please Subscribe to YT Channel Link For Amazon & Google Hiring is Posted There (More will be posted)
Max Sum
Problem DescriptionTwo friends A and B are playing with an array of integers. They both agree upon the operations to be performed on the array but differ on choice of window size to perform the said operations.
The operations to be performed on the array are explained below:
· One can choose to add at the most X consecutive elements.
· After performing the addition operation, it is mandatory to skip the next element in the array.
· The goal is to achieve maximum sum by choosing appropriate elements in the array.
A wants X to be W, while B wants X to be (W + D). This is the only difference that they have. Your task is to find out who wins. Winner is the person whose sum is higher.
The inputs that will be provided are values of elements of array, value of W and value of D.
Example:
Array: 4 5 6 1 2 7 8 9
Window Size (W): 3
Output: 39
Explanation
· We will choose to add elements 4, 5, 6 since window size is 3.
· Since one addition operation is complete, we have to skip one element which is 1.
· We choose to skip element 2 because the next three values are also higher than 2.
· The max sum thus obtained is 39.
Now suppose the array was: 4 5 6 1 2 3 7 8 9
· We will choose to add elements 4, 5, 6 since window size is 3.
· Since one addition operation is complete, we have to skip one element which is 1.
· Now we choose to pick element 2 because we can skip element 3 and still pick up the next 3 values viz 7, 8, 9.
· The max sum thus obtained is 41.
· Note that we picked up only one element in second selection since constraint is only on maximum number to be chosen, not minimum.
Now suppose the array was: 4 5 6 7
· Since one can start from any index, we choose element 5, 6, 7.
· The max sum thus obtained is 18.
The above examples illustrate the game with a fixed window size of W. Since B prefers to play the same game with the size of W+D, the steps will remain the same but the max sum output may be different. Print different output depending on whether A wins, B wins or it’s a tie.
Constraints
0 <= N <= 10 ^ 5
5 <= W <= 10 ^ 5
-10^5 <= D <= 10^5
0 < (W + D) <= N
0 <= elements in array <= 10 ^ 9
Input
First line contains three space separated integers N and W and D respectively, which denote
N - size of array
W - window size
D - difference
Second line contains of N space separated integers denoting the elements of the array
Output
If B wins, print “Right <absolute difference>”
If A wins, print “Wrong <absolute difference>”
If It’s a tie, print “Both are Right”
Refer Examples section for better understanding.
Time Limit
1
Examples
Example 1
Input
8 5 -2
4 5 6 1 2 7 8 9
Output
Wrong 2
Explanation
Here we have given N = 8, W = 5, D = -2
A will maximize the sum of elements of the array using window size 5. Whereas B will maximize the sum of elements of the array using window size 3 (5-2).
Using logic as depicted above A will get the max sum as 41 and B will get the max sum as 39. The absolute difference is 41 - 39 = 2.
Hence, output will be: Wrong 2
Example 2
Input
9 2 2
4 5 6 1 2 3 7 8 9
Output
Right 10
Explanation
Here we have given N = 9, W = 2, D = 2
A will maximize the sum of elements of the array using window size 2. Whereas B will maximize the sum of elements of the array using window size 4 (2+2).
Using logic as depicted above A will get the max sum as 33 and B will get the max sum as 43. The absolute difference is 43 - 33 = 10.
Hence, output will be: Right 10
Example 3
Input
10 9 -3
4 5 6 3 2 3 7 8 9 2
Output
Both are right
Explanation
Here we have given N = 10, W = 9, D = -3
A will maximize the sum of elements of the array using window size 9. Whereas B will maximize the sum of elements of the array using window size 6 (9-3).
Using logic as depicted above A will get the max sum as 47 and B will get the max sum as 47. The absolute difference is 47 - 47 = 0.
Hence, output will be: Both are right
Click Here Please Subscribe to YT Channel Link For Amazon & Google Hiring is Posted There (More will be posted)
Max Sum
ReplyDeleteAns
#include
ReplyDelete//#include
#define ll long long
#define zeus ios_base::sync_with_stdio(false);cin.tie(NULL);
#define w(t) ll t; cin>>t; while(t--)
#define nikallawde(x) {cout<=0;i--)
#define Rep(i,a,b) for(ll i=b;i>=a;i--)
#define all(a) (a).begin(), (a).end()
#define pb push_back;
#define F first
#define S second
using namespace std;
//using namespace boost::multiprecision;
typedef pair pii;
typedef pair pl;
typedef vector vi;
typedef vector vl;
ll m=1e9+7;
#define INF 1e9
string yes={'Y','E','S'},no={'N','O'};
ll po(ll a, ll x, ll m) { if (x == 0) {return 1;} ll ans = 1; ll k = 1; while (k <= x) {if (x & k) {ans = ((ans * a) % m);} k <<= 1; a *= a; a %= m; } return ans; }
int query(int *tree, int index, int s, int e, int qs, int qe) {
if (qs > e || qe < s) {
return INT_MAX;
}
if (qs <= s && qe >= e) {
return tree[index];
}
int mid = (s + e) / 2;
int leftAns = query(tree, 2 * index, s, mid, qs, qe);
int rightAns = query(tree, 2 * index + 1, mid + 1, e, qs, qe);
return min(leftAns, rightAns);
}
void updateNode(int *tree, int index, int s, int e, int i, int inc) {
if (i < s || i > e) {
return;
}
if (s == e) {
tree[index] += inc;
return;
}
int mid = (s + e) / 2;
updateNode(tree, 2 * index, s, mid, i, inc);
updateNode(tree, 2 * index + 1, mid + 1, e, i, inc);
tree[index] = min(tree[2 * index], tree[2 * index + 1]);
return;
}
void buildTree(int *tree, int *a, int index, int s, int e) {
if (s == e) {
tree[index] = a[s];
return;
}
if (s > e) {
return;
}
int mid = (s + e) / 2;
buildTree(tree, a, 2 * index, s, mid);
buildTree(tree, a, 2 * index + 1, mid + 1, e);
tree[index] = min(tree[2 * index], tree[2 * index + 1]);
}
void solve(){
int n, w, d;
cin >> n >> w >> d;
if (n == 0) {
cout << "Both are right";
return;
}
int a[n];
f(i, n) {
cin >> a[i];
}
int dp2[n];
int tot = 0;
f(i, n) {
dp2[i] = a[i];
tot += a[i];
}
int t[4 * n + 1];
buildTree(t, a, 1, 0, n - 1);
int k = w + 1;
for (int i = k; i < n; i++) {
int qs = query(t, 1, 0, n - 1, i - k, i - 1);
updateNode(t, 1, 0, n - 1, i, qs);
}
int ans1;
if (k <= n)
ans1 = query(t, 1, 0, n - 1, n - k, n - 1);
else
ans1 = 0;
k = w + d + 1;
int t2[4 * n + 1];
buildTree(t2, a, 1, 0, n - 1);
rep(i,k,n) {
int qs = query(t2, 1, 0, n - 1, i - k, i - 1);
//dp2[i] += qs;
updateNode(t2, 1, 0, n - 1, i, qs);
}
int ans2;
if (k <= n)
ans2 = query(t2, 1, 0, n - 1, n - k, n - 1);
else
ans2 = 0 ;
ans1 = tot - ans1;
ans2 = tot - ans2;
int res=abs(ans1 - ans2);
if (ans1 > ans2) {
cout << "Wrong "< ans1) {
cout << "Right "<<res;
} else {
cout << "Both are right";
}
}
int main()
{
zeus
// w(t){
solve();
cout<<"\n";
//}
return 0;
}