পাইথনে সেল ফিউশন অনুকরণ করুন

मान लीजिए हमारे पास cells नामक संख्याओं की एक सूची है; यह सूची विभिन्न कोशिकाओं के आकार को दर्शाती है। अब, प्रत्येक पुनरावृत्ति में, दो सबसे बड़ी कोशिकाएं a और b इन नियमों के अनुसार परस्पर क्रिया करती हैं: यदि a = b, तो वे दोनों मर जाती हैं। अन्यथा, दोनों कोशिकाएं मिल जाती हैं और उनका आकार floor((a + b) / 3) हो जाता है। हमें अंतिम कोशिका का आकार ढूंढना है या -1 लौटाना है यदि कोई कोशिका शेष नहीं रहती।

यदि इनपुट [20,40,40,30] जैसा है, तो आउटपुट 16 होगा। पहली पुनरावृत्ति में, 40 और 40 मर जाएंगे, फिर 20 और 30 floor((20+30)/3) = floor(50/3) = 16 बन जाएंगे।

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• cells := cells सरणी के प्रत्येक मान को नेगेटिव में बदलें
• cells से एक हीप बनाएं
• जब तक cells खाली नहीं है, करें:
  • cells से दो तत्वों को हटाएं और उन्हें फिर से नेगेटिव में बदलें, और उन्हें क्रमशः first और second के रूप में निर्दिष्ट करें
• यदि first, second के बराबर नहीं है, तो
  • floor((first+second)/3) के नेगेटिव को हीप में डालें
• यदि cells में कुछ तत्व हैं तो -cells[0] लौटाएं अन्यथा -1

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

उदाहरण

from heapq import heapify, heappop, heappush
class Solution:
    def solve(self, cells):
        cells = [-x for x in cells]
        heapify(cells)
        while len(cells) > 1:
            first, second = -heappop(cells), -heappop(cells)
            if first != second:
                heappush(cells, -((first+second)//3))
        return -cells[0] if cells else -1

ob = Solution()
cells = [20,40,40,30]
print(ob.solve(cells))

इनपुट

[20,40,40,30]

आउटपुट

16