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:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())
#m,d = [int(i) for i in readline().split()]
#xy = [[int(i) for i in readline().split()] for i in range(n)]

ans = [[0]*n for i in range(n)]

L = list(range(n))
def iro(a,b,l): #[a:b],レベルl 以上
    if b-a <= 1: return 
    mid = a + (b-a)//2
    for i in L[a:mid]:
        for j in L[mid:b]:
            ans[i][j] = l
    iro(a,mid,l+1)
    iro(mid,b,l+1)



iro(0,n,1)

#print(*ans, sep="\n")
for i,ai in enumerate(ans[:-1]):
    print(*ai[i+1:])

Submission status: Accepted

Solution code:
def f(V, k):
    n = len(V)
    for i in range(0, n, 2):
        for j in range(1, n, 2):
            Ans.append((V[i], V[j], k))
    V1 = [V[i] for i in range(0, n, 2)]
    V2 = [V[i] for i in range(1, n, 2)]
    if len(V1) > 1:
        f(V1, k+1)
    if len(V2) > 1:
        f(V2, k+1)

N = int(input())
V = list(range(1, N+1))
Ans = []
k = 1
f(V, 1)

Edge = [[None]*(N+1) for _ in range(N+1)]

for i, j, c in Ans:
    Edge[i][j] = c
    Edge[j][i] = c

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

Submission status: Accepted

Solution code:
from functools import lru_cache
N = int(input())


@lru_cache(maxsize=1000)
def get_v(i, j, c, r):

    if i < c // 2 <= j:
        return r
    elif j < c // 2:
        return get_v(i, j, c // 2, r + 1)
    else:
        return get_v(i - c // 2, j - c // 2, c - c // 2, r + 1)


for k in range(N - 1):
    print(*[get_v(k, m, N, 1) for m in range(k + 1, N)])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 二部グラフに分割したい
# 1レベル使っても、半分以上は同じ組になってしまう。
# kレベル使っても、2^k室までしか作れない

N = int(input())

for i in range(1,N):
    row = []
    for j in range(i+1,N+1):
        k=1
        bit = 1
        while (i&bit) == (j&bit):
            k += 1
            bit <<= 1
        row.append(k)
    print(*row)

Submission status: Accepted

Solution code:
from itertools import product

def solve(l, r, offset=1):
    size = r-l
    if size==2:
        Ans[l][l+1] = offset
    elif size==3:
        Ans[l][l+1] = offset
        Ans[l][l+2] = offset
        Ans[l+1][l+2] = offset+1
    else:
        c = (l+r)//2
        solve(l, c, offset+1)
        solve(c, r, offset+1)
        for a, b in product(range(l, c), range(c, r)):
            Ans[a][b] = offset

N = int(input())
Ans = [[0]*N for _ in range(N)]
solve(0, N)
for i, a in enumerate(Ans, 1):
    print(" ".join(map(str, a[i:])))

Submission status: Accepted

Solution code:
N = int(input())

L = [[0] * N for _ in range(N)]

def nasu(l, r, x):
  if l == r:
    return
  if r - l == 1:
    return
  m = (r + l) // 2
  for i in range(l, m):
    for j in range(m, r):
      L[i][j] = x
  nasu(l, m, x + 1)
  nasu(m, r, x + 1)

nasu(0, N, 1)

for i in range(N - 1):
  t = ""
  for j in range(i + 1, N - 1):
    t += str(L[i][j]) + " "
  t += str(L[i][N - 1])
  print(t)

Submission status: Runtime Error

Solution code:
????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

Submission status: Runtime Error

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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
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.block([[E_,np.ones_like(E)],[np.zeros_like(E), E_]])
    res = '\n'.join(' '.join(map(str,e[i+1:N+1])) for i, e in enumerate(E[:N+1]))
    return str(res)

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

Submission status: Runtime Error

Solution code:
def main(n):
	a = []
	b = []
	for i in range(n//2):
		a += [i+1]
		b = [i+1] + b
	if n % 2 == 1:
		a = a[:-1:]
	ans = a+b
	for i in range(n-1):
		for j in range(n-i-1):
			if j % 2 == 0:
				print(j//2+1, end= " " if j!= n-i-2 else "\n")
			else:
				print(ans[i+j//2+1], end=" " if j!= n-i-2 else "\n")
		
main(int(input()))

Submission status: Runtime Error

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: Runtime Error

Solution code:
from math import ceil
N = int(input())
S = input()

level1 = N%2
level2 = ceil(N//2)%2

for i in range(N-1):
    if i == N-1 and level1==1 and N > 3:
        print(3)
    elif i == N-2 and level2==1 and N > 4:
        ans = [1, 3]
        print(*ans)
    res = [k%2+1 for k in range(i, N)]
    print(*res)

Submission status: Runtime Error

Solution code:
n = int(input(n))
for i in range(n):
  for j in range(n - i):
    print(i + 1, end='')
  print('')

Submission status: Runtime Error

Solution code:
N = int(input())
ans = [[0] * N for _ in range(N)]

#スタートを0にしたとき
if N % 2 == 0:
    tmp = 0
    edge = 2
    for s in range(N):
        tmp = s
        no_use = 0
        edge -= 1
        # while edge < N:
        for i in range(1, N): #レベル
            count = 0
            tmp = s
            flag = False #使ったかどうか
            while ans[tmp][(tmp + i) % N] == 0 and count != 2 * (N//2): #まだ貼っていないとき
                flag = True
                ans[tmp][(tmp + i) % N] = i
                ans[(tmp + i) % N][tmp] = i
                tmp = (tmp + i) % N
                count += 1
            if flag == True:
                edge += 1
else:
    print (A)

#出力部分
for index, i in enumerate(ans[:-1]):
    print (*i[index + 1:])

# for i in ans:
#     print (i)

Submission status: Runtime Error

Solution code:
n=int(input())

ans1=[1]*(n//2)
ans2=[]
a=2
c=0
for i in range((n-1)//2):
    for j in range(a-1):
        c+=1
        ans.append(a)
        if c==(n-1)//2:
            break
    if c==(n-1)//2:
        break
    a+=1
ans=[1]*(n-1)
for i in range(n-1):
    if i%2==1:
        ans[i]=ans2[(i-1)//2]
for i in range(n-1,0,-1):
    for j in range(i):
        if j==i-1:
            print(ans[j])
        else:
            print(ans[j],end=' ')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
L = list(map(lambda x: 1 if x == "B" else 0, input().strip()))

if L[0] == 0 or L[-1] == 0:
    print(0)
    exit()

print(*L)

# 1 0 1 1 0 0 0 1

Submission status: Runtime Error

Solution code:
n = int(input())

for i in range(i-1):
  print(" ".join(map(list(int, range(n-i)))