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();
}
}
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();
}
}
0 Comentários