सभी समस्याएँ · Bhash Problem Showcase
समस्या · पेड़ों के बीच मार्ग
Read N (2–10), then the integer coordinates of N trees in the range 0–999. A route visits every tree exactly once and may start and end anywhere. Round each Euclidean segment length to the nearest integer before adding it. Print the longest possible route length first and the shortest second.
समाधान · How the solution works
Round each individual segment to the nearest integer. For every subset of trees and possible last tree, retain the shortest and longest paths. Extending a smaller subset tries every possible predecessor in O(N² × 2ᴺ) time.
उदाहरण · Sample input
4
10 10
20 20
10 20
20 10
अपेक्षित परिणाम · Expected output
38 30
भाष स्रोत · Complete Bhash program
आयात मानक.पाठ्य;
फलन संख्याएँ() -> सूची<पूर्णांक> {
स्थिर पंक्ति: पाठ = पाठपढ़ो();
स्थिर परिणाम: सूची<पूर्णांक> = नया सूची<पूर्णांक>();
मान संख्या: पूर्णांक = 0;
मान चिह्न: पूर्णांक = 1;
मान सक्रिय: तार्किक = असत्य;
मान स्थान: पूर्णांक = 0;
जबतक (स्थान <= लंबाई(पंक्ति)) {
मान अक्षर: पाठ = " ";
यदि (स्थान < लंबाई(पंक्ति)) { अक्षर = अंश(पंक्ति, स्थान, स्थान + 1); }
स्थिर अंक: पूर्णांक = पाठ्य.खोजो("0123456789", अक्षर);
यदि (अंक >= 0) { संख्या = संख्या * 10 + अंक; सक्रिय = सत्य; }
अन्यथा यदि (अक्षर == "-") { चिह्न = -1; }
अन्यथा यदि (सक्रिय) { परिणाम.जोड़ो(चिह्न * संख्या); संख्या = 0; चिह्न = 1; सक्रिय = असत्य; }
स्थान = स्थान + 1;
}
लौटाओ परिणाम;
}
फलन दशमलवलेखन(मानक: पूर्णांक) -> पाठ {
यदि (मानक < 0) { लौटाओ "-" + दशमलवलेखन(-मानक); }
स्थिर अंक: पूर्णांक = मानक % 10;
स्थिर अक्षर: पाठ = अंश("0123456789", अंक, अंक+1);
यदि (मानक < 10) { लौटाओ अक्षर; }
लौटाओ दशमलवलेखन(मानक/10) + अक्षर;
}
फलन मुख्य() -> शून्य {
स्थिर आकार: सूची<पूर्णांक> = संख्याएँ();
स्थिर न: पूर्णांक = आकार[0];
स्थिर कुल: पूर्णांक = 1 << न;
स्थिर दूरियाँ: पूर्णांक[][] = नया पूर्णांक[न][न];
स्थिर क्ष: पूर्णांक[] = नया पूर्णांक[न];
स्थिर य: पूर्णांक[] = नया पूर्णांक[न];
मान क: पूर्णांक = 0;
जबतक (क < न) {
स्थिर बिंदु: सूची<पूर्णांक> = संख्याएँ();
क्ष[क] = बिंदु[0]; य[क] = बिंदु[1];
मान ज: पूर्णांक = 0;
जबतक (ज < क) {
स्थिर अ: पूर्णांक = क्ष[क]-क्ष[ज];
स्थिर ब: पूर्णांक = य[क]-य[ज];
मान द: पूर्णांक = 0;
जबतक ((2*द+1)*(2*द+1) < 4*(अ*अ+ब*ब)) { द = द+1; }
दूरियाँ[क][ज] = द; दूरियाँ[ज][क] = द; ज = ज+1;
}
क = क+1;
}
स्थिर छोटी: पूर्णांक[][] = नया पूर्णांक[कुल][न];
स्थिर बड़ी: पूर्णांक[][] = नया पूर्णांक[कुल][न];
मान न्यून: पूर्णांक = 99999;
मान अधिक: पूर्णांक = 0;
मान समूह: पूर्णांक = 1;
जबतक (समूह < कुल) {
क = 0;
जबतक (क < न) {
स्थिर बिट: पूर्णांक = 1 << क;
यदि ((समूह & बिट) != 0) {
स्थिर शेषसमूह: पूर्णांक = समूह-बिट;
यदि (शेषसमूह != 0) { छोटी[समूह][क] = 99999; }
मान ज: पूर्णांक = 0;
जबतक (ज < न) {
यदि ((शेषसमूह & (1 << ज)) != 0) {
स्थिर अ: पूर्णांक = छोटी[शेषसमूह][ज]+दूरियाँ[ज][क];
स्थिर ब: पूर्णांक = बड़ी[शेषसमूह][ज]+दूरियाँ[ज][क];
यदि (अ < छोटी[समूह][क]) { छोटी[समूह][क] = अ; }
यदि (ब > बड़ी[समूह][क]) { बड़ी[समूह][क] = ब; }
}
ज = ज+1;
}
यदि (समूह == कुल-1) {
यदि (छोटी[समूह][क] < न्यून) { न्यून = छोटी[समूह][क]; }
यदि (बड़ी[समूह][क] > अधिक) { अधिक = बड़ी[समूह][क]; }
}
}
क = क+1;
}
समूह = समूह+1;
}
लिखो(दशमलवलेखन(अधिक)+" "+दशमलवलेखन(न्यून));
}