Resolução F91 por Phyllipe César

Publicado por Phyllipe Categoria: Seletivas|SPOJ

24 Feb 2010

Resumo}

Dado um inteiro N, retorne $f(N)$ seguindo as seguintes restrições:

\begin{enumerate}

\item $ N \geq 101 $

\begin{itemize}

\item $f(N) = N-10$

\end{itemize}

\item $ N \leq 100 $

\begin{itemize}

\item $f(N) = f ( f (N + 11) )$

\end{itemize}

\end{enumerate}

\section{Análise}

Temos dois casos básicos para o problema:

\begin{enumerate}

\item $ N \geq 101 $

\item $ N \leq 100 $

\end{enumerate}

\newline

Para o primeiro caso executaremos a propria definição do algoritmo:

\begin{equation}

f(N) = N - 10

\end{equation}

\newline

O segundo caso é mais "complicado", segue a definição:

\begin{equation}

f(N) = f( f(N + 11) )

\end{equation}

\newline

Note que, se temos um inteiro $x$, sendo $90 \leq x \leq 100$, $f(x+11)$ retornará $x+1$.

\newline

Como dada na definição, o retorno de $f(x)$ será $f( f (x + 11) ) = f(x+1) $

\newline

Considerando $ x = 90 $, notamos que

\begin{equation}

f(90) = f(91) = f(92) = f(93) = ... = f (101)

\end{equation}

Pela equação de número $2.1$ temos:

\begin{equation}

f(101) = 91

\end{equation}

Logo, $f(90) = f(91) = ... f(100) = f(101) = 91$

\newline

Se temos agora um inteiro $k$, $79 \leq k \leq 89$, temos que $f(k) = f (f (k+11))$ Note que $k+11$ está nos limites de $90 \leq k+11 \leq 100$, logo $f(k+11) = 91$, e temos que $f(k) = f(91) $, que como provado anteriormente, retornará $91$.

\newline

O mesmo façamos para uma variavél, $68 \leq v \leq 78$, $f(v)$ claramente retornará $91$.

\newline

Ou seja, o algoritmo baseia-se em:

\begin{enumerate}

\item $N \geq 101$

\begin{itemize}

\item $return$ $N-10$

\end{itemize}

\item $N \leq 100$

\begin{itemize}

\item $return$ $ 91$

\end{itemize}

\end{enumerate}

Resumo

Dado um inteiro $N$ , retorne $f(N)$ seguindo as seguintes restrições:

$N \geq 101$
$N \leq 100$

Link: http://br.spoj.pl/problems/F91/

Análise

Temos dois casos básicos para o problema:

$N \geq 101$
$N \leq 100$

Para o primeiro caso executaremos a propria definição do algoritmo:

$f(N) = N - 10$

O segundo caso é mais "complicado", segue a definição:

$f(N) = f( f(N + 11) )$

Note que, se temos um inteiro x, sendo $90 \leq x \leq 100$ , $f(x+11)$ retornará x+1.

Como dada na definição, o retorno de $f(x)$ será $f( f (x + 11) ) = f(x+1)$

Considerando $x = 90$ , notamos que

$f(90) = f(91) = f(92) = f(9u) = f(100) = f (101)$

Pelas equações anteriores temos:

$f(101) = 91$

Logo, $f(90) = f(91) = f(9u) = f(100) = f(101) = 91$

Se temos agora um inteiro k, $79 \leq k \leq 89$ , temos que $f(k) = f (f (k+11))$ Note que k+11 está nos limites de $90 \leq k+11 \leq 100$ , logo $f(k+11) = 91$ , e temos que $f(k) = f(91)$ , que como provado anteriormente, retornará 91.