प्रत्येक के पूर्णांक पूर्णांक से एक अंक को देखते हुए अनुक्रम

Question

की एक श्रृंखला X से शुरू होने वाले लगातार सकारात्मक पूर्णांक नीचे लिखी गई है। फिर प्रत्येक नंबर से बिल्कुल एक अंक चुना जाता है और उसी क्रम में लिखा जाता है। हमें सबसे छोटे X को खोजने की आवश्यकता है जिसके लिए अंकों की श्रृंखला संतुष्ट है।

N और अंकों की श्रृंखला इनपुट के रूप में दी जाती है। मैंने कुछ गणितीय अंतर्दृष्टि खोजने की कोशिश की लेकिन असफल रहा। N 10^5 जितना बड़ा हो सकता है।

दूसरे शब्दों में, दिए गए और सरणी ए लंबाई वाले एन युक्त अंक, हमें एक लंबाई बी को लगातार सकारात्मक पूर्णांक (बी [i + 1] = बी [i] + 1) युक्त अंक प्राप्त करने की आवश्यकता है ए [i] संख्या बी में पाया जा सकता है [i] और बी [0] सबसे छोटा संभव है। (बी में कोई संख्या अग्रणी नहीं है 0)।

उदाहरण के लिए: यदि दिया गया 9, 2, 1, 2, 2 तो सबसे छोटा एक्स 1 9 (1 9, 20, 21, 22, 23) है।

एक और उदाहरण: यदि 9 8 9 1 0 दिया गया तो ऐसा अनुक्रम 97 98 99 100 101 होगा। देखें कि आप इस श्रृंखला में दिए गए अनुक्रम में दिए गए अनुक्रम में उन अंकों को पा सकते हैं। और 9 7 सबसे छोटा संभव प्रारंभिक संख्या है (10 9 7 भी पर्याप्त होगा लेकिन सबसे छोटा नहीं)।

इस पर पहुंचने के तरीके और इस तरह की समस्या के बारे में कोई संकेत उपयोगी होगा।

Answer 1

यहां एक O(N^2) -ish एल्गोरिदम है, जो शायद पर्याप्त हो सकता है या नहीं, क्योंकि आपने मूल समस्या को लिंक नहीं किया है, ताकि विस्तृत आवश्यकताएं अज्ञात हों।

मुझे निम्नलिखित में N = 100000 का अनुमान लगाया जाएगा।

For every y in [0, 100000): 
    Consider the case that B[0] = 100000 * x + y for some x. 
    This will be equivalent to requiring that x contains some of the digits in [0, 10), 
    and that x + 1 contains some of the digits in [0, 10), 
    from which a smallest x can easily be found (or pre-computed). 
    (But the special case x = 0 needs further attention, problem of leading zero.) 
Find the maximun of all 100000 * x + y found above, which is the answer. 

(, एक अंतिम तीन अंक पर, आदि दिखाई दे सकता है अंतिम पाँच अंक को देखने का उदाहरण बजाय) आगे अनुकूलन, समान विचार के साथ कर रहे हैं। लेकिन अब मैं इन विवरणों को पोस्ट नहीं करूंगा।

Answer 2

इस तरह आप मैन्युअल रूप से पहला उदाहरण का समाधान होता है:

उदाहरण: 9, 2, 1, 2, 2

→ संख्या 5 या कम अंकों का होता है।

9, 2

9 और 2 अलग, और नहीं लगातार → वे अलग अलग स्थानों पर इस प्रकार हैं:

9****, *2*** 

9, 2, 1

1 9 का पालन कर सकता है, लेकिन केवल तभी जब वे सबसे कम स्थिति में हैं (संयुक्त इसके):

****9, 2***0, 2***1 
9****, *2***, **1** 

9, 2, 1, 2

2 9 और/या 1, लेकिन केवल न्यूनतम स्थिति (यूनिट) में पालन कर सकता है; यह भी पहले 2 के रूप में एक ही स्थिति में हो सकता है, लेकिन सबसे कम की स्थिति में नहीं:

****9, 2***0, ****1, ****2 
****9, 2***0, ****1, 2***2 
****9, 2***0, ****1, *2**2 
****9, 2****, *1***, ****2 
9****, *2***, ****1, ****2 
9****, *2***, **1**, *2*** 
9****, *2***, **1**, ***2* 

