Fişierul intrare/ieşire:cuvinte5.in, cuvinte5.outSursăSummer Challenge 2019
AutorAlexandru PetrescuAdăugată detheodor.moroianuTheodor Moroianu theodor.moroianu
Timp execuţie pe test0.2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cuvinte5

Se defineste diferenta intre doua cuvinte ca fiind patratul numarului minim de adaugari, stergeri sau modificari de caractere necesare pentru a transforma un cuvant in celalalt.
De exemplu, pentru a il transforma pe 'abc' in 'ba' in 2 astfel de modificari, putem face 'abc' -> 'bc' -> 'ba', deci diferenta dintre cele doua cuvinte este 22 = 4.

Se considera un dictionar. Distanta intre doua cuvinte A si B, care nu apartin neaparat dictionarului, cu parametrul suplimentar K, se defineste ca fiind cea mai mica suma a diferentelor intre cuvintele consecutive ale unui sir de maxim K + 1 cuvinte, intre care primul este A, ultimul este B, iar restul cuvintelor apartin dictionarului.

Sa presupunem ca in dictionar avem doar cuvintele lavera, lauera si lalala. Atunci distanta intre cuvintele laverita si laura, cand K = 3, se obtine transformand laverita in lavera, lavera in lauera si lauera in laura. Atunci cand K = 2, in schimb, distanta va fi mai mare, pentru ca vom transforma laverita in lavera si lavera in laura.

Cerinta

Se da un dictionar de N cuvinte si Q queryuri de forma K A B. Pentru fiecare query, se cere sa aflati distanta de la cuvantul A la cuvantul B, cu parametrul suplimentar K.

Date de intrare

Prima linie contine N, numarul de cuvinte din dictionar.
A doua linie contine cele N cuvinte, despartite printr-un spatiu.

A treia linie contine Q, numarul de queryuri.
Urmatoarele Q linii contin cate un query, dat sub forma K A B.

Date de ieşire

Pentru fiecare query se afiseaza cate o linie cu raspunsul.

Restricţii

  • 1 ≤ N ≤ 50
  • 1 ≤ Q ≤ 2.500
  • 1 ≤ Lungimea Cuvintelor ≤ 7
  • 1 ≤ K ≤ N + 1
  • Cuvintele sunt formate din litere mici ale alfabetului latin.
  • Pentru teste in valoare de 20p queryurile nu contin decat cuvinte din dictionar (testele 1, 2, 3, 4).
  • Pentru alte teste in valoare de 20p K = N + 1 (testele 5, 6, 7, 8).
  • Pentru alte teste in valoare de 10p 1 ≤ Q ≤ 50 (testele 9, 10).

Exemplu

cuvinte5.incuvinte5.out
5
a aa aaa aaab aaabb
6
2 a aaaa
3 a aaaa
5 ab aaabbb
4 ab aaabbb
6 xxx yyy
6 zz azab
5
3
5
6
9
7

Explicaţie

Pentru primul query, putem face 'a' -> 'aaa' -> 'aaaa', costul este 4 + 1 = 5
Pentru al doilea query, putem face 'a' -> 'aa' -> 'aaa' -> 'aaaa', costul este 1 + 1 + 1 = 3
Pentru al treilea, putem face 'ab' -> 'aa' -> 'aaa' -> 'aaab' -> 'aaabb' -> 'aaabbb', costul este 1 + 1 + 1 + 1 + 1 = 5.
Pentru al patrulea, putem face 'ab' -> 'aaab' -> 'aaabb' -> 'aaabbb', costul este 22 + 1 + 1 = 6
Pentru al cincilea, putem face 'xxx' -> 'yyy', costul este 3^2 = 9
Pentru ultimul caz, putem face 'zz' -> 'aa' -> 'aaa' -> 'aaab' -> 'azab', costul este 22 + 1 + 1 + 1 = 7

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?