रूसी कोड कप 2013 - द्वितीय योग्यता दौर के कार्यों का विश्लेषण

इसलिए रूसी कोड कप का दूसरा क्वालीफाइंग दौर बीत गया। मई की छुट्टियां, कई कहीं गई ... हालांकि, क्वालिफाई करने के लिए, दूसरे क्वालीफाइंग राउंड के प्रतिभागियों को प्रतिस्पर्धा करनी थी।
पिछले दौर में, समाधान भेजने वालों की तुलना में अधिक कुलसचिव थे। इसलिए, भाग लेने वालों में, हम केवल उन लोगों को दर्शाते हैं जिन्होंने कम से कम एक निर्णय भेजा है।
2 घंटे में हल करने के लिए मई गर्मी और 5 कार्य:

• समस्या ए। अणु
• टास्क B. नौसेना लड़ाई
• कार्य सी। ट्रैफिक जाम
• कार्य डी। टेबल
• टास्क ई। अंतरिक्ष अभियान

शर्तों और समाधान - कटौती के तहत।

दूसरी योग्यता के परिणामों पर कुछ आंकड़े।
राउंड 735 लोगों के दौरान अधिकृत। इनमें से 536 लोगों द्वारा कम से कम एक समाधान भेजा गया था।
कुल 2707 समाधान भेजे गए थे।
यहां प्रतिभागियों के उपनाम हैं जिन्होंने सबसे पहले समस्याओं का सही समाधान भेजा (कोष्ठक में मिनट और सेकंड में गोल शुरू होने के बाद का समय)

• टास्क ए: रेब्लास्ट (2:56)
• समस्या B: मिलिन (14:58)
• टास्क सी: कान (20:27)
• टास्क डी: XopEka (51:58)
• टास्क ई: maria.sharapova (18:45)

इस दौर में प्रतिभागियों का क्षेत्रीय वितरण निम्नानुसार था:
रूस => 343
यूक्रेन => 78
बेलारूस => 29
संयुक्त राज्य => 22
कजाकिस्तान => १६
आर्मेनिया => 8
पोलैंड => 5
अजरबैजान => ४
उजबेकिस्तान => ४
आयरलैंड => 3
जॉर्जिया => ३
किर्गिस्तान => ३
स्वीडन => २
यूके => २
जर्मनी => २
मोलदोवा => २
आइसलैंड => 1
बेल्जियम => १
पाकिस्तान => १
लातविया => १
कोरिया गणराज्य => १
स्पेन => १
चीन => १
चेक गणराज्य => १
स्विट्जरलैंड => १
कनाडा => १
क्वालीफाइंग दौर में, पिछले दौर की तरह, 201 लोगों ने प्रवेश किया।

1. मिखाइल कोलुपावे
2. एवगेनी सोबोलेव
3. एंड्रे ग्रिनेंको
4. एवगेनी कपुन
5. डेनिस ने प्रतिबंधित किया
6. एलेक्सी सफ्रोनोव
7. व्लादिस्लाव सिमेंको
8. एंड्री पाव्लिसको
9. ईगोर सुवोरोव
10. पावेल माव्रिन

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

समस्या ए। अणु
विचार: विटाली अक्षेनोव
शर्त: अन्ना मालोवा
कार्यान्वयन: एंड्री कोमारोव
विश्लेषण: अन्ना मालोवा

