C - Subarray Sum

Contest Duration: 2020-01-18(Sat) 12:00 - 2020-01-18(Sat) 14:00 (local time) (120 minutes) Back to Home

C - Subarray Sum Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

$3$ つの整数 $N$ , $K$ , $S$ が与えられます。

$1$ 以上 $10^9$ 以下の整数からなる長さ $N$ の数列 $A_1, A_2, ..., A_N$ であって、以下の条件を満たすものをひとつ求めてください。なお、制約の項で記述される条件のもとで、このような数列は必ず存在することが証明できます。

$1 \leq l \leq r \leq N$ を満たす整数の組 $(l, r)$ であって、 $A_l + A_{l + 1} + \cdots + A_r = S$ を満たすものはちょうど $K$ 個ある。

制約

$1 \leq N \leq 10^5$
$0 \leq K \leq N$
$1 \leq S \leq 10^9$
入力値はすべて整数である。

入力

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

 $N$   $K$   $S$

出力

条件を満たす数列を以下の形式で出力せよ。

 $A_1$   $A_2$   $...$   $A_N$

入力例 1Copy

Copy

4 2 3

出力例 1Copy

Copy

1 2 3 4

問題文の条件を満たす $(l, r)$ は $(1, 2)$ と $(3, 3)$ の $2$ 個あります。

入力例 2Copy

Copy

5 3 100

出力例 2Copy

Copy

50 50 50 30 70

Score : $400$ points

Problem Statement

Given are three integers $N$ , $K$ , and $S$ .

Find a sequence $A_1, A_2, ..., A_N$ of $N$ integers between $1$ and $10^9$ (inclusive) that satisfies the condition below. We can prove that, under the conditions in Constraints, such a sequence always exists.

There are exactly $K$ pairs $(l, r)$ of integers such that $1 \leq l \leq r \leq N$ and $A_l + A_{l + 1} + \cdots + A_r = S$ .

Constraints

$1 \leq N \leq 10^5$
$0 \leq K \leq N$
$1 \leq S \leq 10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$   $S$

Output

Print a sequence satisfying the condition, in the following format:

 $A_1$   $A_2$   $...$   $A_N$

Sample Input 1Copy

Copy

4 2 3

Sample Output 1Copy

Copy

1 2 3 4

Two pairs $(l, r) = (1, 2)$ and $(3, 3)$ satisfy the condition in the statement.

Sample Input 2Copy

Copy

5 3 100

Sample Output 2Copy

Copy

50 50 50 30 70