ओलंपिक का शौक। सिक्कों का आदान-प्रदान

नमस्कार। आज सोमवार है, इसलिए मैंने फैसला किया कि अपनी उंगलियों और मस्तिष्क को गर्म करने के साथ अपने कार्य दिवस को शुरू करने लायक था। उन लोगों के लिए जो नहीं जानते: मेरे ओलंपियाड के शौक में ओलंपियाड प्रोग्रामिंग समस्याओं को हल करना शामिल है, जिसे मैं http://uva.onlinejudge.org/ साइट से लेता हूं। आज हमें गतिशील प्रोग्रामिंग के क्षेत्र से सिक्कों के आदान-प्रदान की समस्या को हल करना होगा। कार्य बहुत मुश्किल नहीं है, लेकिन कुछ प्रतिबिंबित करने के लिए है, इसलिए मैं बिल्ली में दिलचस्पी रखने वालों से पूछता हूं। वैसे, यह हमारा तीसरा कार्य है, लेकिन, निश्चित रूप से, सबसे दिलचस्प है।

एक मामूली गीतात्मक विषयांतर।

जब मैं 3 साल का था, तब मेरा प्रोग्रामिंग पथ शुरू नहीं हुआ था, जब कई भविष्य के प्रोग्रामर पहले ही कैलकुलेटर से अलग हो गए थे और उसमें से एक कंप्यूटर बनाया था। मैंने 8 वीं कक्षा में स्कूल में प्रोग्रामिंग शुरू की। वैसे, मेरा स्कूल तकनीकी से बहुत दूर था, इसलिए मेरे प्रयासों में मैं लगभग अकेला था। लेकिन, हमारे स्कूल के निदेशक के लिए धन्यवाद, हमारे पास प्रोग्रामिंग में एक "सर्कल" था, जहां हमने स्कूल प्रोग्रामिंग ओलंपियाड के लिए तैयार किया। एक समय में हम में से तीन से अधिक नहीं थे, लेकिन हमारे शिक्षक, सौभाग्य से, परेशान नहीं थे। कावोकिन ए.ए. मेरे प्रोग्रामिंग शिक्षक थे, और यह उनके लिए आंशिक रूप से धन्यवाद था कि मैंने एक प्रोग्रामर के रूप में ऐसा अद्भुत पथ लिया। इसलिए, हमारे संरक्षक ने प्रत्येक पाठ को एक तार्किक कार्य के साथ शुरू किया, ताकि हम अपने संकल्पों को पूरा करें। मुझे स्कूल में यह बहुत पसंद आया कि मैंने आपको भी उस तरह से पीड़ा देने का फैसला किया, इसलिए आज हम एक छोटे से तार्किक कार्य के साथ शुरुआत करेंगे जो हमें गर्म करने में मदद करेगा।



वार्मिंग के लिए तार्किक कार्य:

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

मुझे अनुत्तरित कार्य छोड़ दें, क्योंकि मुझे आपके त्वरित बुद्धि पर भरोसा है। और जैसे ही टिप्पणियों में सही उत्तर दिखाई देगा, मैं तुरंत यहां एक लिंक बनाऊंगा।

उत्तर : ओगरा की टिप्पणी में पाया गया उत्तर

शर्त

मुझे आशा है कि जो कार्य मैंने आपको गर्म करने के लिए दिया था वह आपके मस्तिष्क की गतिविधि को सफलतापूर्वक प्रभावित करेगा। अब हम आखिरकार ओलंपियाड समस्या को हल करने जा रहे हैं। आज हमारा कार्य सिक्कों के आदान-प्रदान का कार्य है ।



समस्या की स्थितियों का संक्षिप्त अनुवाद