टास्क की स्थिति
2 सेकंड की समय सीमा
256 एमबी मेमोरी सीमा
एक शीर्ष-गुप्त प्रयोगशाला में हालिया शोध के परिणामस्वरूप, एक नए पदार्थ की खोज की गई थी। इस पदार्थ का प्रत्येक अणु दो प्रकार के परमाणुओं से युक्त एक चक्र का प्रतिनिधित्व करता है, जिसे हम मनमाने ढंग से काले और सफ़ेद कहेंगे (परमाणुओं के वास्तविक नाम सख्त विश्वास में रखे गए हैं)। एक शीर्ष-गुप्त प्रतिक्रिया को अंजाम देने के लिए, अणु को एक अस्थिर अवस्था में स्थानांतरित करना आवश्यक है जिसमें वह दो स्वतंत्र अणुओं में क्षय कर सकता है, जिनमें से प्रत्येक में केवल एक प्रकार का परमाणु होता है।
अध्ययनों से पता चला है कि एक अणु टूट जाता है यदि प्रत्येक रंग के सभी परमाणु एक निरंतर ब्लॉक बनाते हैं।
अणु को पुनर्व्यवस्थित करने के लिए, वैज्ञानिक निम्नलिखित ऑपरेशन कर सकते हैं: परमाणुओं के निरंतर क्रम को चक्र से काटकर दूसरी जगह डाला जाता है। एक अणु के पुनर्व्यवस्था का एक उदाहरण चित्र में दिखाया गया है।

अब वैज्ञानिक यह पता लगाने की कोशिश कर रहे हैं कि वर्णित ऑपरेशन की न्यूनतम संख्या एक अणु को अस्थिर अवस्था में ला सकती है। उन्हें यह पता लगाने में मदद करें।

इनपुट प्रारूप	इनपुट फ़ाइल की पहली पंक्ति में एक प्राकृतिक संख्या n होती है - उन अणुओं की संख्या जिनकी जांच किए जाने की आवश्यकता होती है। अगली एन लाइनों में से प्रत्येक में निम्नलिखित प्रारूप में एक अणु का विवरण होता है: एक पंक्ति जिसमें क्रमशः सफेद और काले परमाणुओं का प्रतिनिधित्व करते हुए कम से कम तीन अक्षर डब्ल्यू और बी होते हैं। यह गारंटी है कि प्रत्येक अक्षर प्रत्येक अणु में कम से कम एक बार होता है। सभी अणुओं की कुल लंबाई 200,000 से अधिक नहीं है।
आउटपुट स्वरूप	एन लाइनों को प्रिंट करें। I-th लाइन में उन न्यूनतम ऑपरेशनों को प्रिंट करें, जिन्हें अस्थिर अवस्था में जाने के लिए i-th अणु के लिए निष्पादित किया जाना चाहिए।
उदाहरण	इनपुट डेटा उत्पादन 3 wbbw wbbwb wbwbwb 0 1 2

पदच्छेद

अणु में एक ही रंग के ब्लॉक की संख्या को मीटर द्वारा निरूपित करें। ध्यान दें कि मी सम है, और ब्लैक एंड व्हाइट ब्लॉक्स की संख्या समान है। इस तथ्य से कि टुकड़ा के दो छोर हैं, और यह दो ब्लॉकों को छूता है, यह इस प्रकार है कि अणु के प्रत्येक पुनर्गठन के साथ, प्रत्येक रंग के ब्लॉकों की संख्या एक से अधिक नहीं घट जाएगी। आप प्रत्येक रंग के ब्लॉक की संख्या को निम्नानुसार एक से कम कर सकते हैं: एक ब्लॉक को काटें और उसी रंग के दूसरे ब्लॉक के बीच में एम्बेड करें। इस प्रकार, कुल मिलाकर, वैज्ञानिकों को मी / 2 - 1 संचालन की आवश्यकता होगी।
भागो समय ओ (अणु लंबाई)।

टास्क बी नवल लड़ाई
विचार: विटाली अक्षोनोव
कार्यान्वयन: बोरिस मिनाएव
विश्लेषण: बोरिस मिनाएव

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

