pesquisa

URI PROBLEMA 1412 - Cadeado com Segredo SOLUÇÃO EM C++

URI Online Judge | 1412

Cadeado com Segredo

Por Pablo Heiber  Argentina
Timelimit: 3
Um cadeado possui um sistema de código para ser aberto ao invés de uma chave. O cadeado contém uma sequência de rodas. Cada roda possui as 26 letras do alfabeto inglês (a..z), em ordem. Se você move uma roda para cima, a letra que ela mostra muda para a próxima letra do alfabeto (se a letra mostrada for 'z', então ela muda para 'a'). Se você move uma roda para baixo, ela muda para a letra anterior do alfabeto (se a letra mostrada for 'a', ela muda para 'z').
Também é possível mover qualquer subsequência contígua de rodas para a mesma direção com apenas um movimento. Isso tem o mesmo efeito que mover todas as rodas da subsequência para aquela direção, mas executando apenas um movimento.
O cadeado abre quando a roda mostra uma determinada sequência de letras. Inicialmente, todas as rodas mostram a letra 'a'. Você quer saber qual o menor número de movimentos necessários para abrir o cadeado.

Entrada

A entrada contém vários casos de teste. Um caso de teste é descrito em exatamente uma linha contendo uma string não-vazia com no máximo 1000 letras minúsculas. A string representa a sequência secreta de letras que abre o cadeado.
O último caso de teste é seguido de uma linha contendo um único asterisco.

Saída

Para cada caso de teste, imprima uma linha contendo um único inteiro, o menor número de movimentos que abre o cadeado.



#include <bits/stdc++.h>


using namespace std;


int main()
{
    vector<int> v;
    string aux;
    string s;
    int pos1, pos2;
    int ans = 0;
   
    while (getline(cin, s))
    {
        if (s == "*") return 0;
        aux.push_back('a');
        aux += s;
        aux.push_back('a');
       
        int n = aux.size();
       
        for (int i = 1; i < n; ++i)
        {
            int a = (int)(aux[i] - aux[i - 1] + 26);
            v.push_back(a % 26);
        }
        sort(v.begin(), v.end());
       
        ans = 0;
        pos1 = 0;
        while (pos1 < v.size() && v[pos1] == 0) ++pos1;
       
        if (pos1 == v.size()) cout << "0\n";
        else
        {
            pos2 = v.size() - 1;
            while (pos2)
            {           
                ++ans;
                v[pos2] = (v[pos2] + 1) % 26;
                v[pos1] = (v[pos1] - 1) % 26;
                while (pos1 < v.size() && (v[pos1] == 0 || v[pos1] == v[pos2])) ++pos1;
                if (pos1 == v.size()) break;
                while (pos2 && !(v[pos2])) --pos2;
            }
            if (v[pos2]) ans += 26 - v[pos2];
            cout << ans << '\n';
        }
        v.clear();
        aux.clear();
    }
       
}

Postar um comentário

0 Comentários