TCS Codevita : Break The Friendship

Problem : Break The Friendship

In a class room everyone is very friendly and has bonded with others in a short span of time. During the exams, students will sit along with their friends and will write the exams, which actually resulted in the finding that only a few members in the batch are good at studies and others are not. After getting several complaints from the staff members, the Principal has agreed to change the sitting pattern during the exams for which she has formed a committee. Using a spy, committee was able to get a list of close friends for all the students in the class. Now using this list they want to identify two groups of people such that a person in one group must not be a friend to any other in the same group. Your task is to help the committee. 

Input Format:

Input consists of two parts, viz. 

1.      First Line contains, number of students in the class room (N) and number of friendship connections (M)

2.      Next M line contains a list that represents two integers i and j, which represents that i and j are friends

Output Format:

Print "Yes" if the committee can divide the students in two groups of people, else print "No".

Constraints:

1 <= N <= 50

1 <= M <= N * (N-1)/2

1 <= I, j <= N

Sample Input and Output

SNo.	Input	Output
1	4 3 1 2 1 3 2 4	Yes

Solution in c:

#include<stdio.h>

int main()

{

  int i,j,n,temp,m,a[50];

  int f=0;

scanf("%d %d",&n,&m);

if((n<=50)&&(m<=n*(n-1)/2))

{

for(i=1;i<=(m*2);i++)

{

scanf("%d",&a[i]);

}

for(i=1;i<=m;i++)

{

for(j=i+1;j<=m;j++)

{

    if((i<=n)&&(j<=n))

{

 temp=a[i];

 if(temp==a[j])

{

f=1;

}

}

}

}

if(f==1)

{

printf("Yes");

}

else

{

printf("No");

}

}

return 0;

}

TCS Codevita : Stone Game - Remove Last

Problem : Stone Game - Remove Last

Alice and Bob are playing a game called "Stone Game". Stone game is a two-player game. Let N be the total number of stones. In each turn, a player can remove 1, 2 or 3 stones. The player who picks the last stone, loses. They follow the "Ladies First" norm. Hence Alice is always the one to make the first move. Your task is to find out whether Alice can win, if both play the game optimally.

Input Format:

First line starts with T, which is the number of test cases. Each test case will contain N number of stones.

Output Format:

Print "Yes" in the case Alice can win, else prints "No".

Constraints:

1<=T<=10

1<=N<=10000

Sample Input and Output

SNo.	Input	Output
1	2 1 3	No Yes

Solution in C++ :

#include <iostream>

using namespace std;

int main() {

int nn, j,aa;

  cin >> aa;

while(aa--)

{

cin >> nn;

int st[nn+1];

for(j = 0; j <= nn; j++)

st[j] = 0;

st[1] = 0;

st[2] = 1;

st[3] = 1;

for(j = 4; j <= nn; j++)

{

if(st[j-1] == 0 || st[j-2] == 0 || st[j-3]==0)

st[j] = 1;

else

st[j] = 0;

}

if(st[nn] == 1)

cout << "Yes\n";

else

cout << "No\n";

}

return 0;

}

TCS Codevita : Hotel trip

roblem : Hotel trip

Tom, Dick and Harry go to a restaurant. Each of them has a certain amount of money. When their monies are pooled they discover they have S Rs. Next, they start going through the menu card to choose items they would like to order.

Your task is to help them find out how many different menu item combinations they can order. Since there can be many menu items with the same price, we are interested only in unique price combinations. Refer output specifications and examples to get a better understanding. 

Input Format:

First line contains N positive integers delimited by space, corresponding to prices of N menu items
Second line contains an integer S corresponding to the amount of money pooled between them 

Output Format: 

1.    Print all possible combinations of item prices whose sum is equal to S. Enclose each such combination in square brackets [ ]. Elements should be separated by, followed by a space character.

2.    Item price combinations must be unique (See example 2 to understand this better)

3.    If more than one combinations exists, then the print order should be as follows 

a.     Combinations should be printed in descending order item prices

b.    Two combinations can be differentiated by first comparing their costliest, followed by second costliest, and followed by the next costliest item, so on and so forth. Refer example outputs for better understanding of print order.

Constraints:

P_i > 0 ; where i = 1 to N and Pi denotes the price of the i^th item