इनपुट प्रारूप	पहली पंक्ति में एक पूर्णांक टी (1 ≤ t) 105) - परीक्षणों की संख्या है। प्रत्येक परीक्षण के विवरण में 4 लाइनें होती हैं। उनमें से पहले में दो पूर्णांक ए और बी (1 B ए, बी) 109) हैं - आयत के आयाम जिसमें जहाजों को रखना आवश्यक है। अगली तीन पंक्तियों में दो पूर्णांक ai और द्वि (1, ai, द्वि lines 109) शामिल हैं - i-th जहाज के आयाम।
आउटपुट स्वरूप	आपको टी लाइनों को प्रिंट करने की आवश्यकता है जो इनपुट से परीक्षण उत्तर हैं। प्रत्येक परीक्षण आउटपुट के लिए हां, यदि जहाजों को रखा जा सकता है, और नहीं तो।
उदाहरण	इनपुट डेटा उत्पादन 2 7 7 ६ ३ ६ १ ३ ३ ४ ४ ५ १ १ १ १ २ हां नहीं

पदच्छेद

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

समस्या सी। कॉर्क
विचार: विटाली अक्षेनोव
अहसास: निकोले वेदरनिकोव
विश्लेषण: निकोले वेदरनिकोव

टास्क की स्थिति
2 सेकंड की समय सीमा
256 एमबी मेमोरी सीमा
2050 में, सड़क सुरक्षा में सुधार के लिए सभी सड़कों पर ओवरटेकिंग को प्रतिबंधित कर दिया गया था। इसके अलावा, L मीटर की तुलना में करीब सामने वाले वाहन को ले जाना मना है। नियमों का अनुपालन सभी सड़कों पर लगाए गए कैमरों द्वारा निगरानी की जाती है। दुर्भाग्य से, इन उपायों ने ट्रैफिक जाम के खिलाफ लड़ाई में पूरी तरह से मदद नहीं की।
प्रोफेसर स्विंकिन को हर सुबह घर से काम करने को मिलता है। जिस सड़क पर वह यात्रा करता है वह एक सीधी रेखा है। हम एक मीटर के बराबर इकाई के साथ उस पर एक समन्वय प्रणाली शुरू करते हैं, और हम इस रेखा पर खंडों के रूप में मशीनों का प्रतिनिधित्व करेंगे, जो बढ़ते निर्देशांक की दिशा में आगे बढ़ते हैं।
प्रारंभ में, प्रोफेसर की कार सड़क की शुरुआत में स्थित होती है, ताकि इसका फ्रंट प्वाइंट मूल स्थान पर हो। प्रोफेसर की अधिकतम गति V मीटर प्रति सेकंड है।
प्रोफेसर की कार के अलावा, सड़क पर n कारें हैं जो सड़क के साथ चलती हैं। वाहन चलाते समय, प्रत्येक मशीन अपनी अधिकतम गति से चलने की कोशिश करती है। जब कार A सामने से कार B के साथ पकड़ लेती है ताकि सामने वाला बिंदु A पीछे के बिंदु B से बिल्कुल L की दूरी पर हो, कार A तुरन्त B को गति देने के लिए अपनी गति को कम कर देता है और फिर गति B में सभी परिवर्तनों को दोहराता है। कोई भी कार सड़क नहीं छोड़ती है।
अपनी नौकरी पाने के लिए प्रोफेसर स्विनकिन को समय निकालें। ऐसा माना जाता है कि यह तब हुआ जब उनकी कार का अगला बिंदु समन्वय एस के साथ एक बिंदु पर था।

