考慮一個由K種相異字元所構成且長度為N的字串S。假設第i種相異字元出現C[i]次，故C[1] +… + C[K] = N。因字元出現的順序不同，這樣的字串將會有很多個，對一個這樣的字串S我們想知道從S[1]到S[N]有幾個位子i (1≤ i < N)，使得S[i] 與S[i+1]相異，我們定義一字串相異位子的個數為“變異次數”。例如：字串“aab”的變異次數為1；字串“aba”的變異次數為2；字串“baa”的變異次數則為1。故對K=2, N=3, C[1]=2, C[2]=1，其平均變異次數為4/3=1.3333…
給定N, K以及C[1],…,C[K]，請寫一程式計算所有可能的字串的平均變異次數。
每筆測資共有2行，第1行為兩個以空白隔開的正整數N和K，第2行為K個以空白隔開的正整數C[1], C[2],…, C[K]，其中每一正整數小於等於1000。
針對每筆測資，輸出平均變異次數。與答案之絕對誤差小於 0.001 者即視為正確。
為列印小數點下固定位數的浮點數answer，C++可使用下列方法印至第三位：
#include <iomanip>
cout << fixed;
cout << setprecision(3) << answer << endl;
C可使用下列方法印至第三位：
#include <stdio.h>
printf("%.3f\n", answer);
Java可使用下列方法印至第三位：
System.out.printf("%.3f\n", answer);
輸入範例 1： 3 2 1 2 輸入範例 2： 10 2 5 5 輸入範例 3： 20 3 11 8 1
輸出範例 1： 1.333 輸出範例 2： 5.000 輸出範例 3： 10.700
本題共有四個子題，每一子題有多筆測資：
第一子題，K = 2，C[1]=1, N ≤ 10，全部解出可得5分；
第二子題，K = 2，N ≤ 20，全部解出可得15分；
第三子題，K ≤ 20，N ≤ 100，全部解出可得23分；
第四子題，K ≤ N ≤ 1000，全部解出可得57分。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 33109 | coffee5427 (unknown) | c893 | 293 | 2022-12-01 14:32 |