Problem:
 Score : 700 points    Problem Statement You are given an integer L . Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.   The number of vertices, N , is at most 20 . The vertices are given ID numbers from 1 to N .  The number of edges, M , is at most 60 . Each edge has an integer length between 0 and 10^6 (inclusive).  Every edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, 1,2,...,N is one possible topological order of the vertices.  There are exactly L different paths from Vertex 1 to Vertex N . The lengths of these paths are all different, and they are integers between 0 and L-1 .   Here, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.      Constraints  2 \leq L \leq 10^6  L is an integer.         Input Input is given from Standard Input in the following format:  L       Output In the first line, print N and M , the number of the vertices and edges in your graph.
In the i -th of the following M lines, print three integers u_i,v_i and w_i , representing the starting vertex, the ending vertex and the length of the i -th edge.
If there are multiple solutions, any of them will be accepted.        Sample Input 1 4      Sample Output 1 8 10
1 2 0
2 3 0
3 4 0
1 5 0
2 6 0
3 7 0
4 8 0
5 6 1
6 7 1
7 8 1  In the graph represented by the sample output, there are four paths from Vertex 1 to N=8 :   1 → 2 → 3 → 4 → 8 with length 0  1 → 2 → 3 → 7 → 8 with length 1  1 → 2 → 6 → 7 → 8 with length 2  1 → 5 → 6 → 7 → 8 with length 3   There are other possible solutions.       Sample Input 2 5      Sample Output 2 5 7
1 2 0
2 3 1
3 4 0
4 5 0
2 4 0
1 3 3
3 5 1

Solution (Python):
L=int(input())
n=L.bit_length()
if L==2**n:
  n+=1
path=[]
for i in range(1,n):
  path.append([i,i+1,0])
  path.append([i,i+1,2**(i-1)])
k=(L-1)-(2**(n-1)-1)
cur=2**(n-1)
while k>0:
  if k==1:
    kk=1
  else:
    kk=k.bit_length()
  path.append([kk,n,cur])
  cur+=2**(kk-1)
  k=L-cur
print(n,len(path))
for p in path:
  print(*p)

Solution (Python):
L = int(input())
b = format(L, 'b')
n = len(b)
m = 2 * (n - 1) + b.count('1') - 1
print(n, m)
for i in range(1, n):
    print(i, i + 1, 0)
    print(i, i + 1, 2 ** (i - 1))
w = 2 ** (n - 1)
for j in range(20,-1,-1):
    if (L - w) >> j & 1:
        print(j + 1, n, w)
        w += 2 ** j

Solution (Python):
L = int(input())

N = L.bit_length()
n = []
for i in range(1, N):
    n += [[i, i + 1, 0], [i, i + 1, 2**(i - 1)]]
v = 2**(N - 1) - 1
while L - 1 - v > 0:
    b = min(N - 1, (L - 1 - v).bit_length())
    n += [[b, N, v + 1]]
    v += 2**(b - 1)
M = len(n)
print(N, M)
for _ in n:
    print(*_)

Solution (Python):
from math import log2,floor
L = int(input())
ans = []

r = floor(log2(L))

for i in range(r):
    ans.append('{} {} {}'.format(i+1,i+2,0))
    ans.append('{} {} {}'.format(i+1,i+2,2**i))

for t in range(r-1,-1,-1):
    if 2**r <= L-2**t:
        ans.append('{} {} {}'.format(t+1,r+1,L-2**t))
        L -= 2**t

print('{} {}'.format(r+1,len(ans)))
for s in ans:
    print(s)

Solution (Python):
def f(k,L,p): 
  m = L
  while m%3 > 0:
    p += [[k+1,20,(m-1)*(3**k)]]
    m = m-1
  if m == 0:
    print(20,len(p))
    for l in p:
      print(" ".join([str(t) for t in l]))
    quit()
  for i in range(3):
    p += [[k+1,k+2,i*(3**k)]]
  m = m//3
  if m > 0:
    return f(k+1,m,p)




f(0,int(input()),[])

Solution (Python):
L = int(input())

r = 0
while 2 ** r <= L:
    r += 1

E = []
for i in range(1, r):
    E.append((i, i + 1, 0))
    E.append((i, i + 1, 2 ** (i - 1)))



n = 2 ** (r - 1)


