52 lines
2.6 KiB
TeX
52 lines
2.6 KiB
TeX
\documentclass{maratona}
|
|
|
|
\begin{document}
|
|
\begin{ProblemaAutor}{}{Bolhas}{1}{256}{UVA - 11495}
|
|
|
|
Carlos e Marcelo decidiram jogar um jogo com sequências de números. O jogo começa com uma permutação de $1, 2, \ldots, N$ gerada aleatoriamente.
|
|
|
|
Os jogadores alternam turnos, e \textbf{Marcelo sempre é o primeiro a jogar}. Um movimento consiste em escolher um par de elementos \textbf{adjacentes} que estejam fora de ordem (onde o elemento da esquerda é maior que o da direita) e trocá-los de lugar.
|
|
|
|
Por exemplo, se a sequência for $(1, 5, 3, 4, 2)$, um jogador pode trocar o $5$ pelo $3$ ou o $4$ pelo $2$. Se o jogador escolher trocar o $5$ e o $3$, a nova sequência será $(1, 3, 5, 4, 2)$.
|
|
|
|
O objetivo do jogo é ordenar a sequência em ordem crescente. O jogador que receber a sequência já ordenada, não tendo movimentos possíveis a realizar, perde a partida. Sua tarefa é determinar quem será o vencedor do jogo para a permutação inicial fornecida.
|
|
|
|
\Entrada
|
|
|
|
A entrada é composta por duas linhas.
|
|
|
|
A primeira linha contém um inteiro $N$ ($2 \le N \le 10^5$), representando o número de elementos da sequência.
|
|
|
|
A segunda linha contém a sequência $P = (X_1, X_2, \ldots, X_N)$ de $N$ inteiros distintos, onde $1 \le X_i \le N$.
|
|
|
|
\Saida
|
|
|
|
Imprima uma única linha contendo o nome do vencedor: \texttt{Carlos} ou \texttt{Marcelo}.
|
|
|
|
\ExemploEntrada
|
|
\begin{Exemplo}
|
|
\texttt{5} & \texttt{Marcelo}\\
|
|
\texttt{1~5~3~4~2} & \\
|
|
\rowcolor{gray!20}\texttt{5} & \texttt{Carlos}\\
|
|
\rowcolor{gray!20}\texttt{5~1~3~4~2} & \\
|
|
\texttt{5} & \texttt{Carlos}\\
|
|
\texttt{1~2~3~4~5} & \\
|
|
\end{Exemplo}
|
|
|
|
|
|
|
|
\Notas
|
|
|
|
No primeiro caso de teste, a sequência inicial é $(1, 5, 3, 4, 2)$. Para ordenar esta sequência, são necessárias 5 trocas. Uma possível sequência de trocas seria:
|
|
\begin{itemize}
|
|
\item $(1, 5, 3, 4, 2) \rightarrow (1, 3, 5, 4, 2)$
|
|
\item $(1, 3, 5, 4, 2) \rightarrow (1, 3, 4, 5, 2)$
|
|
\item $(1, 3, 4, 5, 2) \rightarrow (1, 3, 4, 2, 5)$
|
|
\item $(1, 3, 4, 2, 5) \rightarrow (1, 3, 2, 4, 5)$
|
|
\item $(1, 3, 2, 4, 5) \rightarrow (1, 2, 3, 4, 5)$
|
|
\end{itemize}
|
|
Como o número total de movimentos é 5 (ímpar) e Marcelo é o primeiro a jogar, ele fará o último movimento. Portanto, \textbf{Marcelo} é o vencedor.
|
|
|
|
No terceiro caso, a sequência fornecida é $(1, 2, 3, 4, 5)$. Como a sequência já se encontra perfeitamente ordenada, não existem pares adjacentes fora de ordem para realizar um movimento. Marcelo, sendo o primeiro a jogar, recebe a sequência sem movimentos possíveis e perde a partida imediatamente. Assim, o vencedor é \textbf{Carlos}.\end{ProblemaAutor}
|
|
\end{document}
|