UTS Open '15 #1 - Caesar Salad

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type
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

Every great day begins with a breakfast of champions, and Ms. Evans has chosen her favourite breakfast: a salad.

Picture of a Caesar salad

Ms. Evans has N (1\leq N\leq 100) bowls, each containing a salad ingredient. There are 26 types of ingredients:

  • Anchovies
  • Black pepper
  • Croutons
  • Dates
  • Eggs
  • Feta cheese
  • Garlic
  • Horse meat
  • Iceberg lettuce
  • Juniper berries
  • Kale
  • Lemon juice
  • Mangoes
  • Nectarines
  • Olive oil
  • Parmesan cheese
  • Quinoa
  • Romaine lettuce
  • Sesame seeds
  • Tomatoes
  • Unsweetened mayonnaise
  • Vanilla
  • Walnuts
  • X-tra strength butter
  • Yam
  • Zucchini

Ms. Evans really likes Caesar salad, and as everyone knows, Caesar salad has only 8 ingredients:

  • Anchovies
  • Black pepper
  • Croutons
  • Eggs
  • Garlic
  • Lemon juice
  • Olive oil
  • Romaine lettuce

Ms. Evans wants to put all her bowls together and make a Caesar salad, but she doesn't want any incorrect ingredients to be included. She will be satisfied if all of the ingredients in her bowls are Caesar salad ingredients. Note that it's OK if some of the ingredients aren't present: a combination of olive oil and black pepper would still leave Ms. Evans satisfied.

These bowls are no ordinary bowls: Ms. Evans has a big red button, and when she presses it, the i^\textbf{th} bowl shifts s_i times (1\leq s_i \leq 10). When a bowl shifts, its ingredient becomes the next ingredient in the list: vanilla becomes walnut, garlic becomes horse meat, and zucchini goes all the way back to the start and becomes anchovies.

Ms. Evans wants to know the minimum number of button presses necessary to make all her ingredients Caesar salad ingredients. Can you help her?

Input Format

There will be T (1 \leq T \leq 100) test cases. The first line of input will contain T. T lines will follow, each describing one test case: first the integer N, then a string of N upper-case letters representing the ingredient in each bowl (each ingredient is represented by its first letter), then each value of s_i in order.

Output Format

For each test case, output a single line containing the answer to that test case. If it is impossible to satisfy the conditions no matter how many times Ms. Evans presses the button, output -1.

Sample Input

3
2 CM 2 1
4 ABCD 1 1 1 1
3 ABC 10 5 4

Sample Output

2
-1
0

Explanation

In the first test case, the bowls contain croutons and mangoes. If she presses the button twice, the first bowl will contain garlic and the second bowl will contain olive oil. This is the minimum number of button presses.


Comments


  • 0
    bobhob314  commented on May 12, 2015, 4:01 p.m. edit 4

    Please disregard this comment; upon a re-reading I discovered that all of the bowls shift according to their values s_i simulutaneously.


  • 1
    bobhob314  commented on Feb. 11, 2015, 4:12 p.m.

    Shouldn't it be croutons and mangoes?


    • 1
      nullptr  commented on Feb. 11, 2015, 4:19 p.m.

      Yes; the statement has been corrected.