# AC
# Runtime: 408 ms, faster than 23.80% of Python3 online submissions for Implement Rand10() Using Rand7().
# Memory Usage: 16.7 MB, less than 90.76% of Python3 online submissions for Implement Rand10() Using Rand7().
class Solution:
    def rand10(self):
        while True:
            a = rand7()
            if a <= 3:
                b = rand7()
                if b <= 5:
                    return b
            elif a <= 6:
                b = rand7()
                if b <= 5:
                    return b + 5

# AC
# Runtime: 376 ms, faster than 54.71% of Python3 online submissions for Implement Rand10() Using Rand7().
# Memory Usage: 16.9 MB, less than 38.54% of Python3 online submissions for Implement Rand10() Using Rand7().
class Solution:
    def rand10(self):
        while True:
            a, b = rand7(),  rand7()
            num = (a - 1) * 7 + b
            if num <= 40:
                return num % 10 + 1

# AC
# Runtime: 344 ms, faster than 92.72% of Python3 online submissions for Implement Rand10() Using Rand7().
# Memory Usage: 16.7 MB, less than 90.76% of Python3 online submissions for Implement Rand10() Using Rand7().
class Solution:
    def rand10(self):
        while True:
            a, b = rand7(),  rand7()
            num = (a - 1) * 7 + b
            if num <= 40: return num % 10 + 1
            a = num - 40
            b = rand7()
            num = (a - 1) * 7 + b
            if num <= 60: return num % 10 + 1
            a = num - 60
            b = rand7()
            num = (a - 1) * 7 + b
            if num <= 20: return num % 10 + 1

# The rand7() API is already defined for you.
rand7_c = 0
rand10_c = 0

def rand7():
    global rand7_c
    rand7_c += 1
    import random
    return random.randint(1, 7)
    
def rand10():
    global rand10_c
    rand10_c += 1
    while True:
        a, b = rand7(), rand7()
        num = (a - 1) * 7 + b
        if num <= 40: return num % 10 + 1
        a = num - 40   # [1, 9]
        b = rand7()
        num = (a - 1) * 7 + b  # [1, 63]
        if num <= 60: return num % 10 + 1
        a = num - 60  # [1, 3]
        b = rand7()
        num = (a - 1) * 7 + b  # [1, 21]
        if num <= 20: return num % 10 + 1

if __name__ == '__main__':
    while True:
        rand10()
        print(f'{rand10_c} {round(rand7_c/rand10_c, 2)}')

import math
from typing import List

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        L = range(len(costs))
        from itertools import combinations
        left_set_list = [set(c) for c in combinations(list(L), len(L)//2)]

        min_total = math.inf
        for left_set in left_set_list:
            cost = 0
            for i in L:
                is_left = 1 if i in left_set else 0
                cost += costs[i][is_left]
            min_total = min(min_total, cost)

        return min_total

# AC
# Runtime: 36 ms, faster than 87.77% of Python3 online submissions
# Memory Usage: 14.5 MB, less than 14.84% of Python3 online
from typing import List

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        L = range(len(costs))
        cost_diff_lst = [(i, costs[i][0] - costs[i][1]) for i in L]
        cost_diff_lst.sort(key=lambda x: x[1])

        total_cost = 0
        for c, (idx, _) in enumerate(cost_diff_lst):
            is_left = 0 if c < len(L) // 2 else 1
            total_cost += costs[idx][is_left]

        return total_cost

from ortools.sat.python import cp_model

costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]

I = range(len(costs))

model = cp_model.CpModel()
x = []
total_cost = model.NewIntVar(0, 10000, 'total_cost')
for i in I:
    t = []
    for j in range(2):
        t.append(model.NewBoolVar('x[%i,%i]' % (i, j)))
    x.append(t)

# Constraints
# Each person must be assigned to at exact one city
[model.Add(sum(x[i][j] for j in range(2)) == 1) for i in I]
# equal number of person assigned to two cities
model.Add(sum(x[i][0] for i in I) == (len(I) // 2))

# Total cost
model.Add(total_cost == sum(x[i][0] * costs[i][0] + x[i][1] * costs[i][1] for i in I))
model.Minimize(total_cost)

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print('Total min cost = %i' % solver.ObjectiveValue())
    print()
    for i in I:
        for j in range(2):
            if solver.Value(x[i][j]) == 1:
                print('People ', i, ' assigned to city ', j, '  Cost = ', costs[i][j])

import pulp

costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]   # 1859


I = range(len(costs))

items=[i for i in I]
city_a = pulp.LpVariable.dicts('left', items, 0, 1, pulp.LpBinary)
city_b = pulp.LpVariable.dicts('right', items, 0, 1, pulp.LpBinary)

m = pulp.LpProblem("Two Cities", pulp.LpMinimize)

m += pulp.lpSum((costs[i][0] * city_a[i] + costs[i][1] * city_b[i]) for i in items)

# Constraints
# Each person must be assigned to at exact one city
for i in I:
    m += pulp.lpSum([city_a[i] + city_b[i]]) == 1
# create a binary variable to state that a table setting is used
m += pulp.lpSum(city_a[i] for i in I) == (len(I) // 2)

m.solve()

total = 0
for i in I:
    if city_a[i].value() == 1.0:
        total += costs[i][0]
    else:
        total += costs[i][1]

print("Total cost {}".format(total))

# AC
# Runtime: 32 ms, faster than 54.28% of Python3 online submissions for Pow(x, n).
# Memory Usage: 14.2 MB, less than 5.04% of Python3 online submissions for Pow(x, n).

class Solution:
    def myPow(self, x: float, n: int) -> float:
        ret = 1.0
        i = abs(n)
        while i != 0:
            if i & 1:
                ret *= x
            x *= x
            i = i >> 1
        return 1.0 / ret if n < 0 else ret

# AC
# Runtime: 256 ms, faster than 26.21% of Python3 online submissions for Fibonacci Number.
# Memory Usage: 29.4 MB, less than 5.25% of Python3 online submissions for Fibonacci Number.

class Solution:

    def fib(self, N: int) -> int:
        if N <= 1:
            return N

        import numpy as np
        F = np.array([[1, 1], [1, 0]])

        N -= 1
        powerDouble = F
        powers = np.array([[1, 0], [0, 1]])
        while N > 0:
            if N % 2 == 1:
                powers = np.matmul(powers, powerDouble)
            powerDouble = np.matmul(powerDouble, powerDouble)
            N = N // 2

        return powers[0][0]

# AC
# Runtime: 116 ms, faster than 26.25% of Python3 online submissions for Fibonacci Number.
# Memory Usage: 29.2 MB, less than 5.25% of Python3 online submissions for Fibonacci Number.

class Solution:

    def fib(self, N: int) -> int:
        if N <= 1:
            return N

        from numpy.linalg import matrix_power
        import numpy as np
        F = np.array([[1, 1], [1, 0]])
        F = matrix_power(F, N - 1)

        return F[0][0]

# AC
# Runtime: 36 ms, faster than 98.88% of Python3 online submissions for Number of Ways to Paint N × 3 Grid.
# Memory Usage: 13.9 MB, less than 58.66% of Python3 online submissions for Number of Ways to Paint N × 3 Grid.

class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        dp2, dp3 = 6, 6
        n -= 1
        while n > 0:
            dp2, dp3 = (dp2 * 3 + dp3 * 2) % MOD, (dp2 * 2 + dp3 * 2) % MOD
            n -= 1
        return (dp2 + dp3) % MOD

# AC
# Runtime: 88 ms, faster than 39.07% of Python3 online submissions for Number of Ways to Paint N × 3 Grid.
# Memory Usage: 30.2 MB, less than 11.59% of Python3 online submissions for Number of Ways to Paint N × 3 Grid.

class Solution:
    def numOfWays(self, n: int) -> int:
        import numpy as np

        MOD = int(1e9 + 7)
        ret = np.array([[6, 6]])
        m = np.array([[3, 2], [2, 2]])

        n -= 1
        while n > 0:
            if n % 2 == 1:
                ret = np.matmul(ret, m) % MOD
            m = np.matmul(m, m) % MOD
            n = n // 2
        return int((ret[0][0] + ret[0][1]) % MOD)

# AC
# Runtime: 36 ms, faster than 91.78% of Python3 online submissions for Permutations.
# Memory Usage: 13.9 MB, less than 66.52% of Python3 online submissions for Permutations.

from itertools import permutations
from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return [p for p in permutations(nums)]

# AC
# Runtime: 84 ms, faster than 95.43% of Python3 online submissions for Combinations.
# Memory Usage: 15.2 MB, less than 68.98% of Python3 online submissions for Combinations.
from itertools import combinations
from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return [c for c in combinations(list(range(1, n + 1)), k)]

[lst for lst in product([1, 2, 3], ['a', 'b'])]
[(i, s) for i in [1, 2, 3] for s in ['a', 'b']]

# AC
# Runtime: 24 ms, faster than 94.50% of Python3 online submissions for Letter Combinations of a Phone Number.
# Memory Usage: 13.7 MB, less than 83.64% of Python3 online submissions for Letter Combinations of a Phone Number.

from itertools import product
from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        mapping = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        iter_dims = [mapping[i] for i in digits]

        result = []
        for lst in product(*iter_dims):
            result.append(''.join(lst))

        return result

# AC
# Runtime: 28 ms, faster than 85.56% of Python3 online submissions for Fibonacci Number.
# Memory Usage: 13.8 MB, less than 58.41% of Python3 online submissions for Fibonacci Number.

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        i = 2
        for fib in self.fib_next():
            if i == N:
                return fib
            i += 1
            
    def fib_next(self):
        f_last2, f_last = 0, 1
        while True:
            f = f_last2 + f_last
            f_last2, f_last = f_last, f
            yield f

def outer_generator():
    for i in inner_generator():
        yield i

# AC
# Runtime: 48 ms, faster than 90.31% of Python3 online submissions for Kth Smallest Element in a BST.
# Memory Usage: 17.9 MB, less than 14.91% of Python3 online submissions for Kth Smallest Element in a BST.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def ordered_iter(node):
            if node:
                for sub_node in ordered_iter(node.left):
                    yield sub_node
                yield node
                for sub_node in ordered_iter(node.right):
                    yield sub_node

        for node in ordered_iter(root):
            k -= 1
            if k == 0:
                return node.val

# AC
# Runtime: 56 ms, faster than 63.74% of Python3 online submissions for Kth Smallest Element in a BST.
# Memory Usage: 17.7 MB, less than 73.33% of Python3 online submissions for Kth Smallest Element in a BST.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def ordered_iter(node):
            if node:
                yield from ordered_iter(node.left)
                yield node
                yield from ordered_iter(node.right)

        for node in ordered_iter(root):
            k -= 1
            if k == 0:
                return node.val

# AC
# Runtime: 112 ms, faster than 57.59% of Python3 online submissions for 24 Game.
# Memory Usage: 13.7 MB, less than 85.60% of Python3 online submissions for 24 Game.

import math
from itertools import permutations, product
from typing import List

class Solution:

    def iter_trees(self, op1, op2, op3, a, b, c, d):
        yield op1(op2(a, b), op3(c, d))
        yield op1(a, op2(op3(b, c), d))
        yield op1(a, op2(b, op3(c, d)))
        yield op1(op2(a, op3(b, c)), d)

    def judgePoint24(self, nums: List[int]) -> bool:
        mul = lambda x, y: x * y
        plus = lambda x, y: x + y
        div = lambda x, y: x / y if y != 0 else math.inf
        minus = lambda x, y: x - y

        op_lst = [plus, minus, mul, div]

        for ops in product(op_lst, repeat=3):
            for val in permutations(nums):
                for v in self.iter_trees(ops[0], ops[1], ops[2], val[0], val[1], val[2], val[3]):
                    if abs(v - 24) < 0.0001:
                        return True
        return False

# AC
# Runtime: 116 ms, faster than 56.23% of Python3 online submissions for 24 Game.
# Memory Usage: 13.9 MB, less than 44.89% of Python3 online submissions for 24 Game.

import math
from itertools import combinations, product, permutations
from typing import List

class Solution:

    def judgePoint24(self, nums: List[int]) -> bool:
        mul = lambda x, y: x * y
        plus = lambda x, y: x + y
        div = lambda x, y: x / y if y != 0 else math.inf
        minus = lambda x, y: x - y

        op_lst = [plus, minus, mul, div]

        def recurse(lst: List[int]):
            if len(lst) == 2:
                for op, values in product(op_lst, permutations(lst)):
                    yield op(values[0], values[1])
            else:
                # choose 2 indices from lst of length n
                for choosen_idx_lst in combinations(list(range(len(lst))), 2):
                    # remaining indices not choosen (of length n-2)
                    idx_remaining_set = set(list(range(len(lst)))) - set(choosen_idx_lst)

                    # remaining values not choosen (of length n-2)
                    value_remaining_lst = list(map(lambda x: lst[x], idx_remaining_set))
                    for op, idx_lst in product(op_lst, permutations(choosen_idx_lst)):
                        # 2 choosen values are lst[idx_lst[0]], lst[idx_lst[1]
                        value_remaining_lst.append(op(lst[idx_lst[0]], lst[idx_lst[1]]))
                        yield from recurse(value_remaining_lst)
                        value_remaining_lst = value_remaining_lst[:-1]

        for v in recurse(nums):
            if abs(v - 24) < 0.0001:
                return True

def simulate_bruteforce(n: int) -> bool:
    """
    Simulates one round. Unbounded time complexity.
    :param n: total number of seats
    :return: True if last one has last seat, otherwise False
    """

    seats = [False for _ in range(n)]

    for i in range(n-1):
        if i == 0:  # first one, always random
            seats[random.randint(0, n - 1)] = True
        else:
            if not seats[i]:  # i-th has his seat
                seats[i] = True
            else:
                while True:
                    rnd = random.randint(0, n - 1) # random until no conflicts
                    if not seats[rnd]:
                        seats[rnd] = True
                        break
    return not seats[n-1]

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1.0 if n == 1 else 0.5

def simulate_online(n: int) -> bool:
    """
    Simulates one round of complexity O(N).
    :param n: total number of seats
    :return: True if last one has last seat, otherwise False
    """

    seats = [i for i in range(n)]

    def swap(i, j):
        tmp = seats[i]
        seats[i] = seats[j]
        seats[j] = tmp

    # for each person, the seats array idx available are [i, n-1]
    for i in range(n-1):
        if i == 0:  # first one, always random
            rnd = random.randint(0, n - 1)
            swap(rnd, 0)
        else:
            if seats[i] == i:  # i-th still has his seat
                pass
            else:
                rnd = random.randint(i, n - 1)  # selects idx from [i, n-1]
                swap(rnd, i)
    return seats[n-1] == n - 1

def simulate(n: int) -> bool:
    """
    Simulates one round of complexity O(N).
    :param n: total number of seats
    :return: True if last one has last seat, otherwise False
    """

    seats = [False for _ in range(n)]

    for i in range(n-1):
        if i == 0:  # first one, always random
            rnd = random.randint(0, n - 1)
            seats[rnd] = True
        else:
            if not seats[i]:  # i-th still has his seat
                seats[i] = True
            else:
                # 0 must not be available, now we have 0 and [i+1, n-1],
                rnd = random.randint(i, n - 1)
                if rnd == i:
                    seats[0] = True
                else:
                    seats[rnd] = True
    return not seats[n-1]