Description

Kirito arrives at the boss room on one of the floors of Aincrad. The battle lasts N turns, and he has already learned the boss's attack damage for every turn in advance.

He has two states that change as the battle goes on: power (power) and charge multiplier (multiplier).
At the beginning of the battle, his base capability: 

• power = 100
• multiplier = 3

In each turn, Kirito first choose one of three action, and then the boss strikes back

• Slash: A steady cut. Its damage is equal to his current power.
• Heavy strike: An all-out charged attack. Its damage is his current power multiplied by multiplier. However, such an attack disrupts his rhythn. After using it, multiplier decrease by 1, down to a minimun of 1
• Guard: He does not attack this turn and deals no damage.
  He focus only on blocking the boss's attack and takes only half of the original damage (rounded down).
  At the same time, he steadies his breathing, and multiplier recover by 1, up to maximum of 3
• ​Boss attack: No matter what Kirito chooses, the boss attacks after he acts.
  • When Kirito takes d points of damage, his power decreases by the quotient of d divided by 10 (rounded down).
  • If Kirito chose Guard this turn, d is the damage after being halved.

Kirito wants to know: over the whole battle, what is the maximum total damage he can deal?
 

Recursive Call and Return flow

Hint

• Choosing the action with the highest damage in the current turn is not necessarily the best choice, because every action affects the state in the following turns.
• If you find yourself writing several nearly identical blocks of code, perhaps you can think about whether there is a better way to organize your program.

Starter Code

Your program must define and use all the functions in the starter code. Otherwise, you will receive no credit.

power = 100
multiplier = 3

def slash():
    # TODO
    pass

def heavy_strike():
    # TODO
    pass

def guard(boss_damage):
    # TODO
    pass

def boss_attack(boss_damage):
     # TODO
    pass

def battle(turn):
    # TODO
    pass

n = int(input())
attacks = list(map(int, input().split()))
max_damage = battle(0)
print(max_damage)

Input

The first line contains an integer N, the number of turns, where 1 <= N<=10

The second line contains N integers. The i-th integer is the boss's attack damage in turn i , where  1 <= attack damage <=10

Output

Print one integer: the maximum total damage Kirito can deal over the whole battle.

Sample Input  Download

Sample Output  Download

Discuss