पेट्र मिट्रिक - फेसबुक हैकर कप के विजेता

फेसबुक हैकर कप को जमा किया। यह प्रतियोगिता, जिसमें दुनिया भर के 11768 लोगों ने भाग लिया था, को तीन राउंड में "मक्खी पर जटिल एल्गोरिथम समस्याओं को हल करने" के प्रारूप में आयोजित किया गया है। फाइनल मैच के लिए पालो अल्टो में फेसबुक मुख्यालय में पच्चीस फाइनलिस्ट आमंत्रित किए गए थे।

पोलैंड से 7 प्रतिनिधि, रूस से 6, यूएसए से 4, जापान से 2 और चीन, जर्मनी, नीदरलैंड, सिंगापुर, स्विट्जरलैंड और यूक्रेन से एक-एक फाइनल में पहुंचे। वे सभी फेसबुक के कार्यालय में 2 दिन बिताने में सक्षम थे: डेवलपर्स के साथ मिलना, कैफे एक्स में भोजन करना, कैटन खेलना और रिपस्टिक पर सवारी करने का प्रयास करना।

प्रतिभागियों को एक मशीन (मैक या पीसी) चुनने का अवसर मिला, जिसके बाद अंतिम दौर शुरू हुआ। फाइनलिस्ट को तीन एल्गोरिथम समस्याओं को हल करने की आवश्यकता थी: पार्टी समय, सबसे सुरक्षित स्थान और विदेशी खेल - जितनी जल्दी हो सके।

प्रत्येक कार्य के लिए समाधान तैयार होते ही परिणाम अदालत में प्रस्तुत किए जाते हैं, और दो घंटे के दौर के अंत में, प्रत्येक प्रतिभागी के लिए अंकों की कुल संख्या की गणना की जाती है।

आप फेसबुक इंजीनियरिंग ब्लॉग पर कार्यों की शर्तों को देख सकते हैं (हालांकि, अगर कोई मांग है, तो मैं उन्हें बाद में अनुवाद करने का प्रयास कर सकता हूं)।

नतीजतन, हमारे हमवतन प्योत्र मित्रीचेव ( कई समान प्रतियोगिताओं के प्रतिभागी और विजेता ) "स्वर्ण" में चले गए।

UPD # 1 - स्किमिनोक से दिलचस्प विवरण:
मैं यह भी जोड़ूंगा कि विजेता के संबंध में एक अद्भुत साज़िश थी।
मित्रीचेव का मुख्य प्रतिद्वंद्वी लू तियान चेंग है, जिसे आरसीयूश के नाम से भी जाना जाता है।
इस प्रतियोगिता का सिद्धांत यह है कि तीन कार्यों में से प्रत्येक का मूल्यांकन 1 बिंदु पर किया जाता है, और स्टैंडिंग में सबसे अधिक कार्यों के साथ एक पारित किया जाता है, और यदि यह बराबर है, तो गोल की शुरुआत से प्रत्येक कार्य पर खर्च किया गया कुल समय कम है। इस मामले में, उत्तर की अंतिम जांच राउंड समाप्त होने के बाद ही होती है।

इसलिए, आरसीयूश पूरे दौर में मित्रीचेव से आगे था। मित्रीचेव ने समान कार्य सौंपे, संख्या के संदर्भ में वे हमेशा एक ही थे - लेकिन आरसीयूश ने उन्हें तेजी से सौंप दिया, हमें अब पेटिट की जीत की उम्मीद नहीं थी। और फिर दौर समाप्त होता है, अंतिम जाँच होती है, और ACRush गलत उत्तर के साथ किसी एक कार्य को छोड़ देता है, और वह खुद को दो बिंदुओं के साथ पाता है, और दो स्थानों पर गिर जाता है, जिससे पेट्या को तीन और अधिक धीरे-धीरे हल किया जाता है, लेकिन सही ढंग से।

UPD # 2 - कार्यों का अनुवाद ( स्किमिनोक में फिर से धन्यवाद)

टास्क 1. एलियंस का खेल।

एक अज्ञात ग्रह पर, एलियंस पारंपरिक रूप से एक खेल खेलते हैं जिसे लोटेन कहा जाता है। इसमें दो खिलाड़ी शामिल हैं जो टर्न लेते हैं। खिलाड़ियों के सामने, सेब के एन बास्केट एक पंक्ति में पंक्तिबद्ध हैं। वे 1 से शुरू होने वाले पूर्णांक के साथ बाएं से दाएं तक गिने जाते हैं।

