HACKER RANK Algorithms - Implementation - ACM ICPC Team - Solution.'C++'
Algorithms - Implementation - ACM ICPC Team - Solution
Problem Statement
Problem Statement
You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.
Note Suppose a, b, and c are three different people, then (a,b) and (b,c) are counted as two different teams.
Input Format
The first line contains two integers, N and M , separated by a single space, where N represents the number of people, and M represents the number of topics. N lines follow.
Each line contains a binary string of lengthM . If the i th line's j th character is 1 , then the i thperson knows the j th topic; otherwise, he doesn't know the topic.
Each line contains a binary string of length
Constraints
2≤N≤500
1≤M≤500
Output Format
On the first line, print the maximum number of topics a 2-person team can know.
On the second line, print the number of 2-person teams that can know the maximum number of topics.
On the second line, print the number of 2-person teams that can know the maximum number of topics.
Sample Input
4 5
10101
11100
11010
00101
Sample Output
5
2
Explanation
(1, 3) and (3, 4) know all the 5 topics. So the maximal topics a 2-person team knows is 5, and only 2 teams can achieve this.
Solution:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void myfun(int m,int t,int **mat)
{ int i,j,q=0,maxQ=0,count=0;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
{ q=0;
if (i<j)
{
for(int k=0;k<t;k++)
q+= max(mat[i][k],mat[j][k]);
if ( q > maxQ )
{ maxQ=q;
count=0;
}
if( q==maxQ)
{ count++;
}
}
}
cout<<maxQ<<"\n"<<count;
}
int main() {
long int t,m,i,j;
cin>>m>>t;
char c;
int **mat;
mat = (int **)malloc(m*sizeof(int*));
for(i=0;i<m;i++)
mat[i] = (int*)malloc(t*sizeof(int));
for(i=0;i<m;i++)
for(j=0;j<t;)
{ c=getchar();
if( c!='\n')
mat[i][j++] = (int)c-48;
}
myfun(m,t,mat);
return 0;
}
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void myfun(int m,int t,int **mat)
{ int i,j,q=0,maxQ=0,count=0;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
{ q=0;
if (i<j)
{
for(int k=0;k<t;k++)
q+= max(mat[i][k],mat[j][k]);
if ( q > maxQ )
{ maxQ=q;
count=0;
}
if( q==maxQ)
{ count++;
}
}
}
cout<<maxQ<<"\n"<<count;
}
int main() {
long int t,m,i,j;
cin>>m>>t;
char c;
int **mat;
mat = (int **)malloc(m*sizeof(int*));
for(i=0;i<m;i++)
mat[i] = (int*)malloc(t*sizeof(int));
for(i=0;i<m;i++)
for(j=0;j<t;)
{ c=getchar();
if( c!='\n')
mat[i][j++] = (int)c-48;
}
myfun(m,t,mat);
return 0;
}
Comments
Post a Comment