Problem:


Score: 600 points

Problem Statement

AtCoder's head office consists of N rooms numbered 1 to N. For any two rooms, there is a direct passage connecting these rooms.

For security reasons, Takahashi the president asked you to set a level for every passage, which is a positive integer and must satisfy the following condition:

For each room i\ (1 \leq i \leq N), if we leave Room i, pass through some passages whose levels are all equal and get back to Room i, the number of times we pass through a passage is always even.

Your task is to set levels to the passages so that the highest level of a passage is minimized.

Constraints

N is an integer between 2 and 500 (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print one way to set levels to the passages so that the objective is achieved, as follows:

a_{1,2} a_{1,3} ... a_{1,N}
a_{2,3} ... a_{2,N}
.
.
.
a_{N-1,N}

Here a_{i,j} is the level of the passage connecting Room i and Room j.

If there are multiple solutions, any of them will be accepted.

Sample Input 1

3

Sample Output 1

1 2
1

The following image describes this output:

For example, if we leave Room 2, traverse the path 2 \to 3 \to 2 \to 3 \to 2 \to 1 \to 2 while only passing passages of level 1 and get back to Room 2, we pass through a passage six times.



Sample input:
3


Sample output:
1 2
1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    m, d = LI()
    ans = 0
    for i in range(1, m + 1):
        for j in range(10, d + 1):
            if int(str(j)[0]) < 2 or int(str(j)[1]) < 2:
                continue
            if i == int(str(j)[0]) * int(str(j)[1]):
                ans += 1
    print(ans)
    return

#B
def B():
    n, l = LI()
    a = LI()
    d0 = defaultdict(int)
    d1 = defaultdict(int)
    for i in a:
        d0[i] += 1
    for i in range(n):
        b = 0
        for k in range(i+1, n):
            if a[i] > a[k]:
                b += 1
        d1[i] = b
    ans = 0
    d2 = list(d0.items())
    d2.sort()
    d3 = defaultdict(int)
    d = 0
    for key, value in d2:
        d3[key] = d
        d += value
    for i in range(n):
        ans += d3[a[i]] * l * (l-1) // 2 + d1[i] * l
        ans %= mod
    print(ans % mod)
    return

#C
def C():
    n = II()
    s = S()
    if s[0] == "W":
        print(0)
        return
    lis = [0] * (2 * n)
    l = [0] * (2 * n)
    l[0] = 1
    for i in range(1, 2 * n):
        lis[i] = (lis[i-1] ^ (s[i] == s[i-1]))
        l[i] += l[i - 1] + (lis[i] == 0)
    ans = 1
    if l[-1] != n or s[0] == "W":
        print(0)
        return
    k = 1
    for i in range(2 * n):
        if lis[i]:
            ans *= l[i] - (k - 1)
            ans %= mod
            k += 1
    print(ans * math.factorial(n) % mod)
    return

#D
def D():
    n = II()
    l = len(bin(n)) - 2
    for i in range(n - 1):
        ans = []
        for j in range(i + 2, n + 1):
            for k in range(l):
                if (j >> k) & 1 != ((i + 1) >> k) & 1:
                    ans.append(str(k + 1))
                    break
        print(" ".join(ans))
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    m, d = LI()
    ans = 0
    for i in range(1, m + 1):
        for j in range(10, d + 1):
            if int(str(j)[0]) < 2 or int(str(j)[1]) < 2:
                continue
            if i == int(str(j)[0]) * int(str(j)[1]):
                ans += 1
    print(ans)
    return

#B
def B():
    n, l = LI()
    a = LI()
    d0 = defaultdict(int)
    d1 = defaultdict(int)
    for i in a:
        d0[i] += 1
    for i in range(n):
        b = 0
        for k in range(i+1, n):
            if a[i] > a[k]:
                b += 1
        d1[i] = b
    ans = 0
    d2 = list(d0.items())
    d2.sort()
    d3 = defaultdict(int)
    d = 0
    for key, value in d2:
        d3[key] = d
        d += value
    for i in range(n):
        ans += d3[a[i]] * l * (l-1) // 2 + d1[i] * l
        ans %= mod
    print(ans % mod)
    return

#C
def C():
    n = II()
    s = S()
    if s[0] == "W":
        print(0)
        return
    lis = [0] * (2 * n)
    l = [0] * (2 * n)
    l[0] = 1
    for i in range(1, 2 * n):
        lis[i] = (lis[i-1] ^ (s[i] == s[i-1]))
        l[i] += l[i - 1] + (lis[i] == 0)
    ans = 1
    if l[-1] != n or s[0] == "W":
        print(0)
        return
    k = 1
    for i in range(2 * n):
        if lis[i]:
            ans *= l[i] - (k - 1)
            ans %= mod
            k += 1
    print(ans * math.factorial(n) % mod)
    return

#D
def D():
    n = II()
    ans = [[] for i in range(n - 1)]
    l = len(bin(n)) - 2
    for i in range(n - 1):
        for j in range(i + 2, n + 1):
            for k in range(l):
                if (j >> k) & 1 != ((i + 1) >> k) & 1:
                    ans[i].append(str(k + 1))
                    break
    print()
    for a in ans:
        print(" ".join(a))
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())