एक बड़े डिपार्टमेंटल स्टोर में खरीद के बाद, मेल को 17 सेंट का बदलाव मिला। उसे दस-दस का सिक्का, पाँच-पाँच का सिक्का और 1 प्रतिशत के 2 सिक्के मिले। उस दिन के बाद, वह सुविधा की दुकान पर गया, जहां उसे 17 सेंट का बदलाव भी मिला। इस बार उन्हें 5 सेंट के दो सिक्के और 1 प्रतिशत के 7 सिक्के मिले। तब मेल ने सोचा: "मैं कितने दुकानों में जाकर सिक्कों के एक अलग सेट के साथ 17 सेंट का बदलाव कर सकता हूं?" थोड़ी सी मंथन के बाद, उन्होंने निर्धारित किया कि उत्तर 6. था। तब उन्होंने आपको एक और सामान्य मामले को हल करने के लिए चुनौती दी।



एक कार्यक्रम लिखें जो अमेरिकी सिक्कों के विभिन्न संयोजनों की संख्या (1 प्रतिशत, 5 सेंट, 10 सेंट, 25 और 50 सेंट) निर्धारित करेगा जो एक निश्चित राशि तक जोड़ सकते हैं।



इनपुट : इनपुट में 0 से 30,000 के बीच कई नंबर शामिल होंगे, प्रत्येक लाइन में एक।



आउटपुट : प्रत्येक इनपुट नंबर के लिए, आपको संयोजन और आउटपुट की संख्या निर्धारित करने की आवश्यकता है, जैसा कि उदाहरण में दिखाया गया है।



एक उदाहरण:

इनपुट:

17

11

4



आउटपुट:

17 सेंट बदलाव का उत्पादन करने के 6 तरीके हैं।

11 सेंट परिवर्तन का उत्पादन करने के 4 तरीके हैं।

4 सेंट परिवर्तन का उत्पादन करने का केवल 1 तरीका है।

हमेशा की तरह, मैं सलाह देता हूं कि आप समस्या को स्वयं हल करने का प्रयास करें। और जैसे ही आप निर्णय लेते हैं, हमारे पास वापस आएं और अपना परिणाम दिखाएं।



तो, चलिए शुरू करते हैं ...

निर्णय

समस्या स्पष्ट रूप से गतिशील प्रोग्रामिंग के क्षेत्र से है, और ऐसी समस्याओं को आमतौर पर पुनरावर्ती निर्भरता का उपयोग करके हल किया जाता है। हमें यह निर्धारित करने की आवश्यकता है कि हमारे मामले में कौन सी पुनरावर्ती निर्भरता है।



आप तुरंत नोटिस कर सकते हैं कि संयोजनों की संख्या 1 प्रतिशत से 4 तक गुजरने पर भिन्न नहीं होती है - यह 1 विकल्प है, जब 5 सेंट से 9 तक गुजर रहा है - यह 2 विकल्प हैं, जब 10 सेंट से 14 तक गुजर रहा है - ये 4 विकल्प हैं, आदि। ऐसा इसलिए है क्योंकि 1 प्रतिशत संप्रदाय के ऐसे "पांच" सिक्के के अंदर कुछ भी बदलना असंभव है। इस प्रकार, हमने निर्धारित किया कि प्रत्येक संख्या के लिए समस्या को हल करना व्यर्थ है, इसलिए हम इसे प्रत्येक "पाँच" के लिए हल करेंगे।



आप यह भी देख सकते हैं कि अगले "पाँच" में से प्रत्येक के लिए संयोजन वास्तव में पिछले "पांच" (प्रत्येक 1 प्रतिशत पर सिक्कों की वांछित संख्या के अतिरिक्त) और कई नए संयोजनों के संयोजन को दोहराते हैं। यह स्पष्ट हो जाता है कि अगले "पांच" के संयोजनों की संख्या पिछले "फाइव्स" के संयोजनों की संख्या पर निर्भर है। आइए एक तालिका बनाएं जहां कॉलम "फाइव्स" हैं और पंक्तियां सिक्कों के प्रकार हैं, और दमन यह निर्धारित करेगा कि विशिष्ट चरण में दिए गए सिक्कों के दिए गए प्रकार (सभी छोटे लोगों के साथ) में कितने नए संयोजन हैं - "पांच":

	1	5	10	15	20	25	30	35	40	45	50	55
