UVa 10364 : Square
UVa 演習 2014/6/9 (月) 問2
問題リンク:http://uva.onlinejudge.org/external/103/10364.html
問題概要:
最大20本の棒があり、それらの長さが与えられる
これを使って正方形をつくれるか?
コード:
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; const string YES = "yes", NO = "no"; int M,L; int sticks[21]; bool dfs(int bitmask,int len,int sp){ if( bitmask == ((1<<M)-1) ) { return len == 0; } REP(i,sp,M){ if( (bitmask>>i) & 1 ) continue; int nlen = len + sticks[i]; if( nlen > L ) { continue; } else if( nlen == L ) { return dfs(bitmask|(1<<i),0,0); } else { if( dfs(bitmask|(1<<i),nlen,i+1) ) return true; } } return false; } int main(){ int N; cin >> N; while( N-- ){ cin >> M; int sum = 0; rep(i,M) { cin >> sticks[i]; sum += sticks[i]; } if( sum % 4 ) { cout << NO << endl; continue; } sort(sticks,sticks+M); L = sum / 4; cout << (dfs(0,0,0)?YES:NO) << endl; } return 0; }