Reaching one's lucky numbers in reputation A new code-golfer, Joe, just registered to the site. He has 1 reputation but determined to reach all his lucky numbers in reputation exactly. Joe believes in higher powers which will help him to achieve his goal with minimal amount of (his or others) actions. As a new user he also believes that negative reputation is possible.

You should write a program or function which helps Joe to compute how many action should he expect.

Details


The actions can change the reputation by the following amounts (all actions are available at every step regardless of stackexchange rules):

answer accepted:     +15
answer voted up:     +10
question voted up:    +5
accepts answer:       +2
votes down an answer: −1
question voted down:  −2

Other special reputation changes are disregarded.
Lucky numbers can be negative and can be reached in any order.
Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).


Input


Joe's lucky numbers as a list of integers in a common form of your language.


Output


The number of minimum actions needed as a single integer.
Output could be printed to stdout or returned as an integer.


Examples

Input => Output (Example reputation states)

1                     =&gt; 0  (1)
3 2 1                 =&gt; 2  (1 -&gt; 3 -&gt; 2)
2 10 50               =&gt; 7  (1 -&gt; 3 -&gt; 2 -&gt; 12 -&gt; 10 -&gt; 25 -&gt; 40 -&gt; 50)
10 11 15              =&gt; 3  (1 -&gt; 11 -&gt; 10 -&gt; 15)
42 -5                 =&gt; 7  (1 -&gt; -1 -&gt; -3 -&gt; -5 -&gt; 10 -&gt; 25 -&gt; 40 -&gt; 42)
-10                   =&gt; 6  (1 -&gt; -1 -&gt; -3 -&gt; -5 -&gt; -7 -&gt; -9 -&gt; -10)
15 -65                =&gt; 39
7 2015 25 99          =&gt; 142
-99 576 42 1111 12345 =&gt; 885


This is code-golf so the shortest entry wins.
Rust, 929 923 characters



use std::io;use std::str::FromStr;static C:&amp;'static [i32]=&amp;[-2,-1,2,5,10,15];fn main(){let mut z=String::new();io::stdin().read_line(&amp;mut z).unwrap();let n=(&amp;z.trim()[..]).split(' ').map(|e|i32::from_str(e).unwrap()).collect::&lt;Vec&lt;i32&gt;&gt;();let l=*n.iter().min().unwrap();let x=n.iter().max().unwrap()-if l&gt;1{1}else{l};let s=g(x as usize);println!("{}",p(1,n,&amp;s));}fn g(x:usize)-&gt;Vec&lt;i32&gt;{let mut s=vec![std::i32::MAX-9;x];for c in C{if *c&gt;0&amp;&amp;(*c as usize)&lt;=x{s[(*c-1)as usize]=1;}}let mut i=1us;while i&lt;x{let mut k=i+1;for c in C{if(i as i32)+*c&lt;0{continue;}let j=((i as i32)+*c)as usize;if j&lt;x&amp;&amp;s[j]&gt;s[i]+1{s[j]=s[i]+1;if k&gt;j{k=j;}}}i=k;}s}fn p(r:i32,n:Vec&lt;i32&gt;,s:&amp;Vec&lt;i32&gt;)-&gt;i32{if n.len()==1{h(r,n[0],&amp;s)}else{(0..n.len()).map(|i|{let mut m=n.clone();let q=m.remove(i);p(q,m,&amp;s)+h(r,q,&amp;s)}).min().unwrap()}}fn h(a:i32,b:i32,s:&amp;Vec&lt;i32&gt;)-&gt;i32{if a==b{0}else if a&gt;b{((a-b)as f32/2f32).ceil()as i32}else{s[(b-a-1)as usize]}}


This was fun!



Commentary on the implementation

So I'm obviously not too happy with the size. But Rust is absolutely terrible at golfing anyway. The performance, however, is wonderful.

The code solves each of the test cases correctly in a near-instantaneous amount of time, so performance is obviously not an issue. For fun, here's a much more difficult test case:

1234567 123456 12345 1234 123 777777 77777 7777 777


for which the answer is 82317, which my program was able to solve on my (medium-performance) laptop in 1.66 seconds (!), even with the recursive brute-force Hamiltonian path algorithm.

Observations


First we should build a modified weighted graph, with the nodes being each "lucky" number and the weights being how many changes it takes to get from one reputation level to another. Each pair of nodes must be connected by two edges, since going up is not the same as going down in reputation value (you can get +10, for example, but not -10).
Now we need to figure out how to find the minimum amount of changes from one rep value to another.


For getting from a higher value to a lower value, it's simple: just take ceil((a - b) / 2) where a is the higher value and b is the lower value. Our only logical option is to use the -2 as much as possible, and then the -1 once if necessary.
A low to high value is a bit more complicated, since using the greatest possible value is not always optimal (ex. for 0 to 9, the optimal solution is +10 -1). However, this is a textbook dynamic programming problem, and simple DP is enough to solve it.

Once we have calculated the minimum changes from each number to every other number, we are essentially left with a slight variant of TSP (travelling salesman problem). Luckily, there are a small enough number of nodes (a maximum of 5 in the hardest test case) that brute force is sufficient for this step.


Ungolfed code (heavily commented)

use std::io;
use std::str::FromStr;

// all possible rep changes
static CHANGES: &amp;'static [i32] = &amp;[-2, -1, 2, 5, 10, 15];

fn main() {
    // read line of input, convert to i32 vec
    let mut input = String::new();
    io::stdin().read_line(&amp;mut input).unwrap();
    let nums = (&amp;input.trim()[..]).split(' ').map(|x| i32::from_str(x).unwrap())
        .collect::&lt;Vec&lt;i32&gt;&gt;();

    // we only need to generate as many additive solutions as max(nums) - min(nums)
    // but if one of our targets isn't 1, this will return a too-low value.
    // fortunately, this is easy to fix as a little hack
    let min = *nums.iter().min().unwrap();
    let count = nums.iter().max().unwrap() - if min &gt; 1 { 1 } else { min };
    let solutions = generate_solutions(count as usize);

    // bruteforce!
    println!("{}", shortest_path(1, nums, &amp;solutions));
}

fn generate_solutions(count: usize) -&gt; Vec&lt;i32&gt; {
    let mut solutions = vec![std::i32::MAX - 9; count];

    // base cases
    for c in CHANGES {
        if *c &gt; 0 &amp;&amp; (*c as usize) &lt;= count {
            solutions[(*c-1) as usize] = 1;
        }
    }

    // dynamic programming! \o/
    // ok so here's how the algorithm works.
    // we go through the array from start to finish, and update the array
    //   elements at i-2, i-1, i+2, i+5, ... if solutions[i]+1 is less than
    //   (the corresponding index to update)'s current value
    // however, note that we might also have to update a value at a lower index
    //   than i (-2 and -1)
    // in that case, we will have to go back that many spaces so we can be sure
    //   to update *everything*.
    // so for simplicity, we just set the new index to be the lowest changed
    //   value (and increment it if there were none changed).
    let mut i = 1us;  // (the minimum positive value in CHANGES) - 1 (ugly hardcoding)
    while i &lt; count {
        let mut i2 = i+1;
        // update all rep-values reachable in 1 "change" from this rep-value,
        //   by setting them to (this value + 1), IF AND ONLY IF the current
        //   value is less optimal than the new value
        for c in CHANGES {
            if (i as i32) + *c &lt; 0 { continue; }  // negative index = bad
            let idx = ((i as i32) + *c) as usize;  // the index to update
            if idx &lt; count &amp;&amp; solutions[idx] &gt; solutions[i]+1 {
                // it's a better solution! :D
                solutions[idx] = solutions[i]+1;
                // if the index from which we'll start updating next is too low,
                //   we need to make sure the thing we just updated is going to,
                //   in turn, update other things from itself (tl;dr: DP)
                if i2 &gt; idx { i2 = idx; }
            }
        }
        i = i2;  // update index (note that i2 is i+1 by default)
    }

    solutions
}

fn shortest_path(rep: i32, nums: Vec&lt;i32&gt;, solutions: &amp;Vec&lt;i32&gt;) -&gt; i32 {
    // mercifully, all the test cases are small enough so as to not require
    //   a full-blown optimized traveling salesman implementation
    // recursive brute force ftw! \o/
    if nums.len() == 1 { count_changes(rep, nums[0], &amp;solutions) }  // base case
    else {
        // try going from 'rep' to each item in 'nums'
        (0..nums.len()).map(|i| {
            // grab the new rep value out of the vec...
            let mut nums2 = nums.clone();
            let new_rep = nums2.remove(i);
            // and map it to the shortest path if we use that value as our next target
            shortest_path(new_rep, nums2, &amp;solutions) + count_changes(rep, new_rep, &amp;solutions)
        }).min().unwrap()  // return the minimum-length path
    }
}

fn count_changes(start: i32, finish: i32, solutions: &amp;Vec&lt;i32&gt;) -&gt; i32 {
    // count the number of changes required to get from 'start' rep to 'finish' rep
    // obvious:
    if start == finish { 0 }
    // fairly intuitive (2f32 is just 2.0):
    else if start &gt; finish { ((start - finish) as f32 / 2f32).ceil() as i32 }
    // use the pregenerated lookup table for these:
    else /* if finish &gt; start */ { solutions[(finish - start - 1) as usize] }
}