MtGFight | Topcoder Archive

Problem Statement

In the card game Magic the Gathering, some cards represent creatures. Each creature has two parameters: power and toughness. Whenever two creatures fight, each deals damage equal to its power to the other creature. Whenever a creature receives damage greater than or equal to its toughness, it dies.

You are given the description of N creatures: the int[]s power and toughness, each containing N elements. For each valid i, there is a creature whose power is power[i] and whose toughness is toughness[i].

Find two distinct indices i and j such that if creature i fights creature j, creature i will survive and creature j will die. Return {i, j}. Any valid answer will be accepted. If there is no valid answer, return an empty int[] instead.

Definition

Class:: MtGFight
Method:: findGoodFight
Parameters:: int[], int[]
Returns:: int[]
Method signature:: int[] findGoodFight(int[] power, int[] toughness)
(be sure your method is public)

Notes

If an answer exists, the correct return value is a int[] with two elements. Element 0 should be the number of the creature that survives, and element 1 should be the number of the creature that dies.
You are not given the value N explicitly. Instead, you can determine it by looking at the number of elements in power (or toughness).

Constraints

power will contain between 2 and 50 elements, inclusive.
toughness will contain the same number of elements as power.
Each element of power will be between 0 and 20, inclusive.
Each element of toughness will be between 1 and 20, inclusive.

Examples

```
{0, 2, 1, 4}
```
```
{10, 5, 3, 1}
```
```
Returns: {1, 3 }
```
We will use P/T to denote a creature with power P and toughness T. The input describes four creatures: creature number 0 is 0/10, creature number 1 is 2/5, creature number 2 is 1/3, and creature number 3 is 4/1. The only pair that is a correct answer is {1, 3}. When creatures 1 and 3 fight, creature 1 kills creature 3 and manages to survive the fight. (If creatures 0 and 1 fight, they both survive. If creatures 2 and 3 fight, they both die. And so on.)
```
{0, 1, 2, 3}
```
```
{10, 11, 12, 13}
```
```
Returns: { }
```
All these creatures are weak and tough, so in any fight both creatures survive.
```
{10, 11, 12, 13}
```
```
{1, 2, 3, 4}
```
```
Returns: { }
```
Each of these creatures is powerful but frail. In any fight both creatures will die.
```
{4, 1, 7, 5, 3, 5}
```
```
{3, 2, 9, 1, 3, 4}
```
```
Returns: {0, 1 }
```
There are other correct answers as well, for example, {2, 1} would also be accepted. Note that the order matters: {1, 0} and {1, 2} are not correct answers.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.