## THICC '17 P4 - Kenta's Neural Networks

View as PDF

Points: 10 (partial)
Time limit: 0.6s
Python 4.5s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kenta has a lot of neural networks which are trained to output a specific string. He has a copious amount of neural networks, as he is very good at building neural networks and loves them very much. Unfortunately, he has so many that he needs help finding out which of his neural networks is the best!

Each output for the neural network has a value that represents how accurate his neural network is. The accuracy value represents how many changes the neural network needs to make to the string to get the correct string. A change can be adding a character, removing one or editing one. The smaller the accuracy value, the better the neural network.

For example, to go from "horse" to "hose" you'd need one change, and from "almond" to "nut" you'd need six. You always want to use the minimum number of changes.

You'll be given the correct string which all neural networks wish to achieve, number of neural networks, each accompanied by different outputs from that same neural network. You'll need to output the results of the best (most accurate) neural network.

#### Input Specification

The first line will contain the correct string containing only lowercase letters.

The second line will contain , the number of neural networks.

The following lines will start with , followed by space separated strings, which are the neural networks' outputs.

#### Output Specification

A real number, the average accuracy value of the best neural network. An absolute or relative error of up to will be accepted.

#### Constraints

Length of any String

Length of any String

Length of any String

#### Sample Input

memes
3
2 memes meemes
2 memes same
3 netuhiuoeou eunhouenht oentonhtet

#### Sample Output

0.5

#### Explanation

The first neural network has one perfect output. meemes needs the e removed to make memes. .

The second neural network has a perfect output, and same, which would take moves to turn into memes.

The third is a very bad neural network and need not be considered.