PKU 2794 - Double Patience

Autor da análise: tmadeiratmadeira

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2794

Resumo

Dadas nove pilhas de quatro cartas, repetidamente retiram-se aleatoriamente dos seus topos duas cartas que possuem o mesmo valor, até que não seja mais possível retirar cartas. O problema consiste em determinar a probabilidade de todas as pilhas ficarem vazias.

Solução

Ignoremos eficiência. Dado um estado (e.g., $E = (4, 4, 4, 4, 4, 4, 4, 4, 4)$ significando que todas as pilhas estão com 4 cartas), a solução óbvia (força bruta) é remover (um por vez) todos os $p$ pares que podem ser removidos com as pilhas no estado atual. Com o estado com que sobra resolvemos novamente este problema (recursivamente), e assim sucessivamente, até chegarmos num estado que não tem pares para serem retirados. Neste caso, a função deve retornar 1 se todas as pilhas estão vazias (i.e., o estado é $(0, 0, 0, 0, 0, 0, 0, 0, 0)$) ou 0 caso contrário. Na volta da recursão, basta somar as probabilidades multiplicadas por $\frac{1}{p}$ e retornar esta soma.

Embora esta solução estoure o tempo limite, é fácil ver que estamos resolvendo subproblemas (estados iguais), o que nos motiva a memorizar os resultados. Como são menos de $5^9$ possíveis estados (i.e., cada uma das pilhas pode já ter perdido 0, 1, 2, 3 ou 4 cartas), se memorizarmos os valores das probabilidades dos estados já resolvidos e implementarmos o resto exatamente como na solução de força bruta, o problema passa tranquilamente.

A parte mais chata é implementar uma matriz de marcação de nove dimensões, mas fora detalhes de implementação o problema não parece ter sutileza alguma.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License