S > 0

Sample Input and Output

SNo.	Input	Output
1	10 7 6 5 3 2 1 23	[10, 7, 6] [10, 7, 5, 1] [10, 7, 3, 2, 1] [10, 6, 5, 2] [7, 6, 5, 3, 2]
2	50 100 1 1 1 1 1 51	[50, 1]
3	50 100 4 3 1 1 1 1 54	[50, 4] [50, 3, 1] [50, 1, 1, 1, 1]

Explanation:

In example 1 there are 7 items on the menu each having a fixed price. Tom, Dick and Harry have 23 Rs/- amongst them. So they can order the following combinations 

1. [10, 7, 6]
2. [10, 7, 5, 1]
3. [10, 7, 3, 2, 1]
4. [10, 6, 5, 2]
5. [7, 6, 5, 3, 2]

Note how the items are sorted in descending order within a combination. Also note how the combinations themselves are too sorted in descending order.

In example 2 there are 7 items. 5 of these 7 items have the same price. Tom, Dick and Harry have 51 Rs/- amongst them. So the only unique price combination they can order is [50, 1]

In example 3 there are 8 items. 4 of these 8 items have the same price. Tom, Dick and Harry have 54 Rs/- amongst them. So they can form the following combinations. 

1. [50, 4]
2. [50, 3, 1]
3. [50, 1, 1, 1, 1]

Again, note how the items are sorted in descending order within a combination. Also note how the combinations themselves are too sorted in descending order. Also combinations 2 and 3 are printed only once. 

Solution in Python :

tt = input().split()

pm = int(input())

comb = list()

for ind in range(0,len(tt)):

tt[ind] = int(tt[ind])

def subset_sum(numbers, target, partial=[]):

    s = sum(partial)

    if s == target:

        comb.append(partial)

    if s >= target:

        return

    for ind in range(len(numbers)):

        n = numbers[ind]

        remaining = numbers[ind+1:]

        subset_sum(remaining, target, partial + [n])

subset_sum(tt,pm)

unique = []

for item in comb:

    if sorted(item) not in unique:unique.append(sorted(item))

for items in unique:

    print(items[::-1])

        

TCS Codevita Sheldon Cooper and his beverage paradigm

Problem : Sheldon Cooper and his beverage paradigm

Sheldon Cooper, Leonard Hofstadter and Penny decide to go for drinks at Cheese cake factory. Sheldon proposes to make a game out of this. Sheldon proposes as follows, 

• To decide the amount of beverage they plan to consume, say X.
• Then order for a random number of different drinks, say {A, B, C, D, E, F} of quantities {a, b, c, d, e, f} respectively.
• If quantity of any three drinks add up to X then we'll have it else we'll return the order.
  E.g. If a + d + f = X then True else False

You are given

1.    Number of bottles N corresponding to different beverages and hence their sizes

2.    Next N lines, contain a positive integer corresponding to the size of the beverage

3.    Last line consists of an integer value, denoted by X above

Your task is to help find out if there can be any combination of three beverage sizes that can sum up to the quantity they intend to consume. If such a combination is possible print True else False 

Input Format: 

1.    First line contains number of bottles ordered denoted by N

2.    Next N lines, contains a positive integer A_i, the size of the i^th bottle

3.    Last line contains the quantity they intend to consume denoted by X in text above

Output Format:
True, if combination is possible
False, if combination is not possible 

Constraints:

N >= 3

A_i > 0

1 <= i <= N

X > 0 

Sample Input and Output

SNo.	Input	Output
1	6 1 4 45 6 10 8 22	True
2	4 1 3 12 4 14	False

Solution in Java:


