petr-and-a-combination-lock

Petr and a Combination Lock

لقفل تدريج من \(360\) درجة ومؤشر يشير في البداية إلى الصفر. يجب على بيتر أن يدير القفل \(n\) مرة بالضبط. الدورة رقم \(i\) مقدارها \(a_i\) درجة، إما مع اتجاه عقارب الساعة أو عكسه.

حدّد هل يستطيع بيتر اختيار الاتجاهات بحيث يشير المؤشر إلى الصفر مرة أخرى بعد كل الدورات الـ \(n\).

القيود:

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

الإدخال:

السطر الأول: عدد صحيح \(n\) — عدد الدورات.
الأسطر الـ \(n\) التالية: عدد صحيح \(a_i\) في كل سطر.

المخرجات:

YES إذا كان ذلك ممكنًا، و NO في غير ذلك.

أمثلة:

الإدخال:

المخرجات:

YES

(ندير \(10\) و \(20\) درجة مع اتجاه عقارب الساعة و \(30\) درجة عكسه.)

الإدخال:

المخرجات:

YES

(الدورات الثلاث مع اتجاه عقارب الساعة تعطي \(360\) درجة.)

الحل

لكل دورة اتجاهان ممكنان، لذلك يوجد \(2^n \le 2^{15} = 32768\) اختيارًا ممكنًا. يمكننا فحصها كلها.

نمثّل كل اختيار بقناع بتات، كما في درس توليد المجموعات الجزئية: البت رقم \(j\) في mask يساوي 1 إذا كانت الدورة رقم \(j\) مع اتجاه عقارب الساعة، ويساوي 0 إذا كانت عكسه. لكل قناع نجمع الزوايا التي مع اتجاه عقارب الساعة ونطرح الزوايا التي عكسه. يشير المؤشر إلى الصفر تمامًا عندما تكون النتيجة قابلة للقسمة على \(360\).

في C++ تكون قيمة angle % 360 مساوية لـ 0 أيضًا عندما تكون الزاوية مضاعفًا سالبًا للعدد \(360\)، لذلك يعمل الفحص مع الزوايا السالبة أيضًا.

يعمل الحل كله في زمن \(O(2^n \cdot n)\).

#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";
}