\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 1998}
\end{center}

\begin{center}
{\large  Exercício-Programa 1 -- Entrega: {\bf 24 de março de 1998}}

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

Neste exercício-programa vocês deverão simular um jogo de paciência que
descrevemos a seguir. O jogo é jogado com apenas um baralho (52 cartas). As
quatro primeiras cartas de paus (ás, 2, 3 e 4) são retiradas e colocadas
abertas nas pilhas de saída. As 48 cartas restantes são embaralhadas e
deixadas com as faces para baixo na pilha de entrada. Além das pilhas de
saída, existem 4 pilhas de jogo cuja função descrevemos a seguir. 

As pilhas de saída aceitam cartas de qualquer naipe, e em ordem crescente. A
primeira pilha (a do ás) cresce de um em um. A segunda, de dois em dois. A
terceira de três em três e a quarta de quatro em quatro. Assim, sobre o dois
de paus (segunda pilha) você pode colocar, por exemplo, o 4 de ouros. 
Sobre o 4 de paus (quarta pilha) você pode colocar o oito de espadas. O
objetivo do jogo é, no final, ter todas as 52 cartas nas pilhas de saída, que 
terão quatro reis nos topos. As contas são feitas
circularmente. Assim, sobre uma dama na terceira pilha poderá ser colocado 
um 2. 

Eventualmente uma carta da pilha de entrada não poderá ser colocada
imediatamente em qualquer uma das pilhas de saída. Para isso servem as 
pilhas de jogo. Esta
carta poderá ser colocada em qualquer uma delas. Os topos das pilhas de jogo
podem ser movidos, quando possível, para alguma pilha de saída. A estratégia
do jogo consiste em manipular bem essas pilhas de jogo. 

Cartas da pilha de entrada que servem em alguma pilha de saída podem, ainda
assim, ir para uma pilha de jogo, se você achar que isso é uma boa
estratégia. 

Quando todas as cartas da pilha de entrada forem utilizadas, e nenhuma das
cartas dos topos das pilhas de jogos puderem ser movimentadas para pilhas de
saída o jogo termina. 

Fa\c ca um programa (em C++, Delphi ou Java), que simule um jogo de 
paci\^encia como descrito acima, permitindo que diversos jogos possam ser
executados. Para voc\^es que n\~ao conhecem jogos, as cartas de um 
baralho est\~ao divididas em 4 naipes (ouros \Pisymbol{psy}{168}, copas
\Pisymbol{psy}{169},  
paus \Pisymbol{psy}{167} e espadas \Pisymbol{psy}{170}). Para cada naipe existem 13 cartas: 
A (ás -- 1), 2, 3, 4, 5, 6, 7, 8, 9, 10, J (valete -- 11), Q (dama -- 12) e K (rei --
13). Escolha uma implementa\c c\~ao mais eficiente poss\'\i vel 
para armazenar as cartas. 

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. 
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. Seu programa deve imprimir o conte\'udo das 
pilhas a cada jogada, assim como uma mensagem dizendo que movimento foi 
realizado. As pilhas de jogo DEVER\~AO ser impressas em forma de pilhas 
(uma ao lado da outra), e lembre-se de diferenciar as cartas abertas das 
fechadas. Obviamente seu programa dever\'a ser bem documentado, e a forma
de utiliz\'a-lo tamb\'em ser\'a avaliada. 

Quem quiser treinar um pouco do jogo antes de começar a programar poderá
testar a versão para Windows disponível na página do curso: 
\begin{quote}
{\tt http://www.ime.usp.br/$\sim$cef/mac323}
\end{quote}

Se você desejar, implemente uma versão que permite ao usuário jogar {\em on
line} o jogo (bônus na nota para os que fizerem). As melhores estratégias de
jogo serão recompensadas na nota!!

\end{document}