|
Language:
Square
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".
Sample Input 3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5 Sample Output yes no yes |
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning(disable : 4996)
#define MAX 25
bool vis[MAX];
int stick[MAX];
int n,goal;
bool ans;
bool cmp(int a, int b)
{
return a > b;
}
void dfs(int now, int index, int cnt)
{
if(cnt == 3)
{
ans = true;
}
if(ans) return;
for(int i = index; i < n; i++)
{
if(vis[i])
{
continue;
}
if(now + stick[i] == goal)
{
vis[i] = true;
dfs(0, 0, cnt + 1);
vis[i] = false;
}
else if(now + stick[i] < goal)
{
vis[i] = true;
dfs(now + stick[i], i + 1, cnt);
vis[i] = false;
if(now == 0)
{
break;
}
}
}
}
int main()
{
freopen("in.txt", "r", stdin);
int t, Max, sum;
cin >> t;
while (t--)
{
cin >> n;
sum = 0;
Max = -1;
for(int i = 0; i < n; i++)
{
cin >> stick[i];
sum += stick[i];
Max = max(Max, stick[i]);
}
goal = sum / 4;
if(sum % 4)
{
cout << "no" << endl;
continue;
}
if(Max > goal)
{
cout << "no" << endl;
continue;
}
sort(stick, stick + n, cmp);
memset(vis, false, sizeof(vis));
ans = false;
dfs(0, 0 , 0);
if(ans)
{
cout << "yes" << endl;
}
else
{
cout << "no" << endl;
}
}
}