\documentclass[10pt]{article}

%% Escrevendo em português
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}

\usepackage[colorlinks,backref]{hyperref} 

\usepackage{fullpage}

%% Tamanho da página
%\setlength{\textwidth}{17cm}
%\setlength{\textheight}{24cm}

%% Parágrafo
%\setlength{\parindent}{5mm}
%\setlength{\parskip}{1mm}

%% Empurra para cá empurra para lá
%\evensidemargin -0.3cm
%\oddsidemargin -0.3cm
%\topmargin -0.7in

\newcommand{\ymoldura}[1]{{\noindent\fbox{\parbox[t]{10cm}{ #1 }} \vspace*{.5cm}\\}}
\newcommand{\moldura}[1]{{\noindent\fbox{\parbox[t]{15.75cm}{ #1 }} \vspace*{.5cm}\\}}
\newcommand{\dmoldura}[1]{{\noindent\fbox{\fbox{\parbox[t]{11.0cm}{ #1 }}}\vspace*{.5cm}}}

\def\nl {\medskip \noindent} %\smallskip\noindent}

\pagestyle{empty}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%\null\bigskip\bigskip
\hfill {\small Departamento de Ciência da Computação -- IME-USP}


\begin{center}
  \textbf{\large MAC 115 -- Introdução à Ciência da Computação}

  \smallskip

  \textsc{Instituto de Física - Segundo Semestre de 2005}
\end{center}

\noindent
Primeiro Exercício-Programa (EP1)\hfill 
Entregue até 2/10/2005, pelo
\href{http://panda2.arca.ime.usp.br/panda/index.html}{Panda}

\bigskip
\bigskip

\begin{center}
\dmoldura{
\centerline {\phantom{a} }
\centerline{\bf {\Large {\sc ~  Um jogo de sorte (azar?)~ }}}
\centerline{\phantom{a}}
}
\end{center}

%\vspace{2ex}

\noindent  
Neste jogo, dois jogadores, Alice e Beto, escolhem cada um um padrão de
{\tt0}s e {\tt1}s, de mesmo comprimento.  Daí, joga-se uma moeda honesta até
um dos padrões aparecer (digamos, {\tt0} significa coroa e {\tt1} significa
cara).  Por exemplo: suponha que o padrão de Alice é {\tt1011} e o padrão de
Beto é {\tt0110}.  Suponha que, ao lançarmos a nossa moeda várias vezes,
obtemos
$$
{\tt100100111001010100110...}
$$
(Isto é, cara, coroa, coroa, cara, coroa, etc.)  Então Beto ganhou, já
que o padrão dele apareceu antes do padrão de Alice.  

Para simular a moeda, voce deve usar as funções \texttt{rand()} e
\texttt{srand()}, como neste exemplo: {\small
\begin{verbatim}
#include <stdio.h>
#include <stdlib.h>
int main()
{ int N, i, semente;
  scanf("%d %d", &N, &semente);
  srand(semente);
  for (i=0; i<N; i++) printf("%d", rand()%2);
  printf("\n");
  return 0;
}
\end{verbatim}
}

Por simplicidade, consideraremos apenas os seguintes padrões:
$$
a_n=(1100)^n\qquad b_n=(1001)^n\qquad
c_n=(0011)^n\qquad d_n=(0110)^n,
$$
onde nossa convenção é que $a_1=1100$, $a_2=11001100$, $a_3=110011001100$,
etc.

Nosso objetivo é estimar as seguintes quantidades, através de simulações.
Defina~$A_n$ como sendo o número esperado de lances de moeda necessários até
que ocorra o padrão~$a_n$.  Defina as quantidades~$B_n$, $C_n$, e~$D_n$
analogamente.  Podemos estimar~$A_n$ para qualquer~$n$ fixo, simulando lances
de moeda usando \texttt{rand()} até que o padrão em questão ocorra pela
primeira vez.  Naturalmente, podemos repetir este processo um número~$M$ de
vezes.  Se na $i$-ésima vez foram necessários~$N_i$ lances da moeda para o
padrão~$a_n$ ocorrer, então podemos estimar~$A_n$ pela média dos~$N_i$, isto
é, podemos estimar~$A_n$ por~$M^{-1}\sum_{1\leq i\leq M}N_i$.

Naturalmente, podemos da mesma forma obter estimativas para~$B_n$, $C_n$,
e~$D_n$.  Note que estas estimativas vão ser melhores para valores maiores
de~$M$.  A primeira parte de seu programa deve receber como entrada inteiros
positivos~$n$ e~$M$ e uma semente~$s$.  Seu programa deve então estimar~$A_n$,
$B_n$, $C_n$, e~$D_n$, como descrito acima.

A segunda parte de seu programa deve estimar a probabilidade de Alice vencer o
jogo se Alice escolhe um dos quatro padrões acima e Beto escolhe um outro
padrão.  Seu programa deve estimar esta probabilidade para os pares 
$$
(a_n,b_n),\qquad(b_n,c_n),\qquad(c_n,d_n),\qquad(d_n,a_n).
$$
Isto é, Alice escolhe~$a_n$ e Beto escolhe~$b_n$ em um jogo, Alice
escolhe~$b_n$ e Beto escolhe~$c_n$ no segundo jogo, etc; há portanto quatro
probabilidades que seu programa deve estimar.  Denotemos por~$p_1$, $p_2$,
$p_3$, e~$p_4$ estas quatro probabilidades, respectivamente.  Para
estimar~$p_1,\dots,p_4$, seu programa deve simular o jogo~$M$ vezes para cada
par, onde~$M$ é também dado pelo usuário.

\subsection*{Entrada}
A entrada será formada pelos inteiros positivos~$n$, $M$, e~$s$ ($s$~deve ser
usado como a semente de \texttt{rand()}, através da chamada
\texttt{srand(s)}). 

\subsection*{Saída}
A saída deve ser constituída de suas estimativas para~$A_n$, $B_n$, $C_n$,
$D_n$, $p_1$, $p_2$, $p_3$, e~$p_4$.

\subsection*{Observação}
Se você notar que alguns dos~$A_n,B_n,\dots,p_1,p_2,\dots$ coincidem, você
pode diminuir o número de valores a serem estimados.  (Por exemplo, como se
comparam~$A_n$ e~$C_n$?)

% \subsection*{Exemplo}

% \subsubsection*{Entrada}
% \begin{verbatim}
% 1 10
% 100 200
% 201 210
% 900 1000
% \end{verbatim}

% \subsubsection*{Saída}
% \begin{verbatim}
% 1 10 20
% 100 200 125
% 201 210 89
% 900 1000 174
% \end{verbatim}

% \newpage

\bigskip
\begin{center}
  \underline{\Large \sc Observações Importantes sobre os Exercícios-Programas}
\end{center}

\smallskip

%\footnotesize

Todos os exercícios-programas devem ter o seguinte cabeçalho:

\begin{verbatim}
           /********************************************************/
           /* Fulano de Tal                                        */
           /* Exercicio-Programa xx                                */
           /* Curso yy  - Turma zz  -- Professor:  Ciclano de Tal  */
           /* Computador: .....                                    */
           /* Compilador: .....                                    */
           /********************************************************/
\end{verbatim}

\begin{enumerate}

\item O exercício-programa é \textbf{estritamente individual}. Exercícios
  copiados (com ou sem eventuais disfarces) receberão\ nota ZERO.


\item \textbf{Exercícios atrasados não serão aceitos.}

 \item  Exerc\'\i cios com erros de sintaxe (ou seja, erros de compilação)
 receberão nota ZERO.


\item  É \textbf{muito importante} que seu programa tenha comentários e
   esteja bem indentado, ou seja,
  digitado de maneira a ressaltar a estrutura de subordinação dos comandos
  do programa (conforme visto em aula).  A avaliação dos
  exercícios-programas levará isto em conta. 
  
% \item Cada programa deve ser executado tantas vezes quantas forem necessárias
%   para testar todos os casos possíveis para as entradas.  Você pode dizer no
%   seu programa (em comentários), quais dados você usou para testar seu
%   programa.  \textit{A escolha desses dados também influirá na sua nota.}
  
\item  Guarde com voc\^e at\'e o final do semestre, em seus
  disquetes, os arquivos de seus programas, pois eles podem ser
  solicitados pelo professor caso surja alguma d\'uvida. 

\item  Entregue o seu programa pelo sistema
  \href{http://panda2.arca.ime.usp.br/panda/index.html}{Panda}. 

\end{enumerate}


\end{document}


