413 - Up and Down Sequences

本題請你判斷一個序列中的「上升子序列」與「下降子序列」。

序列中的「上升子序列」定義為每一個連續出現的數值皆不小於前一個數值，上升子序列結束於出現較小的數值為止。

序列中的「下降子序列」定義為每一個連續出現的數值皆不大於前一個數值，下降子序列結束於出現較大的數值為止。

上升子序列可接在下降子序列之後，反之亦然。

在一連串相等的數值出現之後，出現上升或下降的趨勢，則前面那段相等的數值亦被視為上升或下降子序列的一部份，例如2 2 2 2 3為長度為4的上升子序列；4 4 4 4 3為長度為4的下降子序列。

若序列看不出其上升或下降的趨勢，則被視為不符合這兩種情況。

請對每組測試資料輸出其「上升子序列」與「下降子序列」的平均長度。

Input

每組測試資料一列，每一列有1~30個無符號非零整數，每個整數最少一個位數，最多四個位數，並以一個空白字元隔開，每列最後以一個0表示該列結束，最後的0並不視為序列的一部份。
當該列只有一個整數，且其值為0時，表示測試資料結束。

Output

每組輸出資料的格式為"Nr values = N:  AVG1 AVG2"，其中N表示該列整數的個數，AVG1表示「上升子序列」的平均長度，AVG2表示「下降子序列」的平均長度，請輸出到小數點後六位。

Sample Input

1 2 3 0
3 2 1 0
1 2 3 2 1 0
2 2 2 2 3 0
4 4 4 4 3 0
4 4 4 3 3 3 3 0
4 4 4 3 3 3 4 0
5 5 5 5 0
1 2 3 2 3 4 5 0
0

Sample Output (Your output, using your chosen language, may be default-formatted differently).

Nr values = 3:  2.000000 0.000000
Nr values = 3:  0.000000 2.000000
Nr values = 5:  2.000000 2.000000
Nr values = 5:  4.000000 0.000000
Nr values = 5:  0.000000 4.000000
Nr values = 7:  0.000000 6.000000
Nr values = 7:  1.000000 5.000000
Nr values = 4:  0.000000 0.000000
Nr values = 7:  2.500000 1.000000

原文出處