Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python प्रोग्राम - K घंटे में पत्थर हटाने की न्यूनतम दर खोजें

पत्थरों के ढेर की सूची piles और एक मान k दिया गया है। piles[i] ढेर i पर पत्थरों की संख्या दर्शाता है। प्रत्येक घंटे, हम किसी भी ढेर को चुनते हैं और उससे r पत्थर हटाते हैं। यदि हम r से कम पत्थरों वाला ढेर चुनते हैं, तो उसे खाली करने में भी एक घंटा लगता है। हमें r का न्यूनतम मान खोजना है जिससे हम सभी पत्थरों को k घंटे या उससे कम में हटा सकें।

उदाहरण

इनपुट: piles = [3, 6, 4], k = 5

आउटपुट: 3

व्याख्या: r = 3 पत्थर प्रति घंटे की दर से, हम दूसरे ढेर को 2 घंटे में खाली कर सकते हैं, तीसरे को 2 घंटे में, और पहले को 1 घंटे में। कुल 5 घंटे।

एल्गोरिदम (बाइनरी सर्च)

  1. l := 1 (न्यूनतम संभव दर)
  2. h := max(piles) (अधिकतम संभव दर)
  3. r := h
  4. turns(r) फंक्शन परिभाषित करें जो sum(ceil(b / r) for b in piles) लौटाता है
  5. जब l < h:
    • mid := (l + h) // 2
    • यदि turns(mid) > k: l := mid + 1
    • अन्यथा: h := mid, r := min(r, mid)
  6. r लौटाएं

Python कार्यान्वयन

from math import ceil

def solve(piles, k):
    l = 1
    h = max(piles)
    r = h
    
    def turns(r):
        return sum(ceil(b / r) for b in piles)
    
    while l < h:
        mid = (l + h) // 2
        if turns(mid) > k:
            l = mid + 1
        else:
            h = mid
            r = min(r, mid)
    return r

piles = [3, 6, 4]
k = 5
print(solve(piles, k))  # आउटपुट: 3

इनपुट/आउटपुट

Input: [3, 6, 4], 5
Output: 3
  1. पायथन में बहुभुज का क्षेत्रफल खोजने का प्रोग्राम पायथन में बहुभुज का क्षेत्रफल खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक 2D तल पर एक साधारण बहुभुज के अंतिम बिंदुओं को दर्शाने वाले क्रमबद्ध बिंदुओं की सूची है। हमें इस बहुभुज का क्षेत्रफल ढूंढना है।उदाहरण के लिए, यदि इनपुट points = [(0, 0), (0,5), (3, 5), (3,0)] है, तो आउटपुट 15 होगा।समाधान दृष्टिकोणइसे हल करने के लिए हम निम्न चरणों का पालन करेंगे

  1. पायथन में बहुभुज का परिमाप खोजने का प्रोग्राम पायथन में बहुभुज का परिमाप खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक 2D तल पर एक साधारण बहुभुज के अंतिम बिंदुओं को दर्शाने वाले क्रमबद्ध बिंदुओं की सूची है। हमें इस बहुभुज का परिमाप ढूंढना है।उदाहरण के लिए, यदि इनपुट points = [(0, 0), (0,5), (3, 5), (3,0)] है, तो आउटपुट 16 होगा क्योंकिदो भुजाएं लंबाई 3 की हैं और दो भुजाएं लंबाई 5 की हैं, तो 2*5

  1. - पायथन में सबसे लंबा विस्मयकारी उपस्ट्रिंग ज्ञात करने का प्रोग्राम

    मान लीजिए हमारे पास s नामक एक संख्यात्मक स्ट्रिंग है। जैसा कि हम जानते हैं, एक विस्मयकारी उपस्ट्रिंग s का एक गैर-खाली उपस्ट्रिंग है जैसे कि हम इसे पालिंड्रोम बनाने के लिए किसी भी संख्या में स्वैप कर सकते हैं। हमें s के अधिकतम लंबाई वाले विस्मयकारी उपस्ट्रिंग की लंबाई ज्ञात करनी है। इसलिए, यदि इनपुट