while True:
    d = L - 1 - n + 1
    if d <= 0:
        break
    zi = 0
    while 2 ** (zi) <= d:
        zi += 1

    E.append((zi, r, n))
    n = n + 2 ** (zi - 1)

print("{} {}".format(r, len(E)))

for e in E:
    print("{} {} {}".format(e[0], e[1], e[2]))

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



def solve(L: int):
    r = 0
    while (2 ** r) <= L:
        r += 1
    r -= 1

    edges = []
    nodes = list(range(1, r+2))
    for s, d in zip(nodes, nodes[1:]):
        edges.append((s, d, 0))
        edges.append((s, d, 2 ** (s - 1)))

    base = 2 ** r
    for n in list(reversed(nodes))[1:]:
        c = 2 ** (n - 1)
        if base <= (L - c):
            edges.append((n, nodes[-1], L - c))
            L -= c
    ret = ['{} {}'.format(r + 1, len(edges))]  + ['{} {} {}'.format(s, d, c) for s, d, c in edges]
    return '\n'.join(ret)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = int(next(tokens))  
    result = solve(L)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
import math

l = int(input()) - 1
n = int(math.log2(l + 1) + 1)
res = []
for i in range(n - 1):
    res.append([i + 1, i + 2, 0])
    res.append([i + 1, i + 2, 2 ** i])
i = n - 2
while l > 2 ** (n - 1) - 1:
    t = l - 2 ** i + 1
    if t > 2 ** (n - 1) - 1:
        res.append([i + 1, n, t])
        l = t - 1
    i -= 1
print(n, len(res))
for i in range(len(res)):
    print(res[i][0],res[i][1],res[i][2])

Solution (Python):
import math
l=int(input())-1
n=int(math.log2(l+1)+1)
E=[]
for i in range(n-1):
    E.append([i+1,i+2,0])
    E.append([i+1,i+2,2**i])
i=n-2
while l>2**(n-1)-1:
    t=l-2**i+1
    if t>2**(n-1)-1:
        E.append([i+1,n,t])
        l=t-1
    i-=1
print(n,len(E))
for i in range(len(E)):
    print(*E[i])

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance





def main():
    L = intin()

    r = 0
    while True:
        if 2**(r+1) > L:
            break
        r += 1

    n = r + 1

    path_list = []
    path_list.extend([(i + 1, i + 2, 0) for i in range(r)])
    path_list.extend([(i + 1, i + 2, 2**i) for i in range(r)])

    remain = L - 2**r
    next = 2**r

    for i in reversed(list(range(r))):
        if remain >= 2**i:
            path_list.append((i + 1, n, next))
            remain -= 2**i
            next += 2**i

    print('%d %d' % (n, len(path_list)))
    for path in path_list:
        print('%d %d %d' % path)


if __name__ == '__main__':
    main()

Solution (Python):
from math import log2

L = int(input())
n = int(log2(L))
print(n + 1, format(L, "b").count("1") - 1 + 2 * n)
Li = 1
for i in range(n):
    print(i + 1, i + 2, 0)
    print(i + 1, i + 2, Li)
    Li *= 2
mask = 2
for i in range(n):
    if L >> i & 1:
        print(i + 1, n + 1, L - (L & mask - 1))
    mask *= 2

Solution (Python):

def graph(L):
    beki = 1
    for n in range(20):
        beki *= 2
        if beki > L: break

    ans = []
    Li = 1
    for i in range(n):
        ans += [(i + 1, i + 2, 0)]
        ans += [(i + 1, i + 2, Li)]
        Li *= 2

    Lnext = Li
    nokori_kosu = L - Li
    i = n - 1
    way_i = Li // 2
    while nokori_kosu > 0:
        while way_i > nokori_kosu:
            way_i //= 2
            i -= 1
        ans += [(i + 1, n + 1, Lnext)]
        Lnext += way_i
        nokori_kosu -= way_i
    print(n + 1, len(ans))
    for x in ans:
        print(*x)


L = int(input())
graph(L)

Solution (Python):

def get_node(num):
    now_num = 1
    count = 1
    while 1:
        if now_num > num:
            count -= 1
            break
        count += 1
        now_num *= 2
    return count

def get_ans_data(node_num):
    ans_data = []
    for i in range(1, node_num):
        data = [i, i + 1, 2**(i - 1)]
        data2 = [i, i + 1, 0]
        ans_data.append(data)
        ans_data.append(data2)
    return ans_data

