[Codeforces][Round #EDU115][Div.2] B : Groups (C++)

https://codeforces.com/contest/1598/problem/B

https://codeforces.com/contest/1598/problem/B

 

 

[난이도] Div.2
[유형] 브루트포스

[풀이]
두 클래스는 월~금 중 두가지가 되어야 하므로 5C2 = 10 개의 케이스에 대해
체크를 해줍니다. 두 요일 u,v에 대해
u만 참여 가능한 학생을 f1에,
v만 참여 가능한 학생을 f2에,
둘다 참여 가능한 학생을 f12에 저장합니다.
이를 이용해 u,v에 정확히 같은 수의 학생이 들어갈 수 있는지를 확인할 수 있습니다.
먼저 모든 학생이 참가해야 하므로 f1+f2+f12 == n 이 되어야 합니다.
현재 f1, f2가 정확히 같은 수가 아니라면 f12에서 부족한 쪽을 채워 줍니다.
그 뒤에 f12가 짝수라면 정확히 같은 수의 학생으로 나눌 수 있기 때문에 YES를 출력해주면 됩니다.

 

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
int t,n,a[1000][5];

bool check(int u,int v){
    int f1=0,f2=0,f12=0;

    for(int i=0;i<n;i++){
        if(a[i][u] && a[i][v]) f12++;
        else if(a[i][u]) f1++;
        else if(a[i][v]) f2++;
    }
    if(f1+f2+f12!=n) return false;

    if(f1>f2) swap(f1,f2);
    f12-=f2-f1;

    if(f12<0) return false;

    if(f12%2) return false; 

    return true;
}
bool sol(){
    for(int i=0;i<4;i++){
        for(int j=i+1;j<5;j++){
            if(check(i,j)) return true;
        }
    }
    return false;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            for(int j=0;j<5;j++) scanf("%d",&a[i][j]);
        }
        puts(sol()?"YES":"NO");

    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU115-Div.2/B.cpp