प्रत्येक चाल में बास्केट में से एक को चुनने वाले खिलाड़ी होते हैं, जो पंक्ति में पहला और अंतिम नहीं होता है, और जिसमें सेब की संख्या सकारात्मक होती है, और इस टोकरी में सभी सेबों को बाईं ओर टोकरी में स्थानांतरित कर देता है, जबकि एक ही समय में उन सभी को स्थानांतरित करता है। सही करने के लिए टोकरी के बगल में। हां, इस वास्तव में अजीब ग्रह पर, सेब की संख्या नकारात्मक हो सकती है। तो, अगर 3 लगातार टोकरियाँ हैं जिनमें क्रमशः x , y , z सेब हैं, तो आप उनके साथ एक चाल बना सकते हैं यदि y शून्य से अधिक है। परिणामस्वरूप, चाल के बाद, टोकरियों में निम्नलिखित मात्राएँ होंगी: x + y , - y , z + y । खिलाड़ी जो इस कदम को नहीं हार सकता है।

आप अज्ञात ग्रह के निवासियों में से एक से परिचित हैं, जिसका नाम पोपो है। वह लोटेन में एक महान खिलाड़ी है, और लुटेन ग्रह चैम्पियनशिप के फाइनल में गया। खेल से एक दिन पहले, उन्होंने किसी तरह पता लगाया कि प्रत्येक बास्केट में कितने सेब होंगे। दुर्भाग्य से, उसके पास बहुत अच्छी स्मृति नहीं है, और वह टोकरी में सेब की संख्या पी को भूल गया । वह केवल यह याद रखता है कि यह संख्या निरपेक्ष मान से F से अधिक नहीं है।

अब, वह आपको जीतने की संभावनाओं की गणना करने के लिए कहता है। इतने अच्छे खिलाड़ी चैंपियनशिप के फाइनल में जाते हैं कि वे हमेशा जीतने के अपने मौके को अधिकतम करने के लिए केवल सर्वश्रेष्ठ चाल चलते हैं। यदि कोई खिलाड़ी नहीं जीत सकता है, तो एक टाई को गिना जाता है। आपको टोकरी नंबर P में सेब की संभावित मात्रा का पता लगाना होगा, जिस पर पोपो जीतता है। पोपो को भी यकीन है कि यह वह है जो खेल में पहला कदम रखता है।

इनपुट डेटा
इनपुट की पहली पंक्ति में एक पूर्णांक टी , परीक्षण की संख्या शामिल है। प्रत्येक परीक्षण दो पूर्णांक वाली एक पंक्ति से शुरू होता है: एन , बास्केट की संख्या और पी , अज्ञात संख्या में सेब के साथ टोकरी की संख्या। अगली पंक्ति में एन पूर्णांक हैं - संबंधित बास्केट में सेब की संख्या। इस पंक्ति पर Pth संख्या एक सकारात्मक पूर्णांक F है , जो Pth टोकरी में सेब की संख्या की सीमा के अनुरूप है।

उत्पादन
आउटपुट फ़ाइल में टी लाइनें, एक प्रति परीक्षण होना चाहिए। प्रत्येक पंक्ति में संबंधित परीक्षण का उत्तर है, Pth टोकरी के लिए सेब की संख्या के लिए संभावित जीत मूल्यों की संख्या।

प्रतिबंध
टी = 50
1 1 पी ≤ एन । 2,000।
1 ≤ F ≤ 1,000,000,000,000।
खेल की शुरुआत से पहले, प्रत्येक टोकरी में सेब की संख्या निरपेक्ष मूल्य में 1,000,000,000,000 से अधिक नहीं होती है।

टास्क 2. एक सुरक्षित जगह।
बिग गेलेक्टिक पार्टी की 295 वीं वर्षगांठ के रास्ते पर, आपको अचानक अनजाने में हाइपरस्पेस से बाहर निकाल दिया गया था और अब, सेंसर के अनुसार, आप एन स्पेस बम से घिरे हैं। निस्संदेह, आप किसी अज्ञात शत्रु द्वारा स्थापित जाल में गिर गए हैं, आप हाइपरस्पेस पर नहीं लौट सकते हैं, और अब आपको सभी बमों के विस्फोट से बचने के लिए आसपास के क्षेत्र में सबसे सुरक्षित जगह ढूंढनी होगी। एक अदृश्य प्रतिद्वंद्वी ने एक घन के रूप में एक अंतरिक्ष विसंगति बनाई है जिसके आगे आप उड़ नहीं सकते हैं, ताकि आपके स्थान के लिए एक विकल्प के रूप में, इस घन के भीतर के केवल अंक आपके लिए उपलब्ध हों।

इससे पहले कि सभी बम एक साथ फट जाएं, आपके पास घन [0, 0, 0] - [1000, 1000, 1000], समावेशी के भीतर किसी भी पूर्णांक बिंदु तक पहुंचने के लिए पर्याप्त समय है। आपको एक बिंदु खोजने की आवश्यकता है जिस पर निकटतम बम की दूरी अधिकतम है, क्योंकि आपका अंतर्ज्ञान आपको बताता है कि यह सबसे सुरक्षित जगह होगी।

