AIMESOFT test

bai1.py

class Node:
    def __init__(self, value, next):
        self.value = value
        self.next = next


def solve(arr):
    curr = arr
    while curr:
        print(curr.value, end=' -> ')
        curr = curr.next


if __name__ == '__main__':
    arr = Node(1, Node(2, Node(3, Node(4, None))))
    solve(arr)

bai2.py

import random
import bisect


random.seed(42)

def solve(arr):
    set_arr = list(set(arr))

    # normalize value of set_arr
    s = sum(set_arr)
    normalized = [x / s for x in set_arr]

    f = [0]
    for x in normalized:
        f.append(f[-1] + x)

    # get value from uniform distribution
    rand_val = random.uniform(0, 1)
    return set_arr[bisect.bisect_right(f, rand_val) - 1]


if __name__ == '__main__':
    c = []
    for _ in range(1000):
        c.append(solve([3,6,5,2,1,1,3]))

    from collections import Counter
    print(Counter(c))

bai3.py

INFINITY = 99999999999

def build(arr, tree, root, l, r):
    if l == r:
        tree[root] = arr[l]
    else:
        m = (l + r) // 2
        build(arr, tree, root*2+1, l, m)
        build(arr, tree, root*2+2, m+1, r)
        tree[root] = min(tree[root*2+1], tree[root*2+2])


def get(tree, root, l, r, u, v):
    if l > v or u > r:
        return INFINITY

    if u <= l and r <= v:
        return tree[root]

    m = (l + r) // 2
    return min(get(tree, root*2+1, l, m, u, v), get(tree, root*2+2, m+1, r, u, v))

if __name__ == '__main__':
    arr = []
    tree = []

    ops = [
        ('+', 0, 5),
        ('+', 1, 3),
        ('+', 1, 4),
        ('?', 1, 2),
        ('+', 0, 2),
        ('?', 2, 4),
        ('+', 4, 1),
        ('?', 3, 5),
    ]

    for op, i, j in ops:
        if op == '+':
            arr.insert(i, j)
            tree = [INFINITY] * (len(arr) * 4)
            build(arr, tree, 0, 0, len(arr)-1)
        else:
            print(get(tree, 0, 0, len(arr)-1, i-1, j-1))