TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

90.9% (10/11)

Submission's AC Ratio

41.5% (22/53)

Tags

Description

建康中學(簡稱建中)想要在校園中建設一條步道。由於建中是傳說中的「千湖中學」,為了展現其特色,這條步道必須要在下雨時積水。因此校方對工人下達了指令:每一段路和基準水平面都要有非零整數的高度差。具體來說:如果這條步道由$L$段路組成,且第$i$段路和比基準水平面高$a_i$公分(負的代表比基準水平面低),則對於$i=0,1,\cdots,L-1$,$a_i$為整數且滿足$-2^ {31}\leq a_i<2^ {31}$且$a_i\neq 0$。
儘管如此,如果步道蓋成一座大山或一條深谷可就不好了。因此,這條步道中的任意連續$m$段路的平均高度必須比基準水平面低,同時任意連續$n$段路的平均高度必須比基準水平面高。

由於工人希望蓋長一點的步道,這樣才能多賺一點錢。所以請寫一支程式告訴工人們,滿足條件的步道最長能由幾段路組成,並輸出一個可行的方案。

Input Format

每筆測資只包含一行,含有兩個正整數$m,n\leq 10^ 6$。

子任務(測資) 額外限制 分數
1 (0~4) $m,n\leq 5$ 10
2 (0~9) $m,n \leq 100$ 40
3 (10~14) $m,n$互質 30
4 (0~19) 20

Output Format

請輸出兩行。
在第一行,請輸出一個非負整數$L$代表最長步道的長度。
在第二行,請輸出$L$個非零整數,代表一種可行的方案。請照$a_0,\cdots,a_{L-1}$的順序輸出。

Sample Input 1

3 1

Sample Output 1

2
1 1

Sample Input 2

7 11

Sample Output 2

16
5 5 -13 5 5 5 -13 5 5 -13 5 5 5 -13 5 5

Hints

Problem Source

Problem by Paupière
Description by Yihda Yol
改編自1977 IMO P2/1992 APMO P5

Subtasks

No. Testdata Range Score
1 0~4 10
2 0~9 40
3 10~14 30
4 0~19 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2 4
1 1000 65536 262144 1 2 4
2 1000 65536 262144 1 2 4
3 1000 65536 262144 1 2 4
4 1000 65536 262144 1 2 4
5 1000 65536 262144 2 4
6 1000 65536 262144 2 4
7 1000 65536 262144 2 4
8 1000 65536 262144 2 4
9 1000 65536 262144 2 4
10 1000 65536 262144 3 4
11 1000 65536 262144 3 4
12 1000 65536 262144 3 4
13 1000 65536 262144 3 4
14 1000 65536 262144 3 4
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4