इनपुट डेटा
इनपुट की पहली पंक्ति में एक पूर्णांक टी , परीक्षण की संख्या शामिल है। प्रत्येक परीक्षण एक पूर्णांक एन के साथ शुरू होता है, बमों की संख्या, इसके बाद 3 * एन पूर्णांक होते हैं जो प्रत्येक बम के निर्देशांक को निर्दिष्ट करते हैं।

उत्पादन
आउटपुट फ़ाइल में टी लाइनें, एक प्रति परीक्षण होना चाहिए। प्रत्येक पंक्ति पर घन में सबसे सुरक्षित बिंदु से निकटतम बम की दूरी का वर्ग है।

प्रतिबंध
टी = 50
1 ≤ एन ≤ 200
बमों के सभी निर्देशांक [0, 1000] के भीतर हैं।

कार्य 3. किसी पार्टी के लिए समय
आप अपने दोस्तों के लिए एक पार्टी कर रहे हैं, लेकिन चूंकि आपके सभी दोस्त एक-दूसरे को नहीं जानते हैं, इसलिए आप डरते हैं कि उनमें से कुछ पार्टी को पसंद न करें। इस स्थिति से बचने के लिए, आपने अपने दोस्तों के कुछ दोस्तों को आमंत्रित करने का भी फैसला किया। लेकिन वास्तव में एक महान पार्टी प्राप्त करने के लिए किसे आमंत्रित किया जाए?

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

आप G से कई मेहमानों का चयन करना चाहते हैं । मेहमानों के इस सेट में आपके सभी दोस्त होने चाहिए, और इसके अलावा, मेहमानों द्वारा गठित सबग्राफ जी जुड़ा होना चाहिए। आपको लगता है कि यह सभी को पार्टी का आनंद लेने के लिए पर्याप्त होगा, क्योंकि किसी भी दो मेहमानों के बारे में बात करने के लिए कुछ होगा ...

पैसे बचाने के लिए, आपने बहुत सारे मेहमानों को चुनने का फैसला किया ताकि भोजन की कुल मात्रा यथासंभव कम हो। यदि यह कई अलग-अलग तरीकों से प्राप्त किया जा सकता है, तो मेहमानों की कम से कम संख्या के साथ विधि को प्राथमिकता दी जाती है।

सामाजिक ग्राफ के आपके सबसेट जी में लोगों / चोटियों को 0 से N - 1 तक गिना जाता है। इसके अलावा, आपकी सुविधा के लिए, आपके दोस्तों के पास 0 से लेकर F - 1 तक के नंबर हैं, जहाँ F आपके द्वारा आमंत्रित किए जाने वाले दोस्तों की संख्या है। हम यह भी मान सकते हैं कि जी हमेशा जुड़ा हुआ है। हम आपको एक बार फिर याद दिलाते हैं कि आप व्यक्तिगत रूप से जी में प्रतिनिधित्व नहीं करते हैं ।

इनपुट डेटा
इनपुट की पहली पंक्ति में एक पूर्णांक टी , परीक्षण की संख्या शामिल है। प्रत्येक परीक्षण की पहली पंक्ति में तीन पूर्णांक होते हैं: एन - जी में कोने की संख्या, एफ - आपके दोस्तों की संख्या और एम - जी में किनारों की संख्या। अगला, एम लाइनें, प्रत्येक में दो पूर्णांक। पहली ऐसी पंक्ति में दो अलग-अलग पूर्णांक u और v हैं , जिसका अर्थ है व्यक्ति संख्या u और व्यक्ति संख्या v के बीच पारस्परिक मित्रता। उसके बाद, परीक्षण की अंतिम पंक्ति में रिक्त स्थान के माध्यम से एन पूर्णांक होते हैं, जहां i- वीं संख्या व्यक्ति संख्या i द्वारा आवश्यक भोजन की मात्रा होती है।

उत्पादन
आउटपुट फ़ाइल में टी लाइनें, एक प्रति परीक्षण होना चाहिए। प्रत्येक पंक्ति में एक स्थान द्वारा अलग किए गए दो नंबर होते हैं: उपरोक्त शर्तों को पूरा करने वाली पार्टी के लिए भोजन की न्यूनतम कुल राशि और ऐसी पार्टी में लोगों की न्यूनतम संख्या।

प्रतिबंध
टी = 50
1 ≤ एफ ≤ 11
एफ -1 एन -1
2 ≤ एन ≤ 250
एन -1) एम ≤ एन * ( एन - 1) / 2
जी जुड़ा हुआ है और इसमें छोर या कई किनारे नहीं हैं।
प्रत्येक व्यक्ति के लिए, उसके लिए आवश्यक भोजन की मात्रा 0 से 1000 तक की होती है।