建康中學(簡稱建中)想要在校園中建設一條步道。由於建中是傳說中的「千湖中學」,為了展現其特色,這條步道必須要在下雨時積水。因此校方對工人下達了指令:每一段路和基準水平面都要有非零整數的高度差。具體來說:如果這條步道由$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$段路的平均高度必須比基準水平面高。
由於工人希望蓋長一點的步道,這樣才能多賺一點錢。所以請寫一支程式告訴工人們,滿足條件的步道最長能由幾段路組成,並輸出一個可行的方案。
每筆測資只包含一行,含有兩個正整數$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 |
請輸出兩行。
在第一行,請輸出一個非負整數$L$代表最長步道的長度。
在第二行,請輸出$L$個非零整數,代表一種可行的方案。請照$a_0,\cdots,a_{L-1}$的順序輸出。
Problem by Paupière
Description by Yihda Yol
改編自1977 IMO P2/1992 APMO P5
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 10 |
2 | 0~9 | 40 |
3 | 10~14 | 30 |
4 | 0~19 | 20 |