9, 2, 1, 2, 2

2 ही में हो सकता है एक या एक से पहले 2 के दोनों है, लेकिन न्यूनतम स्थिति में नहीं के रूप में स्थिति (यूनिट):

****9, 2***0, ****1, ****2, 2***3 min. 2 digits 19, 20, 21, 22, 23 
****9, 2***0, ****1, ****2, *2**3 min. 3 digits 
****9, 2***0, ****1, 2***2, 2***3 min. 2 digits 19, 20, 21, 22, 23 
****9, 2***0, ****1, 2***2, *2**3 min. 3 digits 
****9, 2***0, ****1, *2**2, 2***3 min. 3 digits 
****9, 2***0, ****1, *2***, **2*3 min. 4 digits 
****9, 2***0, *1**1, ****2, 2***3 min. 3 digits 
****9, 2***0, *1**1, ****2, **2*3 min. 4 digits 
9****, *2***, ****1, ****2, *2**3 min. 3 digits 
9****, *2***, ****1, ****2, **2*3 min. 4 digits 
9****, *2***, **1**, *2***, *2*** min. 3 digits 
9****, *2***, **1**, *2***, ***2* min. 4 digits 
9****, *2***, **1**, ***2*, *2*** min. 4 digits 
9****, *2***, **1**, ***2*, ****2 min. 5 digits 

---

कुंजी की संख्या को सीमित करने के लिए कोशिश करने की संभावनाएं सबसे अधिक आशाजनक अनुसरण करने के लिए निश्चित रूप से है (यानी। अंकों की) पथ सबसे कम संख्या पहले, जैसा कि हम दूसरे उदाहरण के लिए करेंगे:

उदाहरण: 9, 8, 9, 1, 0

→ संख्या 5 या कम अंकों का होता है।

9, 8

8 केवल 9 से एक अलग स्थिति में हो सकते हैं:

9****, *8*** min. 2 digits 

9, 8, 9

9 में हो सकता है 9 (या निम्नतम) स्थिति 9 के रूप में, या समान (निम्न) स्थिति 8:

के रूप में

9****, 98***, 9**** min. 2 digits 
9***7, ****8, ****9 min. 2 digits 

9, 8, 9, 1

1 अन्य अंकों की किसी भी रूप में एक ही स्थिति में नहीं किया जा सकता:

9****, 98***, 9****, **1** min. 3 digits 
9***7, ****8, ****9, *1**0 min. 3 digits 

9, 8, 9 , 1, 0

0 एक या दोनों के बाद आ सकता है नहीं, बल्कि न्यूनतम स्थिति में 9 की:

9****, 98***, 9****, **1**, 0**** min. 3 digits 97, 98, 99, 100, 101 
9***7, ****8, ****9, *1**0, 0***1 min. 3 digits 97, 98, 99, 100, 101 

---

तो एक संभावित एल्गोरिदम होगा:

• प्रत्येक नए अंकों के लिए, जाँच यह पिछले अंक में से किसी का पालन कर सकता है या नहीं, और जिसमें पद (1 → 2 प्रत्येक स्थिति में हो सकता है, लेकिन 1 3 या 1 → x → x → 4 केवल निम्नतम स्थिति में; 1 → 1 किसी भी सबसे कम स्थिति में हो सकता है)।
• पहले सबसे अधिक आशाजनक पथ देखें, यानी यदि कोई नया अंक पिछले अंक के समान स्थिति में हो सकता है।
• यदि नया अंक पिछले किसी भी अंक का पालन नहीं कर सकता है, तो केवल एक अतिरिक्त स्थिति पर विचार करें (यानी समाधान में अंकों की न्यूनतम संख्या)।
• यदि आपको केवल बड़े समाधान मिलते हैं, बैकट्रैक और उस समय का चयन करें जो उस समय कम आशाजनक दिखता हो।

मुझे यकीन नहीं है कि आप यह बताने में सक्षम होंगे कि बैकट्रैकिंग शुरू करने के बाद सबसे छोटा समाधान मिल गया है। यदि आपको n अंकों के साथ कोई समाधान मिल गया है, तो आपको निश्चित रूप से n अंकों के साथ सभी समाधानों की जांच करनी चाहिए।