सभी चुनौतियाँ
कठिन 1 हल किया गया 100.0% स्वीकृति

आयत को वर्गों में काटें

केवल वर्ग बनाने के लिए सबसे कम सीधे कट की संख्या ज्ञात करें।

आप क्या सीखेंगे

  • चौड़ाई और ऊँचाई पर DP तालिका बनाना
  • हर क्षैतिज और ऊर्ध्वाधर कट आज़माना
  • छोटे आयतों के परिणाम दोबारा उपयोग करना

समस्या

हर चाल में, एक आयत चुनें और उसे उसके किसी एक पक्ष के समानांतर पूरी तरह काटें, जिससे दो आयत बनें जिनकी भुजाएँ धनात्मक पूर्णांक हों। यह प्रक्रिया तब तक दोहराएँ जब तक हर टुकड़ा एक वर्ग न बन जाए। वर्गों के आकार अलग-अलग हो सकते हैं। टुकड़ों की नहीं, केवल कट की संख्या गिनें।

rectangle_cutting(height, width) को लागू करें।

इनपुट

height: प्रारंभिक आयत की ऊँचाई।

width: प्रारंभिक आयत की चौड़ाई।

आउटपुट

न्यूनतम कट की संख्या लौटाएँ।

सीमाएँ

1 ≤ height, width ≤ 500। घुमाने से उत्तर नहीं बदलता।

उदाहरण

उदाहरण 1
इनपुट:
height = 2
width = 3

अपेक्षित आउटपुट:
expected = 2
इनपुट:
long long height = 2;
long long width = 3;

अपेक्षित आउटपुट:
long long expected = 2;
इनपुट:
long height = 2;
long width = 3;

अपेक्षित आउटपुट:
long expected = 2;

व्याख्या

2 × 2 का एक वर्ग काट लें, शेष में 2 × 1 का आयत बचेगा। एक और कट से शेष को दो इकाई वर्गों में बाँट सकते हैं।

उदाहरण 2
इनपुट:
height = 4
width = 4

अपेक्षित आउटपुट:
expected = 0
इनपुट:
long long height = 4;
long long width = 4;

अपेक्षित आउटपुट:
long long expected = 0;
इनपुट:
long height = 4;
long width = 4;

अपेक्षित आउटपुट:
long expected = 0;

व्याख्या

प्रारंभिक आयत पहले से ही एक वर्ग है।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

Rectangle को दो छोटे rectangles में split करके और उनके best answers मिलाकर solve किया जा सकता है.

संकेत 2

Minimum पाने के लिए हर possible horizontal और vertical cut try करो.

संकेत 3

Memoization या table मददगार है, क्योंकि कई subrectangles बार-बार आते हैं.

अपेक्षित जटिलता

समय O(h*w*(h+w)), अतिरिक्त स्थान O(h*w)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

# कोडर भाषा समय मेमोरी AI रिव्यू समाधान
1 ННикита Python 954 ms - 4/5 कोड देखें

दूसरों से सीखें

समुदाय समाधान

स्पॉइलर अलर्ट: नीचे 1 पूरा समाधान पहले खुद हल करने की कोशिश करें। आप फिर भी अन्य डेवलपर्स का कोड और AI समीक्षा देख सकते हैं। चर्चा में शामिल होने के लिए साइन इन करें और चुनौती हल करें।