Consider a game, in which you have two types of powers, A and B and there are 3 types of Areas X, Y and Z. Every second you have to switch between these areas, and each area has specific properties by which your power A and power B increase or decrease. We need to keep choosing areas in such a way that our survival time is maximized. Survival time ends when any of the powers, A or B reaches less than 0.
Examples:
Initial value of Power A = 20
Initial value of Power B = 8
Area X (3, 2) : If you step into Area X,
A increases by 3,
B increases by 2
Area Y (-5, -10) : If you step into Area Y,
A decreases by 5,
B decreases by 10
Area Z (-20, 5) : If you step into Area Z,
A decreases by 20,
B increases by 5
It is possible to choose any area in our first step.
We can survive at max 5 unit of time by following
these choice of areas :
X -> Z -> X -> Y -> X
This problem can be solved using recursion, after each time unit we can go to any of the area but we will choose that area which ultimately leads to maximum survival time. As recursion can lead to solving same subproblem many time, we will memoize the result on basis of power A and B, if we reach to same pair of power A and B, we won’t solve it again instead we will take the previously calculated result.
Given below is the simple implementation of above approach.
CPP
// C++ code to get maximum survival time#include <bits/stdc++.h>using namespace std;// structure to represent an areastruct area{ // increment or decrement in A and B int a, b; area(int a, int b) : a(a), b(b) {}};// Utility method to get maximum of 3 integersint max(int a, int b, int c){ return max(a, max(b, c));}// Utility method to get maximum survival timeint maxSurvival(int A, int B, area X, area Y, area Z, int last, map<pair<int, int>, int>& memo){ // if any of A or B is less than 0, return 0 if (A <= 0 || B <= 0) return 0; pair<int, int> cur = make_pair(A, B); // if already calculated, return calculated value if (memo.find(cur) != memo.end()) return memo[cur]; int temp; // step to areas on basis of last choose area switch(last) { case 1: temp = 1 + max(maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)); break; case 2: temp = 1 + max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)); break; case 3: temp = 1 + max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo)); break; } // store the result into map memo[cur] = temp; return temp;}// method returns maximum survival timeint getMaxSurvivalTime(int A, int B, area X, area Y, area Z){ if (A <= 0 || B <= 0) return 0; map< pair<int, int>, int > memo; // At first, we can step into any of the area return max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo));}// Driver code to test above methodint main(){ area X(3, 2); area Y(-5, -10); area Z(-20, 5); int A = 20; int B = 8; cout << getMaxSurvivalTime(A, B, X, Y, Z); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;import java.io.*;class GFG { // Java code to get maximum survival time // class to represent an area static class area { // increment or decrement in A and B public int a, b; public area(int a, int b){ this.a = a; this.b = b; } }; // class to represent pair static class Pair{ public int first,second; public Pair(int first,int second){ this.first = first; this.second = second; } } // Utility method to get maximum of 3 integers static int max(int a, int b, int c) { return Math.max(a, Math.max(b, c)); } // Utility method to get maximum survival time static int maxSurvival(int A, int B, area X, area Y, area Z, int last, HashMap<Pair, Integer> memo) { // if any of A or B is less than 0, return 0 if (A <= 0 || B <= 0) return 0; Pair cur = new Pair(A, B); // if already calculated, return calculated value if (memo.containsKey(cur)) return memo.get(cur); int temp = 0; // step to areas on basis of last choose area switch(last) { case 1: temp = 1 + Math.max(maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)); break; case 2: temp = 1 + Math.max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)); break; case 3: temp = 1 + Math.max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo)); break; } // store the result into map memo.put(cur,temp); return temp; } // method returns maximum survival time static int getMaxSurvivalTime(int A, int B, area X, area Y, area Z) { if (A <= 0 || B <= 0) return 0; HashMap<Pair,Integer> memo = new HashMap<>(); // At first, we can step into any of the area return max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)); } // Driver Code public static void main(String args[]) { area X = new area(3, 2); area Y = new area(-5, -10); area Z = new area(-20, 5); int A = 20; int B = 8; System.out.println(getMaxSurvivalTime(A, B, X, Y, Z)); }}// This code is contributed by shinjanpatra |
Python3
# Python code to get maximum survival time# Class to represent an areaclass area: def __init__(self, a, b): self.a = a self.b = b# Utility method to get maximum survival timedef maxSurvival(A, B, X, Y, Z, last, memo): # if any of A or B is less than 0, return 0 if (A <= 0 or B <= 0): return 0 cur = area(A, B) # if already calculated, return calculated value for ele in memo.keys(): if (cur.a == ele.a and cur.b == ele.b): return memo[ele] # step to areas on basis of last chosen area if (last == 1): temp = 1 + max(maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)) elif (last == 2): temp = 1 + max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)) elif (last == 3): temp = 1 + max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo)) # store the result into map memo[cur] = temp return temp# method returns maximum survival timedef getMaxSurvivalTime(A, B, X, Y, Z): if (A <= 0 or B <= 0): return 0 memo = dict() # At first, we can step into any of the area return max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo))# Driver code to test above methodX = area(3, 2)Y = area(-5, -10)Z = area(-20, 5)A = 20B = 8print(getMaxSurvivalTime(A, B, X, Y, Z))# This code is contributed by Soumen Ghosh. |
C#
// C# code to get maximum survival timeusing System;using System.Collections.Generic;class GFG { // class to represent an area class area { // increment or decrement in A and B public int a, b; public area(int a, int b) { this.a = a; this.b = b; } }; // class to represent pair class Pair { public int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } } // Utility method to get maximum of 3 integers static int max(int a, int b, int c) { return Math.Max(a, Math.Max(b, c)); } // Utility method to get maximum survival time static int maxSurvival(int A, int B, area X, area Y, area Z, int last, Dictionary<Pair, int> memo) { // if any of A or B is less than 0, return 0 if (A <= 0 || B <= 0) return 0; Pair cur = new Pair(A, B); // if already calculated, return calculated value if (memo.ContainsKey(cur)) return memo[cur]; int temp = 0; // step to areas on basis of last choose area switch (last) { case 1: temp = 1 + Math.Max(maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)); break; case 2: temp = 1 + Math.Max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)); break; case 3: temp = 1 + Math.Max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo)); break; } // store the result into map memo[cur] = temp; return temp; } // method returns maximum survival time static int getMaxSurvivalTime(int A, int B, area X, area Y, area Z) { if (A <= 0 || B <= 0) return 0; Dictionary<Pair, int> memo = new Dictionary<Pair, int>(); // At first, we can step into any of the area return max( maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)); } // Driver Code public static void Main(String[] args) { area X = new area(3, 2); area Y = new area(-5, -10); area Z = new area(-20, 5); int A = 20; int B = 8; Console.WriteLine( getMaxSurvivalTime(A, B, X, Y, Z)); }}// This code is contributed by lokeshpotta20. |
Javascript
<script>// JavaScript code to get maximum survival time// Class to represent an areaclass area{ constructor(a, b){ this.a = a this.b = b }}// Utility method to get maximum survival timefunction maxSurvival(A, B, X, Y, Z, last, memo){ // if any of A or B is less than 0, return 0 if (A <= 0 || B <= 0) return 0 let cur = new area(A, B) // if already calculated, return calculated value for(let [key,value] of memo){ if (cur.a == key.a && cur.b == key.b) return memo.get(key) } let temp; // step to areas on basis of last chosen area if (last == 1){ temp = 1 + Math.max(maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)) } else if (last == 2){ temp = 1 + Math.max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo)) } else if (last == 3){ temp = 1 + Math.max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo)) } // store the result into map memo.set(cur , temp) return temp}// method returns maximum survival timefunction getMaxSurvivalTime(A, B, X, Y, Z){ if (A <= 0 || B <= 0) return 0 let memo = new Map() // At first, we can step into any of the area return Math.max(maxSurvival(A + X.a, B + X.b, X, Y, Z, 1, memo), maxSurvival(A + Y.a, B + Y.b, X, Y, Z, 2, memo), maxSurvival(A + Z.a, B + Z.b, X, Y, Z, 3, memo))}// Driver code to test above methodlet X = new area(3, 2)let Y = new area(-5, -10)let Z = new area(-20, 5)let A = 20let B = 8document.write(getMaxSurvivalTime(A, B, X, Y, Z),"</br>") // This code is contributed by shinjanpatra</script> |
Output
5
This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
