नमस्कार। आपको ओलंपियाड का शौक है। यहां हम एक ओलंपियाड प्रोग्रामिंग कार्य का चयन करते हैं, इसका विश्लेषण करते हैं, संभव समाधान विकसित करते हैं और अपनी योजना को लागू करते हैं, और फिर इसे अदालत में भेजते हैं। हमें प्रोग्रामिंग भाषाओं में से एक का ज्ञान आवश्यक है: सी, सी ++, जावा, पास्कल, धैर्य, निपुणता और अंग्रेजी भाषा का मूल ज्ञान समस्या की स्थिति को समझने के लिए, हालांकि अंतिम बिंदु वैकल्पिक है, क्योंकि मैं रूसी में स्थिति को स्वतंत्र रूप से बताऊंगा।
क्या आप खुद को स्ट्रेच करना भूल गए हैं? यदि आप भूल गए, तो जल्दी से गर्म हो जाओ, और हमारे पास वापस आओ।
मैं आपको याद दिलाता हूं कि मैं साइट http://uva.onlinejudge.org से कार्य लेता हूं, और आज एक यादृच्छिक विकल्प कार्य संख्या 154 पर गिर गया - कचरे के निपटान की समस्या।
समस्या की स्थितियों का संक्षिप्त अनुवाद (मुफ्त अनुवाद):
न्यूजीलैंड में केर्बसाइड कचरा संग्रहण तकनीक आ गई है। विभिन्न रंगों के पांच अपशिष्ट डिब्बे: लाल (लाल), नारंगी (नारंगी), पीला (पीला), हरा (हरा) और नीला (नीला), जो 5 प्रकार के कचरे की पहचान करते हैं: प्लास्टिक अपशिष्ट (प्लास्टिक), कांच (ग्लास), एल्यूमीनियम (एल्युमिनियम), स्टील (स्टील) और पेपर (समाचार पत्र)। दुर्भाग्य से, शहरों के बीच कोई समन्वय नहीं था, इसलिए प्रत्येक शहर ने रंग की टोकरियों को एक अनियंत्रित प्रकार के कचरे को सौंपा। अब जब सरकार सभी महत्वहीन कार्यों (जैसे स्वास्थ्य देखभाल, सामाजिक सुरक्षा और शिक्षा का पुनर्गठन) को हल करने में सक्षम थी, तो उसने अन्य समस्याओं से निपटने का फैसला किया। पर्यावरण संरक्षण मंत्री ने रंगीन टोकरी के साथ कचरे के प्रकार के अनुपालन को विनियमित करने के लिए एक दस्तावेज संसद को प्रस्तुत किया, लेकिन इसके लिए उसे रंग द्वारा कचरे के अपने वितरण को चुनने की आवश्यकता है। लोकतंत्र के प्रस्तावक, उन्होंने उन सभी शहरों का पता लगाया जो कार्ब्साइड का उपयोग करते थे। डेटा का उपयोग करते हुए वह एक ऐसे शहर को चुनना चाहता है जिसके अपशिष्ट प्रकारों को रंगीन टोकरियों (पूरे देश में आम होने) से मिलान करने की योजना कम से कम बदलाव का कारण बनेगी। लोकतंत्र के अनुसार, शहर का आकार मायने नहीं रखता: 1 शहर - 1 वोट।
यह एक कार्यक्रम लिखना आवश्यक है जो प्रत्येक शहर में रंग द्वारा कचरे के प्रकार के वितरण पर डेटा पर विचार करता है, और यह निर्धारित करता है कि किस योजना का चयन किया जाना चाहिए। ध्यान रखें कि हमेशा एक स्पष्ट नेता होगा।
इनपुट डेटा : ब्लॉक की श्रृंखला। प्रत्येक ब्लॉक में रंग द्वारा अपशिष्ट प्रकार के वितरण को व्यक्त करने वाली कई लाइनें शामिल होंगी, प्रत्येक शहर के लिए 1 लाइन। 100 शहर तक हो सकते हैं। प्रत्येक ब्लॉक "ई" अक्षर से शुरू होने वाली रेखा के साथ समाप्त होता है। इनपुट का अंत एकल-वर्ण स्ट्रिंग "#" के साथ चिह्नित है।
आउटपुट : प्रत्येक आने वाले ब्लॉक के लिए, आपको शहर के सीरियल नंबर को प्रदर्शित करना होगा, जिसकी वितरण योजना को एक संदर्भ के रूप में चुना जाना चाहिए।
:
r/P,o/G,y/S,g/A,b/N
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
e
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
r/P,o/G,y/S,g/A,b/N
ecclesiastical
#
:
1
4
उन लोगों के लिए जो अपनी क्षमताओं का परीक्षण करना चाहते हैं, इस स्थान पर समस्या का अपना समाधान बनाने के लिए इसे बाधित करने की सिफारिश की जाती है, और फिर हमारे साथ अपने विचारों की तुलना करने के लिए वापस आते हैं।
इस समस्या का पहला (गलत) समाधान, जो लगभग तुरंत मेरे दिमाग में आया, यह है:
- प्रत्येक रंग के लिए, हम उन कचरे के प्रकार का चयन करते हैं जो अधिकतम शहरों में इस रंग द्वारा दर्शाए जाते हैं
- हम उन कचरे के प्रकारों के लिए एक रंग मिलान योजना बनाते हैं, जिन्हें अनुच्छेद 1 में चुना गया था
- एक ऐसा शहर चुनें जिसका वितरण योजना के प्रकार रंग से हो सके जैसा कि पैराग्राफ 2 से संभव है
दुर्भाग्य से, यह निर्णय गलत निकला, यदि केवल इसलिए कि कभी-कभी संदर्भ योजना (पैराग्राफ 2 में चयनित) के साथ समान समानता वाले शहर पाए जाते हैं। यहाँ एक प्रतिरूप है:
आर / पी, ओ / जी, वाई / एस, जी / ए, बी / एन
आर / पी, ओ / एस, वाई / ए, जी / एन, बी / जी
आर / एस, ओ / जी, वाई / पी, जी / एन, बी / जी
आर / ए, ओ / एस, वाई / पी, जी / एन, बी / जी
आर / जी, ओ / एस, वाई / पी, जी / ए, बी / एन
अनुच्छेद 2 के अनुसार संदर्भ आरेख:
आर / पीओ / एस, वाई / पी, जी / एन, बी / जी
दूसरे और चौथे शहर समान रूप से विकसित योजना के समान हैं, विषय कोई कम नहीं है, जब शहर नंबर 4 को चुनते हैं, तो शहर के नंबर 2 को चुनते समय अन्य शहरों में परिवर्तनों की संख्या कम होती है।
दूसरा विकल्प : मैंने यह गणना करने का फैसला किया कि सभी शहरों को बदले में एक मानक के रूप में चुने जाने पर कितने बदलाव करने की आवश्यकता होगी। यानी मैंने प्रत्येक शहर के लिए अन्य सभी शहरों से इसके कुल अंतर की गणना की।
प्रारंभ में, मुझे ऐसा लगा कि ऐसा समाधान इष्टतम नहीं था, ऐसा लगता था कि यह निश्चित रूप से समय सीमा से परे जाएगा। लेकिन यह अनुमान लगाने की कोशिश करें कि प्रत्येक शहर और सभी अन्य लोगों के बीच मतभेदों की संख्या की गणना में कितना समय लगेगा।
प्रत्येक शहर की सभी अन्य लोगों के साथ तुलना की जानी चाहिए, और प्रत्येक रंग के लिए 5 तुलनाएं होंगी, अर्थात। 5 (n-1) प्रत्येक शहर के लिए तुलना, जहां n शहरों की संख्या है। कुल मिलाकर, सभी शहरों के लिए 5n (n-1) तुलनाएँ हैं। यदि हम इस तथ्य को ध्यान में रखते हैं कि 100 से अधिक शहर नहीं हैं, तो तुलनाओं की संख्या 5 * 100 * 99 = 49500 से अधिक नहीं है। प्रत्येक शहर के काउंटर अंतर को बढ़ाने के लिए संचालन के साथ तुलनात्मक संचालन भी किया जाएगा। लेकिन कुल मिलाकर, सबसे खराब परिस्थितियों में भी, संचालन की संख्या इकाइयों की तुलना में 49,500 और 49,500 संचालन से अधिक नहीं होगी। यह स्पष्ट हो जाता है कि हमारे एल्गोरिथ्म को बहुत कम समय में सबसे जटिल परीक्षणों पर भी निष्पादित किया जाएगा।
आइए समाधान नंबर 1 के उदाहरणों और पिछले प्रतिसाद के लिए मतभेदों की संख्या की गणना करने का प्रयास करें:
| योजना | अन्य शहरों से मतभेदों की संख्या |
|---|---|
| आर / पी, ओ / जी, वाई / एस, जी / ए, बी / एन
आर / जी, ओ / पी, वाई / एस, जी / ए, बी / एन आर / पी, वाई / एस, ओ / जी, जी / एन, बी / ए आर / पी, ओ / एस, वाई / ए, जी / जी, बी / एन | 1 + 2 + 1 + 2 + 1 = 7 <- सबसे अच्छा विकल्प
3 + 3 + 1 + 2 + 1 = 10 1 + 2 + 1 + 3 + 3 = 10 1 + 3 + 3 + 3 + 1 = 11 |
| आर / पी, ओ / जी, वाई / एस, जी / ए, बी / एन
आर / पी, ओ / एस, वाई / ए, जी / एन, बी / जी आर / एस, ओ / जी, वाई / पी, जी / एन, बी / जी आर / ए, ओ / एस, वाई / पी, जी / एन, बी / जी आर / जी, ओ / एस, वाई / पी, जी / ए, बी / एन | 3 + 3 + 4 + 3 + 3 = 16
3 + 2 + 4 + 2 + 2 = 13 4 + 3 + 2 + 2 + 2 = 13 4 + 2 + 2 + 2 + 2 = 12 <- सबसे अच्छा विकल्प 4 + 2 + 2 + 3 + 3 = 14 |
दरअसल, यह योजना को लागू करने और इसे न्यायाधीशों तक पहुंचाने के लिए बना हुआ है। और यहाँ C ++ में मेरा समाधान है।
स्वीकृत (0.012)। सौभाग्य है