ZeroJudge D375: Square

UVa 10364 – Square

Given the lengths of some sticks, please determine whether they can be arranged to form a square (endpoint to endpoint, and the sticks cannot be broken).

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line of the input contains an integer N, representing the number of test cases that follow. Each test case is on one line. The first integer is M (4 ≤ M ≤ 20), representing the number of sticks. The following M integers represent the lengths of these M sticks. Each stick's length is between 1 and 10000.For each test case, if the sticks can be arranged to form a square, output "yes"; otherwise, output "no".
5
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
8 1 7 2 6 4 4 3 9
8 1 7 2 6 4 4 3 13		yes
no
yes
yes
no
ZeroJudge D375 Sample Test Case

Thought Process

Since all the sticks must be used, if the total length of all the sticks is not a multiple of 4, it is impossible to form a square. Additionally, if the length of the longest stick is greater than the total length divided by 4, it is also impossible to form a square.

Use the DFS (Depth-First Search) method to determine all possible arrangements.

Sample Code－ZeroJudge D375: Square

#include <iostream>
#include <algorithm>
using namespace std;

bool ok = false;
int MAP[50000] = {}, stick[50000] = {}, N;

void DFS(const int length, const int finish, const int add, const int start) {
    if (finish == 3 || ok) {
        ok = true;
        return;
    }
    if (add == length) {
        DFS(length, finish+1, 0, 0);
        return;
    }
    for (int i = start; i<N; i++) {
        if (MAP[i] == 0 && add+stick[i] <= length) {
            MAP[i] = 1;
            DFS(length, finish, add+stick[i], i+1);
            MAP[i] = 0;
        }
        else if (stick[i]+add > length) return;
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++) {
        int sum = 0, max = -999;
        cin >> N;
        ok = false;
        for (int j = 0; j<N; j++) {
            MAP[j] = 0;
        }
        for (int j = 0; j<N; j++) {
            cin >> stick[j];
            sum += stick[j];
            if (stick[j] > max) max = stick[j];
        }
        if (sum % 4 != 0 || max > sum / 4) {
            cout << "no\n";
            continue;
        }
        sort(stick, stick+N);
        DFS(sum / 4, 0, 0, 0);
        if (ok) cout << "yes\n";
        else cout << "no\n";

    }
}

//ZeroJudge D375
//Dr. SeanXD
Tags

Related Posts

Comments