1	1	0	0	0	0	0	0	0	0	0	0	0
5	0	1	1	1	1	1	1	1	1	1	1	1
10	0	0	1	1	2	2	3	3	4	4	5	5
25	0	0	0	0	0	1	1	2	2	3	4	5
50	0	0	0	0	0	0	0	0	0	0	1	1
Σ	1	2	4	6	9	13	18	24	31	39	50	62

अंतिम पंक्ति इस "पांच" पर संयोजनों की संख्या प्रदर्शित करती है

उदाहरण के लिए: चरण 35 में (8 पाँच: 35-39)

केवल 1 प्रतिशत सिक्का होने से, नए संयोजन दिखाई नहीं देते हैं,

1 सेंट और 5 सेंट के सिक्कों से, आप 1 नए संयोजन की खोज कर सकते हैं: 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 1 (0 से 4 तक)

1 सेंट, 5 सेंट, 10 सेंट - 3 संयोजन: 10 + 10 + 10 + 5 + 1 (0 से 4 तक), 10 + 10 + 5 + 5 + 5 + 1, 10 + 5 * 5 + 1

1, 5, 10, 25 - 2 नए संयोजन: 25 + 10 + 1, 25 + 5 + 5 + 1



1 सेंट और 5 सेंट के सिक्कों के प्रत्येक चरण पर नए संयोजनों की संख्या 1 है, क्योंकि यह संयोजन पिछले संयोजन के 5 प्रतिशत सिक्कों को जोड़कर उत्पन्न होता है। यानी दूसरे पाँच, ५ + १, फिर ५ + ५ + १, फिर ५ + ५ + ५ + १ इत्यादि, प्रत्येक चरण पर १ नया संयोजन।

इस तालिका में भी एक पुनरावर्ती संबंध को समझना मुश्किल नहीं है: सिक्के 1-10 में सिक्कों के नए संयोजनों की संख्या 1-10 में सिक्कों के नए संयोजनों की संख्या 1-5 चरण I-1 से अधिक है और चरण I में सिक्कों के नए संयोजन की संख्या 1-10 है 2 (जब हमारे पास हमारे निपटान में 1 दस-सेंट का सिक्का कम था)। इसी तरह 25 प्रतिशत के सिक्के के लिए और 50 प्रतिशत के सिक्के के लिए।



परिणामस्वरूप, हमारे पास 2 सूत्र और 3 पुनरावर्ती निर्भरताएँ हैं:

N (1, i) = 0, N (1, 0) = 1 को छोड़कर

एन (5, आई) = 1

एन (10, आई) = एन (5, आई -1) + एन (10, आई -2)

N (25, i) = N (10, i-3) + N (25, i-5)

एन (50, आई) = एन (25, आई -5) + एन (50, आई -10)

S (i) = S (i-1) + N (1, i) + N (5, i) + N (10, i) + N (25, i) + N (50, i)

जहां N ऊपर दी गई मैट्रिक्स है, और S संयोजन की वांछित संख्या है।



अब हमें बस शुरुआत से लेकर अनुरोध किए गए चरणों की आवश्यक संख्या की गणना "पांच" तक करनी है, प्रत्येक चरण में संयोजनों (एस) की कुल संख्या की गणना करना है। इस तथ्य को देखते हुए कि समस्या में कई परीक्षण होंगे, आप नए परीक्षणों के लिए मैट्रिक्स के पहले की गणना किए गए टुकड़े का उपयोग कर सकते हैं और केवल इसके लापता भाग को पूरक कर सकते हैं। यह समझना भी बहुत महत्वपूर्ण है कि समस्या की स्थिति द्वारा निर्दिष्ट अधिकतम राशि के साथ: 30,000 सेंट, संयोजन की कुल संख्या इंट और अधिक लंबी हो जाएगी, इसलिए मैं संयोजनों की संख्या की गणना करने के लिए 8 बाइट अहस्ताक्षरित चर का उपयोग करने की सलाह देता हूं।



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



स्वीकृत (0.024)