搜尋
首頁web前端html教學Codeforces Round #275 (Div. 1)C(状压+期望)_html/css_WEB-ITnose

C. Game with Strings

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You play the game with your friend. The description of this game is listed below.

Your friend creates n distinct strings of the same length m and tells you all the strings. Then he randomly chooses one of them. He chooses strings equiprobably, i.e. the probability of choosing each of the n strings equals . You want to guess which string was chosen by your friend.

In order to guess what string your friend has chosen, you are allowed to ask him questions. Each question has the following form: «What character stands on position pos in the string you have chosen?» A string is considered guessed when the answers to the given questions uniquely identify the string. After the string is guessed, you stop asking questions.

You do not have a particular strategy, so as each question you equiprobably ask about a position that hasn't been yet mentioned. Your task is to determine the expected number of questions needed to guess the string chosen by your friend.

Input

The first line contains a single integer n (1?≤?n?≤?50) ? the number of strings your friend came up with.

The next n lines contain the strings that your friend has created. It is guaranteed that all the strings are distinct and only consist of large and small English letters. Besides, the lengths of all strings are the same and are between 1 to 20 inclusive.

Output

Print the single number ? the expected value. Your answer will be considered correct if its absolute or relative error doesn't exceed 10?-?9.

Sample test(s)

input

2aabaac

output

2.000000000000000

input

3aaAaBaCaa

output

1.666666666666667

input

3acavacwqq

output

1.000000000000000

Note

In the first sample the strings only differ in the character in the third position. So only the following situations are possible:

  • you guess the string in one question. The event's probability is ;
  • you guess the string in two questions. The event's probability is  ·  =  (as in this case the first question should ask about the position that is other than the third one);
  • you guess the string in three questions. The event's probability is  ·  ·  = ;
  • Thus, the expected value is equal to 

    In the second sample we need at most two questions as any pair of questions uniquely identifies the string. So the expected number of questions is .

    In the third sample whatever position we ask about in the first question, we immediately identify the string.


    题意:RT


    思路:f[s]表示s二进制状态下,s里面1的数量是已经猜过的位置的字符,0表示还没有猜的


                转移情况为:f[s]由任何的0转移过来,这个过程其实是逆向的,从终点推向起点


                设s的下一步状态为p,即p一定比s多一个1,那么f[s]=1/d∑( m/n*1 + f[p] )  其中d为s的下一步的状态数,


                m为当前s状态的合法字符串数,n为总的字符串,f[p]为下一个状态的期望


                最后f[0]就是答案,即起点


    陳述
    本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
    HTML:結構,CSS:樣式,JavaScript:行為HTML:結構,CSS:樣式,JavaScript:行為Apr 18, 2025 am 12:09 AM

    HTML、CSS和JavaScript在Web開發中的作用分別是:1.HTML定義網頁結構,2.CSS控製網頁樣式,3.JavaScript添加動態行為。它們共同構建了現代網站的框架、美觀和交互性。

    HTML的未來:網絡設計的發展和趨勢HTML的未來:網絡設計的發展和趨勢Apr 17, 2025 am 12:12 AM

    HTML的未來充滿了無限可能。 1)新功能和標準將包括更多的語義化標籤和WebComponents的普及。 2)網頁設計趨勢將繼續向響應式和無障礙設計發展。 3)性能優化將通過響應式圖片加載和延遲加載技術提升用戶體驗。

    HTML與CSS vs. JavaScript:比較概述HTML與CSS vs. JavaScript:比較概述Apr 16, 2025 am 12:04 AM

    HTML、CSS和JavaScript在網頁開發中的角色分別是:HTML負責內容結構,CSS負責樣式,JavaScript負責動態行為。 1.HTML通過標籤定義網頁結構和內容,確保語義化。 2.CSS通過選擇器和屬性控製網頁樣式,使其美觀易讀。 3.JavaScript通過腳本控製網頁行為,實現動態和交互功能。

    HTML:是編程語言還是其他?HTML:是編程語言還是其他?Apr 15, 2025 am 12:13 AM

    HTMLISNOTAPROGRAMMENGUAGE; ITISAMARKUMARKUPLAGUAGE.1)htmlStructures andFormatSwebContentusingtags.2)itworkswithcsssforstylingandjavascript for Interactivity,增強WebevebDevelopment。

    HTML:建立網頁的結構HTML:建立網頁的結構Apr 14, 2025 am 12:14 AM

    HTML是構建網頁結構的基石。 1.HTML定義內容結構和語義,使用、、等標籤。 2.提供語義化標記,如、、等,提升SEO效果。 3.通過標籤實現用戶交互,需注意表單驗證。 4.使用、等高級元素結合JavaScript實現動態效果。 5.常見錯誤包括標籤未閉合和屬性值未加引號,需使用驗證工具。 6.優化策略包括減少HTTP請求、壓縮HTML、使用語義化標籤等。

    從文本到網站:HTML的力量從文本到網站:HTML的力量Apr 13, 2025 am 12:07 AM

    HTML是一種用於構建網頁的語言,通過標籤和屬性定義網頁結構和內容。 1)HTML通過標籤組織文檔結構,如、。 2)瀏覽器解析HTML構建DOM並渲染網頁。 3)HTML5的新特性如、、增強了多媒體功能。 4)常見錯誤包括標籤未閉合和屬性值未加引號。 5)優化建議包括使用語義化標籤和減少文件大小。

    了解HTML,CSS和JavaScript:初學者指南了解HTML,CSS和JavaScript:初學者指南Apr 12, 2025 am 12:02 AM

    WebDevelovermentReliesonHtml,CSS和JavaScript:1)HTMLStructuresContent,2)CSSStyleSIT和3)JavaScriptAddSstractivity,形成thebasisofmodernWebemodernWebExexperiences。

    HTML的角色:構建Web內容HTML的角色:構建Web內容Apr 11, 2025 am 12:12 AM

    HTML的作用是通過標籤和屬性定義網頁的結構和內容。 1.HTML通過到、等標籤組織內容,使其易於閱讀和理解。 2.使用語義化標籤如、等增強可訪問性和SEO。 3.優化HTML代碼可以提高網頁加載速度和用戶體驗。

    See all articles

    熱AI工具

    Undresser.AI Undress

    Undresser.AI Undress

    人工智慧驅動的應用程序,用於創建逼真的裸體照片

    AI Clothes Remover

    AI Clothes Remover

    用於從照片中去除衣服的線上人工智慧工具。

    Undress AI Tool

    Undress AI Tool

    免費脫衣圖片

    Clothoff.io

    Clothoff.io

    AI脫衣器

    AI Hentai Generator

    AI Hentai Generator

    免費產生 AI 無盡。

    熱門文章

    R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
    1 個月前By尊渡假赌尊渡假赌尊渡假赌
    R.E.P.O.最佳圖形設置
    1 個月前By尊渡假赌尊渡假赌尊渡假赌
    威爾R.E.P.O.有交叉遊戲嗎?
    1 個月前By尊渡假赌尊渡假赌尊渡假赌

    熱工具

    SublimeText3 Linux新版

    SublimeText3 Linux新版

    SublimeText3 Linux最新版

    EditPlus 中文破解版

    EditPlus 中文破解版

    體積小,語法高亮,不支援程式碼提示功能

    PhpStorm Mac 版本

    PhpStorm Mac 版本

    最新(2018.2.1 )專業的PHP整合開發工具

    MinGW - Minimalist GNU for Windows

    MinGW - Minimalist GNU for Windows

    這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

    ZendStudio 13.5.1 Mac

    ZendStudio 13.5.1 Mac

    強大的PHP整合開發環境