import java.util.Scanner;
import java.util.Stack;
public class Shell
{
private Stack<Integer> stack = new Stack<Integer>();
   private int sumin = 0,sizeStack=0;
   int c=0;
   public void populateSubset(int[] data, int fromIndex, int last,int t)
   {
   
    int TARGET_SUM=t;
       if (sumin == TARGET_SUM) 
       {
        if(sizeStack==3)
            {
         count(stack);
            }
       }

       for (int now = fromIndex; now < last; now++) {

           if (sumin + data[now] <= TARGET_SUM) {
               stack.push(data[now]);
               sumin += data[now];
               sizeStack=stack.size();
               populateSubset(data, now + 1, last,TARGET_SUM);
               sumin -= (Integer) stack.pop();
           }
       }
   }
   private void count(Stack<Integer> stack)
   {
    c++;
   }
   void print()
   {
    if(c>0)
        System.out.println("True");
    else
    System.out.println("False");
   }
   public static void main(String [] args)
   {
       Shell get = new Shell();
       int t1,n1,i;
       Scanner sc=new Scanner(System.in);
       n1=sc.nextInt();
       int []ip=new int[n1];
       for(i=0;i<n1;i++)
       {
           ip[i]=sc.nextInt();
       }
       t1=sc.nextInt();
       get.populateSubset(ip, 0, ip.length,t1);
      get.print();
   }

}

TCS CodeVita Milk Man Problem

Problem : Milk Man and His Bottles

A Milkman serves milk in packaged bottles of varied sizes. The possible size of the bottles are {1, 5, 7 and 10} litres. He wants to supply desired quantity using as less bottles as possible irrespective of the size. Your objective is to help him find the minimum number of bottles required to supply the given demand of milk. 

Input Format:

First line contains number of test cases N
Next N lines, each contain a positive integer L_i which corresponds to the demand of milk. 

Output Format:

For each input L_i, print the minimum number of bottles required to fulfill the demand 

Constraints:

1 <= N <= 1000

L_i > 0

1 <= i <= N

Sample Input and Output

SNo.	Input	Output
1	2 17 65	2 7

Explanation:

Number of test cases is 2 

1. In first test case, demand of milk is 17 litres which can be supplied using minimum of 2 bottles as follows
• 1 x 10 litres and
• 1 x 7 litres
2. In second test case, demand of milk is 65 litres which can be supplied using minimum of 7 bottles as follows
• 6 x 10 litres and
• 1 x 5 litres

 Solution in C :

#include<stdio.h>

int main()

{

int c,i,cnt,array[1000],j;

scanf("%d",&c);

if(c>=1&&c<=1000)

{

for(j=0;j<c;j++)

{

    scanf("%d",&i);

    cnt=0;

if(i>0)

{

while(i!=0)

{

    if((i==12||i==13||i==19||i==14))

    {

        cnt--;

        if(i==14)

        {

            cnt=cnt-2;

        }

    }

        if(i>=10)

{

    cnt++;

    i=i-10;

}

else if(i>=7)

{

    cnt++;

    i=i-7;

}

else if(i>=5)

{

    cnt++;

    i=i-5;

}

else if(i>=1)

{

    cnt++;

    i=i-1;

}

}

printf("%d\n",cnt);

}

}

}

return 0;

}

Solution in Java :

import java.util.*;
public class bottle{

private static Scanner in;
public static void main(String[] args) {
in = new Scanner(System.in);
int n,v,u,m,m1,s,s1,i,v1,w1;
int l[]=new int[9999];
try
{
n=in.nextInt();
if((n>=1)&&(n<=1000))
{
for(i=1;i<=n;i++)
{
if((i>=1)&&(i<=n))
{
l[i]=in.nextInt();
}
}
for(i=1;i<=n;i++)
{
if(l[i]>0)
{

if(l[i]<=9)
{
if((l[i]==1)||(l[i]==5)||(l[i]==7))
{
int a1=1;
System.out.println(a1);
}
if((l[i]==2)||(l[i]==6)||(l[i]==8))
{
int a2=2;
System.out.println(a2);
}
if((l[i]==3)||(l[i]==9))
{
int a3=3;
System.out.println(a3);

}
if(l[i]==4)
{
int a4=4;
System.out.println(a4);
}
}
int z=l[i]/10;
v=z-1;
u=l[i]%10;
if(l[i]>=10)
{
if(u==0)
{
System.out.println(z);
}
if((u==1)||(u==5)||(u==7))
{
v1=z+1;
System.out.println(v1);
}
if((u==2)||(u==4))
{
m=2;
m1=v+m;
System.out.println(m1);
}
if((u==3)||(u==9))
{
s=3;
s1=v+s;
System.out.println(s1);
}
if((u==6)||(u==8))
{
int k1=z+2;
System.out.println(k1);
}
}
}
}
}

}
catch(Exception e)
{

}

}

}