विस्तार से

भोक्ता को भुगतान

भोक्ता को भुगतान

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

मेरे पास 7 सिल्वर लिंक की एक श्रृंखला है। मेरे प्रवास के अंत में मैं इसे आवास के लिए भुगतान के रूप में वितरित करूंगा।

वह भोला, जिसके प्रति किसान किसी भी भरोसे को प्रेरित नहीं करता, जवाब देता है। आप मुझे अपनी सराय में रहने के लिए हर दिन श्रृंखला में एक लिंक देंगे।

किसान, जिसकी एक कम कार्यकर्ता के रूप में ख्याति है, कम से कम कटौती को संभव बनाने वाले निर्दोष के अनुरोध को पूरा करने के लिए श्रृंखला में लिंक को काटने का सबसे अच्छा तरीका सोचता है।

किसान के अनुरोधों को पूरा करने के लिए किसान को न्यूनतम कितनी कटौती करनी चाहिए और उन्हें कैसे वितरित करना चाहिए?

समाधान

श्रृंखला में एकल कटौती के साथ निर्दोष के अनुरोधों को पूरा करना संभव है इस प्रकार है:

यदि हम श्रृंखला में तीसरी कड़ी काटते हैं, तो हमारे पास एक ढीली कड़ी होगी और दो कड़ियों के साथ एक श्रृंखला होगी और दूसरी चार कड़ियों के साथ होगी:

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