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

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 128M

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.


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


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


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



  • 0
    Tofer_G  commented on July 18, 2022, 4: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, 5: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, 1:04 p.m.

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

  • -2
    lifendead  commented on June 23, 2022, 2: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.

  • -2
    ivan79  commented on June 10, 2022, 6: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?

  • -2
    Skelectric  commented on June 9, 2022, 9:32 p.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

  • 0
    codePerson  commented on May 23, 2022, 10:54 p.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?

  • -2
    rocpix  commented on Feb. 4, 2022, 4: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!