दो नंबर दिए गए हैं, आइए उन्हें X और Y कहते हैं कि उनके बीच सभी "सुपर" नंबर कैसे खोजें।

एक सुपर नंबर एक संख्या है जिसके पड़ोसी अंकों का पूर्ण अंतर 1 से अधिक है, उदाहरण के लिए, संख्या 132 एक सुपर संख्या नहीं है क्योंकि 3 और 2 में 1 के बराबर अंतर है। संख्या 62 एक सुपर संख्या है क्योंकि 6 के बीच का अंतर और 2, 1 से बड़ा है।

डायनेमिक प्रोग्रामिंग का उपयोग करके एक्स और वाई (शामिल) के बीच सभी सुपर नंबर कैसे खोजें?

1 < X,Y < 10^5000 
-3
Lovren97 14 नवम्बर 2018, 00:30

1 उत्तर

सबसे बढ़िया उत्तर

आप डिजिट डीपी" या "डिजिट पर डीपी" नामक तकनीक का उपयोग कर सकते हैं। आइए कल्पना करें कि हमारे पास एक फ़ंक्शन है f(x) 0 से x (सहित) के बीच पूर्णांकों की संख्या बताता है जो सुपर अंक हैं, यदि आप गणना करना चाहते हैं एक्स, वाई के बीच सुपर नंबरों की संख्या आपको केवल एफ (वाई) और एफ (एक्स -1) की गणना करने की आवश्यकता है, क्योंकि एक्स और वाई के बीच सुपर नंबरों की संख्या बराबर है f(Y)-f(X-1) ( यह नोटिस करना सहज है क्यों)।

तो फलन f(x) कैसा होना चाहिए? आपको तीन राज्यों की आवश्यकता है: अनुक्रमणिका: स्ट्रिंग पर अनुक्रमणिका (संख्या) आप क्या संसाधित कर रहे हैं। तंग: यह बताएगा कि वर्तमान अंकों की सीमा प्रतिबंधित है या नहीं।

उदाहरण के लिए यदि आपके पास नंबर है:

१२३४ आप राज्यों तक पहुँच सकते हैं, ०२३४, ००००, १२३१, आदि (संख्या कम या १२३४ के बराबर)

लेकिन आप नहीं पहुँच सकते: २२३४, १२४४, आदि।

सख्त इसे नियंत्रित करने के साथ सौदा करता है।

अंतिम: अंतिम उपयोग किया गया अंक, यह आपको ट्रांज़िशन में मदद करेगा, उदाहरण के लिए यदि आपका अंतिम उपयोग किया गया अंक 4 है तो आपका अगला अंक 0, 1, 2 या 6, 7, 8, 9 हो सकता है (ये तभी हो सकता है जब टाइट न हो सक्रिय)।

मैं आपको एक ट्यूटोरियल और स्थान देता हूं जहां आप अधिक जानकारी प्राप्त कर सकते हैं:

यहां https://www.geeksforgeeks.org/digit-dp-introduction/ आप विचार, और कड़े उपयोग के बारे में बेहतर समझ सकते हैं। आप प्रतिस्पर्धी प्रोग्रामिंग पेज जैसे कोडफोर्स, टॉपकोडर, कोडशेफ के बारे में भी जानकारी प्राप्त कर सकते हैं।

मैं आमतौर पर इन समस्याओं को प्रतिस्पर्धी प्रोग्रामिंग में देखता हूं, क्या यह किसी न्यायाधीश के लिए एक समस्या है? मैं एक समाधान का प्रयास करना चाहता हूं। . अगर ऐसा है, तो मैं वास्तव में आशा करता हूं कि आप लाइव प्रतियोगिता में नहीं होंगे।

1
LuaXD 14 नवम्बर 2018, 16:22