c893: 3. 平均變異次數
標籤 :
通過比率 : 7人/9人 ( 78% ) [非即時]
評分方式:
Special

最近更新 : 2019-01-24 17:16

內容

考慮一個由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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (1%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (1%): 1.0s , <1K
公開 測資點#3 (1%): 1.0s , <1K
公開 測資點#4 (1%): 1.0s , <1K
公開 測資點#5 (11%): 1.0s , <1K
公開 測資點#6 (1%): 1.0s , <1K
公開 測資點#7 (1%): 1.0s , <1K
公開 測資點#8 (1%): 1.0s , <1K
公開 測資點#9 (1%): 1.0s , <1K
公開 測資點#10 (19%): 1.0s , <1K
公開 測資點#11 (1%): 1.0s , <1K
公開 測資點#12 (1%): 1.0s , <1K
公開 測資點#13 (1%): 1.0s , <1K
公開 測資點#14 (1%): 1.0s , <1K
公開 測資點#15 (53%): 1.0s , <1M
公開 測資點#16 (1%): 1.0s , <1K
公開 測資點#17 (1%): 1.0s , <1K
公開 測資點#18 (1%): 1.0s , <1K
公開 測資點#19 (1%): 1.0s , <1M
提示 :

本題共有四個子題,每一子題有多筆測資:

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

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

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

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

標籤:
出處:
107學年度全國資訊學科能力競賽 [編輯:
icube (輸光光)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」