We can compute the points gained by each person using the formula provided and compare their points.

In the formula, for $$$Misha$$$, $$$p = a$$$ and $$$t = c$$$; and for $$$Vasya$$$, $$$p = b$$$ and $$$t = d$$$.

import sys
input = lambda: sys.stdin.readline().rstrip()

a, b, c, d = map(int, input().split())

def find_points(p, t):
    return max((3*p)//10, p - (p*t)//250)


Misha = find_points(a, c)
Vasya = find_points(b, d)

if Misha > Vasya:
    print('Misha')

elif Misha < Vasya:
    print('Vasya')

else:
    print('Tie')
    

Generally it takes the sum of each dust level except the last one, however when we select two indices $$$i$$$ and $$$j$$$ every element in between should be different strictly greater than zero so we have to consider the number of zeros involved in the operations.

That means the minimum operation that meets the goal is the summation of the number of non-zero dust-levels excluding the last dust-level and the number of zeros starting from the left-most non-zero dust-level to the right most dust-level excluding the last dust-level.

for _ in range(int(input())):
    n = int(input())
    dust_levels = list(map(int, input().split()))

    max_ops = 0 
    for dust in dust_levels[:-1]:
        if dust or max_ops > dust:
            max_ops += dust + int(dust == 0)

    print(max_ops)

To solve the problem, we need to consider three cases:

• $$$k >= 3$$$ :  we can be greedy, and put the maximum number in its own segment (containing only itself), making it the minimum in that segment. Therefore, the maximum number becomes the maximum of minimums.
• $$$k = 2$$$ : the array has to be divided into a prefix and a suffix. One way is to run a loop computing the answer for each prefix-suffix pair. But there is another way, the first element $$$a_{1}$$$ will always be in the first subsegment, and the last element $$$a_{n}$$$ will always be in the second subsegment. If these numbers are small numbers, we can't avoid them. But if at least one of them is a large number, we can limit one of the segments to that number, and it will be the maximum of minimums.
  
  *It can be proven that for $$$k = 2$$$ the answer is the maximum of the first and last element. 
  
• $$$k = 1$$$ :  then the only possible partition is one segment equal to the whole array. So the answer is the minimum value on the whole array.

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = list(map(int, input().split()))

if k == 1:
    print(min(a))

elif k == 2:
    print(max(a[0], a[-1]))

else:
    print(max(a))
    

Firstly, we can see that for any two different vertices, their children are independent. It means that infection can not spread from children of one vertex to children of another. Also it does not matter how the infection spreads among the children of some vertex, so we only need to know the amount of vertices with the same parent.

Using this knowledge we can reduce the problem to this one: You are given an array of k

positive integers, each integer denotes the amount of healthy vertices with the same parent. Each second you can infect an integer in this array (by injection). Also each second all infected integers decrease by 1 (because of spreading).

Let's now use a greedy algorithm. We will sort this array in decreasing order and infect all integers one by one. These injections are always needed because the integers are independent. After that, each second, all numbers decrease by 1, and we can choose one number to be decreased once more in the same second.

We start from the first integer. Normally, after infecting just one of the children, the amount of time it takes for that child to infect all the others is equal to the total number of children. The total time it takes, in general, is the amount of time it took to infect the first child in the vertices with the same parent plus the number of children with the same parent. We proceed this way, starting from the largest integer.

Finally, if the last number we processed is greater than all the other numbers, our answer is the last time. If not, we need to do some additional work. If the last group we injected finishes faster than at least one of the other groups, it means we have the capacity to inject while the others spread. So, we will inject into the largest group, since we want the total time to be smaller. We use a heap to simulate this: every time, we get the largest time and decrease it by one, since we are injecting and spreading simultaneously.

from heapq import heapify, heappop, heappush
from sys import stdin


def input(): return stdin.readline().strip()


t = int(input())
for _ in range(t):
    n = int(input())
    parent = list(map(int,input().split()))
    
    graph = [[] for i in range(n)]
    for i in range(n -1):
        graph[parent[i] - 1].append(i + 1)
    
    graph.sort(key = lambda x : len(x),reverse=True)
    

    arr = []

    for i in graph:
        if len(i) != 0:
            arr.append(len(i))
    
    arr.append(1)
    
    for i in range(len(arr)):
        arr[i] += i
        
    if max(arr) == arr[-1]:
        print(arr[-1])
        
    else:
        
        cur_ans = arr[-1]
        for i in range(len(arr)):
            arr[i] = -arr[i]
            
        heapify(arr)
        
        while cur_ans < -arr[0]:
            cur = heappop(arr)
            heappush(arr,cur + 1)
            cur_ans += 1
            
        print(cur_ans) 

Simple greedy observation: if at some point in time there exists an animal $$$i$$$ such that no one fears it (there is no index $$$a_j=i$$$), then it is optimal to sell that animal first.

Let's iteratively sell such animals as long as they exist. After selling animal $$$i$$$, we must additionally check if animal $$$a_i$$$ has become such that no one fears it, and if so, add it to the list for sale.

What will we get when we sell all such animals? Note that when there are no such animals left, $$$a_i$$$ will form a permutation, as each animal must be feared by at least one other animal.

As it is known, a permutation consists of cycles of the form $$$i→a_i→a_{a_i}→…→i$$$.

Obviously, for each cycle we must solve the problem independently, and then combine the answers in any order. Note that if we sell animals in the order of the cycle, we will only receive a single payment for the last animal sold.

At the same time, it is not possible to obtain double payment for all animals in any case: the last animal sold from the cycle will always be sold for a single payment.

Therefore, it is optimal to sell all animals in the order of the cycle so that the animal with the minimum cost ends up being the last in this order.

import sys

t = int(sys.stdin.readline().strip())
for _ in range(t):

    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    c = list(map(int, sys.stdin.readline().strip().split()))

    sons = [0] * n
    for i in range(n):
        a[i] -= 1
        sons[a[i]] += 1
        
    q = []
    for i in range(n):
        if sons[i] == 0:
            q.append(i)

    ans = []
    added = [0] * n
    while q:
        v = q.pop()
        ans.append(v)
        added[v] = 1
        sons[a[v]] -= 1
        if sons[a[v]] == 0:
            q.append(a[v])

    for v in range(n):
        if not added[v]:
            v2 = a[v]
            cycle = [v]
            while v2 != v:
                cycle.append(v2)
                v2 = a[v2]
            minc = 10 ** 9
            for u in cycle:
                added[u] = 1
                minc = min(minc, c[u])
            for i in range(len(cycle)):
                if c[cycle[i]] == minc:
                    ans += cycle[i + 1:]
                    ans += cycle[:i + 1]
                    break
    
    print(*map(lambda x: x + 1, ans))