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

Description

Given n positive fractions, add them one by one in the given order.

The running total starts as 0/1. After each fraction is added, print the total in lowest terms. The denomiantor is always positive, and the numerator and denominator are coprime.

When combining two fractions, use their least common denominator instead of directly multiplying their denominators.

The program uses four global variables:

• gcd_steps: the total number of times gcd has been called. Every call counts, including the outermost call and the final call where b=0. Its initial value is 0.
• total_n, total_d: the numerator and denominator of the current total. Their initial values are 0 and 1, respectively.

You need to complete the following three functions:

• gcd(a, b): returns the greatest common divisor of a and b, and keeps count of how many times gcd is called. It must be recursive.
• simplify(num, den): returns the simplified numerator / denominator. It must use gcd.
• add_fraction(p, q): adds p/q to the current total using the least common denominator, simplifies the result and prints the new total. It must use both gcd and simplify.

Hint

• When a fraction needs to be reduced to lowest terms, the greatest common divisor of its numerator and denominator is useful. The Euclidean algorithm provides a recursive way to compute it.
• Example of the Euclidean Algorithm:
  To find the gcd of 8 and 12

  8  = 12 * 0 + 8
  12 = 8 * 1 + 4 ➡️ gcd(8, 12) = 4
  8 = 4 * 2 + 0
  

  ​

Starter Code

Your program must define and use all the functions in the starter code and do not use gcd function provided by any library. Otherwise, you will receive no credit.

gcd_steps = 0
total_n = 0
total_d = 1

def gcd(a, b):
    # TODO
    pass

def simplify(num, den):
    # TODO
    pass

def add_fraction(p, q):
    # TODO
    pass

n = int(input())
for _ in range(n):
    p, q = map(int, input().split())
    add_fraction(p, q)
print(f"Total gcd steps: {gcd_steps}")

Input

The first line input one postive integer n , where1 ≤ n ≤ 10.
Each of the next n lines contains two positive integers p and q, representing the fraction p/q , where 1 ≤  p,q ≤ 20

Output

After each fraction is added, print the current total in lowest terms on one line format numerator / denominator

Finally, print out total gcd steps on the last line.

Sample Input  Download

Sample Output  Download

Discuss