Skip to content

Instantly share code, notes, and snippets.

@hyunjun
Created December 17, 2014 04:16
Show Gist options
  • Save hyunjun/66d2dec613355d36c891 to your computer and use it in GitHub Desktop.
Save hyunjun/66d2dec613355d36c891 to your computer and use it in GitHub Desktop.
4 5
10101
11100
11010
00101
256 500
10101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101
11100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100
11010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010
00101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101
...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TEAM_CNT 500
#define MAX_TOPIC_CNT 500
void max_topic_and_team(char data[MAX_TEAM_CNT][MAX_TOPIC_CNT], int team_num, int topic_num, int* max_num_of_topics, int* num_of_teams) {
int maximal_topics = 0;
int maximal_topics_teams = 0;
int i = 0, j = 0, k = 0;
for ( i = 0; i < team_num; ++i ) {
for ( j = i + 1; j < team_num; ++j ) {
/*printf("[%d] ", i);
printf("%s ", data[i]);
printf("[%d] ", j);
printf("%s ", data[j]);*/
int num_of_ones = 0;
for ( k = 0; k < topic_num; ++k ) {
if ( data[i][k] == '1' || data[j][k] == '1' ) {
++num_of_ones;
}
}
//printf("\t%d\n", num_of_ones);
if ( maximal_topics < num_of_ones ) {
maximal_topics = num_of_ones;
maximal_topics_teams = 1;
} else if ( maximal_topics == num_of_ones ) {
++maximal_topics_teams;
}
}
}
*max_num_of_topics = maximal_topics;
*num_of_teams = maximal_topics_teams;
}
int main() {
int team_num = 0;
fscanf(stdin, "%d", &team_num);
int topic_num = 0;
fscanf(stdin, "%d", &topic_num);
int i = 0;
char data[MAX_TEAM_CNT][MAX_TOPIC_CNT];
for ( i = 0; i < team_num; ++i ) {
fscanf(stdin, "%s", data[i]);
//printf("%s\n", data[i]);
}
int max_num_of_topics = 0;
int num_of_teams = 0;
max_topic_and_team(data, team_num, topic_num, &max_num_of_topics, &num_of_teams);
printf("%d\n", max_num_of_topics);
printf("%d\n", num_of_teams);
}
/*
$ time ./a.out < inp
5
2
real 0m0.001s
user 0m0.001s
sys 0m0.000s
$ time ./a.out < inp2
500
8192
real 0m0.075s
user 0m0.074s
sys 0m0.000s
*/
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Solution {
public static int[] maxTopicsAndTeams(final List<String> data, final int teamNum, final int topicNum) {
int maximalTopics = 0;
int maximalTopicsTeams = 0;
for ( int i = 0; i < teamNum; ++i ) {
for ( int j = i + 1; j < teamNum; ++j ) {
int numOfOnes = 0;
final String d1 = data.get(i);
final String d2 = data.get(j);
for ( int k = 0; k < topicNum; ++k ) {
if ( d1.charAt(k) == '1' || d2.charAt(k) == '1' )
++numOfOnes;
}
if ( maximalTopics < numOfOnes ) {
maximalTopics = numOfOnes;
maximalTopicsTeams = 1;
} else if ( maximalTopics == numOfOnes ) {
++maximalTopicsTeams;
}
}
}
int[] res = new int[2];
res[0] = maximalTopics;
res[1] = maximalTopicsTeams;
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String inp = sc.nextLine();
int teamNum = Integer.parseInt(inp.split(" ")[0]);
int topicNum = Integer.parseInt(inp.split(" ")[1]);
List<String> data = new ArrayList<String>();
for ( int i = 0; i < teamNum; ++i ) {
data.add(sc.nextLine());
}
int[] res = new int[2];
res = maxTopicsAndTeams(data, teamNum, topicNum);
System.out.println(res[0]);
System.out.println(res[1]);
}
}
/*
$ time java Solution < inp
5
2
real 0m0.110s
user 0m0.121s
sys 0m0.030s
$ time java Solution < inp2
500
8192
real 0m0.208s
user 0m0.301s
sys 0m0.065s
*/
object Solution {
def maxTopicsAndTeams(data: Array[String], teamNum: Int, topicNum: Int): (Int, Int) = {
var maxTopicNum: Int = 0
var maxTeamNum: Int = 0
for ( i <- 0 until teamNum;
j <- i + 1 until teamNum ) {
var numOfOnes = 0
for ( k <- 0 until topicNum ) {
if ( data(i)(k) == '1' || data(j)(k) == '1' ) {
numOfOnes += 1
}
}
if ( maxTopicNum < numOfOnes ) {
maxTopicNum = numOfOnes
maxTeamNum = 1
} else if ( maxTopicNum == numOfOnes ) {
maxTeamNum += 1
}
}
(maxTopicNum, maxTeamNum)
}
def main(args: Array[String]) {
val inps = io.Source.stdin.getLines.toArray
val teamNum = inps(0).split(" ")(0).toInt
val topicNum = inps(0).split(" ")(1).toInt
val data = inps.drop(1)
val res: (Int, Int) = maxTopicsAndTeams(data, teamNum, topicNum)
println(res._1)
println(res._2)
}
}
/*
$ time scala Solution.scala < inp
5
2
real 0m0.797s
user 0m0.617s
sys 0m0.078s
$ time scala Solution.scala < inp2
500
8192
real 0m1.052s
user 0m1.009s
sys 0m0.109s
*/
from itertools import product
def max_topic_and_team(data):
maximal_topics, maximal_topics_teams = 0, 0
team_cnt = len(data)
for p in product(range(team_cnt), range(team_cnt)):
if p[0] < p[1]:
num_of_ones = len([i for i in map(lambda t: t[0] | t[1], zip(data[p[0]], data[p[1]])) if i == 1])
if maximal_topics < num_of_ones:
maximal_topics, maximal_topics_teams = num_of_ones, 1
elif maximal_topics == num_of_ones:
maximal_topics_teams += 1
return maximal_topics, maximal_topics_teams
if __name__ == '__main__':
team_num, topic_num = map(int, raw_input().split())
data = []
[data.append([int(c) for c in raw_input()]) for i in range(team_num)]
maximal_topics, maximal_topics_teams = max_topic_and_team(data)
print maximal_topics
print maximal_topics_teams
'''
$ time python2.7 test2_0.py < inp
5
2
real 0m0.015s
user 0m0.010s
sys 0m0.004s
$ time python2.7 test2_0.py < inp2
500
8192
real 0m5.979s
user 0m5.965s
sys 0m0.002s
'''
def max_topic_and_team(data):
maximal_topics, maximal_topics_teams = 0, 0
team_cnt = len(data)
for p in [(i, j) for i in range(team_cnt) for j in range(team_cnt) if i < j]:
num_of_ones = len([i for i in map(lambda t: t[0] | t[1], zip(data[p[0]], data[p[1]])) if i == 1])
if maximal_topics < num_of_ones:
maximal_topics, maximal_topics_teams = num_of_ones, 1
elif maximal_topics == num_of_ones:
maximal_topics_teams += 1
return maximal_topics, maximal_topics_teams
if __name__ == '__main__':
team_num, topic_num = map(int, raw_input().split())
data = []
[data.append([int(c) for c in raw_input()]) for i in range(team_num)]
maximal_topics, maximal_topics_teams = max_topic_and_team(data)
print maximal_topics
print maximal_topics_teams
'''
$ time python2.7 test2_1.py < inp
5
2
real 0m0.015s
user 0m0.011s
sys 0m0.003s
$ time python2.7 test2_1.py < inp2
500
8192
real 0m5.934s
user 0m5.914s
sys 0m0.008s
'''
def max_topic_and_team(data):
maximal_topics, maximal_topics_teams = 0, 0
team_cnt, topic_cnt = len(data), len(data[0])
for p in [(i, j) for i in range(team_cnt) for j in range(team_cnt) if i < j]:
d1, d2 = data[p[0]], data[p[1]]
topics = [d1[i] | d2[i] for i in range(topic_cnt)]
num_of_ones = len([t for t in topics if t == 1])
if maximal_topics < num_of_ones:
maximal_topics, maximal_topics_teams = num_of_ones, 1
elif maximal_topics == num_of_ones:
maximal_topics_teams += 1
return maximal_topics, maximal_topics_teams
if __name__ == '__main__':
team_num, topic_num = map(int, raw_input().split())
data = []
[data.append([int(c) for c in raw_input()]) for i in range(team_num)]
maximal_topics, maximal_topics_teams = max_topic_and_team(data)
print maximal_topics
print maximal_topics_teams
'''
$ time python2.7 test2_2.py < inp
5
2
real 0m0.015s
user 0m0.007s
sys 0m0.007s
$ time python2.7 test2_2.py < inp2
500
8192
real 0m3.570s
user 0m3.555s
sys 0m0.007s
'''
from itertools import product
def max_topic_and_team(data):
maximal_topics, maximal_topics_teams = 0, 0
team_cnt = len(data)
for p in product(range(team_cnt), range(team_cnt)):
if p[0] < p[1]:
num_of_ones = len([i for i in map(lambda t: t[0] | t[1], zip(data[p[0]], data[p[1]])) if i == 1])
if maximal_topics < num_of_ones:
maximal_topics, maximal_topics_teams = num_of_ones, 1
elif maximal_topics == num_of_ones:
maximal_topics_teams += 1
return maximal_topics, maximal_topics_teams
if __name__ == '__main__':
team_num, topic_num = map(int, input().split())
data = []
[data.append([int(c) for c in input()]) for i in range(team_num)]
maximal_topics, maximal_topics_teams = max_topic_and_team(data)
print(maximal_topics)
print(maximal_topics_teams)
'''
$ time python3 test3_0.py < inp
5
2
real 0m0.071s
user 0m0.067s
sys 0m0.004s
$ time python3 test3_0.py < inp2
500
8192
real 0m33.711s
user 0m33.644s
sys 0m0.009s
'''
def max_topic_and_team(data):
maximal_topics, maximal_topics_teams = 0, 0
team_cnt = len(data)
for p in [(i, j) for i in range(team_cnt) for j in range(team_cnt) if i < j]:
num_of_ones = len([i for i in map(lambda t: t[0] | t[1], zip(data[p[0]], data[p[1]])) if i == 1])
if maximal_topics < num_of_ones:
maximal_topics, maximal_topics_teams = num_of_ones, 1
elif maximal_topics == num_of_ones:
maximal_topics_teams += 1
return maximal_topics, maximal_topics_teams
if __name__ == '__main__':
team_num, topic_num = map(int, input().split())
data = []
[data.append([int(c) for c in input()]) for i in range(team_num)]
maximal_topics, maximal_topics_teams = max_topic_and_team(data)
print(maximal_topics)
print(maximal_topics_teams)
'''
$ time python3 test3_1.py < inp
5
2
real 0m0.070s
user 0m0.069s
sys 0m0.001s
$ time python3 test3_1.py < inp2
500
8192
real 0m33.892s
user 0m33.821s
sys 0m0.011s
'''
def max_topic_and_team(data):
maximal_topics, maximal_topics_teams = 0, 0
team_cnt, topic_cnt = len(data), len(data[0])
for p in [(i, j) for i in range(team_cnt) for j in range(team_cnt) if i < j]:
d1, d2 = data[p[0]], data[p[1]]
topics = [d1[i] | d2[i] for i in range(topic_cnt)]
num_of_ones = len([t for t in topics if t == 1])
if maximal_topics < num_of_ones:
maximal_topics, maximal_topics_teams = num_of_ones, 1
elif maximal_topics == num_of_ones:
maximal_topics_teams += 1
return maximal_topics, maximal_topics_teams
if __name__ == '__main__':
team_num, topic_num = map(int, input().split())
data = []
[data.append([int(c) for c in input()]) for i in range(team_num)]
maximal_topics, maximal_topics_teams = max_topic_and_team(data)
print(maximal_topics)
print(maximal_topics_teams)
'''
$ time python3 test3_2.py < inp
5
2
real 0m0.071s
user 0m0.067s
sys 0m0.004s
$ time python3 test3_2.py < inp2
500
8192
real 0m24.119s
user 0m24.062s
sys 0m0.015s
'''
from itertools import product
def max_topic_and_team(data):
maximal_topics, maximal_topics_teams = 0, 0
team_cnt = len(data)
for p in [(i, j) for i, j in product(range(team_cnt), range(team_cnt)) if i < j]:
d1, d2 = data[p[0]], data[p[1]]
topics = [1 for i, j in zip(d1, d2) if 1 == i or 1 == j]
num_of_ones = len(topics)
if maximal_topics < num_of_ones:
maximal_topics, maximal_topics_teams = num_of_ones, 1
elif maximal_topics == num_of_ones:
maximal_topics_teams += 1
return maximal_topics, maximal_topics_teams
if __name__ == '__main__':
team_num, topic_num = map(int, input().split())
data = []
[data.append([int(c) for c in input()]) for i in range(team_num)]
maximal_topics, maximal_topics_teams = max_topic_and_team(data)
print(maximal_topics)
print(maximal_topics_teams)
'''
$ time python3 test3_3.py < inp
5
2
real 0m0.071s
user 0m0.068s
sys 0m0.003s
$ time python3 test3_3.py < inp2
500
8192
real 0m9.717s
user 0m9.695s
sys 0m0.005s
'''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment