मान लीजिए, हमें विभिन्न आकारों की कई धातु की छड़ों को ट्रांसपोर्ट करने का कार्य दिया गया है। लेकिन ट्रांसपोर्टेशन कंटेनर लंबाई में छोटा है, यह केवल लंबाई 1 की छड़ें समाहित कर सकता है। हमें n छड़ें दी गई हैं, और उनकी लंबाई एक सूची में दी गई है। तो, सभी छड़ों को कंटेनर में फिट करने के लिए; हमें सभी छड़ों को काटना और विभाजित करना होगा ताकि वे यूनिट आकार की हों। इसके अलावा, हम सभी छड़ों को कंटेनर में फिट करते हैं जिसमें एक ऑपरेशन खर्च होता है। हमें छड़ों पर किए जाने वाले ऑपरेशन्स की संख्या ढूंढनी है।
इसलिए, यदि इनपुट है: input_arr = [6, 3, 7], तो आउटपुट 22 होगा।
- आकार 6 की छड़ को आकार 1 की छड़ों में बनाने के लिए, हमें 10 ऑपरेशन करने होंगे।
- आकार 3 की छड़ को आकार 1 की छड़ों में बनाने के लिए, हमें 4 ऑपरेशन करने होंगे।
- आकार 7 की छड़ को आकार 1 की छड़ों में बनाने के लिए, हमें 8 ऑपरेशन करने होंगे।
हल करने के चरण
- prime_find() फंक्शन परिभाषित करें जो input_num लेता है
- मुख्य फंक्शन से:
- prime_nums := prime_find(10^6 + 100)
- result := 0
- input_arr में प्रत्येक value के लिए:
- result := result + value
- f_list := नई सूची
- prime_nums में प्रत्येक p_num के लिए:
- जब value % p_num == 0: f_list में p_num जोड़ें, value := value // p_num
- यदि p_num^2 > value: यदि value > 1 तो f_list में value जोड़ें, लूप से बाहर निकलें
- temp := 1
- f_list में प्रत्येक p_num के लिए रिवर्स ऑर्डर में:
- result := result + temp
- temp := temp * p_num
- result वापस करें
उदाहरण
from math import floor, sqrt
def prime_find(input_num):
prime_check = [True] * ((input_num - 1) // 2)
for p_num in range(3, floor(sqrt(input_num)) + 1, 2):
if prime_check[(p_num - 3) // 2]:
prime_check[(p_num**2 - 3) // 2 :: p_num] = [False] * ((input_num - p_num**2) // (2 * p_num) + 1)
return [2] + [2 * i + 3 for i in range((input_num - 1) // 2) if prime_check[i]]
def solve(input_arr):
prime_nums = prime_find(10**6 + 100)
result = 0
for value in input_arr:
result += value
f_list = []
for p_num in prime_nums:
while value % p_num == 0:
f_list.append(p_num)
value //= p_num
if p_num**2 > value:
if value > 1:
f_list.append(value)
break
temp = 1
for p_num in f_list[::-1]:
result += temp
temp *= p_num
return result
if __name__ == "__main__":
print(solve([6, 3, 7]))
इनपुट
[6, 3, 7]
आउटपुट
22
