DMOPC '19 Contest 5 P2 - Charlie's Crazy Conquest

View as PDF
Submit solution
Points: 5
Time limit: 2.0s
Memory limit: 128M
Author:
tankibuds
Problem type

Charlie just downloaded the new free-to-play game Raid: Shadow Legends Conquest. Just what he wanted! In this game, he must defeat enemies, all of which are bots, and restore power to his clan. Both Charlie and the enemy before him start with H health points. Then, the two take turns performing actions, with Charlie going first. On each turn, one can perform one of two actions:

  • A d Attack your opponent, dealing d damage.
  • D d Dodge your opponent if they attack on the next turn. If they do not attack on the next turn, take d damage from self-humility.

Because he is such a computer genius, Charlie has hacked the game and created two lists of N actions each representing what the opponent will do and what he will do. Your job is to simulate his battle and find out who wins. If any person's health reaches 0 or below, your program is to output the correct answer and terminate.

Note: Dodging at the end of the list of actions counts as a failed dodge. (i.e. if the enemy prepares a dodge as their last move, they will inflict self-harm.)

Input Specification

The first line of input contains two space separated positive integers N and H.

The next N lines contain an uppercase Latin letter and a non-negative integer d representing Charlie's actions.

The next N lines contain an uppercase Latin letter and a non-negative integer d representing his opponent's actions.

Output Specification

Output VICTORY if Charlie wins or DEFEAT if he loses or TIE if none of them die.

Constraints

1 \le N, H \le 1000

0 \le d \le 1000

Sample Input 1

3 100
A 50
D 10
A 100
A 90
D 0
A 0

Sample Output 1

DEFEAT

Sample Explanation 1

After the first turn, the bot's health is at 50. After the second turn, Charlie's health is at 10. After the third turn, Charlie attempts to dodge the next attack but his opponent also dodges causing Charlie's health to drop to 0. The remaining commands are ignored due to Charlie losing.

Sample Input 2

4 100
D 10
D 20
D 30
D 30
D 10
D 20
D 30
D 40

Sample Output 2

VICTORY

Sample Explanation 2

After the second last turn, Charlie's health is at 10 and his opponent's is at 40. Then, his opponent tries to dodge but Charlie does not attack (because the list of actions has been completed) and his opponent takes 40 damage reducing their health to 0.

Sample Input 3

2 100
A 99
A 99
D 1
A 1

Sample Output 3

TIE

Comments


  • 0
    valegrete  commented on Jan. 1, 2023, 9:45 p.m. ← edit 2

    This problem needs to be rewritten to stipulate that the enemy only inflicts self-harm on the final move if Charlie doesn't die from his own self-damage first. For example:

    2 100