# Twitterカンニング
# 二部グラフにする
# どの頂点対も一度以上別の頂点集合に属するようにする
ans = np.zeros((N, N), dtype=int)
level = 1
shift = 0
while True:
    groups = np.arange(N) >> shift & 1
    g0 = np.where(groups)[0]
    g1 = np.where(1 - groups)[0]
    if len(g0) == 0 or len(g1) == 0:
        break
    for i, j in itertools.product(g0, g1):
        ans[i, j] = level
    ans = np.maximum(ans, ans.T)
    shift += 1
    level += 1

for i in range(N - 1):
    print(*ans[i, i + 1:])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
b = 0
t = n
while t > 0:
    t >>= 1
    b += 1
ans = [[0] * n for _ in range(n)]
for k in range(b):
    for i in range(n):
        for j in range(i + 1, n):
            if (i >> k & 1) ^ (j >> k & 1):
                ans[i][j] = k + 1
for i in range(n):
    print(*ans[i][i + 1:], sep=' ')

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

def solve(n):
    for i in range(1, n):
         edges = []
         for j in range(i+1, n+1):
             for k in range(9):
                 if i % (2**(k+1)) != j % (2**(k+1)):
                     # print(i, j, k+1)
                     edges.append(k+1)
                     break
         print(" ".join(map(str,edges)))

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    solve(n)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
n = len(format(N,'b'))