def main():
    num = int(input())

    node_num = get_node(num)
    ans_data = get_ans_data(node_num)

    now_path = 2 ** (node_num - 1)
    now_num = node_num - 1


    for i in range(now_num, 0, -1):
        now_data = 2 ** (i - 1)
        if num - now_data >= now_path:
            ans_data.append((i, node_num, num - now_data))
            num -= now_data

    print(node_num, len(ans_data))
    for data in ans_data:
        print(' '.join(list(map(str, data))))


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

L = int(input())

branches = []

node_count = int(np.log2(L)) + 1



for n in range(node_count - 1):
    branches.append((n, n + 1, 0))
    branches.append((n, n + 1, 2 ** n))


byte_list = list(reversed(format(L, 'b')))[:-1]

a = 2 ** (node_count - 1)
for i in reversed(range(len(byte_list))):
    if byte_list[i] == '1':
        branches.append((i, node_count - 1, a))
        a += 2 ** i

print(node_count, len(branches))
for u, v, w in branches:
    print(u + 1, v + 1, w)

Solution (Python):

import sys


def solve(L: int):
    tmp = L
    a = []
    while tmp > 0:
        a.append(tmp)
        tmp //= 2
    a.reverse()
    
    e = []
    for i in range(1, len(a)):
        e.append([i, i + 1, 0])
        e.append([i, i + 1, a[i - 1]])
        if a[i] % 2 > 0:
            e.append([1, i + 1, a[i] - 1])
    print(len(a), len(e))
    for t in e:
        print(t[0], t[1], t[2])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = int(next(tokens))  
    solve(L)

if __name__ == '__main__':
    main()

Solution (Python):
import math
L=int(input())

N=int(math.log(L,2))

print(N+1,bin(L)[3:].count("1")+2*N)


for i in range(1,N+1):
    print(i,i+1,0)
    print( i, i+1 , 2**(i-1) )


tmp=2**N
for i in range(N,0,-1):
    if tmp+2**(i-1)-1<=L-1:
        print(i,N+1,tmp)
        tmp=tmp+2**(i-1)

Solution (Python):
L = int(input())


N = L.bit_length()
ans = []
for i in range(N - 1):
    ans.append((i, i + 1, 0))
    ans.append((i, i + 1, 2 ** (N - i - 2)))


X = L - 2 ** (N - 1)
dist = 2 ** (N - 1)
for i in reversed(range(X.bit_length())):
    if X & (1 << i):
        ans.append((0, N - i - 1, dist))
        dist += (2 ** i)


print(N, len(ans))
for a, b, d in ans:
    print(a + 1, b + 1, d)

Solution (Python):
L = int(input())

b = bin(L-1)[2:]
l = len(b)
out = []
for i in range(1,l+1):
    out.append([i,i+1,0])
for i in range(2,l+1):
    out.append([i,i+1,1<<(l-i)])

if not "0" in b:
    out.append([1,2,1<<(l-1)])
    b = ""
while len(b)>0 and b != "0":
    if b[-1] == "0":
        out.append([1,len(b)+1,int((b+"0"*l)[:l],2)])
        b = bin(int(b,2)-1)[2:]
    b = b[:-1]

if l < 20:
    print(l+1,len(out))
    for sub in out:
        print(" ".join(map(str,sub)))
else:
    print(l,len(out)-1)
    for u,v,w in out[1:]:
        u = max(1,u-1)
        v = max(1,v-1)
        print(u,v,w)

Solution (Python):
l = int(input())

v_count = 1
additional_e = []
while True:
  if l == 1:
    break
  elif l%2 == 0:
    l = l//2
    v_count += 1 
  elif l%2 == 1:
    l -= 1
    additional_e.append(v_count)

print(v_count, (v_count-1)*2 + len(additional_e))

for i in range(1,v_count):
  print(i, i+1, 0)
  print(i, i+1, 2**(i-1))

num = 2**(v_count-1)

for i in additional_e[::-1]:
  print(i, v_count, num)
  num = num + (2**(i-1))

Solution (Python):
L = int(input())

n = 0
while 2**n <= L:
    n += 1

side_lst = []
    
rest = L - 2**(n-1)
next_num = 2**(n-1)

