Fişierul intrare/ieşire:shift.in, shift.outSursăInfoarena Monthly 2012, Runda 3
AutorAndrei GrigoreanAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Shift

Se da o masinarie care poate sa citeasca si sa scrie caractere. Masinaria dispune de o banda de perechi de caractere de lungime 26 (asezate una dupa alta). Un caracter dintr-o pereche apartine multimii 'a'..'z' si fiecare caracter apare de exact doua ori pe banda. Pentru a scrie un text, masinaria are nevoie mai intai sa-l citeasca asa ca dispune de un cap de citire, pozitionat initial pe pozitia 1 pe banda. Pentru a citi un caracter, masinaria trebuie sa-si pozitioneze capul pe un element al benzii care contine caracterul respectiv. Se stie ca, pentru a deplasa capul de citire intr-o directie (stanga sau dreapta) , masina va consuma un joul. De asemenea , pentru a citi primul caracter de pe o pereche i, masina va counsuma Ci,0 jouli si, pentru a citi al doilea caracter de pe o pereche i, masina va consuma Ci,1 jouli.

Cerinta

Dandu-se un text S, scrieti timpul minim necesar pentru a-l scrie la masina.

Date de intrare

Fişierul de intrare shift.in va contine pe prima linie textul S. Pe urmatoarele 26 de linii vor se vor afla cate doua caractere ai,0 si ai,1 separate printr-un spatiu reprezentand primul si respectiv al doilea caracter din perechea a i-a. Pe urmatoarele 26 de linii se for afla Ci,0 si Ci,1 , numarul de jouli necesari scrierii primului caracter din perechea i si respectiv numarul de jouli necesari scrierii celui de-al doilea caracter din perechea i.

Date de ieşire

În fişierul de ieşire shift.out se va afla un singur numar, Sol, reprezentand numarul minim de jouli necesari scrierii textului S cu ajutorul masinariei.

Restricţii

  • 1 ≤ lungime(S) ≤ 100.000
  • sirul S va contine doar caractere din multimea 'a'..'z'
  • 1 ≤ Ci,j ≤ 10

Exemplu

shift.inshift.out
phqghumeay
l n
l f
d x
f i
r c
v s
c x
g g
b w
k n
q d
u w
o z
v s
r t
k j
p e
p y
t m
y q
e i
m z
a a
o b
j u
h h
1 1
1 2
2 2
1 1
1 1
2 2
2 1
2 1
2 2
2 1
1 2
1 2
2 2
2 1
1 2
2 1
1 1
2 1
1 2
2 2
2 2
2 2
2 1
1 1
1 1
1 1
84
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content