/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 600 点
問題文
AtCoder 本社は N 室の部屋からなる施設であり、部屋には 1 から N の番号がついています。どの 2 部屋の間にも、それらを直接結ぶ通路が 1 本通っています。
社長の高橋君はセキュリティのため、全ての通路に レベル を設定するようあなたに依頼しました。ここで、レベルは正の整数値であり、以下の条件を満たさなければなりません。
- 全ての部屋 i\ (1 \leq i \leq N) について、部屋 i から出発し、レベルが等しい通路のみをいくつか通って部屋 i に戻るとき、通路を通る回数は必ず偶数になる。
あなたの仕事は、通路ごとのレベルをうまく設定して、レベルの最大値を最小化することです。
制約
- N は 2 以上 500 以下の整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
目的を達成するような設定の仕方を次のように出力してください。
a_{1,2} a_{1,3} ... a_{1,N}
a_{2,3} ... a_{2,N}
.
.
.
a_{N-1,N}
ここで、a_{i,j} は部屋 i と部屋 j の間の通路に設定するレベルです。
答えが複数ありえる場合、どれを出力してもかまいません。
入力例 1
3
出力例 1
1 2 1
この出力例は下の画像のようになります。
たとえば部屋 2 から出発して、2 \to 3 \to 2 \to 3 \to 2 \to 1 \to 2 という経路でレベル 1 の通路のみを通って元の部屋に戻るとき、通路を通る回数は 6 回です。
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.