इनपुट प्रारूप	कार्य के इनपुट में कई परीक्षण सूट शामिल हैं। प्रत्येक सेट के विवरण में कई लाइनें होती हैं। विवरण की पहली पंक्ति में चार पूर्णांक होते हैं: n, L, S और V (1 of n, 10000, 1, L ≤ 1000, 1 ≤ S, 109, 1 ≤ V) 100) - प्रोफेसर के सामने कारों की संख्या, मशीनों के बीच न्यूनतम दूरी। मीटर में, घर से प्रोफेसर के काम की जगह और मीटर प्रति सेकंड में प्रोफेसर की कार की अधिकतम गति। अगली n लाइनों में तीन पूर्णांक xi, li और vi (1 ≤ xi lines 109, 1, li ≤ 10, 1 ≤ vi) 100) हैं - प्रारंभिक समय में ith मशीन के सामने बिंदु का समन्वय, इसकी लंबाई और अधिकतम मीटर प्रति सेकंड में गति। यह गारंटी है कि मशीनें प्रोफेसर की मशीन को हटाने के क्रम में सेट की गई हैं, और यह कि शुरुआती समय में दो पड़ोसी मशीनों के बीच की दूरी एल मीटर से कम नहीं है। परीक्षण की अंतिम पंक्ति में चार शून्य हैं। सभी परीक्षणों में कारों की कुल संख्या 10,000 से अधिक नहीं है
आउटपुट स्वरूप	प्रत्येक परीक्षण के अनुरोध के लिए, प्रोफेसर को काम करने के लिए सेकंड में, एक अलग लाइन में प्रिंट करें। उत्तर 10 .5 से अधिक नहीं की एक पूर्ण या सापेक्ष त्रुटि के साथ घटाया जाना चाहिए।
उदाहरण	इनपुट डेटा उत्पादन 1 1 10 2 ३ १ १ १ १ १ १ १ ३ २ १ 1 1 10 2 ३ १ २ २ ३ १५ ३ ४ १ २ १० ३ १ 1 3 500 93 123 3 2 ० ० ० ० ९.०००००००००० १०.०००००००००० ५.०००००००००० १५.०००००००००० १९१.५०००००००००

पदच्छेद
कार्य यह पता लगाना था कि प्रोफेसर को अपने काम में कितने मिनट लगेंगे। जब एक कार दूसरे को पकड़ती है, तो वह उसी गति से उसका पीछा करना शुरू कर देता है। तब हम मान सकते हैं कि पहली मशीन की लंबाई लेन _पहले + एल + लेन _{दूसरी है} , और दूसरी नहीं है। उस समय के बिंदु पर विचार करें जब i-th मशीन (i + 1) -th के साथ पकड़ लेती है, यदि वह इसे नहीं पकड़ती है, तो हम मानते हैं कि यह क्षण अनंत पर होगा। हम उस समय पर भी विचार करते हैं जब प्रोफेसर की कार फिनिश लाइन तक पहुँचती है। वह घटना चुनें जो पहले होगी। वह समय जोड़ें जिसके माध्यम से उत्तर होता है। यदि यह ईवेंट फिनिश लाइन पर प्रोफेसर की कार का आगमन है, तो समस्या हल हो गई है। अन्यथा, हम ऊपर वर्णित नियम के अनुसार मशीनों को जोड़ते हैं और निचले आयाम की समस्या को हल करते हैं। यह चरण O (n) में किया जाता है। कुल में n ऐसे चरणों से अधिक नहीं हैं।
कुल परिचालन समय O (n ² )। विभिन्न डेटा संरचनाओं का उपयोग करते हुए, इस समाधान को ओ (एन लॉग एन) और यहां तक ​​कि ओ (एन) तक त्वरित किया जा सकता है।

टास्क D. तालिका
विचार: विटाली अक्षोनोव
बोध: विटालि अक्ष्योनोव
विश्लेषण: विटाली अक्षोनोव

टास्क की स्थिति
2 सेकंड की समय सीमा
256 एमबी मेमोरी सीमा
एक आयताकार तालिका पर विचार करें जो n × m कोशिकाओं से बनी है। प्रत्येक सेल को काले या सफेद रंग में रंगने की अनुमति है। एक रंग को सही कहा जाता है अगर एक ही रंग की चार कोशिकाएं नहीं होती हैं जिनके केंद्र एक गैर-पतित आयताकार के कोनों में स्थित होते हैं, जो तालिका के किनारों के समानांतर पक्षों के साथ होते हैं।
आयत के विभिन्न सही रंगों की संख्या की गणना करना आवश्यक है। चूंकि यह संख्या बड़ी हो सकती है, इसलिए इसे दिए गए मॉड्यूल आर को मोडुलो प्राप्त करना आवश्यक है।
उदाहरण के लिए, एक 2 × 2 आयत के लिए, इस तरह के रंग की संख्या 14 है: सभी रंग उपयुक्त हैं, सिवाय उन सभी में जिनमें सभी चार कोशिकाओं को एक ही रंग चित्रित किया गया है।

