Connection Status:
Competition Arena > MtGFight

MtGFight

SRM 757 · 2019-04-28 · by misof

SRM 757 · 2019-04-28 · by misof · Brute Force, Simple Math, Simple Search, Iteration
Class Name: MtGFight
Return Type: int[]
Method Name: findGoodFight
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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)
{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.)

1)
{0, 1, 2, 3}
{10, 11, 12, 13}
Returns: { }

All these creatures are weak and tough, so in any fight both creatures survive.

2)
{10, 11, 12, 13}
{1, 2, 3, 4}
Returns: { }

Each of these creatures is powerful but frail. In any fight both creatures will die.

3)
{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.

4)
{20, 19, 10, 9}
{8, 1, 10, 9}
Returns: {2, 3 }

The strongest creature cannot be the killer and the one with the smallest toughness cannot be the victim.

Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MtGFight with a public method vector<int> findGoodFight(vector<int> power, vector<int> toughness) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous