"""BTVN: lũy thừa nhanh, tìm gần nhất và vùng chỉ số.

Python3:
  python3 g11-cs-thiet-ke-chia-de-tri.py luy-thua 2 13
  python3 g11-cs-thiet-ke-chia-de-tri.py gan "3 9" 6
  python3 g11-cs-thiet-ke-chia-de-tri.py vung "-1 2 2 5 5 5 9" 5
  python3 g11-cs-thiet-ke-chia-de-tri.py do --repeat 5000
Quy ước gần nhất: nếu hai giá trị cùng khoảng cách, chọn giá trị lớn hơn.
"""
import argparse
from time import perf_counter


def power_linear(a, n):
    p = 1
    for _ in range(n):
        p = p * a
    return p


def power_fast(a, n):
    # a != 0, n nguyên không âm.
    if n == 0:
        return 1
    b = power_fast(a, n // 2)
    if n % 2 == 0:
        return b * b
    return a * b * b


def power_loop(a, n):
    p = 1
    c = a
    while n != 0:
        if n % 2 == 0:
            n = n // 2
            c = c * c
        else:
            n = n - 1
            p = p * c
    return p


def valueClosest(A, left, right, K):
    # A không giảm; trả giá trị gần nhất, không phải chỉ số.
    if left > right:
        return None
    if left == right:
        return A[left]
    if right - left == 1:
        if abs(A[left] - K) < abs(A[right] - K):
            return A[left]
        return A[right]
    mid = (left + right) // 2
    if A[mid] == K:
        return A[mid]
    if K < A[mid]:
        return valueClosest(A, left, mid, K)
    return valueClosest(A, mid, right, K)


def closest_loop(A, K):
    left, right = 0, len(A) - 1
    while left <= right:
        if left == right:
            return A[left]
        if right - left == 1:
            if abs(A[left] - K) < abs(A[right] - K):
                return A[left]
            return A[right]
        mid = (left + right) // 2
        if A[mid] == K:
            return A[mid]
        if K < A[mid]:
            right = mid
        else:
            left = mid
    return None


def closest_linear(A, K):
    if not A:
        return None
    value = A[0]
    for item in A:
        distance = abs(item - K)
        best_distance = abs(value - K)
        if distance < best_distance or (distance == best_distance and item > value):
            value = item
    return value


def findRange(A, left, right, K):
    if left > right:
        return -1, -1
    mid = (left + right) // 2
    if A[mid] == K:
        start, end = mid, mid
        while start >= left and A[start] == K:
            start -= 1
        while end <= right and A[end] == K:
            end += 1
        return start + 1, end - 1
    if A[mid] < K:
        return findRange(A, mid + 1, right, K)
    return findRange(A, left, mid - 1, K)


def benchmark(repeat):
    rows = []
    for n in [10, 20, 50, 100]:
        A = list(range(0, 2 * n, 2))
        K = 2 * n - 3  # Cách đều hai giá trị cuối; chọn giá trị lớn hơn.
        functions = [lambda: closest_linear(A, K),
                     lambda: valueClosest(A, 0, len(A) - 1, K),
                     lambda: closest_loop(A, K)]
        times = []
        for function in functions:
            checksum = 0
            start = perf_counter()
            for _ in range(repeat):
                checksum += function()
            times.append((perf_counter() - start) * 1000 / repeat)
            assert checksum == repeat * (2 * n - 2)
        rows.append((n, *times))
    return rows


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    modes = parser.add_subparsers(dest='mode', required=True)
    power = modes.add_parser('luy-thua')
    power.add_argument('a', type=int)
    power.add_argument('n', type=int)
    for mode in ['gan', 'vung']:
        search = modes.add_parser(mode)
        search.add_argument('array')
        search.add_argument('K', type=int)
    timer = modes.add_parser('do')
    timer.add_argument('--repeat', type=int, default=5000)
    args = parser.parse_args()
    try:
        if args.mode == 'luy-thua':
            if not (0 < abs(args.a) <= 1000 and 0 <= args.n <= 512):
                raise ValueError('Mẫu nhận cơ số nguyên khác 0, trị tuyệt đối không quá 1000; số mũ từ 0 đến 512.')
            print('Nhân lần lượt:', power_linear(args.a, args.n))
            print('Chia để trị đệ quy:', power_fast(args.a, args.n))
            print('Chia để trị vòng lặp:', power_loop(args.a, args.n))
        elif args.mode in ['gan', 'vung']:
            A = [int(x) for x in args.array.split()]
            if any(A[i] > A[i + 1] for i in range(len(A) - 1)):
                raise ValueError('Dãy cần sắp xếp không giảm.')
            if args.mode == 'vung':
                print('Vùng chỉ số:', findRange(A, 0, len(A) - 1, args.K))
            else:
                results = [closest_linear(A, args.K),
                           valueClosest(A, 0, len(A) - 1, args.K),
                           closest_loop(A, args.K)]
                for label, result in zip(['Tuần tự', 'Đệ quy', 'Vòng lặp'], results):
                    print(label + ':', 'không có' if result is None else result)
        else:
            if not 1 <= args.repeat <= 100000:
                raise ValueError('Số lần lặp cần từ 1 đến 100000.')
            print('n,tuan_tu_ms,de_quy_ms,vong_lap_ms')
            for n, a, b, c in benchmark(args.repeat):
                print(f'{n},{a:.9f},{b:.9f},{c:.9f}')
    except ValueError as error:
        parser.exit(2, f'Dữ liệu không phù hợp: {error}\n')


if __name__ == '__main__':
    main()