m = n
while rest > 0:
    if rest >= 2**(m-2):
        side_lst.append([m-1, n, next_num])
        next_num += 2**(m-2)
        rest -= 2**(m-2)
    m -= 1
    
print(n, len(side_lst)+(n-1)*2)
for i in side_lst:
    print(i[0], i[1], i[2])
    
for i in range(1, n):
    print(i, i+1, 0)
    print(i, i+1, 2**(i-1))

Solution (Python):
def all_your_paths_are_different_lengths(L: int)->tuple:
    if L == 1:
        return 2, [(1, 2, 0)]

    r = 0
    while 2 ** (r+1) <= L:
        r = r + 1

    N = r + 1
    edges = []
    power2 = 1
    for i in range(1, N):
        edges.append((i, i+1, 0))
        edges.append((i, i+1, power2))
        power2 = power2 * 2

    for t in range(N-1, 0, -1):
        if L - (2**(t-1)) >= 2**r:
            edges.append((t, N, L - 2**(t-1)))
            L = L - 2**(t-1)

    return N, edges


if __name__ == "__main__":
    L = int(input())
    N, edges = all_your_paths_are_different_lengths(L)
    print(N, len(edges))
    for u, v, w in edges:
        print(u, v, w)

Solution (Python):
L = int(input())

l = L
r = 1
nodes = 1
bits = 0
while l!=1:
    bits += l & 1
    l>>=1
    r<<=1
    nodes+=1
print(str(nodes)+" "+str((nodes-1)*2+bits))

for i in range(1,nodes):
    r>>=1
    print(str(i)+" "+str(i+1)+" "+str(0))
    print(str(i)+" "+str(i+1)+" "+str(r))

r = 1<<(nodes-1)
d = r
for i in range(1,nodes):
    if (r>>i)&L:
        print(str(1)+" "+str(i+1)+" "+str(d))
        d+= (r>>i)

Solution (Python):
length = int(input())
goal = 0
while 2**goal <= length:
    goal += 1
edge = []
for i in range(1,goal):
    edge.append((i, i+1, 0))
    edge.append((i, i+1, 2**(i-1)))
remain = length - 2**(goal - 1)
def addedge(r, s):
    if r == 1:
        edge.append((1, goal, s))
        return
    if r == 2:
        edge.append((1, goal, s))
        edge.append((1, goal, s+1))
        return
    else:
        k = 0
        while 2**k <= r:
            k += 1
        remain = r - 2**(k-1)
        edge.append((k, goal, s))
        if remain:
            addedge(remain, s + 2**(k-1))
if remain:
    shift = 2**(goal-1)
    addedge(remain, shift)
print(goal, len(edge))
for v1, v2, w in edge:
    print(v1, v2, w)

Solution (Python):
import math
l=int(input())
n=math.floor(math.log2(l))
edge=[]
for i in range(n):
    edge.append((i+1,i+2,0))
    edge.append((i+1,i+2,2**i))
i=n-1
while l>2**n:
    m=l-2**i
    if m>=2**n:
        edge.append((i+1,n+1,m))
        l=m
    i-=1
print(n+1,len(edge))
for a,b,c in edge:
    print(a,b,c)

Solution (Python):
import math
l=int(input())
n=int(math.log2(l)+1)
E=[]
for i in range(n-1):
    E.append([i+1,i+2,0])
    E.append([i+1,i+2,2**i])
i=n-2
while l>2**(n-1):
    t=l-2**i
    if t>2**(n-1)-1:
        E.append([i+1,n,t])
        l=t
    i-=1
print(n,len(E))
for i in range(len(E)):
    print(*E[i])

Solution (Python):
import math
l=int(input())-1
n=int(math.log2(l+1)+1)
E=[]
for i in range(n-1):
    E.append([i+1,i+2,0])
    E.append([i+1,i+2,2**i])
i=n-2
while l>2**(n-1)-1:
    t=l-2**i+1
    if t>2**(n-1)-1:
        E.append([i+1,n,t])
        l=t-1
    i-=1
print(n,len(E))
for i in range(len(E)):
    print(*E[i])

