Petr and a Combination Lock
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:
YESif this is possible, andNOotherwise.
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";
}