웹 프론트엔드 HTML 튜토리얼 Codeforces Round #275 (Div. 1)C(状压+期望)_html/css_WEB-ITnose

Codeforces Round #275 (Div. 1)C(状压+期望)_html/css_WEB-ITnose

Jun 24, 2016 am 11:54 AM

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으로 문의하세요.

    핫 AI 도구

    Undresser.AI Undress

    Undresser.AI Undress

    사실적인 누드 사진을 만들기 위한 AI 기반 앱

    AI Clothes Remover

    AI Clothes Remover

    사진에서 옷을 제거하는 온라인 AI 도구입니다.

    Undress AI Tool

    Undress AI Tool

    무료로 이미지를 벗다

    Clothoff.io

    Clothoff.io

    AI 옷 제거제

    AI Hentai Generator

    AI Hentai Generator

    AI Hentai를 무료로 생성하십시오.

    뜨거운 도구

    메모장++7.3.1

    메모장++7.3.1

    사용하기 쉬운 무료 코드 편집기

    SublimeText3 중국어 버전

    SublimeText3 중국어 버전

    중국어 버전, 사용하기 매우 쉽습니다.

    스튜디오 13.0.1 보내기

    스튜디오 13.0.1 보내기

    강력한 PHP 통합 개발 환경

    드림위버 CS6

    드림위버 CS6

    시각적 웹 개발 도구

    SublimeText3 Mac 버전

    SublimeText3 Mac 버전

    신 수준의 코드 편집 소프트웨어(SublimeText3)

    공식 계정 웹 페이지의 캐싱 업데이트에 어려움 : 버전 업데이트 후 사용자 경험에 영향을 미치는 이전 캐시를 피하는 방법은 무엇입니까? 공식 계정 웹 페이지의 캐싱 업데이트에 어려움 : 버전 업데이트 후 사용자 경험에 영향을 미치는 이전 캐시를 피하는 방법은 무엇입니까? Mar 04, 2025 pm 12:32 PM

    공식 계정 웹 페이지 업데이트 캐시, 이것은 간단하고 간단하며 냄비를 마시기에 충분히 복잡합니다. 공식 계정 기사를 업데이트하기 위해 열심히 노력했지만 사용자는 여전히 기존 버전을 열었습니까? 이 기사에서는이 뒤에있는 비틀기와 회전을 살펴 보고이 문제를 우아하게 해결하는 방법을 살펴 보겠습니다. 읽은 후에는 다양한 캐싱 문제를 쉽게 처리 할 수있어 사용자가 항상 가장 신선한 콘텐츠를 경험할 수 있습니다. 기본 사항에 대해 먼저 이야기 해 봅시다. 액세스 속도를 향상시키기 위해 브라우저 또는 서버는 일부 정적 리소스 (예 : 그림, CSS, JS) 또는 페이지 컨텐츠를 저장합니다. 다음에 액세스 할 때 다시 다운로드하지 않고도 캐시에서 직접 검색 할 수 있으며 자연스럽게 빠릅니다. 그러나 이것은 또한 양날의 검입니다. 새 버전은 온라인입니다.

    HTML5 양식 유효성 검사 속성을 사용하여 사용자 입력을 유효성있게하려면 어떻게합니까? HTML5 양식 유효성 검사 속성을 사용하여 사용자 입력을 유효성있게하려면 어떻게합니까? Mar 17, 2025 pm 12:27 PM

    이 기사에서는 브라우저에서 직접 사용자 입력을 검증하기 위해 필요한, Pattern, Min, Max 및 Length 한계와 같은 HTML5 양식 검증 속성을 사용하는 것에 대해 설명합니다.

    HTML5의 크로스 브라우저 호환성에 대한 모범 사례는 무엇입니까? HTML5의 크로스 브라우저 호환성에 대한 모범 사례는 무엇입니까? Mar 17, 2025 pm 12:20 PM

    기사는 HTML5 크로스 브라우저 호환성을 보장하기위한 모범 사례에 대해 논의하고 기능 감지, 점진적 향상 및 테스트 방법에 중점을 둡니다.

    웹 페이지의 PNG 이미지에 뇌졸중 효과를 효율적으로 추가하는 방법은 무엇입니까? 웹 페이지의 PNG 이미지에 뇌졸중 효과를 효율적으로 추가하는 방법은 무엇입니까? Mar 04, 2025 pm 02:39 PM

    이 기사는 CSS를 사용한 웹 페이지에 효율적인 PNG 테두리 추가를 보여줍니다. CSS는 JavaScript 또는 라이브러리에 비해 우수한 성능을 제공하며, 미묘하거나 눈에 띄는 효과를 위해 테두리 너비, 스타일 및 색상 조정 방법을 자세히 설명합니다.

    & lt; datalist & gt의 목적은 무엇입니까? 요소? & lt; datalist & gt의 목적은 무엇입니까? 요소? Mar 21, 2025 pm 12:33 PM

    이 기사는 HTML & LT; Datalist & GT에 대해 논의합니다. 자동 완성 제안을 제공하고, 사용자 경험을 향상시키고, 오류를 줄임으로써 양식을 향상시키는 요소. 문자 수 : 159

    & lt; Progress & Gt의 목적은 무엇입니까? 요소? & lt; Progress & Gt의 목적은 무엇입니까? 요소? Mar 21, 2025 pm 12:34 PM

    이 기사는 HTML & lt; Progress & Gt에 대해 설명합니다. 요소, 그 목적, 스타일 및 & lt; meter & gt의 차이; 요소. 주요 초점은 & lt; progress & gt; 작업 완료 및 & lt; meter & gt; Stati의 경우

    html5 & lt; time & gt; 의미 적으로 날짜와 시간을 나타내는 요소? html5 & lt; time & gt; 의미 적으로 날짜와 시간을 나타내는 요소? Mar 12, 2025 pm 04:05 PM

    이 기사는 html5 & lt; time & gt; 시맨틱 날짜/시간 표현 요소. 인간이 읽을 수있는 텍스트와 함께 기계 가독성 (ISO 8601 형식)에 대한 DateTime 속성의 중요성을 강조하여 Accessibilit를 향상시킵니다.

    & lt; meter & gt의 목적은 무엇입니까? 요소? & lt; meter & gt의 목적은 무엇입니까? 요소? Mar 21, 2025 pm 12:35 PM

    이 기사는 HTML & lt; meter & gt에 대해 설명합니다. 범위 내에 스칼라 또는 분수 값을 표시하는 데 사용되는 요소 및 웹 개발의 일반적인 응용 프로그램. & lt; meter & gt; & lt; Progress & Gt; 그리고 Ex

    See all articles