segunda-feira, 20 de agosto de 2012

#16 Exercício - Elementar, meu caro Watson

Nome: Elementar, meu caro Watson
Link: http://br.spoj.pl/problems/WCW/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.23
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 4

Comentário:
Este exercício me tomou mais tempo do que eu esperava, e só não vou marcá-lo como difícil porque o algoritmo final é bem simples.
Trata-se de um exercício de ordenação, porém deve-se descobrir o menor número possível de trocas.
Já vou adiantando para vocês que algoritmos como Bubble sort, Quick sort não funcionam, pois estes podem ser rápidos e úteis, porém utilizam de trocas desnecessárias, o que vai diretamente contra a proposta do exercício.
Eu mesmo fiquei tentando os algoritmos clássicos e estes deram resposta errada. Portanto pulem esta parte.
Tive que pensar bastante, nas lógicas e possibilidades, e encontrei uma que no início julgava fora de questão, e no final percebi que era possível, e funcionou.
O algoritmo que fiz, só para constar, me lembrou o filme Inception (vocês vão entender quando fizerem, eu acho haha).
E em momento algum eu faço de fato trocas, isso é o máximo que eu posso dizer.

Dicas:
- A primeira dica é pensar num próprio algoritmo de ordenação que faz apenas trocas absolutamente necessárias.
- Vale notar que, os valores estão entre 1 e n e não se repetem. Isso já lhe garante um belo de um 'atalho' (Inception).
- Vale notar também que é possível a troca de valores não adjacentes, ou seja, valores que não estão lado a lado.

Nenhum comentário:

Postar um comentário