Solution (Python):
def main():
    L = int(input())
    N = 2
    while 2**N <= L:
        N += 1
    L -= 2**(N-1)
    E = []
    for i in range(N-1):
        E.append((N-i-1, N-i, 0))
        E.append((N-i-1, N-i, 2**i))
    i = 0
    nxt = 2**(N-1)
    for i in range(2, N+1):
        tmp = 2**(N-i)
        if tmp <= L:
            E.append((1, i, nxt))
            L -= tmp
            nxt += tmp
    print(N, len(E))
    for u, v, w in E:
        print(u, v, w)


if __name__ == "__main__":
    main()

Solution (Python):
import math

l = int(input())

n = int(math.log2(l)) + 1
g = []

for i in range(1, n):
    g.append([i, i + 1, 2**(n - i - 1)])
    g.append([i, i + 1, 0])
    
s = 2**(n - 1)

while l > s:
    t = n - int(math.log2(l - s))
    g.append([1, t, s])
    s += 2**int(math.log2(l - s))
    
print(n, len(g))
for i in range(0, len(g)):
    print(" ".join(list(map(str, g[i]))))

Solution (Python):
import math
l = int(input())
n = math.floor(math.log2(l)) + 1
e = []
for v in range(n-1):
  e.append([v+1, v+2, 0])
  e.append([v+1, v+2, 2**v])
  if (l>>v)&1:
    e.append([v+1, n, l-2**v])
    l -= 2**v
print(n, len(e))
for x in e:
  print(" ".join(map(str, x)))

Solution (Python):
L=int(input())
count=0
k=1
max=0
LL=format(L,'b')
N=len(LL)
M=(len(LL)-1)*2+LL.count('1')-1

print(N,M)
max=2**(N-1)-1
for n in range(1,N):
    print(n,n+1,0)
    print(n,n+1,k)
    k*=2
    if LL[::-1][n-1]=='1' and n!=N:
        print(n,N,max+1)
        max+=2**(n-1)

Solution (Python):
L = int(input())
node = 0
for i in range(21):
    if L < 2**i:
        L2 = 2**(i-1)
        N = i
        node = i - 1
        break

l = L - L2

L_reg = L2
L_tmp = L2
L_new = L2
L_bai = 1

a = []
b = []

def make_arr(init, N, a, b):
    global L_reg
    global L_tmp  
    global L_new  
    global L_bai

    L_new = L_reg

    if [init, N] in a:
        
        L_tmp = L_new - L_bai
        L_bai *= 2
        
        make_arr(init+1, N, a, b)
        a.remove([init, N])
        b.remove(max(b))
    else:
        a.append([init, N])
        b.append(L_new)
        L_reg += 1
        L_bai = 1


for i in range(l):
    make_arr(1,N,a,b)

for i in range(len(a)):
    a[i].append(b[i])

arr_0 = []
arr_2 = []

for i in range(node):
    arr_0.append([i + 1, i + 2, 0])
    arr_2.append([i + 1, i + 2, 2**i])

print(node+1,len(arr_0)+len(arr_2)+len(a))
for i in arr_0:
    print(i[0], i[1], i[2])
for i in arr_2:
    print(i[0], i[1], i[2])
for i in a:
    print(i[0], i[1], i[2])

Solution (Python):


def main():
    L = int(input())

    N = 0
    e = []

    d = L
    k = 0
    while 0 < d:
        d = int(d / 2)
        k += 1
        if 2 <= k:
            e.append((k - 1, k, 0))
            e.append((k - 1, k, 2 ** (k - 2)))

    N = k

    d = L
    k = 0
    s = []
    while 1 < d:
        d, m = int(d / 2), d % 2
        if m == 1:
            s.append(k)
        k += 1

    a = 2 ** (N - 1)
    for i in range(len(s) - 1, -1, -1):
        k = s[i]
        e.append((k + 1, N, a))
        a += 2 ** k


    print('{} {}'.format(N, len(e)))
    for v in e:
        print('{} {} {}'.format(v[0], v[1], v[2]))

if __name__ == '__main__':
    main()

Solution (Python):
L = int(input())

N, r = 0, 1

while r <= L:
    r *= 2
    N += 1

G = []
for i in range(1, N):
    G.append( [i, i+1, 0] )
    G.append( [i, i+1, int(2**(i-1))] )

remain = L - int(2**(N-1))

for i in range(N-1, 0, -1):
    if remain == 0:
        break

    if remain >= int(2**(i-1)): 
        G.append( [i, N, L-remain] )
        remain -= int(2**(i-1))

