एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

Coin Change (सिक्कों से राशि बनाना) - तरीकों की संख्या

एक मुद्रा प्रणाली दी गई है जिसमें n सिक्के शामिल हैं, और प्रत्येक सिक्के का मान धनात्मक है। आपको इन सिक्कों का उपयोग करके कुल x राशि प्राप्त करने के सभी संभव तरीकों की गिनती करनी है।
उदाहरण के लिए, यदि सिक्कों के मान दिए गए हैं और हमें 5 प्राप्त करना है, तो इसे पाने के 4 अलग-अलग तरीके हैं: 5, 1 + 2 + 2, 1 + 1 + 1 + 2, और 1 + 1 + 1 + 1 + 1। combination sum के विपरीत, यहाँ क्रम महत्व नहीं रखता—हम केवल यह देखते हैं कि कौन से सिक्के (एक multiset के रूप में) उपयोग किए गए हैं।

इनपुट

इनपुट की पहली पंक्ति में दो पूर्णांक n (1 ≤ n ≤ 100) और x (1 ≤ x ≤ ) दिए जाते हैं।
अगली पंक्ति में n पूर्णांक (1 ≤ ≤ ) स्पेस से अलग करके दिए जाते हैं।

आउटपुट

प्रोग्राम को यह निकालना चाहिए कि दिए गए सिक्कों को इस्तेमाल करके x प्राप्त करने के कितने तरीके संभव हैं। क्योंकि उत्तर बहुत बड़ा हो सकता है, आपको इसे से मॉड करने के बाद छापना होगा।

उदाहरण

Input
Output
3 5 1 2 5
4
3 9 2 3 5
3

व्याख्या

  1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2, और 1 + 1 + 1 + 1 + 1
  1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
 

Tutorial

ध्यान दें कि यदि हम d[s] के साथ एक स्थिति सहेजें, जहाँ d[s] सिक्कों का उपयोग करके योग s प्राप्त करने के विभिन्न तरीकों की संख्या दर्शाता है, तो हमें एक दोहराव (double counting) की समस्या का सामना करना पड़ेगा। उदाहरण के लिए, 1 + 2 + 2 जैसे सेट को, जिसे केवल एक बार गिना जाना चाहिए, हम तीन बार गिन लेंगे: 1 + 2 + 2, 2 + 1 + 2, और 2 + 2 + 1।
इस समस्या को दूर करने के लिए, हम ci तक के सभी सिक्कों पर प्रक्रिया चलाते हुए, s प्राप्त करने के तरीकों की गणना करेंगे (ci सिक्के का c ऐरे में इंडेक्स है)। हम ci सिक्के का उपयोग न भी कर सकते हैं या उसे कई बार उपयोग में ले सकते हैं—ये सब स्थितियां उसी अवस्था (state) में शामिल होंगी। इस तरह, हमारी अवस्था d[s][ci] इंगित करेगी कि ci तक के सारे सिक्कों को इस्तेमाल करते हुए योग s पाने के कितने तरीके हैं।
 
ऐसी दो अवस्थाएँ हैं जो पिछली परिस्थितियों से वर्तमान d[s][ci] में योगदान करती हैं (वर्तमान सिक्के का इंडेक्स ci है और उसका मान val):
  1. सिक्के ci को बिल्कुल भी न इस्तेमाल करना → d[s][ci - 1]
  1. सिक्के ci को 0, 1, 2, … k बार इस्तेमाल करना → d[s - val][ci]
अतः ci तक के सभी सिक्कों का प्रयोग करते हुए योग s पाने के कुल तरीकों की संख्या, उपर्युक्त पुरानी अवस्थाओं से आने वाले सभी अंतरण (transitions) का योग होगी।
 
c = [...]
x = ...
# d को x+1 पंक्तियों और len(c) स्तंभों के साथ 0 से आरंभ करें
d = [[0] * len(c) for _ in range(x + 1)]
हम पहले सिक्के से शुरू करके, उस सिक्के को इस्तेमाल करके संभव सभी s राशियों के लिए अवस्था d[s][0] को अपडेट कर सकते हैं। इसके बाद, दूसरे सिक्के पर जाएँगे और d[s][1] को अपडेट करेंगे। फिर तीसरे सिक्के के लिए d[s][2] को, इसी तरह आगे बढ़ते हुए अंतिम सिक्के तक पहुँचेंगे।
सभी सिक्कों को प्रोसेस करने के बाद, हम अंतिम सिक्के के प्रोसेस हो जाने पर x पाने की अवस्था (यानी d[x][len(c) - 1]) प्रिंट करके, यह जान सकते हैं कि x राशि तक पहुँचने के कितने तरीके संभव हैं:
for ci, val in enumerate(c):      # सिक्कों पर एक-एक करके पुनरावृत्ति करें
    d[0][ci] = 1                  # 0 राशि प्राप्त करना संभव है बिना कोई सिक्का उपयोग किए
    for s in range(1, x + 1):     # 1...x तक की सभी राशियों पर पुनरावृत्ति करें
        if ci - 1 >= 0:           # (1) सिक्के ci का बिल्कुल उपयोग न करें
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) सिक्के ci को 0 या अधिक बार उपयोग करें
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])
 
😎 क्या आप ऐसा कोई तरीका सोच सकते हैं जिससे <code>d</code> को एक-आयामी सूची के रूप में रखा जा सके?
हम सिक्कों को एक-एक करके प्रोसेस करते हैं, इसलिए ci - 2 और उससे पहले के सिक्के के लिए बनाई गई सारी स्थितियाँ हटाना संभव है। प्रत्येक इटररेशन में हमें सिर्फ वर्तमान सिक्के ci और पिछले सिक्के ci - 1 की स्थितियों में रुचि होती है। अतः हम पिछले सिक्के की स्थिति को एक ऐरे में और वर्तमान सिक्के की स्थिति को दूसरे ऐरे में रख सकते हैं।
😎 क्या आप ऐसा तरीका सोच सकते हैं जिससे कोई अतिरिक्त ऐरे न इस्तेमाल किया जाए और केवल एक-आयामी <code>d</code> का उपयोग हो?
हम देख सकते हैं कि पिछले सिक्के की अवस्था से जुड़ी एकमात्र क्रिया d[s] में prev[s] को जोड़ना है। इस वजह से हमें पिछला ऐरे रखने की आवश्यकता नहीं है:
# d को x+1 आइटमों से प्रारंभ करें
d = [1] + [0] * x                 # बिना किसी सिक्के के 0 राशि पाना संभव

for ci, val in enumerate(c):      # सिक्कों पर एक-एक करके पुनरावृत्ति करें
    for s in range(1, x + 1):     # 1...x तक की सभी राशियों पर पुनरावृत्ति करें
        if s - val >= 0:          # (2) सिक्के ci को 0 या अधिक बार उपयोग करें
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue