Square

http://acm.pku.edu.cn/JudgeOnline/problem?id=2362

Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

Source

Waterloo local 2002.09.21



Solving

다양한 길이의 막대가 주어진다. 이들 막대를 연결하여 정 사각형을 만들 수 있는가?

우선 막대의 길이를 모두 더한 후 4로 나누어 정사각형의 한 변의 길이 s를 구한다.
이제 막대를 연결하여 길이가 s의 막대 네 개를 만들어야 한다.

우선 막대를 연결하여 길이가 s가 되는 모든 경우를 구하여 후보리스트에 넣는다.
Ci를 i번째 후보라고 한다면 후보에 대해 3중 루프를 돌면서 Ci, Cj, Ck (i != j &&  j != k && i != k) 에 사용된 막대 중 중복되는 것이 없다면 정사각형을 만들 수 있다.(Ci, Cj, Ck에서 사용이 안된 막대를 이용하여 마지막 네번째 변을 만들 수 있다)


#include <cstdlib> #include <cstdio> #include <memory> #include <vector> #include <algorithm> using namespace std; int n, d; vector<int> length; vector<int> candi; int ccount = 0; void doit(int index, int sum, int number) { ccount++; if (sum > d) return; if (sum == d) { candi.push_back(number); return; } for (int i = index+1; i < n; i++) doit(i, sum+length[i], number | (1 << i)); } int main() { int T; scanf("%d", &T); while (T--) { int i, j, k, sum = 0; int num; length.clear(); candi.clear(); scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &num); sum += num; length.push_back(num); } sort(length.begin(), length.end()); d = sum / 4; if (d * 4 != sum) { printf("no\n"); continue; } ccount = 0; for (i = 0; i < n; i++) doit(i, length[i], 1<<i); for (i = 0; i < candi.size(); i++) { for (j = i+1; j < candi.size(); j++) { if ((candi[i] & candi[j]) == 0) for (k = j+1; k < candi.size(); k++) { if ((candi[j] & candi[k]) == 0 && (candi[k] & candi[i]) == 0) { printf("yes\n", i, j, k); goto NEXT; } } } } printf("no\n"); NEXT:; } return 0; }