\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 323 -- Estruturas de Dados}
\end{center}

\begin{center}
{\bf Primeiro semestre de 1999}
\end{center}

\begin{center}
{\large  Exercício-Programa 1 -- Entrega: {\bf 5 de abril de 1999}}

\vspace{0.3cm}
Jogo de paci\^encia
\end{center}


O objetivo desse exerc\'\i cio--programa \'e simular um jogo de paci\^encia
que descrevemos a seguir. Esse jogo \'e jogado com apenas 1 baralho
(52 cartas). Distribuem-se 28 dessas cartas em 7 pilhas de jogo da seguinte
forma: coloque uma carta em cada pilha de jogo da esquerda para a direita,
tal que na i-\'esima passada voc\^e come\c ca na i-\'esima pilha colocando 
uma carta aberta e todas as outras cartas ficam fechadas. As demais 
cartas ficam na chamada {\em pilha de estoque}. Ainda existe uma {\em pilha
de descarte} e 4 {\em pilhas de sa\'\i da}. O objetivo do jogo \'e 
conseguir o maior n\'umero poss\'\i vel de cartas nas pilhas de sa\'\i da. 

Nas pilhas de jogo voc\^e s\'o pode colocar cartas que formem uma 
seq\"u\^encia decrescente consecutiva e de cores alternadas. Assim, se o topo de uma
pilha de jogo \'e um 9 de espadas, voc\^e s\'o poder\'a colocar sobre 
ele um 8 de ouros ou um 8 de copas. Todas as cartas abertas de uma 
pilha de jogo podem ser removidas como uma unidade e colocadas em outra 
pilha de jogo, desde que se respeite a regra de a seq\"u\^encia ser 
decrescente e de cores alternadas. Por exemplo, a seq\"u\^encia 8 de copas, 
7 de paus e 6 de ouros pode ser movida como uma unidade e colocada na
pilha de jogo cujo topo \'e um 9 de paus.

Cada pilha de jogo deve ter sempre pelo menos uma carta aberta. Assim, 
se as cartas abertas forem removidas, a carta do topo deve ser aberta. Se
uma pilha de jogo ficar vazia, ela s\'o poder\'a ser reaberta por um 
Rei que esteja aberto em alguma pilha de jogo ou no topo da pilha de descarte.

Sempre que um \'As aparece no topo de uma pilha de jogo ou na pilha de 
descarte ele \'e transferido para uma das pilhas de sa\'\i da. Cada pilha de
sa\'\i da conter\'a as cartas de um naipe consecutivamente em ordem 
crescente. N\~ao \'e permitido remover as cartas das pilhas de sa\'\i da. 

As cartas da pilha de estoque s\'o podem ser removidas abertas para a 
pilha de descarte, uma de cada vez. Sempre que a pilha de descarte ficar 
vazia uma nova carta da pilha de estoque deve ser movida para l\'a. 

Observe que pode ocorrer que diversos movimentos s\~ao poss\'\i veis. 
Nesse caso, voc\^e deve desenvolver uma estrat\'egia que lhe pare\c ca 
trazer melhores chances de ganhar o jogo. O jogo termina quando nenhum 
movimento for poss\'\i vel e a pilha de estoque estiver vazia. 

Fa\c ca um programa que simule uma m\'aquina de jogar
paci\^encia como descrito acima, permitindo que diversos jogos possam ser
executados. Você deve permitir que o usuário entre com um baralho já
embaralhado (que será um arquivo com 52 linhas, em que cada uma contém uma
carta), ou deverá embaralhar aleatoriamente o baralho. 
Para voc\^es que n\~ao conhecem jogos, as cartas de um 
baralho est\~ao divididas em 4 naipes (ouros O, copas C-- que s\~ao vermelhos --
paus P e espadas E-- que s\~ao pretos). Para cada naipe existem 13 cartas: 
\'As, 2, 3, 4, 5, 6, 7, 8, 9, 10, J (valete), Q (dama) e K (rei). Escolha
uma implementa\c c\~ao mais eficiente poss\'\i vel para armazenar as cartas. O
formato do arquivo de entrada será dado por 52 linhas. Se a primeira linha for 
\texttt{10 O}, a primeira carta será um 10 de ouros. Se a segunda linha é
\texttt{K P}, a segunda carta será um rei de paus, e assim por diante. A
última carta do arquivo estará no topo do monte, e portanto será a primeira a
ser distribuída.  

TODAS AS PILHAS NECESS\'ARIAS PARA SEU PROGRAMA DEVEM SER ARMAZENADAS
EM UM \'UNICO VETOR COM 60 POSI\c C\~OES, e para o tratamento de 
overflow voc\^e deve usar o 
algoritmo de realoca\c c\~ao de tabelas seq\"uenciais, descrito no livro 
do Knuth, vol. I, pags. 245 e 246 (e explicado em sala de aula). 
Observe que devido ao tamanho m\'aximo do vetor, ocorrer\~ao muitas colis\~oes 
entre as pilhas, portanto, seu tratamento deve ser o mais eficiente 
poss\'\i vel. 

Voc\^e deve entregar um disquete contendo o programa fonte e
uma listagem do programa. A saída do seu programa deve ser clara, e você
deverá mostrar graficamente como o vetor está sendo ocupado e quantas colisões
estão ocorrendo. Obviamente seu programa dever\'a ser bem documentado,  
e a forma de utiliz\'a-lo tamb\'em ser\'a avaliada.

\noindent
{\bf Bônus:} Você poderá ganhar alguns bônus em sua nota neste EP. Qualquer
coisa que você implemente além do pedido no enunciado dá direito a um
bônus. Documente isso no seu programa. Aí vão algumas idéias: 
\begin{itemize}
\item Faça um programa que permita também ao usuário jogar; 
\item Implemente versões diferentes do jogo (como nas implementações
disponíveis no Windows). 
\end{itemize}
\end{document}