Solução Campeonato de SMS

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:

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

view raw

sms.cpp

hosted with ❤ by GitHub