Clash Of Clans

user_1164828
c_cpp
11 days ago
2.0 kB
2
Indexable
Never
```//Clash Of Clans
You are King of a Clan. You have to play a simple game. You initially have ‘X’ units of troops and ‘Y’ gold coins. There are 4 opponent-player bases you are allowed to attack. You are not allowed to attack the same player base twice in a row. You can choose any of the 4 player bases for 1st attack.
With every attack you gain or lose your troops and gold. For example (see below table) if you attack Player1, you gain 3 units of troops and 2 units of gold. But when you attack Player2 you lose 20 troops and gain 5 units gold. Result of attacking each player base is predefined and is given in below table.

Opponent_Player	Troops	Gold

1	+3	+2
2	-20	+5
3	-10	-5
4	-5	-10

Notation: “+” = You Gain; “-” You Lose.
Once number of troops or gold reaches zero, then, in this attack you have not survived, and the Game ends instantly.
Given initial number of troops and gold, find the maximum number of attacks you can survive.
Note: Given above table and constraints on N and M, Game terminates within finite number of attacks.
Input for each test-case (and constraints)
N = Starting number of Troops: 1 <= N <= 1000
M = Starting amount of Gold: 1 <= M <= 1000
Expected Output
Maximum number of attacks you can survive (integer).
Input format

·         First line: Number of test-cases.

·         Following lines: 1 line for each test case (N M)
Sample Input
3
2 10
4 4
20 8
Sample Output
#1 1
#2 1
#3 5

//code
#include<iostream>
using namespace std;

int arr[][3] = { {-17, 7}, {-7,-3}, {-2,-8}};
int ans;
int N, M;
int visited[5];

void BT(int n, int m, int sum, int index){
if(n <= 0 || m <= 0){
sum--;
if(sum > ans){
ans = sum;
}
return;
}

for(int i=2; i>= index; i--){
BT(n + arr[i][0], m + arr[i][1], sum + 2, i);
}

}

int main(){
freopen("Text.txt", "r", stdin);
int T;
cin >> T;

for(int tc = 1; tc <= T; tc ++){

cin >> N >> M;
ans = 0;
BT(N, M, 0, 0);
cout << "#" << tc << " " << ans << endl;
}
return 0;
}```