Problema: 1448
Enunciado:
Toda criança já brincou de "telefone sem fio". Joãozinho inventou uma variação da brincadeira. O grupo de crianças é dividido em dois times. Os times se organizam como na brincadeira original, em que cada um repete o que lhe foi falado para o seguinte, até que o último diz o que chegou até ele. No caso da brincadeira de Joãozinho será falada uma frase com n caracteres (contando letras, espaços, sinais de pontuação, etc). Todos sabem que a frase tem este comprimento. A frase é falada pelo juiz ao primeiro competidor de cada time que a repete para o segundo, e este para o terceiro e assim sucessivamente, até que o último competidor de cada time escreve a frase final (garantindo que n caracteres sejam escritos) e a entrega para o juiz. A equipe vencedora é aquela cuja frase final seja mais próxima da frase original. Para calcular a semelhança entre duas frases de mesmo comprimento você deve contar o número de vezes em que o caractere da frase do time coincide com o caractere da frase original. Ganha o time para o qual o número de coincidências seja máximo. Se os dois times empataram neste critério, a primeira vez que um dos times acertou e o outro errou decide. Exemplo: Se a frase original foi "O rato roeu a roupa do rei.", o primeiro time escreveu "O ator morreu, garoupa rei." e o segundo time escreveu "O pato moeu garoupa dorlei." O segundo time ganhou pois teve 21 coincidências contra 9 coincidências do primeiro:
Linguagem: C++
Ao fazer a leitura das 3 linhas, elas são percorridas identificando quantas linhas de cada uma são diferentes. Além disso, é verificado quando cada uma das linhas teve seu primeiro erro. Caso as duas linhas tenha o erro na mesma posição, então essa identificação é reiniciada, buscando a próxima posição com erro.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <iostream> #include <map> using namespace std; int main() { int limit; string line, line1, line2; cin >> limit; getline(cin,line); int iteracao = 1; while(getline(cin,line)){ if(iteracao==limit+1) break; cout << "Instancia "<< iteracao++ << endl; getline(cin,line1); getline(cin,line2); int errors1 = 0; int errors2 = 0; int first_error1 = line.length()+1; int first_error2 = line.length()+1; for(int i =0;i<line.length();i++){ if(line[i]!=line1[i]){ errors1++; first_error1 = first_error1 > i ? i : first_error1; } if(line[i]!=line2[i]){ errors2++; first_error2 = first_error2 > i ? i : first_error2; if(first_error1 == first_error2){ first_error1 = line.length()+1; first_error2 = line.length()+1; } } } if(errors1==errors2){ if(first_error1 > first_error2){ cout << "time 1"<<endl<<endl; } else if(first_error2 > first_error1){ cout << "time 2"<<endl<<endl; } else cout << "empate"<<endl<<endl; } else{ if(errors1>errors2){ cout << "time 2"<<endl<<endl; } else{ // errors2>errors1 cout << "time 1"<<endl<<endl; } } } return 0; } |
