प्रोग्रामर के लिए प्रतियोगिता №2

वस्तुओं का एक स्थान है । प्रत्येक वस्तु की पहचान 4-बाइट पहचानकर्ता द्वारा की जाती है। वस्तुओं के बीच दिशात्मक संचार होते हैं । प्रत्येक लिंक को प्रारंभिक वस्तु के एक पहचानकर्ता, अंतिम वस्तु के एक पहचानकर्ता और सूचना भार के 4 बाइट्स की विशेषता है। कनेक्शन अनुक्रम object1-> object2; object2-> object3; ... रूप मार्ग । मार्ग की लंबाई लिंक की संख्या से निर्धारित होती है। एक वस्तु से कई वस्तुएं गुजर सकती हैं। यदि रूट कनेक्शन में से किसी एक का अंतिम ऑब्जेक्ट किसी अन्य रूट कनेक्शन का प्रारंभिक ऑब्जेक्ट है, तो एक रूट बंद किया जा सकता है। एक बंद मार्ग की लंबाई लिंक से लिंक की संख्या है, जिसमें अंतिम ऑब्जेक्ट किसी अन्य रूट लिंक की प्रारंभिक वस्तु है, इस लिंक को शामिल नहीं किया गया है।

इनपुट फ़ाइल में प्रारूप में लिंक की एक सूची है:

4 बाइट्स ऑब्जेक्ट आइडेंटिफ़ायर शुरू
4 बाइट्स गंतव्य पहचानकर्ता
4 बाइट्स संचार लोड

चाहिए
रूट फ़ाइल (रूट, यदि कई हैं) को इनपुट फ़ाइल में अधिकतम लंबाई का पता लगाएं और प्रारूप में आउटपुट फ़ाइल में सहेजें

4 बाइट्स मार्ग की लंबाई
12 एक्स मार्ग लंबाई मार्ग लिंक सूची

मैं आपको याद दिलाता हूं कि प्रतियोगिता के नियम, साथ ही स्रोत फ़ाइल यहां मिल सकती है

गुड लक !!!

युपीडी:
फिलहाल (03/15/2011 17:30)

2 उत्तर हैं
1 उत्तर का विश्लेषण:

फ़ाइल एक रूट फ़ाइल है: नहीं

2 उत्तर का विश्लेषण:

फ़ाइल एक रूट फ़ाइल है: हाँ
मार्ग लिंक की संख्या: 264
क्या मार्ग खुला है: हाँ
मार्ग एक उत्तर विकल्प है: हाँ

लेकिन मार्ग की लंबाई अधिकतम नहीं है, फ़ाइल में अधिक मार्ग हैं, यह इतना सरल नहीं है।

हालांकि कोई सही उत्तर नहीं है, प्रतियोगिता जारी है

युपीडी:
फिलहाल (03/16/2011 17:00)
कोई नया जवाब नहीं

प्रतियोगिता की गतिशीलता को देखते हुए, एक प्रयास का नियम रद्द कर दिया गया है

युपीडी:
फिलहाल (03/17/2011 18:00)
कोई नया जवाब नहीं
प्रतियोगिता जारी है

इसलिए, प्रोग्रामर नंबर 2 के लिए प्रतियोगिता की घोषणा के बाद सप्ताह समाप्त हो गया है

प्रतियोगिता के दौरान, 2 उत्तरों की पेशकश की गई थी, सही उत्तर - 0. यह कार्य असाध्य था और अनिश्चित काल के लिए मॉथबॉल किया जाएगा।

प्रिय पाठक! यदि आप इस प्रविष्टि को इसके प्रकाशन के 300 साल बाद पढ़ते हैं (शायद थोड़ा पहले या थोड़ा बाद में) जानते हैं कि 2011 में यह कार्य कठिन माना जाता था, और मैं किसी को भी नहीं जानता (खुद को छोड़कर) जो इसे एक से कम में हल कर सकते थे एक सप्ताह। हमारे समय में औसत कंप्यूटर के प्रोसेसर की घड़ी की गति 3 गीगाहर्ट्ज़ थी, एक कंप्यूटर के प्रोसेसर की औसत संख्या चार थी। यदि आप समस्या को हल कर सकते हैं, तो कृपया मुझे बताएं, और अगर मैं अभी भी जीवित हूं, तो मैं अपने ब्लॉग के पन्नों पर लिखूंगा (वे बहुत अच्छे हैं;)

युपीडी:
प्रोग्रामर के लिए प्रतियोगिता संख्या 2 का कार्य इस सहस्राब्दी में हल किया गया है!

फ़ाइल विश्लेषण परिणाम:

फ़ाइल एक मार्ग है: हाँ
मार्ग लिंक की संख्या: 90899
क्या मार्ग खुला है: हाँ
मार्ग एक उत्तर विकल्प है: हाँ

प्रतियोगिता की घोषणा के 17 दिन बाद 31 मार्च को जवाब मिला।
नायक का नाम एलेक्स है! [ escoman @ ]
बधाई! ऐसा लगता है कि ऐसे कई लोग नहीं हैं जो इस समस्या को हल कर सकते हैं, यह वास्तव में अच्छा है!

मिनी साक्षात्कार: :)

टास्क नंबर 2 के समाधान को सरल बनाने के लिए, मैंने तुरंत FromPoint फ़ील्ड द्वारा स्रोत फ़ाइल को सॉर्ट किया और इसे सहेजा। इससे बाद में लिंक की सूची में बाइनरी खोज का उपयोग करने में मदद मिली।

मूल संचार क्षेत्रों (FromPoint, ToPoint और डेटा) के अलावा, मैंने मैक्सलेन फ़ील्ड को जोड़ा - एक ऐसा क्षेत्र जो इस कनेक्शन से गुजरने वाले लिंक की अधिकतम संख्या को संग्रहीत करता है। इसके अलावा, यह क्षेत्र इस बात का सूचक है कि एल्गोरिथ्म संचार से गुजरा है या नहीं। इसने हमें कई बार एक ही कनेक्शन का पालन नहीं करने दिया।

नतीजतन, मेरे लैपटॉप पर परिणामस्वरूप एल्गोरिथ्म लगभग 2 घंटे के लिए एक समाधान की तलाश में है। हालांकि इसमें अड़चनें हैं जिन्हें सुधारा जा सकता है ...