ACM ICPC Team:-
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.
// pick 2 people out of N people
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 length M. In this string, 1 indicates that the ith person knows a particular topic, and 0 indicates that the ith person does not know the topic.
//N people , M topic
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.
// condiser each topic's character array AS a binary or integer
// then screen all combination by taking "OR" operation and find a maximum number of "1" and the team
// to put the result , use a HashMap then put the team number and max count "Map<Integer,Integer>"
// key is to do "OR" operation in given array element.
//1. receive all necessary input parameters
//2. store to character array
//3. convert character array to integer array for "OR" operation
//4. screen all combination but there's no need to concern an order
//5. after 4, check number of "1" value and compare to previous max value if it exceeds or same
//6. iterate above
//7. print max and number of teams value - hashmap size
Constraints
2 ≤ N ≤ 500
1 ≤ M ≤ 500
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.
Code
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class ACMICPC {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//no of people
int N = in.nextInt();
//no of topic
int M= in.nextInt();
char[][] t = new char[N][M];
//each pereons's topic data
for(int i=0;i<N;i++){
t[i]=in.next().toCharArray();
}
//convert to int type for "OR" operation
int [][] p = new int[N][M];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
p[i][j]=(int)(t[i][j]-'0');
}
}
//map for storing teams data
Map<Integer,Integer> hmap = new HashMap<>();
int count=0;
int max=0;
for(int i=0;i<N;i++){
//first person
int[] a=p[i];
for(int j=i+1;j<N;j++){
//second person
int[] b=p[j];
count=0;
//"OR" operation and count total number of "1"
for(int k=0;k<M;k++){
if((a[k]|b[k]) ==1)
count++;
}
//new MAX found , previous max and map data will be removed
if(count>max){
max=count;
hmap.clear();
hmap.put(i,j);
//same as max , count
}else if(count==max){
hmap.put(i,j);
}
}
}
//max number of "OR"
System.out.println(max);
//number of team who meet "max"
System.out.println(hmap.size());
}
}
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.
// pick 2 people out of N people
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 length M. In this string, 1 indicates that the ith person knows a particular topic, and 0 indicates that the ith person does not know the topic.
//N people , M topic
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.
// condiser each topic's character array AS a binary or integer
// then screen all combination by taking "OR" operation and find a maximum number of "1" and the team
// to put the result , use a HashMap then put the team number and max count "Map<Integer,Integer>"
// key is to do "OR" operation in given array element.
//1. receive all necessary input parameters
//2. store to character array
//3. convert character array to integer array for "OR" operation
//4. screen all combination but there's no need to concern an order
//5. after 4, check number of "1" value and compare to previous max value if it exceeds or same
//6. iterate above
//7. print max and number of teams value - hashmap size
Constraints
2 ≤ N ≤ 500
1 ≤ M ≤ 500
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.
Code
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class ACMICPC {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//no of people
int N = in.nextInt();
//no of topic
int M= in.nextInt();
char[][] t = new char[N][M];
//each pereons's topic data
for(int i=0;i<N;i++){
t[i]=in.next().toCharArray();
}
//convert to int type for "OR" operation
int [][] p = new int[N][M];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
p[i][j]=(int)(t[i][j]-'0');
}
}
//map for storing teams data
Map<Integer,Integer> hmap = new HashMap<>();
int count=0;
int max=0;
for(int i=0;i<N;i++){
//first person
int[] a=p[i];
for(int j=i+1;j<N;j++){
//second person
int[] b=p[j];
count=0;
//"OR" operation and count total number of "1"
for(int k=0;k<M;k++){
if((a[k]|b[k]) ==1)
count++;
}
//new MAX found , previous max and map data will be removed
if(count>max){
max=count;
hmap.clear();
hmap.put(i,j);
//same as max , count
}else if(count==max){
hmap.put(i,j);
}
}
}
//max number of "OR"
System.out.println(max);
//number of team who meet "max"
System.out.println(hmap.size());
}
}
No comments:
Post a Comment