print (N, len(G))

for i in G:
    print (" ".join(map(str, i)))

Solution (Python):
L = int(input())
r = 0
while 2 ** r <= L:
    r += 1
r -= 1

ans = []
N = r + 1
for i in range(1, N):
    ans.append((i, i + 1, 0))
    ans.append((i, i + 1, 2 ** (i - 1)))
    
for t in range(N - 1, 0, -1):
    if L - 2 ** (t - 1) >= 2 ** r:
        ans.append((t, N, L - 2 ** (t - 1)))
        L -= 2 ** (t - 1)
        
print(N, len(ans))
for i in ans:
    print(i[0], i[1], i[2])

Solution (Python):
from itertools import accumulate
L = int(input())
p2 = [2 ** i for i in range(20)]
p2acc = list(accumulate(p2))

for i in range(19, -1, -1):
    if L >= p2[i]:
        N = i + 1
        break

ans = []
for i in range(N - 1):
    ans.append((i, i + 1, 0))
    ans.append((i, i + 1, 2 ** i))


remain = L - 2 ** (N - 1)

bypass = 2 ** (N - 1)

while remain:
    for i in range(19, -1, -1):
        if remain >= p2[i]:
            ans.append((i, N - 1, bypass))
            remain -= p2[i]
            bypass += p2acc[i - 1] + 1

print(N, len(ans))
for u, v, w in ans:
    print(u + 1, v + 1, w)

Solution (Python):


"""
ちょっと編集
・残り調べるとこ、ビットシフトにしてみた。この方が前からいけるしいいかな。
"""

L = int(input())


edges = []

v = base = 1
while base * 2 <= L:
    edges.append([v, v+1, 0])
    edges.append([v, v+1, base])
    base *= 2
    v += 1

end = edges[-1][1]

rest = L - base

for i in range(19):
    if rest >> i & 1:
        num = 2 ** i
        
        edges.append([i+1, end, L-rest])
        rest -= num
print(v, len(edges))
for i in range(len(edges)):
    print(*edges[i])

Solution (Python):


"""
参考：https://minus9d.hatenablog.com/entry/2018/09/02/004610
・2べきで作るといいのは気づいたんだけどなぁ。
・2べき以外の数値をどうつなげばうまく処理できるかまとめられず…。
"""

L = int(input())


edges = []

v = base = 1
while base * 2 <= L:
    edges.append([v, v+1, 0])
    edges.append([v, v+1, base])
    base *= 2
    v += 1

end = edges[-1][1]

rest = L - base

for i in range(18, -1, -1):
    num = 2 ** i
    if rest >= num:
        
        edges.append([i+1, end, L-rest])
        rest -= num
print(v, len(edges))
for i in range(len(edges)):
    print(*edges[i])

Solution (Python):
L = int(input())


N = 0
for i in range(21):
    if 2 ** i > L:
        break
    else:
        N = i
N += 1


G = []

for i in range(N - 1):
    G.append((i, i + 1, 0))
    G.append((i, i + 1, 2 ** i))


R = list(range(2 ** (N - 1), L))
marker = 0  
B = bin(len(R))[2:][::-1]  


for i in range(len(B) - 1, -1, -1):
    if B[i] == '0':
        continue

    G.append((i, N - 1, R[marker]))
    marker += 2 ** i

print(N, len(G))
for u, v, w in G:
    print(u + 1, v + 1, w)

Solution (Python):
import math
L = int(input())

n = int(math.log2(L))
w1 = pow(2,n-1)
w1n = bin(L - pow(2, n))
p = 2 * n  + w1n.count('1')
print(str(n + 1) + " " + str(p))

print("1 2 0")
print("1 2 " + str(w1))
for i in range(2, n + 1):
  print(str(i) + " " + str(i + 1) + " 0")
  print(str(i) + " " + str(i + 1) + " " + str(pow(2, n - i)))

w = L - 1
for i in range(len(w1n) - 2):
  if w1n[-1] == '1':
    print("1 " + str(n + 1 - i) + " " + str(w))
    w -= pow(2, i)
  w -= pow(2, i)
  w1n = w1n[:-1]
  if w1n.count('1') == 0:
    break

Solution (Python):
L = int(input())

