1607 - Avance as Letras

Um raciocínio simples para um problema que parece bem difícil.

Descrição

Solução

Para entendermos o que o problema quer, vamos analisar quantos passos vamos precisar para que uma letra se transforme em outra letra. Por exemplo, vamos supor que queiramos saber quantos passos precisamos para ir de 'a' até 'd'. Essa resposta é tranquila, precisamos de 3 passos: 'a' -> 'b' -> 'c' -> 'd'. Isso é facilmente obtido se fizermos ASCII('d') - ASCII('a') (ver página Tabela ASCII). Entretanto, quantos passos precisamos para ir de 'x' até 'a'? Também 3 passos, pois fazemos 'x' -> 'y' -> 'z' -> 'a'. Esse aspecto de poder voltar à letra 'a' quando avançamos 'z' pode tornar nosso cálculo um pouco mais difícil, mas isso é facilmente contornado se ao invés de calcularmos ASCII('a') - ASCII('x'), que daria um número negativo, podemos fazer (ASCII('a') - ASCII('x') + 26) % 26 (ver página Deslocar dentro de um intervalo [0, N - 1] para entender porque este cálculo funciona).

Logo, para termos o número mínimo de operações entre uma string e outra, basta apenas calcular a soma do número de operações de uma letra para outra, na ordem.

#include <string.h>
#include <stdio.h>

int main(){
    int T, diferenca;
    char A[10001], B[10001];

    scanf("%d\n", &T);

    for(int i = 0; i < T; ++i){
        scanf("%s %s\n", &A, &B);

        diferenca = 0;
        for(int j = 0; j < strlen(A); ++j){
            diferenca += (B[j] - A[j] + 26) % 26;
        }

        printf("%d\n", diferenca);
    }

    return 0;
}

#include <iostream>

using namespace std;

int main(){
    string A, B;
    int T, diferencas;

    cin >> T;

    for(int i = 0; i < T; ++i){
        cin >> A >> B;

        diferencas = 0;
        for(int j = 0; j < A.length(); ++j){
            diferencas += (B[j] - A[j] + 26) % 26;
        }

        cout << diferencas << endl;
    }

    return 0;
}

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');

let T = parseInt(lines.shift());

for(let i = 0; i < T; ++i){
    let [A, B] = lines.shift().trim().split(' ');

    let diferenca = 0;
    for(let j = 0; j < A.length; ++j){
        diferenca += (B.charCodeAt(j) - A.charCodeAt(j) + 26) % 26;
    }

    console.log(diferenca);
}

Previous1581 - Conversa Internacional Next1871 - Zero vale Zero

Last updated 4 years ago

hashtagDescrição

hashtagSolução

Descrição

Solução