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:
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]就是答案,即起点

핫 AI 도구

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

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

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

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

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

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

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

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

뜨거운 주제











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

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

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

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

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

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

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

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