coding-problems/problems/kattis/rationalsequence/sol.py at master · NicoKNL/coding-problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# TODO: finish
def computeDepth(n):
    depth = 1
    nodes = 1

    while nodes < n:
        depth += 1
        nodes = treeSize(depth)

    return depth


def treeSize(n):
    return pow(2, n) - 1


def nodesAtDepth(n):
    return treeSize(n) - treeSize(n - 1)


def sequenceToRational(sequence):
    left = 1
    right = 1

    for char in sequence:
        if char == "L":
            right = left + right
        else:
            left = left + right

    return f"{left}/{right}"


def solve(n):
    depth = computeDepth(n)

    sequence = ""
    while depth > 1:
        index = n - treeSize(depth - 1) - 1
        if index < nodesAtDepth(depth) / 2:
            sequence += "L"
            n = n - nodesAtDepth(depth) // 2
        else:
            sequence += "R"
            n = n - nodesAtDepth(depth)

        depth -= 1

    return sequenceToRational(sequence)


def determineN(p, q):
    root = [1, 1]
    tmp = [p, q]

    sequence = []

    height = 0

    while tmp != root:
        # height += 1
        print(tmp)
        if tmp[0] > tmp[1]:
            div = tmp[0] // tmp[1]
            height += div
            tmp[0] -= div * tmp[1]
            sequence.append([div, "r"])
            # sequence += "r"

        else:
            div = tmp[1] // tmp[0]
            height += div
            tmp[1] -= div * tmp[0]
            sequence.append([div, "l"])
            # sequence += "l"

        if tmp[0] == 0:
            tmp[0] = 1

        if tmp[1] == 0:
            tmp[1] = 1

    sequence = sequence[::-1]

    # pos = 1
    # for count, c in sequence:
    # if c == "l":
    # pos = pow(2, count) * pos - 1
    # else:
    # pos = 2 * pow(pos, count)

    nodes_above_height = 0
    if height > 0:
        nodes_above_height = (2 << (height - 1)) - 1
    print("done")
    return nodes_above_height + pos


if __name__ == "__main__":
    p = int(input())

    for _ in range(p):
        k, n = input().split()
        k = int(k)
        n = str(n).split("/")
        p = int(n[0])
        q = int(n[1])

        n = determineN(p, q)
        print(k, solve(n + 1))