Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BALDES - Bolhas e baldes

Andrea, Carlos e Marcelo são muito amigos e passam todos os finais de semana à beira da piscina. Enquanto Andrea se bronzeia ao sol, os dois ficam jogando Bolhas. Andrea, uma cientista da computação muito esperta, já disse a eles que não entende por que passam tanto tempo jogando um jogo tão primário.

Usando o computador portátil dela, os dois geram um inteiro aleatório N e uma seqüência de inteiros, também aleatória, que é uma permutação de 1, 2, . . . , N.

O jogo então começa, cada jogador faz um movimento, e a jogada passa para o outro jogador. Marcelo é sempre o primeiro a começar a jogar.

Um movimento de um jogador consiste na escolha de um par de elementos consecutivos da seqüência que estejam fora de ordem e em inverter a ordem dos dois elementos. Por exemplo, dada a seqüência 1, 5, 3, 4, 2, o jogador pode inverter as posições de 5 e 3 ou de 4 e 2, mas não pode inverter as posiçõoes de 3 e 4, nem de 5 e 2. Continuando com o exemplo, se o jogador decide inverter as posições de 5 e 3 então a nova seqüência será 1, 3, 5, 4, 2.

Mais cedo ou mais tarde, a seqüência ficará ordenada. Perde o jogador impossibilitado de fazer um movimento.

Andrea, com algum desdém, sempre diz que seria mais simples jogar cara ou coroa, com o mesmo efeito. Sua missão, caso decida aceitá-la, é determinar quem ganha o jogo, dada a seqüência inicial.

Entrada

A entrada contém vários casos de teste. Os dados de cada caso de teste estão numa única linha, e são inteiros separados por um espaço em branco. Cada linha contém um inteiro N, 2 <= N <= 10^5, seguido da seqüência inicial P = (X1 , X2 , . . . , XN ) de N inteiros distintos dois a dois, onde 1 <= Xi <= N para 1 <= i <= N. O final da entrada é indicado por uma linha que contém apenas o número zero.

Saída

Para cada caso de teste da entrada seu programa deve imprimir uma única linha, com o nome do vencedor, igual a Carlos ou a Marcelo, sem espaços em branco.

Exemplo

Entrada:

5 1 5 3 4 2        
5 5 1 3 4 2        
5 1 2 3 4 5        
6 3 5 2 1 4 6      
5 5 4 3 2 1        
6 6 5 4 3 2 1      
0

Saída
Marcelo
Carlos
Carlos
Carlos
Carlos
Marcelo

Adicionado por:Wanderley Guimarăes
Data:2008-10-25
Tempo limite:0.730s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2008

hide comments
2014-08-15 19:11:40 Rogerio Guerreiro
Em C++ utilizei std::vector e nem cin/cout e tomei TLE, utilizando o mesmo algoritmo sem usar nada da STL o problema passou...
2013-04-08 04:28:59 Diogo Boaventura
selection sort fail
2012-12-10 23:40:18 .
Bubble Sort fail
2012-05-03 19:37:57 Glauco Buarque
bubousorti
2011-09-09 23:57:55 thiagojobson [UERN]
"... mas năo pode inverter as posiçőoes de 3 e 4, nem de 5 e 2" -- vocę pode sim, basta saber contar.
2010-08-10 22:00:00 Matheus Pacheco [UFMG]


Last edit: 2010-11-17 12:30:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.