A 90
D 10
A 90
D 10

    The way the problem reads, Charlie should take 10 self damage (and die) since the enemy defended on the subsequent move, and the enemy should also take 10 self damage (and die) because he defended on the final move.

    It seems like a TIE but the judge appears to consider this a DEFEAT. I understand the problem says "tie if none of them die," but there's a gaping lacuna since the rules as written imply both players can take fatal damage on the final move. They can't. Or, at the very least, Charlie dies first (and loses) in such a scenario.


    • 0
      chika  commented on Jan. 14, 2023, 12:02 a.m.

      If you're unhappy about this case, then you should be unhappy about all cases where both players commit to fatal dodging moves for themselves. This "ambiguity" you assert exists cannot simply be exclusive to when this happens on the final turn of the game.

      However, the easiest way to resolve this is to interpret the problem statement literally. The damage can only be inflicted on turn N+1 - alternatively phrased as you should not preemptively special-case turn N dodges as inflicting damage immediately. Therefore, once Charlie's opponent initiates the dodge, Charlie takes fatal damage and loses. Whether it is the final turn is irrelevant.

      Note also that if you interpret the statement in this way, then the order in which all damage happens is well-determined. If someone dodges, then on the next turn, either the attack is blocked or the other person dodges and the original person who dodged takes damage. Just because you have the input and you know it's the end doesn't mean that the damage can be inflicted immediately, you have to wait for "Charlie doesn't make an attack" because being allowed to inflict that damage.


  • 0
    jamros  commented on Dec. 31, 2022, 11:11 p.m. ← edit 4

    I'm struggling with this one. I'm passing all samples as well as the first batch of questions, but in the first question of batch 2 my code outputs DEFEAT and TIE and I'm not seeing where my mistake is.

    Is this one of those where each question can have multiple data sets or am I missing something more basic in my code? Would someone be able to provide a sample input where my code fails so I can understand better?

    edit: nvm I found my mistake, I did:

    if player_health and enemy_health > 0:
    print("TIE")

    Instead of:

    if player_health > 0 and enemy_health > 0:
    print("TIE")

  • 0
    JinchengLuo2007  commented on Dec. 16, 2022, 8:23 p.m.

    what happens if they both knock each other out in the same hit?


    • -2
      volcano  commented on Dec. 17, 2022, 12:00 a.m.

      You misunderstood the problem statement. They cannot "knock each other out in the same hit".

      They alternate turns, for example, first Charlie performs his first move (first move of game), then the bot performs its first move (second move of game), then Charlie performs his second move (third move of game), and so on.


  • 3
    panzer_shrek  commented on Aug. 27, 2022, 2:38 p.m.

    This problem is sponsored by Raid: Shadow Legends Nord VPN.


  • 1
    Tofer_G  commented on July 18, 2022, 8:02 p.m.

    I really don't understand how sample 3 is a tie.

    How I understand it:

    Round 1-

    Charlie hits for 99 HP damage, enemy sets up dodge.

    Charlie HP 100, enemy HP 1

    Round 2-

    Charlie misses his attack, enemy hits for 1 HP damage

    Charlie HP 99, enemy HP 1

    Please help me see my error.


    • 1
      InfinityAtEnd  commented on July 19, 2022, 9:04 a.m.

      TIE if none of them die. They both remain alive so it's a TIE even if one of them has more HP left than the other.


      • 0
        Tofer_G  commented on July 19, 2022, 5:04 p.m.

        Thank you. This is so obvious now that you've said it.


  • 0
    lifendead  commented on June 23, 2022, 6:14 p.m.

    This one gave me quite a headache. I've managed to mess up order of action, bot attacked first. Then got indices wrong when searching for opponents next move, it goes ziggzaggy if you're working with two lists as I did. And finally the thing, that gave me The most trouble. Only players first move always hits, and only bots last dodge always inflicts self harm.


  • 1
    ivan79  commented on June 10, 2022, 10:41 a.m. ← edited

    Why would you intentionally make the explanations vague. What happens when Charlie attacks and enemy defends? Whose points go where? Seriously why do you make simple problems so hard to understand?

    Anyway, can anyone explain the logic behind sample 3?


  • 0
    Skelectric  commented on June 10, 2022, 1:32 a.m. ← edited

    If dodges get carried over to the next turn, then the dodges happen concurrently with the next attacks lined up, yet that contradicts the prompt - which one takes precedence, the 1-turn-delayed dodge or the non-delayed attack? This game design doesn't make sense, and so neither do the sample explanations. GG


  • 1
    codePerson  commented on May 24, 2022, 2:54 a.m.

    In the Sample Explanation 1, it says that "After the third turn, Charlie attempts to dodge the next attack but his opponent also dodges causing Charlie's health to drop to 0". However, in Sample Input 1, in the 3rd round, Charlie dodges and the opponent actually attacks instead of dodging like the explanation said. Shouldn't sample 1 result in a Tie?


    • 4
      aja  commented on Aug. 26, 2022, 4:57 a.m.

      I think you just got confused about how the actions actually work, instead of going from 1 row to another it's Charlie's actions first and the Enemie's actions after

      so Charlie's actions are:

      A 50 
D 10 
A 100

      and the Enemy's actions are:

      A 90
D 0
A 0

      Lets visualize for a second like a game Charlie - 100 hp Enemy - 100 hp

      Move 1 - Charlie attacks enemy for 50 damage

      Charlie - 100 hp Enemy - 50 hp

      Move 2 - Enemy attacks charlie for 90 damage

      Charlie - 10 hp Enemy - 50 hp

      Move 3 - Charlie uses dodge which will do 10 damage to him if the enemy doesn't attack him

      Charlie - 10 hp Enemy - 50 hp

      Move 4 - Enemy uses dodge, Charlie loses 10 hp because of self-humility

      Charlie - 0 hp Enemy - 50 hp

      Defeat


  • 1
    rocpix  commented on Feb. 4, 2022, 9:46 p.m.

    wow need to watch details on this one....took me 7 days all because my if statement check the health equaling zero instead of less than equal to zero.not so easy to see where mistakes are with pass/fail system... good luck!