एरिक और एलईडी बोर्ड
ऐसा होता है कि एक निश्चित लंबाई के सभी बिट अनुक्रमों को सूचीबद्ध करना आवश्यक है। या दूसरे शब्दों में, सभी संभावित विकल्पों पर पुनरावृति करें, जहां प्रत्येक वस्तु के लिए दो संभावित अवस्थाओं में से एक का चयन किया जाता है।
ऐसी स्थितियों में, बिट मास्क का प्रयोग करके गणना लागू करना संभव है। इस दृष्टिकोण का लाभ यह है कि ऐसे कोड गैर-पुनरावर्ती रूप से काम करते हैं और संग्रह या इसी तरह के बजाय संख्याओं पर काम करते हैं, जिससे प्रदर्शन में काफी सुधार होता है।
बिटमास्क का उपयोग करने वाला सामान्य कोड नीचे दिया गया है:
इंटन; // ऑब्जेक्ट्स की संख्या (बिट अनुक्रम की लंबाई)
के लिए (इंट मास्क = 0; मास्क < (1 << n); मास्क++) {// 0 से 2^n - 1 तक सभी नंबरों के माध्यम से लूप करें, जहां प्रत्येक संख्या एक बिटमास्क से मेल खाती है
// वर्तमान नंबर मास्क एक बिटमास्क है, जहां i-th बिट i-th ऑब्जेक्ट की स्थिति को निर्दिष्ट करता है
for (int i = 0; i < n; i++) {// n बिट्स पर पुनरावृति यह समझने के लिए कि प्रत्येक वस्तु की स्थिति क्या है
अगर ((1 << i) और मास्क) {// जांचें कि क्या i-th बिट एक के बराबर है
// विकल्प को प्रोसेस करें कि i-th ऑब्जेक्ट की स्थिति '1'
}
और {// केस जब आई-वें बिट शून्य है
// विकल्प को संसाधित करें कि राज्य की i-वें वस्तु '0'
}
}
}
यह कोड O(2^n * f(n)) में चलता है, जहां f(n) वह समय है जब आपको एक विशेष पुनरावृत्ति को संसाधित करने में समय लगता है।
Problem
एरिक को अपने दादाजी के पुराने गैरेज में एक एलईडी बोर्ड मिला। हालांकि, वह हैरान था कि सक्रिय होने पर डायोड एक दूसरे के साथ सिंक्रनाइज़ नहीं थे। यानी, उनमें से कुछ जले, और कुछ नहीं।
बोर्ड ही असामान्य निकला। यह n पंक्तियों और m स्तंभों वाला एक आयताकार ग्रिड है, जहाँ प्रत्येक कोशिका में एक डायोड होता है। प्रत्येक पंक्ति के पास एक लीवर होता है जो इस पंक्ति के सभी डायोड को स्विच करता है (जलते हुए डायोड बाहर निकलते हैं और इसके विपरीत)। प्रत्येक कॉलम में समान लीवर होते हैं (जो कि मैं संबंधित कॉलम में डायोड का उपयोग करता हूं)।
एरिक ने सोचा कि क्या लीवर को स्विच करके डायोड को उसी अवस्था में स्विच करना संभव है।
इनपुट:
पहली पंक्ति में दो प्राकृतिक संख्याएँ n और m (1 <= n, m <= 7) - क्रमशः बोर्ड पर पंक्तियों और स्तंभों की संख्या होती है।
फिर m संख्या के साथ n लाइनें हैं - डायोड की स्थिति, जहां 0 का मतलब है कि डायोड बंद है, और 1 का मतलब है कि यह चालू है।
आउटपुट:
यदि डायोड को एक स्थिति में लाना संभव है तो "हाँ" और यदि असंभव है तो "नहीं" प्रिंट करें।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
2 2
0 1
10 |
हाँ |
2 2
0 1
0 0
| नहीं |
व्याख्या:
पहले उदाहरण में, आप सभी डायोड को पहली पंक्ति में स्विच कर सकते हैं, फिर सभी डायोड को पहले कॉलम में स्विच कर सकते हैं। फिर सभी डायोड बंद हो जाएंगे।