Old teletext P77839


Statement
 

pdf   zip

html

In this problem, we use a simplified model of teletext, where the available pages are 100–899, the initial page is always 100, and there are only two ways to move to any page:

  • By pressing its three digits.
  • By (repeatedly) pressing the ‘+’ key or the ‘-’ key. The ‘+’ key increments the current page number by one (or from 899 to 100). The ‘-’ key decrements the current page number by one (or from 100 to 899).

Professor Oak’s television is so old, that some keys of its remote control are broken. For instance, assume that the keys ‘1’ and ‘-’ are broken. If he wants to change from page 140 to page 211, he cannot press ‘211’ directly. Still, he can just press ‘+’ 71 times. Alternatively, he can press ‘200’, and afterwards press ‘+’ 11 times, for a total cost of 14. For this example, the minimum cost is 5: first press ‘209’; then press ‘+’ twice.

Given a list of broken keys, and a list of teletext pages that must be visited, which is the minimum cost to visit all those pages at least once, in any order?

Input

Input consists of at most 100 cases. Every case has two lines. The first line has a string with all the broken keys in any order, following exactly the sample input. The second line has a number p, followed by p page numbers with no repetitions. Assume 1 ≤ p ≤ 9.

Output

For every case, print the minimum cost. Print “no solution” if there is none.

Public test cases
  • Input

    broken:1-
    2 211 140
    broken:
    9 899 897 101 800 799 802 300 301 299
    broken:38+7-5
    1 899
    broken:-+01
    3 444 100 443
    broken:+0123456789
    3 150 100 300
    

    Output

    45
    16
    no solution
    6
    750
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Cinquè Concurs de Programació de la UPC - Final
    Date
    2007-10-03