TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

79.2% (38/48)

Tags

Description

SET! 是蕾娜最愛玩的桌遊,這款桌遊蘊含了許多特別的數學性質。

SET! 的主要架構為 $81$ 張相異的卡牌,每張牌有 $4$ 種特徵,每一種特徵有 $3$ 種不同的狀態,例如顏色是特徵,而它有紅、綠、紫共三種狀態。

為了方便,我們可以視每張牌為一個有序四元組。更明確的說,對於所有 $0\le x\le 80$,假設 $x=a_3\cdot 3^ 3+a_2\cdot 3^ 2+a_1\cdot 3^ 1+a_0\cdot 3^ 0$,其中 $a_0,a_1,a_2,a_3\in\lbrace 0,1,2\rbrace$,則有序四元組 $v_x=(a_0,a_1,a_2,a_3)$ 代表編號為 $x$ 的牌,其中 $a_i$ 代表這張卡第 $i$ 種特徵是第 $a_i$ 種狀態。

舉例來說,因為 $29=1\cdot 3^ 3+0\cdot 3^ 2+0\cdot 3^ 1+2\cdot 3^ 0$,所以 $v_{29}=(2,0,0,1)$。

對於三張兩兩相異的牌 $v_x=(a_0,a_1,a_2,a_3),v_y=(b_0,b_1,b_2,b_3),v_z=(c_0,c_1,c_2,c_3)$,我們稱它們能形成一組 SET 若且唯若對於每種特徵,三張牌該特徵的狀態都相同或是都相異,即 $(a_i+b_i+c_i)\bmod 3=0,\forall 0\le i\le 3$。

舉例來說,$v_{29}=(2,0,0,1),v_{37}=(1,0,1,1),v_{45}=(0,0,2,1)$ 可以形成一組 SET,但是 $v_{28}=(1,0,0,1),v_{37}=(1,0,1,1),v_{45}=(0,0,2,1)$ 不行,因為第 $0$ 個特徵不完全一樣,也不完全不一樣。

蕾娜認為按照 SET! 原本的規則玩 SET! 固然有趣,但研究其數學性質更有趣,尤其是她最近一直在研究的 anti-SET 集合。

對於一個整數集合 $S\subseteq\lbrace 0,1,2,\ldots,80\rbrace$,我們稱 $S$ 是一個 anti-SET 集合若且唯若對於所有 $x,y,z\in S,x\neq y,y\neq z,z\neq x$,$v_x,v_y,v_z$ 不形成一組 SET。

蕾娜表示她已經證明出所有 anti-SET 集合的大小皆不超過 $20$,同時她也證明了大小恰好為 $20$ 的 anti-SET 集合恰好有 $682344$ 個。

蕾娜認為身為 IOIC 學員的你肯定能夠輕易地構造出數個相異的 anti-SET 集合。給定一個正整數 $N$,請你找出 $N$ 個大小為 $20$ 的相異 anti-SET 集合 $S_1,S_2,\ldots,S_N$ 來回應蕾娜的期待。

Input Format

輸入只有一個正整數 $N$。

  • $N\in\lbrace 1,682344\rbrace$

Output Format

輸出 $N$ 行,其中第 $i$ 行輸出 $20$ 個相異的整數 $a_{i,1},a_{i,2},\ldots,a_{i,20}$,代表 $S_i={a_{i,1},a_{i,2},\ldots,a_{i,20}}$。

注意到你給出的答案必須滿足以下條件:

  • $0\le a_{i,j}\le 80$
  • $S_i$ 是一個 anti-SET 集合
  • 對於所有 $j\neq k$,$a_{i,j}\neq a_{i,k}$
  • 對於所有 $i\neq j$,$S_i\neq S_j$

Sample Input 1

1

Sample Output 1

0 5 6 11 13 17 18 23 24 39 41 56 57 62 63 67 69 74 75 80

Hints

Problem Source

IOICamp 2023 Day1 pP

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~1 無其他限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 7000 1048576 65536 1 2
1 7000 1048576 65536 2