"""BTVN: luyện đệ quy với nhị phân, cặp nghịch đảo và đa thức.

Chạy Python3: python3 g11-cs-luyen-tap-de-quy.py 13
Các hàm nhận dữ liệu đúng điều kiện trong bài; CLI chỉ nhận n từ 0 đến4095.
"""
import argparse


def binary(n):
    # n nguyên không âm; trả xâu không có số 0 thừa ở đầu.
    if n == 0:
        return '0'
    if n == 1:
        return '1'
    return binary(n // 2) + str(n % 2)


def binary_list(n):
    if n == 0:
        return [0]
    if n == 1:
        return [1]
    return binary_list(n // 2) + [n % 2]


def decimal(s, n):
    # s chỉ gồm 0/1; 0 <= n <= len(s).
    # Giá trị phần đầu rỗng quy ước bằng0.
    if n == 0:
        return 0
    return 2 * decimal(s, n - 1) + int(s[n - 1])


def nghich_dao(A, k):
    # k là chỉ số cuối phần đầu cần xét; k=-1 dùng cho dãy rỗng.
    if k <= 0:
        return 0
    c = 0
    for i in range(k):
        if A[i] > A[k]:
            c += 1
    return c + nghich_dao(A, k - 1)


def nghich_dao_lap(A):
    c = 0
    for i in range(len(A) - 1):
        for j in range(i + 1, len(A)):
            if A[i] > A[j]:
                c += 1
    return c


def F(A, x, k):
    # A[i] là hệ số của x**i; A không rỗng, 0 <= k < len(A).
    if k == 0:
        return A[0]
    return A[k] * (x ** k) + F(A, x, k - 1)


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument('n', type=int)
    args = parser.parse_args()
    if not 0 <= args.n <= 4095:
        parser.error('Mẫu thử nhận n từ 0 đến 4095.')
    s = binary(args.n)
    print('Nhị phân:', s)
    print('Danh sách:', binary_list(args.n))
    print('Đổi lại:', decimal(s, len(s)))
    values = [4, 1, 4, 2]
    print('Dãy gốc:', values)
    print('Số cặp nghịch đảo:', nghich_dao(values, len(values) - 1))
    print('Bản lặp:', nghich_dao_lap(values))
    coefficients = [2, -3, 4]
    print('Đa thức tại x=2:', F(coefficients, 2, len(coefficients) - 1))


if __name__ == '__main__':
    main()