C - Enumerate Sequences Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

以下の条件を満たす長さ N の整数列を辞書順で小さい方から順に全て出力して下さい。

  • i 番目の要素は 1 以上 R_i 以下
  • 総和が K の倍数
数列の辞書順とは？ 数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。
  1. |A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
  2. ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
    • A_i < B_i

制約

  • 入力は全て整数
  • 1 \le N \le 8
  • 2 \le K \le 10
  • 1 \le R_i \le 5

入力

入力は以下の形式で標準入力から与えられる。

N K
R_1 R_2 \dots R_N

出力

出力すべき数列が X 個あり、そのうち i 個目が A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}) であったとき、答えを以下の形式で出力せよ。

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

入力例 1

3 2
2 1 3

出力例 1

1 1 2
2 1 1
2 1 3

出力すべき数列は 3 個で、辞書順で (1,1,2),(2,1,1),(2,1,3) です。

入力例 2

1 2
1

出力例 2



出力すべき数列が無い場合もあります。

この場合、出力は空で構いません。













入力例 3
5 5
2 3 2 3 2












出力例 3
1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1







Score : 300 points







Problem Statement
Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.


    

  • The i-th element is between 1 and R_i, inclusive.
    • 

  • The sum of all elements is a multiple of K.
    • 



 What is lexicographical order for sequences?
A sequence A = (A_1, \ldots, A_{|A|}) is lexicographically smaller than B = (B_1, \ldots, B_{|B|}) if either 1. or 2. below holds:

    

  1. |A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
    2. 

  2. There exists an integer 1\leq i\leq \min\{|A|,|B|\} such that both of the following are true:

      

    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
      • 

    • A_i < B_i
      • 

    















Constraints
    

  • All input values are integers.
    • 

  • 1 \le N \le 8
    • 

  • 2 \le K \le 10
    • 

  • 1 \le R_i \le 5
    • 
















Input
The input is given from Standard Input in the following format:


N K
R_1 R_2 \dots R_N












Output
Print the answer in the following format, where X is the number of sequences to print, the i-th of which is A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}):


A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}
















Sample Input 1
3 2
2 1 3












Sample Output 1
1 1 2
2 1 1
2 1 3



There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.













Sample Input 2
1 2
1












Sample Output 2


There may be no sequences to print.

In this case, the output can be empty.













Sample Input 3
5 5
2 3 2 3 2












Sample Output 3
1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1