for i in range(N-1):
    i2 = format(i,'b').zfill(n)
    ans = []
    for j in range(i+1,N):
        j2 = format(j,'b').zfill(n)
        for k in range(n):
            if i2[n-1-k] != j2[n-1-k]:
                ans.append(k+1)
                break
    print(*ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N = int(input())

    for i in range(1, N):
        for j in range(i + 1, N + 1):
            digit = 0
            while (i & (1 << digit)) == (j & (1 << digit)):
                digit += 1
            print('{} '.format(digit + 1), end='')
        print('')

sol()

Submission status: Accepted

Solution code:
r = range
n = int(input())
for i in r(n):
 for j in r(i+1, n):
  d=i^j&-(i^j)
  print(d.bit_length())

Submission status: Accepted

Solution code:
n = int(input())
for i in range(n):
    for j in range(i+1, n):
        diff = i^j & -(i^j)
        print(diff.bit_length())

Submission status: Accepted

Solution code:
n = int(input())
edge = [[] for _ in range(n)]
for i in range(n):
    for j in range(i+1, n):
        num = ((i ^ j) & - (i ^ j)).bit_length()
        print(num)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
K = N.bit_length()
ans = [[] for _ in range(N)]
for a, b in itertools.combinations(range(1, N + 1), 2):
    c = a ^ b
    for i in range(K):
        if 1 << i & c:
            ans[a] += [i + 1]
            break
for _ in ans[1:]:
    print(*_)
# https://www.youtube.com/watch?v=JTH27weC38k

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
import math
import bisect
import random

def LI(): return list(map(int, input().split()))
def I(): return int(input())
def LIM(): return list(map(lambda x:int(x) - 1, input().split()))
def LS(): return input().split()
def S(): return input()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


n = I()

for i in range(n):
    for j in range(i + 1, n):
        k = 0
        while (i ^ j) & (1 << k) == 0:
            k += 1
        print(k + 1, end = ' ')
    print('')

Submission status: Accepted

Solution code:
def ans(n):
  if n==0:
    return ['0']
  else:
    l=[['0' for i in range(2**n)] for j in range(2**n)]
    ans2=ans(n-1)
    for i in range(2**n):
      for j in range(2**n):
        if i<2**(n-1) and j<2**(n-1):
          l[i][j]=ans2[i][j]
        elif i<2**(n-1) and j>=2**(n-1):
          l[i][j]=str(n)
        elif i>=2**(n-1) and j<2**(n-1):
          l[i][j]='0'
        else:
          l[i][j]=ans2[i-2**(n-1)][j-2**(n-1)]
    return l
import math
n=int(input())
ans=ans(math.ceil(math.log(n,2)))
for i in range(n-1):
  print(' '.join(ans[i][i+1:n]))

Submission status: Accepted

Solution code:
def ans(n):
  if n==1:
    return [['0','1'],['0','0']]
  else:
    l=[['0' for i in range(2**n)] for j in range(2**n)]
    ans2=ans(n-1)
    for i in range(2**n):
      for j in range(2**n):
        if i<2**(n-1) and j<2**(n-1):
          l[i][j]=ans2[i][j]
        elif i<2**(n-1) and j>=2**(n-1):
          l[i][j]=str(n)
        elif i>=2**(n-1) and j<2**(n-1):
          l[i][j]='0'
        else:
          l[i][j]=ans2[i-2**(n-1)][j-2**(n-1)]
    return l
import math
n=int(input())
N=math.ceil(math.log(n,2))
ans=ans(N)
for i in range(n-1):
  print(' '.join(ans[i][i+1:n]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
n = int(input())
ans = [[0 for _ in range(n)] for _ in range(n)]

def search(level, cand):
	if len(cand) == 1:
		return
	elif len(cand) == 2:
		ans[cand[0]][cand[1]] = level
		return
	even = [cand[i] for i in range(0, len(cand), 2)]
	odd = [cand[i] for i in range(1, len(cand), 2)]
	for e in even:
		for o in odd:
			ans[min(e, o)][max(e, o)] = level
	search(level+1, even)
	search(level+1, odd)
	return

search(1, list(range(n)))
for i in range(n-1):
	print(*ans[i][i+1:])

Submission status: Accepted

Solution code:
n=input()
while n:
	n-=1
	for j in range(n):print(j+1&~j).bit_length()

Submission status: Accepted

Solution code:
n=input()
while n:
	n-=1
	for j in range(n):print (j+1&~j).bit_length()

Submission status: Accepted

Solution code:
n=input()
while n:
	n-=1
	for j in range(n):print((j+1&~j).bit_length())

Submission status: Accepted

Solution code:
n=input()
while n:
	n-=1
	for j in range(n):print-~bin(j+1)[::-1].find('1')

Submission status: Accepted

Solution code:
n=input()
while n:
	n-=1
	for j in range(n):print bin(j+1)[::-1].find('1')+1

Submission status: Accepted

Solution code:
n=input()
while n:
	n-=1
	for j in range(n):print(bin(j+1)[::-1].find('1')+1)

Submission status: Accepted

Solution code:
n=input()
while n:
	n-=1
	for j in range(n):print(bin(j+1)[::-1].index('1')+1)

Submission status: Accepted

Solution code:
n=int(input())
while n:n-=1;print(*[bin(j+1)[::-1].find('1')+1for j in range(n)])

Submission status: Accepted

Solution code:
n=int(input())
while n:n-=1;print(*[bin(j+1)[::-1].index('1')+1for j in range(n)])

Submission status: Accepted

Solution code:
a=int(input())
ans=[[0 for i in range(a-j-1)]for j in range(a-1)]

for i in range(a):
  for j in range(i+1,a):
    k=str(bin(i^j))
    l=len(k)
    for s in range(l):
      if k[-1-s]=="1":
        ans[i][j-i-1]=s+1
        break
        

for i in range(a-1):
  print(*ans[i])

Submission status: Accepted

Solution code:
N=int(input())
for i in range(N):
    i = i + 1
    for j in range(N-i):
        j = i+j+1
        for k in range(9):
            if i % (2**(k+1)) != j % (2**(k+1)):
                print(k+1, end=" ")
                break
    print()

Submission status: Accepted

Solution code:
from math import log, floor

N = int(input())

for i in range(N - 1):
    ans = [1 + floor(log(i ^ j, 2)) for j in range(i + 1, N)]
    print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
for i in range(1, N+1):
    print(*[((i^j)&(-(i^j))).bit_length() for j in range(i+1, N+1)])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

def solve():
    N = int(input())
    E = np.array([[0,1],[0,0]])
    for i in range((N-1).bit_length()-1):
        E_ = E+(E>0)
        E = np.vstack([np.hstack([E_,np.ones_like(E)]),np.hstack([np.zeros_like(E), E_])])
    res = '\n'.join(' '.join(map(str,e[i+1:N])) for i, e in enumerate(E[:N]))
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import math
n=int(input())
l=[1,2,4,8,16,32,64,128,256,512]
for i in range(len(l)):
  if n>l[i]:
    N=l[i+1]
    y=i+1
ANS=[]
L=[]
for i in range(1,y+1):
  L.append([str(i) for j in range(1,2**(i-1)+1)])
L.reverse()
for i in range(N-1):
  x=format(N-i-1,'0'+str(y)+'b')
  ans=[]
  for j in range(len(x)):
    if x[j]=='1':
      ans=L[j]+ans
  if i>=N-n:
    print(' '.join(ans))

Submission status: Accepted

Solution code:
n=int(input())
l=[1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 9, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2]
for i in range(n):
    print(*l[:n-i-1])

Submission status: Accepted

Solution code:
def solve(a,b):
    for i in range(10):
        x=(a>>i)%2
        y=(b>>i)%2
        if x!=y:
            return i+1

n=int(input())
for i in range(1,n):
    print(*[solve(i,j) for j in range(i+1,n+1)])

Submission status: Accepted

Solution code:
n = int(input())
a = [[0]*n for i in range(n)]
pos = [i for i in range(n)]

def bipartite_graph(pos, level):
    pos1 = pos[:len(pos)//2]
    pos2 = pos[len(pos)//2:]  
    for i in pos1:
        for j in pos2:
            a[i][j] = level
    if len(pos1) >= 2:
        bipartite_graph(pos1, level + 1)
    if len(pos2) >= 2:
        bipartite_graph(pos2, level + 1)

bipartite_graph(pos, 1)
for i in range(n):
    print(*a[i][i+1:])

Submission status: Accepted

Solution code:
N = int(input())

A = [[None]*N for _ in [0]*N]

def f(B,level):
    if len(B)==1 : return
    B0 = B[::2]
    B1 = B[1::2]
    for b0 in B0:
        for b1 in B1:
            A[b0][b1] = level
            A[b1][b0] = level
    f(B0,level+1)
    f(B1,level+1)

f(list(range(N)),1)

for i,a in enumerate(A[:-1]):
    print(*a[i+1:])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    m,d = LI()
    ans = 0
    for i in range(1,m+1):
        for j in range(1,d+1):
            d1 = j%10
            d2 = j//10
            if d1 >= 2 and d2 >= 2 and d1*d2 == i:
                ans += 1
    print(ans)
    return

#B
def B():
    def add(i):
        while i <= m:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n,k = LI()
    m = 2000
    a = LI()
    bit = [0]*(m+1)
    ans = 0
    for i in range(n):
        ans += (i-sum(a[i]))*k
        add(a[i])
    inv = pow(2,mod-2,mod)
    for i in range(n):
        ans += sum(a[i]-1)*k*(k-1)*inv%mod
    print(ans%mod)
    return

#C
def C():
    n = I()
    s = S()
    if "W" in (s[0],s[-1]):
        print(0)
        return

    return

#D
def D():
    n = I()
    m = n.bit_length()
    v = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            k = i^j
            for l in range(m):
                if k&(1<<l):
                    v[i][j] = l+1
                    break
    for i in range(n-1):
        print(*v[i][i+1:])
    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
input = raw_input

N = int(input())

levels = [[0 for j in range(501)] for i in range(501)]

nums = [0 for i in range(501)]
nums[2] = 1
nums[3] = 2

graphs = [None for i in range(501)]
graph2 = [[None, None, None], [None, None, 1], [None, 1, None]]
graphs[2] = graph2
graph3 = [[None for i in range(3+1)] for j in range(3+1)]
graph3[1][2] = 2
graph3[1][3] = 1
graph3[2][1] = 2
graph3[2][3] = 1
graph3[3][1] = 1
graph3[3][2] = 1
graphs[3] = graph3

def get_graph(cur_graph, nodes):
    n_nodes = len(nodes)

    old_graph = graphs[n_nodes]
    #print(old_graph, cur_graph, n_nodes)
    new_nodes = nodes
    old_nodes = list(range(1, n_nodes+1))

    for i, new_node1 in enumerate(new_nodes):
        old_node1 = i + 1
        for j2, new_node2 in enumerate(new_nodes[i+1:]):
            j = i + j2 + 1
            #if i == j:
            #    continue
            old_node2 = j + 1
            #print(new_node1, new_node2, old_node1, old_node2)
            cur_graph[new_node1][new_node2] = old_graph[old_node1][old_node2] + 1

    return cur_graph

for n in range(4, N+1):
    n1 = n // 2 
    n2 = n1

    if n % 2 == 1:
        n1 += 1

    nodes1 = [i for i in range(1, n1+1)]
    nodes2 = [i for i in range(n1+1, n+1)]

    cur_graph = [[None for i in range(n+1)] for j in range(n+1)]
    for node1 in nodes1:
        for node2 in nodes2:
            cur_graph[node1][node2] = 1
            cur_graph[node2][node1] = 1

    nums[n] = 1 + max(nums[n1], nums[n2])

    min_level = 2
    cur_graph = get_graph(cur_graph, nodes1)
    cur_graph = get_graph(cur_graph, nodes2)

    graphs[n] = cur_graph


cur_graph = graphs[N]
for i in range(1, N+1):
    out_txt = " ".join([str(cur_graph[i][j]) for j in range(i+1, N+1)])
    print(out_txt)
#out = nums[N]

Submission status: Accepted

Solution code:
n = int(input())

def get_val(a, b):
    for i in range(10):
        x = (a >> i) % 2
        y = (b >> i) % 2
        if x != y:
            return (i + 1)

for i in range(1, n):
    print(*[get_val(i,j) for j in range(i + 1, n + 1)])

Submission status: Accepted

Solution code:
n = int(input())
m = n
k = int(n/2)
cou = 0

while (m > 0):
        if m%2 == 0:
                m = m//2
        else:
                m = (m-1)//2
        cou += 1
cou -= 1

#print(cou)

cost = [[0 for i in range(n)] for i in range(n)]

def p(a):
        for i in range(len(a)):
                print(a[i])

#p(cost)

nuri = 0

def mois(n,a,b,c,d):
        global nuri
        for i in range(a,b+1):
                for j in range(c+1,d+1):
                        cost[i][j] = n
                        cost[j][i] = n
                        if i == j:
                                nuri += 1
                        else:
                                nuri += 2
                
def secl(na,a,b):
        global nuri
        if a == b:
                return 
        else:
                
                mois(na,a,(a+b)//2,(a+b)//2,b)
                #p(cost)
                
                secl(na+1,a,(a+b)//2)
                
                secl(na+1,((a+b)//2)+1,b)

secl(1,0,n-1)
#print((1+2)//2)
#p(cost)

#print(nuri)

#p(cost)

for i in range(n-1):
        a = []
        for j in range(i+1,n):
                a.append(cost[i][j])
        print(*a)

Submission status: Accepted

Solution code:
N=int(input())
def tigai(a,b):
  for i in range(10):
    x = (a>>i)%2
    y = (b>>i)%2
    if x!=y:
      return(i+1)

for i in range(1,N):
  print(*[tigai(i,j) for j in range(i+1,N+1)])

Submission status: Accepted

Solution code:
N=int(input())

ANS=[[0]*N for i in range(N)]

def line(L,i):
    if len(L)<=1:
        return

    
    for k in range(len(L)):
        for l in range(k+1,len(L)):
            if k%2!=l%2:
                ANS[L[k]][L[l]]=i

    M=[L[i] for i in range(0,len(L),2)]
    N=[L[i] for i in range(1,len(L),2)]

    line(M,i+1)
    line(N,i+1)

line(list(range(N)),1)


for i in range(N-1):
    print(*ANS[i][i+1:])

Submission status: Accepted

Solution code:
N = int(input())

ans = [[-1]*N for i in range(N)]

mx = 0
for i in range(N-1):
    for j in range(i+1,N):
        k = j-i
        a = 1
        while k&1==0:
            a += 1
            k >>= 1
        ans[i][j] = a
        mx = max(mx, a)

for i,row in enumerate(ans[:-1]):
    print(*(row[i+1:]))

Submission status: Accepted

Solution code:
def zeros(n):
    ret = 0
    while n != 0:
        if n % 2 == 0:
            ret += 1
            n //= 2
        else:
            break
    return ret

N = int(input())
for i in range(1,N):
    a = []
    for j in range(i+1,N+1):
        d = j - i
        z = zeros(d)
        a.append(z+1)
    print(' '.join(map(str, a)))

Submission status: Accepted

Solution code:

N = int(input())

color = [0] * N
Group = [0] * N

Q = []
num = 1

lis = []

nnq = []
for i in range(N):

    lis.append([0] * N)

    nnq.append(i)

Q.append(nnq)
nexQ = []

while True:

    nq = Q[-1]
    del Q[-1]

    nexa = []
    nexb = []

    for i in range(len(nq)):

        if i % 2 == 0:

            nexa.append(nq[i])

            for j in range(len(nq)):

                if j % 2 == 1:
                    lis[nq[i]][nq[j]] = num

        else:

            nexb.append(nq[i])

            for j in range(len(nq)):

                if j % 2 == 0:
                    lis[nq[i]][nq[j]] = num

    if len(nexa) > 1:
        nexQ.append(nexa)

    if len(nexb) > 1:
        nexQ.append(nexb)


    if len(Q) == 0:

        num += 1

        for k in nexQ:
            Q.append(k)

        nexQ = []

        if len(Q) == 0:
            break

    #print (Q,nq)

for i in range(N):

    l = []

    for j in range(N-1-i):

        j += 1 + i

        l.append(lis[i][j])

    print (" ".join(map(str,l)))

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())

edge = [[0 for j in range(N)] for i in range(N)]

room1 = []
for i in range(N):
	room1.append(i)
room1.append(1)
room = [room1]

while len(room) > 0:
	now = room.pop()
	num = now.pop()
	now1 = now[0:len(now)//2]
	now2 = now[len(now)//2:len(now)]
	for i in now1:
		for j in now2:
			edge[i][j] = num
	if len(now1) > 1:
		now1.append(num + 1)
		room.append(now1)
	if len(now2) > 1:
		now2.append(num + 1)
		room.append(now2)
for i in range(N - 1):
	for j in range(i + 1, N - 1):
		print(edge[i][j], end="")
		print(" ", end="")
	print(edge[i][N - 1])

Submission status: Accepted

Solution code:
n = int(input())

p = [-1]*501

q = 1

for i in range(1,n):
    for j in range(i+1,n+1):
        if p[j-i] == -1:
            if j == n:
                print(q)
            else:
                print(q,end = ' ')
            ind = j-i
            while ind <= len(p)-1:
                p[ind] = q
                ind += (j-i)*2
            q += 1
        else:
            if j==n:
                print(p[j-i])
            else:
                print(p[j-i],end = ' ')

Submission status: Accepted

Solution code:
N = int(input())

ans = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
L = 1


def f(i, j):
    global L
    if i == j:
        return
    mid = (i + j) // 2
    for k in range(i, mid + 1):
        for r in range(mid + 1, j + 1):
            ans[k][r] = L
            ans[r][k] = L
    L += 1
    f(i, mid)
    f(mid + 1, j)
    L -= 1


f(1, N)
for i in range(1, N):
    print(' '.join(
        str(ans[i][j])
        for j in range(i + 1, N + 1)
    ))

Submission status: Accepted

Solution code:
N = int(input())

for i in range(N):
    ans = []
    for j in range(i + 1, N):
        po = j - i
        lv = 1
        while po % 2 == 0:
            po //= 2
            lv += 1
        ans.append(lv)
    print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
level = [[0]*n for _ in range(n)]
nums = [i for i in range(n)]


cnt = n
l = 0
while cnt >= 1:
    l += 1
    cnt = cnt//2
    gr = [[],[]]
    for i in range(n):
        if nums[i]%2 == 0:
            gr[0].append(i)
        else:
            gr[1].append(i)
        nums[i] = nums[i] >> 1
    for numl in gr[0]:
        for numr in gr[1]:
            if level[numl][numr] == 0:
                level[numl][numr] = l
                level[numr][numl] = l
    #print(l,gr,nums,level)
                    
for i in range(n):
    tmpstr = ""
    for j in range(i+1,n):
        tmpstr += str(level[i][j]) + " "
    print(tmpstr)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
tmpl = list(range(1,N+1))

lines = [[0]*(N+1) for _ in range(N+1)]

def solve(tmpl,cnt):
    global lines

    L = len(tmpl)
    if L == 1:
        return

    aa,bb = tmpl[:L//2],tmpl[L//2:]
    for a in aa:
        for b in bb:
            if a < b:
                lines[a][b] = str(cnt)
            else:
                lines[b][a] = str(cnt)

    solve(aa,cnt+1)
    solve(bb,cnt+1)

solve(tmpl,1)

for i in range(1,N):
    print(' '.join(lines[i][i+1:N+1]))

Submission status: Accepted

Solution code:
n = int(input())
g = [[0]*n for i in range(n)]
for s in range(n-1):
  for t in range(s+1,n):
    i,j = s,t
    ed = 1
    while j-i > 3:
      ed += 2
      i //= 4
      j //= 4
    g[s][t] = ed + 1 - (j-i)%2
for i in range(n):
  print(" ".join(map(str,g[i][i+1:])))

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    ANS = [ [0]*N for _ in range(N)]
    for i in range(11):
        if N <= pow(2,i):
            M = i
            break
    # for s in range(1, N, 2):
    #     for i in range(N-s):
    #         ANS[i][i+s] = 1
    for t in range(1,M+1):
        w = pow(2,t-1)
        for s in range(1,N+1, 2):
            if w*s >= N:
                break
            for i in range(N-s*w):
                if ANS[i][i+w*s] == 0:
                    ANS[i][i+w*s] = t
    for i in range(N-1):
        print( " ".join( map( str, ANS[i][i+1:])))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [[0]*N for i in range(N)]
for i in range(N):
    for k in range(10):
        for j in range(2**k-1,N-i-1,2**(k+1)):
            A[i][j] = k+1
for i in A[:-1]:
    for j in i:
        if j == 0:
            break
        print(j,end = " ")
    print()