Petr and a Combination Lock

Petr and a Combination Lock
Codeforces medium

A lock has a scale of \(360\) degrees and a pointer that initially points at zero. Petr must rotate the lock exactly \(n\) times. The \(i\)-th rotation is \(a_i\) degrees, either clockwise or counterclockwise.

Determine whether Petr can choose the directions so that after all \(n\) rotations the pointer points at zero again.

Constraints:

  • \(1 \le n \le 15\)
  • \(1 \le a_i \le 180\)

Input:

  • First line: integer \(n\) — the number of rotations.
  • Next \(n\) lines: one integer \(a_i\) per line.

Output:

  • YES if this is possible, and NO otherwise.

Examples:

Input:

3
10
20
30

Output:

YES

(Rotate by \(10\) and \(20\) degrees clockwise and by \(30\) degrees counterclockwise.)

Input:

3
120
120
120

Output:

YES

(All three rotations clockwise give \(360\) degrees.)

Solution

Each rotation has two possible directions, so there are \(2^n \le 2^{15} = 32768\) possible choices. We can check all of them.

We encode a choice as a bitmask, as in the lesson on generating subsets: bit \(j\) of mask is 1 if rotation \(j\) is clockwise and 0 if it is counterclockwise. For each mask we add the clockwise angles and subtract the counterclockwise angles. The pointer points at zero exactly when the result is divisible by \(360\).

In C++, angle % 360 is 0 for a negative multiple of \(360\) as well, so the check also works for negative angles.

The whole solution takes \(O(2^n \cdot n)\) time.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int a[15];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // bit j of mask is 1 if rotation j is clockwise
    for (int mask = 0; mask < (1 << n); mask++) {
        int angle = 0;
        for (int j = 0; j < n; j++) {
            if (mask & (1 << j)) {
                angle += a[j];
            } else {
                angle -= a[j];
            }
        }

        if (angle % 360 == 0) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";
}