fork(1) download 
  1. import java.util.BitSet;
  2.  
  3. /*
  4.  * プログラミングのお題スレ Part11 
  5.  * //mevius.5ch.net/test/read.cgi/tech/1524570314/597
  6.  * 597 名前：デフォルトの名無しさん[sage] 投稿日：2018/07/14(土) 05:33:19.05 ID:jpR0mrXc
  7.  * 国際数学オリンピック
  8.  * 問３反パスカル的三角形
  9.  * //twitter.com/worapolketanond/status/1017612366840717312
  10.  */
  11. class Q11_597
  12. {
  13.     public static void main(String[] args)
  14.     {
  15.         for(int i = 1; i <= 8; i++) solve(i);
  16.     }
  17.  
  18.     static void solve(int n)
  19.     {
  20.         System.out.println("N=" + n);
  21.         int max = n * n + n >> 1;
  22.         int[][] table = new int[n][];
  23.         for (int i = 0; i < n; i++)
  24.             table[i] = new int[i + 1];
  25.         BitSet bitset = new BitSet();
  26.  
  27.         LOOP: for (int pos = 0; pos >= 0;)
  28.         {
  29.             table[pos][0] = bitset.previousClearBit(table[pos][0] == 0 ? max : table[pos][0] - 1);
  30.             if (table[pos][0] == 0)
  31.             {
  32.                 pos--;
  33.                 for (int i = 0; i <= pos; i++) bitset.clear(table[pos][i]);
  34.                 continue;
  35.             }
  36.  
  37.             bitset.set(table[pos][0]);
  38.             for (int i = 0; i < pos; i++)
  39.             {
  40.                 table[pos][i + 1] = Math.abs(table[pos][i] - table[pos - 1][i]);
  41.                 if (bitset.get(table[pos][i + 1]))
  42.                 {
  43.                     for (int j = 0; j <= i; j++) bitset.clear(table[pos][j]);
  44.                     continue LOOP;
  45.                 }
  46.                 bitset.set(table[pos][i + 1]);
  47.             }
  48.  
  49.             pos++;
  50.             if (pos == n)
  51.             {
  52.                 StringBuilder sb = new StringBuilder();
  53.                 for (int i = n - 1; i >= 0; i--)
  54.                 {
  55.                     sb.append('[').append(table[i][i]);
  56.                     for (int j = i + 1; j < n; j++)
  57.                     {
  58.                         sb.append(", ").append(table[j][i]);
  59.                     }
  60.                     sb.append("]\n");
  61.                 }
  62.                 System.out.println(sb);
  63.  
  64.                 pos--;
  65.                 for (int i = 0; i <= pos; i++)
  66.                     bitset.clear(table[pos][i]);
  67.             }
  68.         }
  69.         System.out.println();
  70.     }
  71. }
  72.  
Success #stdin #stdout 2.82s 31592KB
comments (?)
stdin 
Standard input is empty
stdout 
N=1
[1]


N=2
[1]
[3, 2]

[2]
[3, 1]

[1]
[2, 3]

[2]
[1, 3]


N=3
[1]
[4, 3]
[6, 2, 5]

[2]
[5, 3]
[6, 1, 4]

[3]
[1, 4]
[5, 6, 2]

[1]
[3, 4]
[5, 2, 6]

[3]
[2, 5]
[4, 6, 1]

[2]
[3, 5]
[4, 1, 6]

[3]
[4, 1]
[2, 6, 5]

[3]
[5, 2]
[1, 6, 4]


N=4
[4]
[6, 2]
[1, 7, 5]
[9, 10, 3, 8]

[4]
[1, 5]
[6, 7, 2]
[9, 3, 10, 8]

[4]
[5, 1]
[2, 7, 6]
[8, 10, 3, 9]

[3]
[7, 4]
[2, 9, 5]
[8, 10, 1, 6]

[4]
[2, 6]
[5, 7, 1]
[8, 3, 10, 9]

[3]
[2, 5]
[7, 9, 4]
[8, 1, 10, 6]

[3]
[5, 2]
[4, 9, 7]
[6, 10, 1, 8]

[3]
[4, 7]
[5, 9, 2]
[6, 1, 10, 8]


N=5
[5]
[9, 4]
[2, 11, 7]
[10, 12, 1, 8]
[13, 3, 15, 14, 6]

[5]
[4, 9]
[7, 11, 2]
[8, 1, 12, 10]
[6, 14, 15, 3, 13]


N=6

N=7

N=8
https://ideone.com/VUgSXO
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!