Techgig hackathon 2018 first round
Q1 Ruby Necklace (100 Marks)
It is the wedding day of Sanchi, the beautiful princess of Byteland. Her fiance Krishna is planning to gift her an awesome ruby necklace. Krishna has currently b -blue rubies, g -green rubies, r-red rubies and y -yellow rubies. He has to arrange the rubies next to each other in a straight line to make the necklace. But, there are a couple of rules to be followed while making this necklace:
A blue ruby should be followed by either a blue ruby or a red ruby
A green ruby should be followed by either a green ruby or a yellow ruby
A red ruby should be followed by either a green ruby or a yellow ruby
A yellow ruby should be followed by either a blue ruby or a red ruby
If it is possible, we should always start a necklace with a blue or a red ruby
Can you tell what is the maximum possible length of the necklace that Krishna can make. The length of a necklace is the number of rubies in it.
Input Format
The first line contains an integer representing b.
The second line contains an integer representing r.
The third line contains an integer representing y.
The fourth line contains an integer representing g.
Constraints
0 <= b, r, y, g <= 2000
At least one of b, r, y, g is greater than 0
Output Format
A single integer which is the answer to the problem.
Sample TestCase 1
Input
1
1
1
0
Output
3
Solution in c++ :
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int blue,red,yellow,green;
cin>>blue>>red>>yellow>>green;
int ans=0;
if(red<=0)
{
if(blue>0)
ans=blue;
else
{
if(green>0)
{
if(yellow>0)
ans=green+1;
else
ans=green;
}
else
{
ans=1;
}
}
}
else
{
if(green>0 && yellow>0)
{
ans= 2*min(red,yellow) +green;
if(red>yellow)
ans+=1;
}
else if(green>0)
{
ans=green+1;
}
else if(yellow>0)
{
if(yellow>=red)
ans=2*red;
else
ans=2*yellow+1;
}
else
{
ans=1;
}
ans+=blue;
}
cout<<ans<<endl;
return 0;
}
Q2 Ben – The Gamer (100 Marks)
Ben is one of the best gamers in India. He also happens to be an excellent programmer. So, he likes to play games which require use of both gaming skills as well as programming skills. One such game is SpaceWar.
In this game there are N levels and M types of available weapons. The levels are numbered from 0 to N-1 and the weapons are numbered from 0 to M-1 . Ben can clear these levels in any order. In each level, some subset of these M weapons is required to clear this level. If in a particular level, Ben needs to buy x new weapons, he will pay x2 coins for it. Also note that Ben can carry all the weapons he has currently to the next level . Initially, Ben has no weapons. Can you tell the minimum coins required such that Ben can clear all the levels.
Input Format
The first line of input contains 2 space separated integers;
N – the number of levels in the game and M – the number of types of weapons.
N lines follows. The ith of these lines contains a binary string of length M. If the jth character of
this string is 1 , it means we need a weapon of type j to clear the ith level.
Constraints
1 <= N <=20
1<= M <= 20
Output Format
Print a single integer which is the answer to the problem.
Sample TestCase 1
Input
1 4
0101
Output
4
Explanation
There is only one level in this game. We need 2 types of weapons – 1 and 3. Since, initially Ben
has no weapons he will have to buy these, which will cost him 22 = 4 coins.
Sample TestCase 2
Input
3 3
111
001
010
Output
3
Explanation
There are 3 levels in this game. The 0th level (111) requires all 3 types of weapons. The 1st level (001) requires only weapon of type 2. The 2nd level requires only weapon of type 1. If we clear the levels in the given order(0-1-2), total cost = 32 + 02 + 02 = 9 coins. If we clear the levels in the order 1-2-0, it will cost = 12 + 12 + 12 = 3 coins which is the optimal way.
Solution in c++ :
#include <iostream>
#include <string>
#include <limits.h>
using namespace std;
int main() {
// latest
int n,m;
cin>>n>>m;
int a[n][m];
for(int i=0;i<n;i++)
{
string s;
cin>>s;
for(int j=0;j<m;j++)
a[i][j]=s[j]-‘0’;
}
int mark[n],w[m];
for(int i=0;i<n;i++)
mark[i]=0;
for(int i=0;i<m;i++)
w[i]=0;
int coins=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cout<<a[i][j]<<” “;
cout<<endl;
}
for(int limit=1;limit<=n;limit++)
{
int min_index=0,min_sum=INT_MAX;
for(int pick=0;pick<n;pick++)
{
if(mark[pick]==0)
{
int count1=0;
for(int k=0;k<m;k++)
{
if(a[pick][k]==1)
count1++;
}
int second_square=INT_MAX;
for(int i=0;i<n;i++)
{
if(mark[i]==0 && pick!=i)
{
int count2=0;
for(int j=0;j<m;j++)
{
if( a[i][j]==1 && a[pick][j]==0 )
count2++;
}
second_square=min(second_
}
}
if(second_square==INT_MAX)
second_square=0;
if( count1*count1 + second_square < min_sum)
{
min_index=pick;
min_sum=count1*count1 + second_square;
}
}
}
int tcoin=0;
for(int j=0;j<m;j++)
{
if(a[min_index][j]==1)
tcoin++;
}
coins+=(tcoin*tcoin);
for(int i=0;i<n;i++)
{
if(i!=min_index)
{
for(int j=0;j<m;j++)
{
if(a[min_index][j]==1)
a[i][j]=0;
}
}
}
mark[min_index]=1;
for(int j=0;j<m;j++)
a[min_index][j]=0;
}
cout<<coins<<endl;
return 0;
}