इनपुट प्रारूप	इनपुट फ़ाइल की पहली पंक्ति में एक प्राकृतिक संख्या t है - परीक्षणों की संख्या (1 ≤ t) 150)। अगली टी लाइनों में से प्रत्येक में 3 पूर्णांक हैं: n, m और r तालिका के आकार और मॉड्यूल हैं जिनके द्वारा आप उत्तर प्रदर्शित करना चाहते हैं। (1) एन, एम, आर ≤ 1018)
आउटपुट स्वरूप	प्रत्येक परीक्षण अनुरोध के लिए, एक अलग लाइन पर उत्तर प्रिंट करें।
उदाहरण	इनपुट डेटा उत्पादन 2 1 1 2 2 2 1,000,000 0 14

पदच्छेद
हम आयत n के न्यूनतम पक्ष को निरूपित करते हैं, और अधिकतम पक्ष - m। हम क्षैतिज रूप से लंबे पक्ष के साथ तालिका की व्यवस्था करते हैं और तदनुसार, हम छोटी पंक्तियों को कॉलम के रूप में कहेंगे।
विचार करने के लिए 3 मामले हैं:
• n = 1. तब उत्तर 2 ^{मीटर होगा} ।
• n = 2. हम केवल दो मोनोक्रोमैटिक कॉलम की अनुमति दे सकते हैं - एक काला और दूसरा सफेद। अन्य सभी कॉलम दो-रंग वाले होने चाहिए, यानी प्रत्येक में दो विकल्प होंगे। इसलिए, इसका उत्तर C _m ² • 2 ^{m - 1} + C _m ¹ • 2 ^m + 2 ^{m है} ।
• n> 2. यह ध्यान दिया जा सकता है कि यदि m> 6, तो एक अच्छा रंग नहीं है। दरअसल, दूसरे के रंग के साथ पहले कॉलम का रंग केवल दो स्थानों पर मेल खा सकता है। इसी तरह पहले और तीसरे के रंग के साथ। और अगर m> 6, तो दूसरे और तीसरे का रंग कम से कम तीन स्थानों पर होता है। और इसका मतलब है कि कोई अच्छा रंग नहीं है। जब हमने तालिका का आकार सीमित कर दिया है, तो यह समझना आसान है कि बाकी के लिए यह खोज का काम करता है।

टास्क ई। अंतरिक्ष अभियान
विचार: विटाली अक्षेनोव
एहसास: पावेल क्रोटकोव
विश्लेषण: पावेल क्रोटकोव

टास्क की स्थिति
2 सेकंड की समय सीमा
256 एमबी मेमोरी सीमा
2345 में, मानव जाति को सुदूर ग्रह नुटपेन में पहला अंतरिक्ष अभियान भेजने का अवसर मिला। इसका रास्ता लंबा और खतरों से भरा है, इसलिए इसे विभिन्न प्रकारों के तुरंत स्पेसशिप में भेजने का निर्णय लिया गया।
प्रत्येक जहाज दो अलग-अलग प्रकार के ईंधन पर काम कर सकता है। चूंकि जहाज अलग होते हैं, इसलिए ईंधन की खपत भी अलग-अलग हो सकती है। उसी समय, उड़ान में, जहाज को केवल दो प्रकार के ईंधन में से एक का उपयोग करना चाहिए, अंतरिक्ष में एक से दूसरे में स्विच करना असंभव है।
जहाज संख्या के बारे में मुझे पता है कि नटपेन ग्रह की सड़क पर वह या तो पहले प्रकार के ईंधन के एक किलोटन या दूसरे प्रकार के ईंधन के जैव किलोटन खर्च करेगा। जहाजों की डिज़ाइन विशेषताओं के कारण, उनमें से किसी के लिए समानता ai + bi = 4k रखती है, और संख्या k सभी जहाजों के लिए समान है।
अभियान कमांड के निपटान में पहले प्रकार के ईंधन के बिल्कुल k (n + 1) किलोटन होते हैं और दूसरे प्रकार के ईंधन के किलोटन की समान मात्रा होती है। अब आपको यह तय करने की आवश्यकता है कि प्रत्येक जहाज किस प्रकार के ईंधन से नटपेन ग्रह पर उड़ान भरेगा।

