मान लीजिए 0 से n-1 तक संख्याबद्ध n शहर हैं और n निर्देशित सड़कें हैं। हम शहर i से शहर (i + 1) % n [0 से 1 से 2 से .... से N - 1 से 0] तक यात्रा कर सकते हैं। हमारे पास एक कार है। हमारी कार के ईंधन टैंक की क्षमता cap इकाई है। शहर i की शुरुआत में fuel[i] इकाई ईंधन है जिसका हम उपयोग कर सकते हैं और कार को शहर i से (i + 1) % n तक यात्रा करने में cost[i] इकाई ईंधन लगता है। हमें पता लगाना है कि कितने शहर हैं जहां से हम अपनी कार शुरू कर सकते हैं, ताकि हम सभी शहरों की यात्रा कर सकें और उसी शहर में पहुंच सकें जहां से शुरू किया था?
तो, यदि इनपुट cap = 3, fuel = [3,1,2], costs = [2,2,2] है, तो आउटपुट 2 होगा क्योंकि दो संभावित समाधान हैं।
हम शहर 0 से शुरू कर सकते हैं, टैंक को 3 इकाई ईंधन से भरते हैं, और शहर 1 तक यात्रा करने के लिए 2 इकाई ईंधन का उपयोग करते हैं। टैंक में एक इकाई बचती है। शहर 1 पर 1 इकाई ईंधन लेने के बाद, कार में 2 इकाई ईंधन होता है और हम 2 इकाई ईंधन का उपयोग करके शहर 2 तक यात्रा कर सकते हैं। ईंधन टैंक अब खाली है। शहर 2 पर 2 गैलन ईंधन भरने के बाद, हम फिर 2 गैलन ईंधन का उपयोग करके शहर 0 पर वापस यात्रा करते हैं।
हम शहर 2 से शुरू कर सकते हैं, कार को 2 इकाई ईंधन से भरते हैं, और शहर 0 तक यात्रा करते हैं। फिर शहर 0 से 3 गैलन ईंधन भरने के बाद, हम फिर शहर 1 तक यात्रा करते हैं, और हमारे पास 1 इकाई ईंधन होता है। हम फिर शहर 1 पर 1 इकाई ईंधन भर सकते हैं, और अब 2 इकाई ईंधन है और शहर 2 तक यात्रा कर सकते हैं।
हालांकि, हम शहर 1 से शुरू नहीं कर सकते, वहां केवल 1 इकाई ईंधन मौजूद है, लेकिन शहर 2 तक यात्रा करने के लिए 2 गैलन की आवश्यकता होती है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- n := fuel का आकार
- req := आकार n की एक सरणी जिसे 0 से भरा गया है
- k को 0 से 1 तक की रेंज में, करें
- i को n-1 से 0 तक, 1 से घटाते हुए, करें
- nexti :=(i + 1) mod n
- req[i] := 0 और req[nexti] + costs[i] - fuel[i] का अधिकतम
- यदि (req[i] + fuel[i] और cap का न्यूनतम) - costs[i] < req[nexti], तो
- 0 लौटाएं
- i को n-1 से 0 तक, 1 से घटाते हुए, करें
- r में 0 की गिनती लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
def solve(cap, fuel, costs): n = len(fuel) req = [0] * n for k in range(2): for i in range(n-1, -1, -1): nexti = (i + 1) % n req[i] = max(0, req[nexti] + costs[i] - fuel[i]) if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]: return 0 return sum(1 for r in req if r == 0) cap = 3 fuel = [3,1,2] costs = [2,2,2] print(solve(cap, fuel, costs))
इनपुट
3, [3,1,2], [2,2,2]
आउटपुट
2