搜索
首页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
    > gt;的目的是什么 元素?> gt;的目的是什么 元素?Mar 21, 2025 pm 12:34 PM

    本文讨论了HTML< Progress>元素,其目的,样式和与< meter>元素。主要重点是使用< progress>为了完成任务和LT;仪表>对于stati

    < datalist>的目的是什么。 元素?< datalist>的目的是什么。 元素?Mar 21, 2025 pm 12:33 PM

    本文讨论了html< datalist>元素,通过提供自动完整建议,改善用户体验并减少错误来增强表格。Character计数:159

    < meter>的目的是什么。 元素?< meter>的目的是什么。 元素?Mar 21, 2025 pm 12:35 PM

    本文讨论了HTML< meter>元素,用于在一个范围内显示标量或分数值及其在Web开发中的常见应用。它区分了< meter>从< progress>和前

    HTML5中跨浏览器兼容性的最佳实践是什么?HTML5中跨浏览器兼容性的最佳实践是什么?Mar 17, 2025 pm 12:20 PM

    文章讨论了确保HTML5跨浏览器兼容性的最佳实践,重点是特征检测,进行性增强和测试方法。

    如何使用HTML5表单验证属性来验证用户输入?如何使用HTML5表单验证属性来验证用户输入?Mar 17, 2025 pm 12:27 PM

    本文讨论了使用HTML5表单验证属性,例如必需的,图案,最小,最大和长度限制,以直接在浏览器中验证用户输入。

    视口元标签是什么?为什么对响应式设计很重要?视口元标签是什么?为什么对响应式设计很重要?Mar 20, 2025 pm 05:56 PM

    本文讨论了视口元标签,这对于移动设备上的响应式Web设计至关重要。它解释了如何正确使用确保最佳的内容缩放和用户交互,而滥用可能会导致设计和可访问性问题。

    我如何使用html5< time> 元素以语义表示日期和时间?我如何使用html5< time> 元素以语义表示日期和时间?Mar 12, 2025 pm 04:05 PM

    本文解释了HTML5< time>语义日期/时间表示的元素。 它强调了DateTime属性对机器可读性(ISO 8601格式)的重要性,并在人类可读文本旁边,增强Accessibilit

    < iframe>的目的是什么。 标签?使用时的安全考虑是什么?< iframe>的目的是什么。 标签?使用时的安全考虑是什么?Mar 20, 2025 pm 06:05 PM

    本文讨论了< iframe>将外部内容嵌入网页,其常见用途,安全风险以及诸如对象标签和API等替代方案的目的。

    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.能量晶体解释及其做什么(黄色晶体)
    3 周前By尊渡假赌尊渡假赌尊渡假赌
    R.E.P.O.最佳图形设置
    3 周前By尊渡假赌尊渡假赌尊渡假赌
    R.E.P.O.如果您听不到任何人,如何修复音频
    3 周前By尊渡假赌尊渡假赌尊渡假赌
    WWE 2K25:如何解锁Myrise中的所有内容
    3 周前By尊渡假赌尊渡假赌尊渡假赌

    热工具

    SublimeText3 英文版

    SublimeText3 英文版

    推荐:为Win版本,支持代码提示!

    SublimeText3汉化版

    SublimeText3汉化版

    中文版,非常好用

    WebStorm Mac版

    WebStorm Mac版

    好用的JavaScript开发工具

    SublimeText3 Mac版

    SublimeText3 Mac版

    神级代码编辑软件(SublimeText3)

    SublimeText3 Linux新版

    SublimeText3 Linux新版

    SublimeText3 Linux最新版