Python में फेरिस व्हील से अधिकतम लाभ के लिए न्यूनतम रोटेशन खोजने का प्रोग्राम

मान लीजिए चार केबिन वाला एक फेरिस व्हील है और प्रत्येक केबिन में चार यात्री बैठ सकते हैं। पहिया वामावर्त घूमता है, और प्रत्येक रोटेशन के लिए, इसकी लागत 'run' राशि होती है। अब हमारे पास एक ऐरे 'cust' है जिसमें n आइटम हैं और प्रत्येक आइटम i iवीं रोटेशन से पहले फेरिस व्हील में बैठने की प्रतीक्षा कर रहे लोगों की संख्या को दर्शाता है। पहिया में चढ़ने के लिए, प्रत्येक ग्राहक को 'board' राशि का भुगतान करना पड़ता है, और उतना ही पैसा पहिया के एक वामावर्त रोटेशन के लिए होता है। लाइन में प्रतीक्षा कर रहे लोगों को इंतजार नहीं करना चाहिए यदि किसी भी केबिन में कोई खाली सीट उपलब्ध है। तो दिए गए डेटा से, हमें न्यूनतम रोटेशन की मात्रा ढूंढनी है ताकि लाभ को अधिकतम किया जा सके।

उदाहरण के लिए, यदि इनपुट है cust = [6,4], board = 6, run = 4, तो आउटपुट 3 होगा।

सबसे पहले, 6 लोग लाइन में प्रतीक्षा कर रहे हैं। तो पहले 4 लोग पहले केबिन में बैठते हैं, और बाकी अगले केबिन की प्रतीक्षा करते हैं।

पहिया घूमता है, और दूसरा केबिन आता है। इस बीच, 4 और लोग लाइन में आ जाते हैं। तो अगले 4 प्रतीक्षारत लोग अगले केबिन में बैठते हैं।

पहिया फिर घूमता है, और शेष तीन ग्राहक अगले केबिन में बैठते हैं।

तो, सभी ग्राहकों को सेवा देने के लिए न्यूनतम तीन रोटेशन की आवश्यकता होती है।

इन रोटेशन से प्राप्त अधिकतम लाभ है (10 * 6) - (3 * 4) = 48।

समाधान के चरण

1. res := -1
2. mst := 0
3. tmp := 0
4. wt := 0
5. cust में प्रत्येक इंडेक्स idx और मान val के लिए:
   • wt := wt + val
   • chg := min(4, wt)
   • wt := wt - chg
   • tmp := tmp + chg * board - run
   • यदि mst < tmp:
     • res := idx + 1
     • mst := tmp
6. x, y := divmod(wt, 4)
7. यदि 4 * board > run:
   • res := res + x
8. यदि y * board > run:
   • res := res + 1
9. res वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(cust, board, run):
    res = -1
    mst = 0
    tmp = 0
    wt = 0
    for idx, val in enumerate(cust):
        wt += val
        chg = min(4, wt)
        wt -= chg
        tmp += chg * board - run
        if mst < tmp:
            res, mst = idx+1, tmp
    x, y = divmod(wt, 4)
    if 4 * board > run:
        res += x
    if y * board > run:
        res += 1
    return res

print(solve([6,4], 6, 4))

इनपुट

[6,4], 6, 4

आउटपुट

3