c893. 3. 平均變異次數 - 高中生程式解題系統

內容

考慮一個由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

輸入範例 1：
3 2
1 2

輸入範例 2：
10 2
5 5

輸入範例 3：
20 3
11 8 1

範例輸出 #1

輸出範例 1：
1.333

輸出範例 2：
5.000

輸出範例 3：
10.700

測資資訊：

記憶體限制： 512 MB

提示：

本題共有四個子題，每一子題有多筆測資：

第一子題，K = 2，C[1]=1, N ≤ 10，全部解出可得5分；

第二子題，K = 2，N ≤ 20，全部解出可得15分；

第三子題，K ≤ 20，N ≤ 100，全部解出可得23分；

第四子題，K ≤ N ≤ 1000，全部解出可得57分。

標籤:

出處:

107學年度全國資訊學科能力競賽 [管理者： icube (!@#$%^&*()_...) ]

編號	身分	題目	主題	人氣	發表日期
33109	coffee5427 (unknown)	c893	組合(期望值&機率)	291	2022-12-01 14:32