Solução Campeonato de SMS

0 Flares Facebook 0 0 Flares ×

Solução de Rogério Júnior

Para ver o problema original, clique aqui.

Imagine um vetor de nome seq em que aparecem todas as teclas que o competidor deve digitar, na ordem em que devem ser digitadas e repetidas exatamente o número de vezes que o competidor deve repetir. Imagine também que a matriz t[i][j] tem guardado exatamente o tempo de mover um dedo da tecla de número i para a de número j.

Resolver esse problema com uma DP agora é bem simples. Seja o estado da DP definido pelas variáveis (esq, dir, pos), que significam as teclas em que estão os dedos direito e esquerdo e qual a posição em seq da tecla que temos que apertar agora. Se a posição aponta para o fim de seq (uma posição após a última), basta retornarmos zero. Caso contrário retornamos o melhor entre usar o dedo esquerdo ou o direito para pressionar a tecla em pos mais 0.2 s que usamos para apertar a tecla. Seja prox a tecla salva na posição pos de seq. Seja total a função recursiva que usaremos para calcular o valor de um estado da DP. Usar o dedo esquerdo tem custo t[esq][seq[pos]] para movê-lo até a tecla e depois tem custo total(prox,dir,pos+1) para terminarmos de digitar as teclas em seq, pois o dedo esquerdo agora está na tecla de número prox, o direito não se move e a próxima tecla a ser digitada é a que está na posição pos+1 de seq. De maneira análoga, usar o dedo direito tem custo t[dir][prox]+total(esq,prox,pos+1).

Sabendo isso, basta calcularmos o valor da matriz t e o vetor seq. Calcular t é simples, basta salvarmos um vetor com 11 posições em que a casa i guarda um par de inteiros que representam as coordenadas do centro da tecla i (podemos colocar o (0,0) na tecla 5, por exemplo) e usarmos dois for para calcular a distância euclidiana entre quaisquer dois pontos do vetor e guardá-la em t.

Para criarmos o vetor seq, vamos ler cada caractere da entrada. Usando if é fácil sabermos em qual tecla está o caractere a ser digitado e quantas vezes devemos apertar a tecla para que ele apareça. Se a tecla deste caractere for a mesma do anterior, devemos colocar a tecla 10 em seq antes da nova tecla. Feito isso, basta colocarmos a nova tecla em seq quantas vezes for necessária.

Segue o código para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: