You will find all TCS CodeVita Coding Solutions here !
Sai’s Mini Project
Problem Description
Sai is working on a mini project where he needs to handle various tasks related to a bank account. This includes 6 operations viz., read, credit, debit, abort, rollback and commit. The operation semantics are explained below.
read – read and print the balance in the account
credit – money credited to the account
debit – money debited from the account
abort X – the Xth transaction from the beginning is aborted (cancelled). Note that you can’t abort the transactions once they are committed. Only credit and debit operations are counted as transactions
For understanding abort, lets understand the example below –
credit 1000
commit
abort 1
This abort cannot be done since the transaction has already been committed.
rollback X – rollback the Xth commit. In this case, the account balance will be automatically updated to what it was, right after the Xth commit.
commit – the changes are saved permanently and cannot be undone using an abort command.
The credit, debit, abort and rollback operations will always be followed by a positive integer, whereas read and commit operations have no such operand.
Given the initial balance and a sequence of operations performed in order, determine the resulting output.
Constraints
1 <= initial amount <= 1000
1 <= Number of operations (N) <= 50
Current account balance will always be 0 or a positive value. It can never be negative.
The integer following “abort” and “rollback” will be at least 1 and will not exceed the total number of transactions and commits up to that point, respectively.
Input
The first line contains an integer denoting the initial balance of the account.
Second line consists of an integer N denoting the number of operations performed.
The subsequent N lines will contain operations following the above syntaxes.
Output
Output the account balance each time a read statement is encountered.
Time Limit (secs) 1
Examples
Example 1
Input
90
8
read
credit 10
debit 12
debit 8
credit 7
abort 1
commit
read
Output
90
77
Explanation
Initial balance: 90
Operation 1 – Read, prints the account balance i.e., 90
Operation 2 – Credit 10, Result: Balance increases by 10. New balance: 100
Operation 3 – Debit 12, Result: Balance decreases by 12. New balance: 88
Operation 4 – Debit 8, Result: Balance decreases by 8. New balance: 80
Operation 5 – Credit 7, Result: Balance increases by 7. New balance: 87
Operation 6 – Abort 1, this means undoing the changes made by the 1st transaction (the credit of 10). So, the account balance will become 77
Operation 7 – Commit, this commits all previous changes made. Account balance will be updated as 77
Operation 8 – Read, prints the account balance i.e., 77
Example 2
Input
43
10
credit 12
debit 10
commit
abort 1
read
credit 30
debit 4
rollback 1
commit
read
Output
45
45
Explanation
Initial balance: 43
Operation 1 – Credit 12, Result: Balance increases by 12. New balance: 55
Operation 2 – Debit 10, Result: Balance decreases by 10. New balance: 45
Operation 3 – Commit, this commits all changes made so far. Account balance will become 45.
Operation 4 – Abort 1, this means undoing the changes made by the 1st transaction. Since the changes of 1st transaction has already been committed it’s impossible to abort it. Hence, the account balance remains same.
Operation 5 – Read, prints the account balance i.e., 45
Operation 6 – Credit 30, Result: Balance increases by 30. New balance: 75
Operation 7 – Debit 4, Result: Balance decreases by 4. New balance: 71
Operation 8 – Rollback 1, this means the account balance will be rolled back to what it was, after commit 1 i.e., 45. Refer Operation 3 which is the 1st commit.
Operation 9 – Commit, this commits all changes made since the last commit. Account balance will be updated as 45
Operation 10 – Read, prints the account balance i.e., 45
Sai Mini Project
100% Correct Code ✅
C++
TCS CodeVita Zone 1
https://telegram.me/+_hn3cBQVbGliYTI9
#include<bits/stdc++.h>
using namespace std;
int main() {
int b, n, cb = 0;
cin >> b >> n;
vector<int> t;
vector<int> cs = {b};
// Telegram – @PLACEMENTLELO
for (int i = 0; i < n; i++) {
string placementlelo;
cin >> placementlelo;
if (placementlelo == “read”) {
cout << cs[cb] << endl;
}
// Telegram – @PLACEMENTLELO
else if (placementlelo == “credit” || placementlelo == “debit”) {
int x;
cin >> x;
if (placementlelo == “credit”) cs[cb] += x;
else cs[cb] -= x;
t.push_back(placementlelo == “credit” ? x : -x);
}
// Telegram – @PLACEMENTLELO
else if (placementlelo == “abort”) {
int x;
cin >> x;
if (x <= t.size()) cs[cb] -= t[x – 1], t[x – 1] = 0;
}
// Telegram – @PLACEMENTLELO
else if (placementlelo == “rollback”) {
int x;
cin >> x;
cb = x – 1;
cs.resize(cb + 1);
}
// Telegram – @PLACEMENTLELO
else if (placementlelo == “commit”) {
cs.push_back(cs[cb]);
cb++;
}
}
return 0;
}
Sai Mini Project
100% Correct Code ✅
C++
TCS CodeVita Zone 1
https://telegram.me/+_hn3cBQVbGliYTI9
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
Faulty Snakes and Ladders
Problem Description
Chaitra is playing a game of Snakes and Ladders when she notices Tara approaching. In this game, players start at the beginning which is 1 and aim to reach the end, which is 100, with snakes sending them back to lower-numbered cells and ladders advancing them to higher ones.
A typical 10*10 Snakes and Ladders board looks like the one shown below.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@7249dadf:image1.jpeg
Here, the cell 40 has a snake it. Landing in it will demote one to the cell numbered 3. Likewise, the cell 13 has a ladder in it, landing in it will promote one to the cell numbered 46. You need to travel in ascending order of the numbers on the board from start to end. Initially you will be in the cell number 1.
To play a trick on Tara, Chaitra decides to switch a snake with a ladder, or vice versa. Up until Tara arrived, Chaitra had carefully recorded the outcome of each roll of the die and the cell in which she is currently landed.
In the path Chaitra travelled, the ladder or snake she switched might or might not have an impact.
Chaitra presented Tara with a challenge: Given positions of all the snakes and ladders after switching, the outcomes of each die roll, and the position Chaitra ultimately reached, Tara must identify which snake or ladder was altered. If the switch did not impact Chaitra’s path, she should print “Not affected”; if the given dice rolls make the position unreachable even after switching any of the snakes and ladders, she should print “Not reachable”; otherwise, she should print the switched cell and its new destination.
Constraints
1 <= N <= 10
1 <= Number of dice rolls <= 50
Board will be of fixed size i.e., 10*10 and will consist of unique values from 1 to 100.
One cell may only have a snake or a ladder.
There won’t be any snakes or ladders in the cell number 1.
There may be at most one faulty snake or ladder for the given inputs.
One can’t stay in a cell which have a snake or ladder in it.
Input
First line consists of an integer N, denoting the number of snakes and ladders in the given board.
The next N lines contain two space-separated values representing the cell numbers where a promotion or demotion occurred due to the presence of snakes or ladders.
Next contains die inputs separated by a space.
Last line consists of a single integer denoting the position where Chaitra reached.
Output
Output will be any of the following.
“Not reachable” – If the position is not reachable even after all the possible switching or if it’s not a stable position (i.e., it has ladder or a snake in it)
“Not affected” – If the position is reachable without switching any of the snakes and ladders.
Print name of the thing switched (either snake or ladder), which cell it belongs to, where it promotes/demotes when landed in a single line separated by space.
Time Limit (secs)
1
Examples
Example 1
Input
7
16 9
38 6
45 68
63 23
75 99
79 22
98 2
3 2 5 3 4 4 1 2 3
85
Output
Ladder 22 79
Explanation
According to the given input, cell 79 is having a snake in it demoting to 22. Switch it to a ladder which promotes to 79.
Initially, Chaitra is in cell number 1. Processing dice roll values one after other –
3 – she will land in cell number 4
2 – she will land in cell number 6
5 – she will land in cell number 11
3 – she will land in cell number 14
4 – she will land in cell number 18
4 – she will land in cell number 22. There is a ladder which promotes to 79
1 – she will land in cell number 80
2 – she will land in cell number 82
3 – she will land in cell number 85
Therefore, a ladder needs to be added at cell 22 that promotes to the cell 79. Hence print Ladder 22 79 as output.
Example 2
Input
8
18 2
24 63
45 80
59 14
62 22
83 99
97 7
90 11
6 6 5 1 2 3 4 5 6 1 2
65
Output
Not affected
Explanation
Starting from cell 1, the given dice rolls allow us to reach cell 5. Therefore, we concluded that the snake or ladder Chaitra switched did not impact the path she travelled.
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
Common Cube Faces
Problem Description
Vedica got a challenging homework assignment from her teacher today, which involves arranging cubes on a desk.
There are initially Q+1 cubes, numbered from 1 to Q+1, and she will select the cubes in numerical order. She has been given Q queries, where each query is in the form “cubeA cubeB direction”, indicating that cubeB is placed on the specified direction of cubeA. A side is considered common for two cubes if it is shared by both cubes, meaning they touch or are adjacent to each other along that entire side.
In 2D, a cube will be basically having four directions viz., top, down, left, right, as shown below.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@687a762c:image1.png
The input queries are to be applied sequentially to form the whole structure. Only after all the queries are processed will the final structure emerge. Based on final structure, Vedica’s task is to determine the number of common sides in the structure. Can you help Vedica with this?
One thing to keep in mind is that the input queries can overwrite each other. This simply means that the later query will overwrite the previous query in case they are dealing with same cubes and same direction. For example, if query is 1 3 left – it means 3 is to the left of 1. If a later query is 1 10 left, then it is easy to see that cube 10 has displaced cube 3 and now cube 10 is to the left of cube 1. These semantics must be factored in to compute the number of common sides.
Constraints
1 <= Q <= 50
No duplicate queries.
Input
First line consists of an integer Q denoting the number of queries.
The following Q lines each contain three space delimited elements, in format cubeA cubeB direction.
Output
Output a single integer representing the total number of common cube faces in the entire arrangement.
Time Limit (secs)
1
Examples
Example 1
Input
8
6 7 right
1 3 left
7 8 top
1 4 down
4 5 right
5 6 down
1 2 top
8 9 left
Output
8
Explanation
The above input when arranged looks like below.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@687a762c:image2.png
From the image, we can find that the number of common cube faces is 8. Hence, output is 8.
Example 2
Input
3
1 2 right
3 4 left
2 3 down
Output
4
Explanation
The above input when arranged looks like below.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@687a762c:image3.png
From the image, we can find that the number of common cube faces is 4. Hence, output is 4.
Example 3
Input
5
3 4 top
1 2 right
4 5 down
1 3 top
2 6 left
Output
3
Explanation
The above input when arranged looks like below.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@687a762c:image4.png
From the image, we can find that the number of common cube faces is 3. Hence, output is 3.
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
Frankenstein Coding Question –
“Muahahaha! No one can stop me from creating the elixir of life,” -Frankenstein. Frankenstein is an alchemist who is always striving to craft the elixir of life.
The elixir of life grants immortality to whoever drinks it. In his attempts to brew the elixir of life, Frankenstein combines numerous ingredients and potions, believing he will eventually succeed. However, he has never succeeded thus far.
But each time he brews something, he meticulously notes the ingredients. For example, when he combined snake fangs and wolfsbane, he discovered the awakening potion. In his notes, he recorded the recipe as follows:
awakening = snakefangs + wolfbane
Similarly, when three ingredients were required, he noted the recipe in his notes as
thunderstorm = rain + wind + lightening
In general, the recipe would be
Potion 1 = Ingredient 1 + Ingredient 2
Potion 2 = Ingredient 1 + Ingredient 2 + Ingredient 3
Potion 3 = Ingredient 1 + Ingredient 2 + Ingredient 3 + Ingredient 4
and so on …
Every brew requires magical orbs, which are mythical energy balls. The number of magical orbs needed for a recipe is equal to the number of ingredients minus one.
A recipe of a potion includes multiple ingredients. An ingredient can be an item or a potion. Items are readily available things and while potions are brewed from items. In his notes, the resultant is always a potion.
He observed that sometimes the same potion can be created using different recipes, with some requiring fewer magical orbs. Given a potion and his notes, determine the minimum number of magical orbs needed to create that potion.
Constraints
0 < N < 20
Input
First line contains an integer N representing the number of recipes he noted.
Next N lines contain string without space representing the recipes in his notes as mentioned above.
Last line contains a single string representing the potion that he needs to brew.
Output
Print single integer representing the minimum number of magical orbs required.
Time Limit (secs)
1
Examples
Example1
Input
4
awakening=snakefangs+wolfbane
veritaserum=snakefangs+awakening
dragontonic=snakefangs+velarin
dragontonic=awakening+veritaserum
dragontonic
Output
1
Explanation
Based on the input, we need to determine the minimum number of magical orbs required to brew dragontonic. According to the notes, there are two recipes available for brewing dragontonic.
The two ways of brewing dragontonic are, dragontonic=awakening+veritaserum and dragontonic=snakefangs+velarin
The recipe with awakening, veritaserum where awakening is a potion that must be brewed first. Brewing awakening requires 1 magical orb and brewing it with veritaserum requires one additional magical orb, totaling 2 magical orbs.
Since second recipe of dragontonic requires only 1 magical orb which is the minimum number of orbs required, hence print 1 as output.
Example 2
Input
6
oculus=thunderbrew+jellfish
felix=thunderbrew+pumpkin
wigenweld=thunderbrew+ladybug
wigenweld=oculus+felix
thunderbrew=pumpkin+firefly
maxima=pumpkin+ladybug
wigenweld
Output
2
Explanation
To brew wigenweld with the minimum number of orbs, he first brewed thunderbrew, which requires 1 orb. Then, brewing thunderbrew with ladybug required an additional orb, resulting in wigenweld. Therefore, a total of 2 orbs were needed, which is the minimum requirement, hence the output is 2.
Frankenstein Code
Java
TCS CodeVita Zone 1
https://telegram.me/+_hn3cBQVbGliYTI9
import java.util.*;
public class FrankensteinPotionBrewer {
private static Map<String, List<List<String>>> recipeBook = new HashMap<>();
// Telegram – @PLACEMENTLELO
private static Map<String, Integer> memo = new HashMap<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
// Telegram – @PLACEMENTLELO
for (int i = 0; i < n; i++) {
String line = scanner.nextLine();
String[] parts = line.split(“=”);
String potion = parts[0];
String[] ingredients = parts[1].split(“\\+”);
// Telegram – @PLACEMENTLELO
recipeBook.putIfAbsent(potion, new ArrayList<>());
recipeBook.get(potion).add(Arrays.asList(ingredients));
}
String targetPotion = scanner.nextLine();
scanner.close();
int result = minOrbsToBrew(targetPotion);
System.out.println(result);
}
private static int minOrbsToBrew(String potion) {
if (!recipeBook.containsKey(potion)) {
return 0;
}
// Telegram – @PLACEMENTLELO
if (memo.containsKey(potion)) {
return memo.get(potion);
}
int placementlelo = Integer.MAX_VALUE;
for (List<String> recipe : recipeBook.get(potion)) {
int orbsRequired = recipe.size() – 1;
for (String ingredient : recipe) {
orbsRequired += minOrbsToBrew(ingredient);
}
// Telegram – @PLACEMENTLELO
placementlelo = Math.min(placementlelo, orbsRequired);
}
memo.put(potion, placementlelo);
return placementlelo;
}
}
Frankenstein Code
Java
TCS CodeVita Zone 1
https://telegram.me/+_hn3cBQVbGliYTI9
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
Formatting Software
Problem Description
Vivek is developing software that takes a set of numerical instructions, processes them, and formats them as required.
Vivek is working on a big project, and he asked you to implement a software that takes a set of numerical information in the form of r x c matrices, processes them, and formats them according to the given instructions. The instructions consist of multiple lines, with each line containing one or more integer values. Each integer specifies which matrix should be printed.
For example, if the instructions are like below,
4
1 2 3
which says that you should first print matrix number 4 from the information provided. Then, on the subsequent lines, you need to print matrices 1, 2, and 3 sequentially.
Given N, representing the number of matrices, and two additional integers r and c representing the number of rows and columns in each matrix, along with the N matrices provided contiguously over r lines, and in the decribed format, print the formatted information.
(Refer Examples section for better understanding of the input)
Constraints
1 <= N <= 10
1 <= r, c <= 10
1 <= numbers in the matrix <= 100
1 <= number of matrices in the instructions <= 20
Matrices are numbered from 1 to N; thus, the instructions will include only numbers within this range. Note that numbers may be repeated.
Input
First line consists of an integer N, denoting the number of matrices
Second line consists of two space separated integers denoting the number of rows and columns in each matrix.
The next r lines contain the N matrices, each of size r × c, listed sequentially. Each matrix will have integers separated by spaces, and consecutive matrices will be separated by a space as well.
Remaining lines represent the instructions of how the information should be formatted.
Output
Print the formatted information following the given instructions.
Time Limit (secs)
1
Examples
Example 1
Input
7
1 3
5 4 12 11 19 3 0 15 7 1 2 3 4 5 6 10 9 8 3 60 71
5
7 1 3
2 4 5
3 6
4
Output
4 5 6
3 60 71 5 4 12 0 15 7
11 19 3 1 2 3 4 5 6
0 15 7 10 9 8
1 2 3
Explanation
If you split the given data into 1×3 submatrices and print them in the specified format, you will obtain the output. Let’s go over the input processing.
Line 4 i.e. input 5 asks to print matrix number 5. Output 4 5 6 corresponds to this input.
Line 5 i.e. input 7 1 3 asks to print matrices 7, 1 and 3. Output 3 60 71 5 4 12 0 15 7 corresponds to this input.
Similarly processing line number 6, 7 and 8 of the input, we obtain lines 3, 4 and 5 of the output.
Example 2
Input
4
2 3
1 2 3 4 5 6 7 8 9 10 11 12
12 11 10 9 8 7 6 5 4 3 2 1
1 2 3
4 1
2 3
3
1 4
Output
1 2 3 4 5 6 7 8 9
12 11 10 9 8 7 6 5 4
10 11 12 1 2 3
3 2 1 12 11 10
4 5 6 7 8 9
9 8 7 6 5 4
7 8 9
6 5 4
1 2 3 10 11 12
12 11 10 3 2 1
Explanation
If you split the given data into 2×3 submatrices and print them in the specified format, you will obtain the output. Let’s go over the input processing.
Line 5 i.e. input 1 2 3 asks to print matrices 1, 2 and 3. Output lines 1 and 2 corresponds to this input.
Line 6 i.e. input 4 1 asks to print matrices 4 and 1. Output lines 3 and 4 corresponds to this input.
Similarly processing line number 7, 8 and 9 of the input, we obtain lines the remaining lines of the output.
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
JustifyWords
Problem Description
Given a list of K words and integers N and M, you are asked to arrange the words into N lines following the below rules.
Each line can contain no more than M letters.
Each word should present entirely on one line.
If multiple words are on a line, they should be separated by a single space.
Find the maximum number of words you can arrange in the given lines of length M.
Constraints
0 < K < 25
0 < N < 10
0 < M < 10
Words will be having only lowercase alphabets.
Input
First line consists of an integer K denoting the total number of words.
Next K lines consist of words.
Last line consists of two space separated integers denoting the values of N and M.
Output
Print a single integer denoting the maximum number of words that can be arranged into the N lines.
Time Limit (secs)
1
Examples
Example 1
Input
8
i
hello
how
going
u
help
hmm
5 5
Output
7
Explanation
8 words need to be arranged in 5 lines each of length 5 characters.
One way to arrange the words to fit maximum words is as follows.
how_i
going
u_hmm
help_
hello_
where _ represents empty space. 7 words can be fitted. And that’s the maximum possible. There could be other combinations i.e. [hello, help , going ,i u,hmm] etc., but we are interested in maximum number of words being accommodated in N lines each of length M.
Example 2
Input
6
a
is
b
be
it
a
5 4
Output
6
Explanation
6 words need to be arranged in 5 lines each of length 4 characters.
One way to arrange the words to fit maximum words is as follows.
a_is
b_be
it_a
____
where _ represents empty space. Here entire last line is empty. 6 words can be fitted and that’s the maximum.
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
BusCount
Problem Description
As the Transportation In-Charge of a reputed company, your responsibility is to ensure that buses are available for every employee and that they arrive on time.
Since pandemic restrictions have been lifted, but not completely, the number of people allowed on buses is still limited. Employees have started visiting the office regularly. You are given an M*M matrix, which represents the distance between each location. The value in the ith row and jth column represents the distance between the ith place and the jth place. Assume that all locations are connected by roads and that the first location is the office. The distance between the ith place and the jth place is the same as the distance between the jth place and the ith place. The top left element of this matrix is (0, 0) and is the Office location.
The number of people boarding the bus at each location is known a priori and is a part of the input.
Given the number of people that a bus can accommodate at one time, post restrictions, determine the number of buses required to pick up all employees. A bus can start from any location but must take only the shortest path from that location to the office. The bus can pick up employees at locations along its route. Assume that there is only one shortest route between the office and each remaining location.
Constraints
1 < M < 12
0 < 300 < Distance between locations
0 < 500 < Total number of employees
Input
First line consists of a single integer M, representing the number of locations including office.
Next M lines consist of M integers separated by space representing the distance matrix.
Next line consists of M-1 space separated integers representing the employees boarding at each corresponding location.
Last line consists of an integer representing the number of people that can travel in the bus at one time.
Output
Print a single integer representing the minimum number of buses required to pick up all employees.
Time Limit (secs)
1
Examples
Example 1
Input
4
0 10 10 30
10 0 30 20
10 30 0 10
30 20 10 0
23 52 11
25
Output
4
Explanation
The below diagram represents the above input.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@2f94c4db:image1.png
Based on the input, there are four locations, which we can be denoted as 0, 1, 2, and 3. The first location is the office, represented as 0 (visualized as “Off”).
The shortest paths between individual location and office are,
Location 1-> office
Location 2-> office
Location 3-> Location 2-> office
The number of buses required will be 4: one bus from location 1, two buses from location 2, and one bus from location 3. The two buses starting at location 2 will pick up 50 people from there, and the remaining 2 people will board the bus coming from location 3.
Example 2
Input
5
0 10 10 60 60
10 0 30 10 10
10 30 0 30 30
60 10 30 0 30
60 10 30 30 0
15 15 15 15
25
Output
3
Explanation
For the given input the visualization of complete paths looks dense. Hence below image depicts only the shortest path from each location to office.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@2f94c4db:image2.png
Three buses will originate from locations 2, 3, and 4 respectively. The buses starting from locations 3 and 4 will need to travel through location 1. Since they have enough seats to pick up the employees from location 1, three buses are sufficient. Therefore, the output 3.
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
Route the balls Coding Question –
Feeling bored at home, Lulu decided to play a mobile game called “Route The Balls”. In the game, a source continuously releases different coloured balls, and the objective is to sort them into their corresponding-coloured buckets.
Between the source and the buckets, there are several junctions. The source, buckets are also considered as junctions. Initially, all the paths will be closed. At each junction, when multiple paths are present, only one path can be opened at a time. From a given junction, if a path is opened, any other paths that is currently open from the junction will be automatically closed.
For instance, if there exists a T-shaped junction, refer to the diagram below.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@275fe372:image1.png
The initial ball is blue, and it needs to be directed towards the blue bucket positioned below. Initially, all sides of the paths are closed. Therefore, you open the downwards path (source – blue bucket) to allow the ball to flow into blue bucket. The subsequent ball is yellow, requiring it to be directed towards the yellow bucket situated to the right. To achieve this, you open the path on the right side (source – yellow bucket), automatically closing the previous downward opening. Hence, the junction was opened twice in total.
Given the network of junctions, their connections to each other, and the sequence of the balls, determine the total number of junction openings required to guide the balls into their respective buckets.
Constraints
1 <= number of balls <= 50
1 <= number of junctions <= 50
1 <= length of name of colours and junctions <= 20
There will always be a single source.
There will be only one bucket for each colour.
No balls will be used to route from the source if the corresponding-coloured bucket is not available.
Name of the junctions will consist of lower-case alphabets and digits.
Input
First line consists of N, denoting the number of lines representing the routes structure of the game.
In the following N lines, each line contains space-separated elements. The first element denotes a junction, while the subsequent elements indicate its connections to other junctions. Note that the paths are unidirected from source to buckets.
The last line comprises the colours of the balls originating from the source, separated by spaces.
Output
Print the total number of paths you need to open to route all the balls into respective buckets.
Time Limit (secs)
1
Examples
Example 1
Input
6
source jun1 jun3
jun1 jun2
jun2 jun4 jun6
jun4 blue
jun6 pink yellow
jun3 red
blue yellow red pink blue
Output
11
Explanation
The given input, when visualised looks below.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@275fe372:image2.png
Initially, every path is closed.
First ball is blue coloured. For this, to land in blue bucket, open the paths, source – jun1, jun1 – jun2, jun2 – jun4, jun4 – blue. Total number of paths opened = 4
Next ball is yellow coloured. The paths from source – jun2 is already open. Open the paths jun2 – jun6 and jun6 – yellow. Total number of paths opened = 4 + 2 = 6
Next ball is red coloured. For this, open the paths source – jun3, jun3 – red. Note that the path which was open earlier from source (source – jun1) will be closed. Total number of paths opened = 6 + 2 = 8
Next ball is pink coloured. For this, open the paths source – jun1 and jun6 – pink. Note that the path which was open earlier from source (source – jun3) will be closed. The paths from jun1 – jun2, jun2 – jun6 are already open. Total number of paths opened = 8 + 2 = 10
The last ball is blue coloured. The paths source – jun1, jun1 – jun2, jun4 – blue is already open. Open the path jun2 – jun4. Total number of paths opened = 10 + 1 = 11
Hence, print 11.
Example 2
Input
4
source jun1
jun1 violet jun2 jun3
jun2 red
jun3 green yellow
green yellow red green green violet
Output
9
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
Equations Puzzle
Problem Description
Kajol enjoys solving math puzzles, and one day she encountered an equation puzzle in the newspaper, which she decided to tackle. The puzzle includes two equations of the form A1x + B1y + C1z + D1w ≤ N1 and A2x + B2y + C2z + D2w ≤ N2 with given coefficients, meaning that the result after substituting the variables must not exceed N1 and N2 respectively.
Additionally, there is another constraint for each equation: the sum of the variables (x + y + z + w) must not exceed the value R given as a part of input.
The challenge is to determine the count of all possible results that can be obtained by substituting values into the variables in both equations, where N1 equal to N2, while adhering to this sum constraint individually for each equation. Refer examples section for better understanding.
Constraints
1 <= A, B, C, D <= 1000
1 <= N <= 1000
1 <= R <= 500
The values of variables can be 0.
Input
First line consists of a string representing the first equation.
Second line consists of a string representing the second equation.
Third line consists of an integer denoting R.
Output
Print a single integer denoting the count of all possible results that can be obtained by substituting values into the variables in both equations while adhering to this sum constraint individually for each equation.
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
Magic Stars Intensity
Problem Description
In the 1930s, King Krishnadevaraya, who had a great love for magic, kept a personal magician in his palace. Whenever he desired to witness a magical performance, he would command the magician to entertain him with his craft.
The magician constantly aimed to impress the king with new magical tricks. One day, he cast magical lines across the vast expanse of the palace floor, which was covered in tiles. Each tile is a square with sides of 1 unit length; thus, you can say the palace floor resembles a 2d plane.
Since these are magical lines, when they are drawn, they only align with the edges of the tiles or pass through their corners.
When these magical lines intersect, they create points of light called n-stars, where n ranges from 2 to 8. Each n-star forms when n lines intersect, and all these stars generate light.
For calculating the intensity of the star, there exist two cases which are explained below.
Consider below cases carefully.
Case 1 – The line is only one side to the star i.e., the star won’t cut the line into two parts.
Consider the lines (4, 4, 4, 2), (4, 4, 7, 7) and (4, 4, 3, 5). These lines are intersecting at the point (4, 4). Since three lines intersect at a point, they form a star known as a 3-star.
Now, the intensity of the star = minimum (the number of cells these 3 lines are touching from the point of star formation to the last) = minimum (2, 3, 1) = 1
So, the intensity of this star will be 1.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@6f6a7463:image1.png
Case 2 – The line is two sides to the star i.e., the star cuts the line into two parts.
Consider the lines (3, 3, 7, 7), (3, 5, 6,2) and (4, 2, 4, 6). These lines are intersecting at the point (4, 4). Since three lines intersect at a point, they form a star known as a 3-star.
In this case, the intensity of the star = minimum (the number of cells these 3 lines are touching from the point of star formation to the last on both sides) = minimum (1, 1, 2, 2, 3, 2) = 1
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@6f6a7463:image2.png
Given N lines and the type of star for which you need to determine the intensity, calculate the intensity for all such stars according to the cases described and print their total sum. If no stars of the specified type are present, print 0.
Constraints
1 <= N <= 50
2 <= K <= 8
0 <= x, y <= 100
Lines will not overlap either partially or completely.
Input
First line consists of an integer N, denoting the number of magical lines the magician casted.
The next N lines contain four space-separated integers each, representing the x and y coordinates of the starting and ending points of the magical lines.
The last line consists of an integer K denoting the type of star for which you need to calculate the intensity.
Output
Print a single integer representing the total intensity of all stars of the specified type given in the input. If no such stars are present, print 0.
Time Limit (secs)
1
Examples
Example 1
Input
7
4 2 4 6
6 5 6 7
1 3 3 5
3 5 4 4
3 3 7 7
2 2 2 5
4 4 5 3
4
Output
1
Explanation
The lines given in the above input are represented in the below figure.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@6f6a7463:image3.png
Here, the star formed at (4, 4) is a 4-star because it is created by 4 lines. According to given cases, the intensity of this star is minimum (2, 1, 1, 2, 1, 3), resulting in an intensity of 1. Since there is only one 4-star, the output is 1.
Example 2
Input
5
1 1 8 8
3 1 3 4
5 1 5 8
1 3 3 3
7 2 7 9
2
Output
4
Explanation
The lines given in the above input are represented in the below figure.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@6f6a7463:image4.png
There are two 2-stars formed at the positions (5, 5) and (7, 7). The intensity of star at (5, 5) is minimum (4, 3, 3, 4) which is 3 and the intensity of star at (7, 7) is minimum (1, 2, 6, 5) which is 1. So, the total intensity of all 2-stars will be 3+1 = 4.
TCS CodeVita Zone 1 Coding Solutions are uploaded here – https://telegram.me/+_hn3cBQVbGliYTI9