paths = []
n = 2
v = 1
while n <= L:
    paths.append((v, v+1, 0))
    paths.append((v, v+1, n//2))
    v += 1
    n *= 2
n //= 2

vlast = v
nn = n
ll = L - n

while ll > 0:
    if ll >= n:
        paths.append((v, vlast, nn))
        ll -= n
        nn += n
    n //= 2
    v -= 1

print(vlast, len(paths))
for e in paths:
    print(*e)

Solution (Python):
L=int(input())
L_list=list(str(bin(L)))
del L_list[0:2]
N=len(L_list)
for i in range(N):
  L_list[i]=int(L_list[i])
M=2*N-2
for n in range(1,N):
  if L_list[n]==1:
    M+=1
print(N,M)
for i in range(N):
  L_list[i]=int(L_list[i])
for n in range(N-1):
  print(n+1,n+2,0)
  print(n+1,n+2,2**(N-n-2))
A=2**(N-1)
for n in range(1,N):
  if L_list[n]==1:
    print(1,n+1,A)
    A+=2**(N-n-1)

Solution (Python):
L = int(input())
rec = []
r = 0
K = L
while K > 1:
    K //= 2
    r += 1

N = r + 1
for i in range(1, N):
    rec.append([i, i + 1, 0])
    rec.append([i, i + 1, 2 ** (i - 1)])

for i in range(N - 1, 0, -1):
    if L - 2 ** (i - 1) >= 2 ** r:
        rec.append([i, N, L - 2 ** (i - 1)])
        L -= 2 ** (i - 1)

rec.sort()
print(N, len(rec))
for i, j, k in rec:
  print(i, j, k)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    L = int(input())

    m = []
    while L > 1:
        if L % 2 == 0:
            m.append(0)
            L //= 2
        else:
            m.append(1)
            L -= 1

    ans = []
    last = 1
    l = 1
    for x in m[::-1]:
        if x == 0:
            for i in range(len(ans)):
                ans[i][2] *= 2

            ans.append([last, last + 1, 0])
            ans.append([last, last + 1, 1])
            last += 1
            l *= 2
        else:
            ans.append([1, last, l])
            l += 1

    print(last, len(ans))
    for x in ans:
        print(*x)


if __name__ == '__main__':
    main()

Solution (Python):
L=int(input())
keta=0
while(2**keta -1<L):
    keta+=1


edge=[]
tmp=1
for i in range(0,keta-1):
    edge.append("{} {} 0".format(keta-1-i,keta-i))
    edge.append("{} {} {}".format(keta-1-i,keta-i,tmp))
    tmp*=2
    if(L & 1<<(keta-2-i)):
        edge.append("{} {} {}".format(keta-1-i,keta,tmp))
        tmp+=1

if(L==1):
    edge=["1 2 0"]

print("{} {}".format(keta,len(edge)))
for e in edge:
    print(e)

Solution (Python):
l = int(input())
r = 0
g = []

while 2**r <= l:
    r += 1
for i in range(1,r):
    g.append((i,i+1,0))
    g.append((i,i+1,2**(i-1)))
n = r
l -= 2**(r-1)
edge = 2**(n-1)
while l > 0:
    if l < 2**(r-1):
        r -= 1
        continue
    l -= 2**(r-1)
    g.append((r,n,edge))
    edge += 2**(r-1)

print(n,len(g))
for a,b,c in g:
    print(a,b,c)

Solution (Python):
L = int(input())
def divideBin(n):
    d = 1
    ans=[]
    while n > 0:
        r,q=divmod(n,2)
        ans.append(q*d)
        d *= 2
        n = r
    return(ans)
divided = divideBin(L)
N = len(divided)
M = 2*(N-1) + len([x for x in divided if x!=0]) - 1
print(N,M)
for i in range(1,N):
    print(i,i+1,0)
    print(i,i+1,pow(2,i-1))
node = N-1
value = divided[N-1]
while node > 0:
    if divided[node-1] != 0:
        print(node,N,value)
        value += divided[node-1]
    node -= 1

Solution (Python):
L = int(input())
N=0
A=[]
ret=[]
while True:
    N += 1
    A.append(L % 2)
    L //= 2
    if L<1:
        break

s=2
l=1
M = 0
for i in range(len(A)-2,-1,-1):
    ret.append("{0} {1} {2}".format(s-1, s, l))
    ret.append("{0} {1} {2}".format(s-1, s, 0))
    M += 2
    if A[i]==1:
        l *= 2
        ret.append("{0} {1} {2}".format(1, s, l))
        l += 1
        M += 1
    else:
        l *= 2
        
    s += 1
        
print ("{0} {1}".format(N, M))
for r in ret:
    print (r)

Solution (Python):
L = int(input())
r = 0
while 1:
    r += 1
    if 2**r > L or r == 20:
        N = r
        break

path = []
for i in range(1,N):
    path.append([i, i+1, 0])
    path.append([i, i+1, 2**(i-1)])

for t in range(N-1,0,-1):
    if L - 2**(t-1) > 2**(N-1)-1:
        path.append([t, N, L - 2**(t-1) ])
        L -= 2**(t-1)


M = len(path)
print("{} {}".format(N, M))
for i in range(M):
    print(" ".join(map(str,path[i])))

Solution (Python):

L = int(input())


for l_max in range(1, 21):
    if 2 ** l_max > L: break


bits_sub = [None] * l_max
L_temp = L - 2 ** (l_max - 1)
for l in range(l_max):
    bits_sub[l] = L_temp % 2
    L_temp = L_temp // 2


N = l_max
M = 2 * (l_max - 1) + sum(bits_sub)
print(N, M) 


for i in range(l_max - 1):
    for j in range(2):
        print(i + 1, i + 2, j * (2 ** i))


maxlen = 2 ** (l_max - 1)
for i, bit in enumerate(bits_sub):
    if bit == 0: continue
    for j in range(bit):
        print(i + 1, l_max, maxlen)
        maxlen += 2 ** i

Solution (Python):
from math import log, floor
L = int(input())
n = floor(log(L, 3))
l = [(L // (3**(n + 1 - i))) % 3 for i in range(1, n + 2)]
N = n + 2
uvws = [(i, i + 1, j * 3**(n + 1 - i)) 
                for i in range(2, n + 2)
                for j in range(3)] + \
             [(1, i, j * 3**(n + 2 - i)  + sum(l[k - 1] * 3**(n + 1 - k) for k in range(1, i - 1)))
                for i in range(2, n + 3)
                for j in range(l[i - 2])]
M = len(uvws)
print('{} {}'.format(N, M))
for uvw in uvws:
  print('{} {} {}'.format(*uvw))

Solution (Python):
L = int(input())

b = []
while L > 0:
    b.append(L % 2)
    L = int(L / 2)

p = []

cost = 1
for i in range(len(b), 1, -1):
    p.append((i - 1, i, 0))
    p.append((i - 1, i, cost))
    cost *= 2

cost2 = cost
for i in range(2, len(b) + 1):
    cost2 = int(cost2 / 2)
    if b[-i] % 2 == 1:
        p.append((1, i, cost))
        cost += cost2

print(len(b), len(p))
for tp in p:
    print(tp[0], tp[1], tp[2])

Solution (Python):
L = int(input())
B = bin(L)
N = len(B)-2

print(N,2*N+B.count("1")-3)

for i in range(1,N):
    print(i,i+1,0)
    print(i,i+1,2**(i-1))
    if int(B[N+2-i]):
        print(i,N,L-2**(i-1))
        L -= 2**(i-1)

Solution (Python):
L = int(input())
B = bin(L)
N = len(B)-2
Lines = []
for i in range(1,N):
    Lines.append((i,i+1,0))
    Lines.append((i,i+1,2**(i-1)))

for i in range(N-1):
    if B[N+1-i] == '1':
        Lines.append((i+1,N,L-2**i))
        L -= 2**i

print(N,len(Lines))
for Line in Lines:
    print("{} {} {}".format(Line[0],Line[1],Line[2]))

Solution (Python):
L = int(input())
N = len(bin(L)[2:])
M = 0
Lines = []
for i in range(N-1):
    M += 2
    Lines.append((i+1,i+2,0))
    Lines.append((i+1,i+2,2**i))

tmp = 2**(N-1)
for i,j in enumerate(bin(L)[3:],1):
    if j == '1':
        M += 1
        Lines.append((N-i,N,tmp))
        tmp += 2**(N-i-1)



print(N,M)
for Line in Lines:
    print("{} {} {}".format(Line[0],Line[1],Line[2]))