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


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Tzak

Let a = [a_1 \dots a_N] represent the list of Charlie's moves, and let b = [b_1 \dots b_N] represent the list of the bot's moves. Form a list of moves l = [a_1, b_1 \dots a_N, b_N], or in other words form a list that represents moves in the chronological order in which they occur. Iterate through this list, and implement the processes as described in the problem statement by comparing the move types of each index to the next.

Pseudocode:

read N, H
charlie.health is bot.health is H
for i in [0, N)
    read l[i * 2].action, l[i * 2].amount
for i in [0, N)
    read[l * 2 + 1].action, l[i * 2 + 1].amount
player is charlie
opponent is bot
for move in l
    if move.action is attack and (last_move.action is not dodge or no last_move)
        subtract move.amount from opponent.health
    else if next_move.action is dodge or no next_move
        subtract move.amount from player.health
    if charlie.health < 0 print "DEFEAT", terminate
    if bot.health < 0 print "VICTORY", terminate
    swap player with opponent
print "TIE"

Time complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.