Can any one help me solve this problem

help
, , , ,
1

Asha and Amar are playing SpaceKings a video game. It is a two-player game where the second player is the helper. Asha needs your help maximizing her gold while playing her favorite game. Both are facing N aliens. Asha and Amar are both at a single location and the aliens are lined up in front of them. Asha and Amar take turns shooting the aliens, and she goes first. During her turn, Asha may choose any alien to shoot at (this means Asha may choose to skip a turn). During his turn, Amar always shoots the alien closest to him to help Asha maximize her gold. Asha and Amar can not shoot dead aliens.

If Asha shoots at an alien, its hit points are reduced by P. If Amar shoots at an alien, its hit points are reduced by Q. If an alien’s hit points go below 1, it is killed. The ith alien starts with Hi hit points. Asha is awarded Gi gold if her shot kills the ith alien, but none if Amar’s shot kills it. What is the maximum amount of gold Asha can obtain?

Input:

Each case begins with one line containing three space-separated integers representing P, Q and N. N lines then follow, with the ith line containing two space-separated integers representing Hi and Gi. The aliens are given in the order of their distance from Asha and Amar. In other words, Amar will shoot at the ith alien only if all aliens < i are dead.

Output - The maximum amount of gold that Asha can get

Input

20 60 3

80 100

80 200

120 300

Output - 500

Explanation:

Asha should give up the first alien. During her first two turns she should soften up the third alien bringing it down to 80 hp, allowing her to easily get the last shot on the second and the third aliens

Here are some of there other test cases:

Input

50 60 2

40 100

40 90

Output - 100

Input

50 60 2

40 100

40 200

Output - 200

Input

50 100 2

60 100

60 200

Output - 200

Input

50 400 2

60 100

190 200

Output - 0

2

Problem Source?

3

interview question

4

Do you have a link? Or was it asked onsite.

5

onsite but i have a link that solves only 8/14 test cases

6

Can I have it?

7
9

sample test cases
20 60 3
80 100
80 200
120 300

output 500

290 10 5
2 100
30 22
2 101
20 5
10 1

output: 228

10

Tried this approach in JavaScript

function getMaxGold(p, q, n, aliens, turn, memo = {}) {
    if (JSON.stringify(aliens) + ',' + String(turn) in memo) return memo[JSON.stringify(aliens) + ',' + String(turn)];
    let isAllDead = true;
    aliens.forEach((item) => {
        if (item[0] !== 0) {
            isAllDead = false;
        }
    });
    if (isAllDead) return 0;
    let max = null;
    if (turn) {
        for (let i = 0; i < aliens.length; i++) {
            if (aliens[i][0] !== 0) {
                let goldGained = 0;
                let hit = aliens[i][0] - p;
                hit <= 0 ? hit = 0 : null;
                let aliensCopy = JSON.parse(JSON.stringify(aliens));
                aliensCopy[i][0] = hit;
                let result = getMaxGold(p, q, n, aliensCopy, !turn, memo);
                if (hit === 0) goldGained = aliens[i][1];
                if (result >= 0) result += goldGained;
                if (max === null || result > max) max = result;
            }
        }
        let result = getMaxGold(p, q, n, JSON.parse(JSON.stringify(aliens)), !turn, memo);
        if (max === null || result > max) max = result;
    } else {
        let j = 0;
        while (aliens[j][0] === 0) j++;
        let hit = aliens[j][0] - q;
        hit <= 0 ? hit = 0 : null;
        let aliensCopy = JSON.parse(JSON.stringify(aliens));
        aliensCopy[j][0] = hit;
        let result = getMaxGold(p, q, n, aliensCopy, !turn, memo);
        if (max === null || result > max) max = result;
    }
    memo[JSON.stringify(aliens) + ',' + String(turn)] = max;
    return max;
}

console.log(getMaxGold(20, 60, 3, [

[80, 100],

[80, 200],

[120, 300]

], true)); //output:500

11

Hi, were you able to solve this problem? Is it a DP solution?