Solução de Rogério Júnior
Para ver o problema original, clique aqui.
Imagine um vetor de nome 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 tem guardado exatamente o tempo de mover um dedo da tecla de número para a de número .
Resolver esse problema com uma agora é bem simples. Seja o estado da DP definido pelas variáveis (, , ), que significam as teclas em que estão os dedos direito e esquerdo e qual a posição em da tecla que temos que apertar agora. Se a posição aponta para o fim de (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 mais que usamos para apertar a tecla. Seja a tecla salva na posição de . Seja a função recursiva que usaremos para calcular o valor de um estado da DP. Usar o dedo esquerdo tem custo para movê-lo até a tecla e depois tem custo para terminarmos de digitar as teclas em , pois o dedo esquerdo agora está na tecla de número , o direito não se move e a próxima tecla a ser digitada é a que está na posição de . De maneira análoga, usar o dedo direito tem custo .
Sabendo isso, basta calcularmos o valor da matriz e o vetor . Calcular é simples, basta salvarmos um vetor com posições em que a casa guarda um par de inteiros que representam as coordenadas do centro da tecla (podemos colocar o na tecla , por exemplo) e usarmos dois para calcular a distância euclidiana entre quaisquer dois pontos do vetor e guardá-la em .
Para criarmos o vetor , vamos ler cada caractere da entrada. Usando é 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 em antes da nova tecla. Feito isso, basta colocarmos a nova tecla em quantas vezes for necessária.
Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <iostream> | |
#include <algorithm> | |
#include <cstring> | |
#include <vector> | |
#include <cmath> | |
using namespace std; | |
#define MAXN 200 | |
#define PB push_back | |
#define F first | |
#define S second | |
typedef pair<int,int> ii; | |
char s[MAXN]; | |
int tam; | |
vector<int> seq; | |
double t[15][15], dp[15][15][1000]; | |
// função recursiva para calcular a DP | |
double total(int esq, int dir, int pos){ | |
// se já tiver calculado este estado, retorno o valor salvo | |
if(dp[esq][dir][pos]>=0) return dp[esq][dir][pos]; | |
// se seq tiver acabado, retorno 0 | |
if(pos==seq.size()) return dp[esq][dir][pos]=0.0; | |
// prox é a nova tecla a ser digitada | |
int prox=seq[pos]; | |
// retorno o melhor entre usar o dedo esquerdo ou o direito | |
return dp[esq][dir][pos]=0.2+min(t[esq][prox]+total(prox,dir,pos+1), t[dir][prox]+total(esq,prox,pos+1)); | |
} | |
// tempo será a função usada para pré-calcularmos os valores de seq, t e chamarmos a DP | |
double tempo(){ | |
// limpo tudo que está em seq | |
seq.clear(); | |
// salvo -1 em todas as casas da tabela de DP, para recalcular tudo | |
for(int i=0;i<15; i++) | |
for(int j=0; j<15; j++) | |
for(int k=0; k<1000; k++) | |
dp[i][j][k]=-1.0; | |
// salvo o tamanho da entrada | |
tam=strlen(s); | |
// adciono -1 na pos 0 de seq para ela começar da posição 1 | |
// e não me preocupar em acessar memória inválida quando olho a tecla anterior | |
seq.PB(-1); | |
// para cada caractere a ser digitado | |
for(int i=0; i<tam; i++){ | |
ii davez; | |
char c=s[i]; | |
// calculo o par (tecla pressionada, quantas vezes devo pressionar a tecla) | |
if(c=='a' or c=='b' or c=='c') davez=ii(2,c-'a'+1); | |
if(c=='d' or c=='e' or c=='f') davez=ii(3,c-'d'+1); | |
if(c=='g' or c=='h' or c=='i') davez=ii(4,c-'g'+1); | |
if(c=='j' or c=='k' or c=='l') davez=ii(5,c-'j'+1); | |
if(c=='m' or c=='n' or c=='o') davez=ii(6,c-'m'+1); | |
if(c=='p' or c=='q' or c=='r' or c=='s') davez=ii(7,c-'p'+1); | |
if(c=='t' or c=='u' or c=='v') davez=ii(8,c-'t'+1); | |
if(c=='w' or c=='x' or c=='y' or c=='z') davez=ii(9,c-'w'+1); | |
if(c==' ') davez=ii(0,1); | |
// se for a mesma tecla do caractere anterior, coloco a tecla 10 | |
if(seq.back()==davez.F) seq.PB(10); | |
// adiciono a tecla a seq quantas vezes for necessária | |
for(int j=1; j<=davez.S; j++) seq.PB(davez.F); | |
} | |
// vetor com todas as coordenadas dos centros das teclas | |
ii p[11]={ii(0,-2), ii(-1,1),ii(0,1),ii(1,1),ii(-1,0),ii(0,0),ii(1,0),ii(-1,-1),ii(0,-1),ii(1,-1),ii(1,-2)}; | |
// calculo a distância entre quaisquer duas teclas | |
for(int i=0; i<=10; i++) | |
for(int j=0; j<=10; j++) | |
t[i][j]=sqrt((p[i].F-p[j].F)*(p[i].F-p[j].F)+(p[i].S-p[j].S)*(p[i].S-p[j].S))/30.0; | |
// chamo a DP para calcular o resultado | |
// no começo, o dedo esquerdo está na tecla 4, o direito na 6 | |
// e tenho que pressionar a tecla que está na posição 1 de seq | |
return total(4,6,1); | |
} | |
int main(){ | |
// enquanto houver entrada, imprimo a resposta até a 2ª casa decimal | |
while(scanf(" %[^\n]", s)!=EOF) printf("%.2lf\n", tempo()); | |
return 0; | |
} |