考慮一個由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 | 304 | 2022-12-01 14:32 |