मान लीजिए, n संख्या के हॉस्टल कमरे हैं जो 0 से n-1 तक नंबर किए गए हैं। हॉस्टल कमरों के छात्र दूसरे कमरे में ट्रांसफर होना चाहते हैं, और वे ऐसा करने के लिए कई अनुरोध करते हैं। कोई हॉस्टल सीट खाली नहीं रहती, एक ट्रांसफर अनुरोध केवल तभी लिया जाता है जब कोई अन्य छात्र ट्रांसफर करने के इच्छुक छात्र की जगह ले ले। तो, दिए गए अनुरोधों को देखते हुए, हमें यह पता लगाना है कि कितने अनुरोध संतुष्ट किए जा सकते हैं।
उदाहरण के लिए, यदि इनपुट n = 3, requests = [[0,2],[1,0],[2,1]] है, तो आउटपुट 3 होगा।
- कमरा 0 का छात्र कमरा 2 में ट्रांसफर होता है।
- कमरा 1 का छात्र कमरा 0 में ट्रांसफर होता है।
- कमरा 2 का छात्र कमरा 1 में ट्रांसफर होता है।
हल करने के चरण
kकोlen(requests)से -1 तक घटाते हुए लूप चलाएं:cके लिएrange(len(requests))सेkतक सभी कॉम्बिनेशन में लूप चलाएं:d :=आकारnका ऐरे जिसमें मान 0 होcमें प्रत्येकiके लिए:d[requests[i][0]] := d[requests[i][0]] - 1d[requests[i][1]] := d[requests[i][1]] + 1
- यदि
dमें कोई भी आइटम True नहीं है, तोkवापस करें।
0वापस करें।
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
from itertools import combinations
def solve(n, requests):
for k in range(len(requests), 0, -1):
for c in combinations(range(len(requests)), k):
d = [0] * n
for i in c:
d[requests[i][0]] -= 1
d[requests[i][1]] += 1
if not any(d):
return k
return 0
print(solve(3, [[0,2],[1,0],[2,1]]))
इनपुट
3, [[0,2],[1,0],[2,1]]
आउटपुट
3