103672: [Atcoder]ABC367 C - Enumerate Sequences

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：3 Solved：0

Description

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. 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



	  

    

  

        

        

          
Output

          

		  
得分：300分






问题陈述
按升序字典序打印所有满足以下条件的长度为$N$的整数序列。


    

  • 第$i$个元素在$1$到$R_i$之间，包括边界。
    • 

  • 所有元素的和是$K$的倍数。
    • 



 序列的字典序是什么？
一个序列$A = (A_1, \ldots, A_{|A|})$如果满足以下1.或2.的条件，则称它按字典序小于$B = (B_1, \ldots, B_{|B|})$：

    

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

  2. 存在一个整数$1\leq i\leq \min\{|A|,|B|\}$使得以下两个条件都成立：

      

    • $(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



要打印的序列有三个，分别是按字典序的$(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


		  

        

    

  
                

      

        

        Source/Category        

        
      

    

    

  
    

      

        

        加入题单
        

        


		

		
		上一题  下一题		算法标签：