इनपुट प्रारूप	पहली पंक्ति में एक पूर्णांक t होता है - परीक्षण में इनपुट डेटा के सेट की संख्या। निम्नलिखित इनपुट डेटा का विवरण स्वयं सेट है। इनपुट डेटा के अगले सेट के विवरण की पहली पंक्ति में एक पूर्णांक n (1 of n ≤ 105) शामिल है - जहाजों की संख्या जो ग्रह नटपेन के लिए उड़ान भरेगी। अगली एन लाइनों में दो गैर-नकारात्मक पूर्णांक एआई और द्वि शामिल हैं - संबंधित जहाज द्वारा आवश्यक पहले और दूसरे प्रकार के ईंधन की मात्रा। यह गारंटी दी जाती है कि एआई और बीआई का योग सभी जहाजों के लिए समान है, चार का एक और 108 से अधिक नहीं है। एक परीक्षण में सभी सेटों में n का योग 500,000 से अधिक नहीं है।
आउटपुट स्वरूप	प्रत्येक इनपुट डेटा सेट के लिए, n वर्णों की एक पंक्ति को प्रिंट करें, जिसमें प्रतीक संख्या i '1' प्रतीक है यदि जहाज नंबर i को पहले प्रकार के ईंधन का उपयोग करके Nutpen पर उड़ान भरना है, और अगर इसे ईंधन का उपयोग करना है तो प्रतीक '2'। दूसरे प्रकार। प्रत्येक प्रकार के आवश्यक ईंधन की मात्रा k (n + 1) से अधिक नहीं होनी चाहिए। यदि कई संभावित उत्तर हैं, तो उनमें से किसी को भी प्रिंट करें। यह गारंटी है कि उत्तर हमेशा मौजूद है।
उदाहरण	इनपुट डेटा उत्पादन 2 5 1 3 ३ १ २ २ ४ ० 0 4 1 ४ ४ 12221 2

पदच्छेद
हम सभी जहाजों को पहले प्रकार के ईंधन की मात्रा के आधार पर छाँटते हैं जिनकी उन्हें ज़रूरत होती है। तब हम अधिकतम टी चुनते हैं - जैसे कि पहले टी जहाजों का योग k (n + 1) से अधिक नहीं है। ये टी जहाज पहले प्रकार के ईंधन का उपयोग करेंगे, और बाकी सभी दूसरे प्रकार के ईंधन का उपयोग करेंगे।

आइए हम यह साबित करते हैं कि यह एल्गोरिदम हमेशा समस्या में निर्धारित शर्तों के तहत उत्तर ढूंढेगा। ध्यान दें कि योग that _{i = 1} ^{t + 1} a _i > n • (k + 1)। इसलिए, किसी भी i> t के लिए, एक _i > (n + 1) / (t + 1) रखती है। इसलिए, हम पाते हैं कि किसी भी i> t, b _i <4k - (n + 1) / (t + 1) के लिए। यह साबित होता है कि दूसरी राशि बताई गई अभिव्यक्ति से अधिक नहीं है। ∑ _{i = t + 1 ⁿ} b _i <(n - (t + 1) + 1) • (4k - (n + 1) / (t + 1)) ≤ (n + 1) k। कोष्ठक खोलने के बाद अंतिम असमानता, असमानता "अंकगणित माध्य माइनस ज्यामितीय माध्य" में बदल जाती है। इसका मतलब है कि उपरोक्त एल्गोरिथ्म हमेशा एक समाधान ढूंढेगा।

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