Yet Another Contest 5 P1 - Number Pyramid

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Josh is playing with number pyramids! A number pyramid consists of N rows, labelled from 1 to N from top to bottom. The i-th row contains i cells, each containing a single integer between 0 and K-1 (inclusive).

A number pyramid has a special property; each cell (apart from those on the N-th row) contains an integer equal to the sum of the two integers in the cells directly below it, modulo K. Formally, if v_{i, j} is the integer written in the j-th cell (from the left) of the i-th row, then v_{i, j} = (v_{i+1, j} + v_{i+1, j+1}) mod K. A number pyramid with N = 6 and K = 5 is shown below for clarity.

Josh would like to construct a number pyramid such that the integer written in the topmost cell is X (i.e. v_{1, 1} = X). He wonders the following question: what is the lexicographically largest sequence of integers written in the bottom row of any such number pyramid? Formally, what is the lexicographically largest possible sequence v_{N, 1}, v_{N, 2}, \dots, v_{N, N}? Note that Josh cannot choose the values of N and K, and that all integers in the pyramid must be between 0 and K-1 (inclusive).

Sequence a_1, a_2, a_3, \dots, a_N is lexicographically larger than sequence b_1, b_2, b_3, \dots, b_N if, for the smallest i such that a_i \neq b_i, a_i > b_i.


2 \le N \le 10^6

1 \le K \le 10^9

0 \le X < K

Subtask 1 [10%]

N = 2

Subtask 2 [20%]

2 \le N \le 200

1 \le K \le 200

Subtask 3 [30%]

2 \le N \le 2000

Subtask 4 [40%]

No additional constraints.

Input Specification

The only line contains three space-separated integers, N, K, and X respectively.

Output Specification

On a single line, output N space-separated integers, representing the lexicographically largest possible sequence of integers written on row N.

Sample Input

3 2 1

Sample Output

1 1 0


The optimal number pyramid is shown below.


There are no comments at the moment.