Campeonato de SMS

sms.cpp

#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;
}