\documentclass[brazil]{article}

\usepackage[latin1]{inputenc}
\usepackage[portuguese]{babel}

\title{Prova\\ Algoritmos e Estruturas de Dados I}

\pagestyle{empty}	

\addtolength\textwidth{16mm}
\addtolength\textheight{2.2cm}
\addtolength\topmargin{-2.2cm}
\setlength{\parindent}{0pt}

\author{Prof.: Carlos Camar\~ao}
\date{13 de Dezembro de 2005}

\begin{document}

\maketitle
\thispagestyle{empty}

Em todas as quest\~oes, voc\^e pode supor a exist\^encia de m\'etodos
est\'aticos de entrada e sa\'{\i}da de valores de tipos básicos,
definidos em uma classe {\tt EntradaPadr\~ao}. Por exemplo, para ler
inteiros, voc\^e pode usar {\tt EntradaPadr\~ao.l\^eInteiro()}. Esse
método lê um inteiro do dispositivo de entrada padrão e retorna o
valor lido, de tipo {\tt int}.

\vspace*{\baselineskip}

{\bf 1.} (6 pontos) Escreva um programa que leia um valor inteiro
positivo $n$, calcule o valor dado por $\sum_{i=1}^n (-i+1)/(3*i)$, e
imprima esse valor.  Decomponha o seu programa em tr\^es partes, cada
uma delas implementada por um m\'etodo: leitura, c\'alculo do valor
desejado a partir do valor lido, e impress\~ao do valor calculado.

O programa deve tratar a exce\c{c}\~ao que ocorre quando a cadeia de
caracteres lida não representa um n\'umero inteiro, informando o
usuário com uma mensagem apropriada e realizando a operação de leitura
novamente.

A operação de divisão não pode ser uma ``divisão inteira'' (não pode
ter como parâmetros dois números inteiros), mas sim uma divisão de
números de ponto flutuante (i.e.~deve ser realizada depois de
converter pelo menos um dos números inteiros para um número de ponto
flutuante).

\vspace*{\baselineskip}

{\bf 2.} (9 pontos) Uma opera\c{c}\~ao de {\em contra\c{c}\~ao de uma
lista\/} \'e definida como sendo tal que, dados um inteiro positivo
$i$, chamado de {\it \'{\i}ndice\/} da contra\c{c}\~ao, e uma lista de
$n$ n\'umeros inteiros $x = [a_0, a_1,\ldots, a_i,\ldots, a_{n-1}]$,
onde sup\~oe-se $0 \leq i < n-1$, retorna como resultado a lista
$[a_0, \ldots, a_{i-1}, a_i-a_{i+1}, a_{i+2},\ldots, a_{n-1}]$.

Aplicando $n-1$ contra\c{c}\~oes a uma lista de $n$ inteiros quaisquer
obt\'em-se uma lista com um \'unico inteiro, chamado de {\em valor
alvo\/}. Por exemplo, se chamarmos de {\it con\/} a opera\c{c}\~ao de
contra\c{c}\~ao e por $con(x,i)$ a opera\c{c}\~ao de aplicar {\it
con\/} a uma lista {\it x} e a um \'{\i}ndice $i$, temos:

  \[ \begin{array}{rcl}
       con([12,10,4,3,5],1) & = & [12,6,3,5] \\
       con([12,6,3,5],2)    & = & [12,6,-2]\\
       con([12,6,-2],1)     & = & [12,8]\\
       con([12,8],0)        & = & [4]
     \end{array}
  \]

Fa\c{c}a um programa que:

\begin{itemize}

\item leia um valor inteiro positivo $n$ (o n\'umero de inteiros da
seq\"u\^encia original), $n$ valores inteiros de uma seq\"u\^encia
$a_0, \ldots, a_{n-1}$ e, em seguida, uma seq\"u\^encia de $n-1$
valores que indicam os \'{\i}ndices de constra\c{c}\~oes,

\item realize contra\c{c}\~oes consecutivamente como no exemplo
acima, e

\item imprima o valor alvo $x$. 

\end{itemize}

Se n\~ao existir valor alvo (i.e.~se a entrada estiver de alguma forma
incorreta), o programa deve emitir uma mensagem de erro apropriada.

\end{document}


