text:
Permutation? Permutatino!
Specifications
Your program must can take in an integer n, then take in n more strings (containing only alphanumeric characters) in your preferred method (separated by whitespace, file input, hash table etc.). You must then find the permutation before the inputted strings when sorted in lexicographical order, and output that in your preferred method.
If it is already sorted in lexicographical order, output the permutation in reverse regular lexicographical order.
Rules

Code can be just a function

If you pipe in from a file, you can to exclude the file name's length from your program (just the filename, not full path)

If there are repeated characters, take the permutation before the first occurrence of the repeats

Test cases
3 abc hi def

The possible permutations of this (in lexicographical order) are:
abc def hi
abc hi def
def abc hi
def hi abc
hi abc def
hi def abc

Now see that abc hi def is the 2nd permutation, so we output abc def hi.
If instead we pick abc def hi(the first permutation), then output abc def hi.
Another test case is in the title: your function should map Permutation to Permutatino
Scoring:
The winner is the code with the smallest score, which is the length of the code multiplied by the bonus.
Bonus:
20% -90% (to keep non-esolangs in the fight) of your byte count if you can do this in O(N) time.
-50% (stacks with the above -90% to give a total of -95%) if your solution isn't O(N!) which is listing out permutations, finding the element and getting the index, subtracting 1 from the index (keep it the same if the index is 0) and outputting the element with the subtracted index
With the above 2 bonuses, I won't be surprised if there's a 2 byte answer.
Hint: there is definitely a faster way to do this apart from listing all the permutations and finding the supposed element in the general case
Congrats to @Forty3 for being the first person to get the O(N) solution!
Here's some (C based) pseudocode:
F(A) { // A[0..n-1] stores a permutation of {1, 2, .., n}
  int i, j;
  for (i = n - 1; i > 0 && (A[i-1] < A[i]); i--)
    ; // empty statement
  if (i = 0)
    return 0;
  for (j = i + 1; j < n && (A[i-1] > A[j]); j++)
    ; // empty statement
  swap(A[i-1], A[j-1]); // swap values in the two entries
  reverse(A[i..n-1]); // reverse entries in the subarray
  return 1;
}

If you want to test if your program is O(N), try with n=11 and the strings being the individual letters of Permutation. If it takes longer than a second, it's most definitely not O(N).

Can we get more test cases?

@Okx If you test with the individual characters of the word "Permutation" and you get "Permutatino", then it's good. Of course, you have to wait about 5 hours if your solution isn't O(N). Other than that I'm a bit too lazy to add more test cases.

C++ has a linear time builtin for that but sadly even using that won't come close to a golfing language. Moreover: do you consider string compares to be a single step ?

Can we choose to only support char arrays as input, not string arrays?

@Okx My interpretation of that comment is that you want to only support chars instead of strings. In that case, no. If you can then extend that to support char array arrays, then yes.

@Christoph String compares are O(N), sum of O(N) and O(1) functions is still O(N). It really doesn't matter.

Where is the wrap around gone?

@GB It has disappeared into the garbage void. You don't have to handle wrap around anymore, now you have to handle special case when it's the first element

@Thunda My solution implements wrap-around since I wrote it before the spec change. Can i keep that behaviour?

@math_junkie yes, but it would be nice if you could add another solution :)

Things to avoid when writing challenges: Bonuses in code-golf

@mbomb007 I'll keep that in mind before making about 20 edits to my question next time.

In meta there is a "sandbox" where you can post an idea for a challenge and get feedback.

Python 2, 118 96 - 50% = 48 bytes
Takes input in the form ['abc','def','ghi']. Note that this solution returns the list reversed if the input is sorted, as per a previous spec.
def f(n):m=n[1:];S=sorted;a=S(n);return[a.pop(a.index(n[0])-1)]+a[::-1]if m==S(m)else[n[0]]+f(m)

Try it Online!
Seems to be the O(n) solution more efficient than computing all permutations.
Explanation: Recursively checks if everything after the current element is in sorted order. If so, returns the string immediately lexicographically before (a.index(n[0])-1)) the first element + the rest of the list reversed (a[::-1]).
Runtime: O(n^2 logn) In the worst case (list is reversed), the function will call sorted, which has a runtime of nlogn, for each element in the list (n times).

I didn't count this specifically but I believe you can save 2 bytes by extracting sorted to a variable. You can also remove the unnecessary space between return [b]. Otherwise, nice solution!

What do you take as input?

Surely, sorted can't have a worst-case performance better than O(n log n) for large enough problem sizes.

Using sorted() definitely makes this non O(n)

If you can prove that this isn't O(N!) then you can have a -50% byte reduction.

Python 2, 83 bytes
-18 bytes, thanks to @Emigna
Takes strings without number as input. As rules were clarified, this is the solution.
Try it online
from itertools import*
def F(A):s=sorted(permutations(A))+[A];print s[s.index(A)-1]

To clarify, if the input string is ordered, it should output the input string

You could save 18 bytes like this

@Emigna Thank you, this is neat

Jelly, 8 - 50% = 4 bytes
Œ¿’»1œ?Ṣ

Try it online!
Runs in O(n log n) time. (This typically takes just over a second, due mostly to Jelly's startup time – the time of just over a second is true for both very short and fairly long inputs. There's some variation in how long it takes in TIO; the fastest I've observed is 0.914 real, 0.772 user, 0.121 system.)
Explanation
Jelly actually has builtins for most of the challenge, but the way they're defined requires a sort. As far as I know, Jelly uses a comparison sort to sort lists of strings, which is what leads to the O(n log n) performance.
Œ¿’»1œ?Ṣ
Œ¿         Find index of {the input} in a sorted list of its permutations
  ’        Decrement it
   »1      saturating from below at 1
     œ?    Find the nth permutation of
       Ṣ   the sorted input

Œ¿ is a builtin with an optimized implementation (i.e. not slower than O(n log n)); it doesn't do brute-forcing.
Variations
If wrap-around is allowed (it was under an earlier version of the spec), you can remove the »1 for a 6-byte solution and a score of 3. (Most of Jelly's builtins, including the relevant ones here, will naturally wrap around in the absence of other hints about what to do with an out-of-range value.)

JavaScript ES6, 170 - 95% = 8.5 bytes

f=n=>a=>{while(--n&&a[n]>=a[n-1]);if(!n)return a;s=a.slice(--n);for(k=s.length;s[--k]>=a[n];);t=a[n];s[0]=s[k];s[k]=t;return a.slice(0,n).concat(s[0],s.slice(1).reverse())}

function Permutatino() {
  input = document.getElementById("input").value.split(" ");
  console.log(input)
  num= input.length;
  document.getElementById("output").innerHTML=(f(num)(input));
}
<input type="text" id="input" value="abc def ghi">
<button onclick="Permutatino()"> Run </button>
<pre id="output">

n=>a=>{while(--n&&a[n]>=a[n-1]);if(!n)return a;s=a.slice(--n);for(k=s.length;s[--k]>=a[n];);t=a[n];s[0]=s[k];s[k]=t;return a.slice(0,n).concat(s[0],s.slice(1).reverse())}

This code is a sequence of O(n) operations.
Try it online!
Explanation:
while(--n>0&&a[n]>=a[n-1]);

Find the last location in the array that is not sorted
if(!n)return a;

If already sorted return
s=a.slice(--n);

Get everything starting from the point where it was not sorted
for(k=s.length;s[--k]>=a[n];);

Find the index of the lexicographically closest element to the first element in the unsorted section which is lexicographically less than the first element.
t=a[n];s[0]=s[k];s[k]=t;

Swap the first element with the found element.
return a.slice(0,n).concat(s[0],s.slice(1).reverse())

Return the first section of the array + the first element of the second section + the reversed remainder of the second section of the array.
Time complexity of operations:
slice() O(n)
concat() O(n)
reverse() O(n)
indexOf() O(n) //essentially what the for and while loops were
O(Nlog(N)) solution 143 - 50% = 71.5 bytes
n=>a=>{while(--n&&a[n]>=a[n-1]);if(!n)return a;s=a.slice(--n).sort();t=s.splice(s.indexOf(a[n])-1,1);return a.slice(0,n).concat(t,s.reverse())}

Try it online!

Nice solution - takes advantage of the fact that the "right" side of the array will always be in ascending order to start with and need only be reversed. Nicely done.

JavaScript, 460 399 369 332 - 95% = 16.6 bytes
Unformatted
function f(n,v){var i=n-1,c=v[i],z="concat",y="slice",x="indexOf",w="reverse";for(;i>=0&&v[i]<=c;i--){c=v[i];}if(i==-1)return v;if(i==0){let s=v[z]().sort(),t=s[x](v[i])-1;return [s[t]][z]((s[y](0,t)[z](s[y](t+1)))[w]());}let p=v[y](0,i),r=v[y](i)[z]().sort()[w](),t=r[x](v[i])+1,m=r[t];r.splice(t-1,2,v[i]);return p[z]([m])[z](r);}

I am not convinced it is the O(n) solution but would appreciate if someone could take a quick glance and let me know. Also, I suspect there is some serious golfing which can be accomplished.. just haven't taken the time (yet).
Formatted
function f2(n, v) {
  var i = n-1,c = v[i],z="concat",y="slice",x="indexOf",w="reverse";
  for ( ; i >= 0 && v[i] <= c; i--) {
    c = v[i];
  }
  if (i == -1) return v;
  if (i == 0) {
    let s = v[z]().sort(), t = s[x](v[i]) - 1;
    return [s[t]][z]((s[y](0, t)[z](s[y](t + 1)))[w]());
  }

  let p = v[y](0,i),
  r = v[y](i)[z]().sort()[w](),
  t = r[x](v[i])+1,
  m = r[t];
  r.splice(t-1,2,v[i]);
  return p[z]([m])[z](r);

}

Fiddle: https://jsfiddle.net/n2Lmswxf/8/
Edit 1 - whitespace and function name per @Emigna's suggestions.
Edit 2 - using some pointers from the link @Emigna suggested. If I ever found this code in a system I had to maintain, I would hunt the developer down and flog him.
Edit 3 - @Thunda - I hope it wasn't presumptuous to recalc the savings based on my latest golfing.
Edit 4 - Removed a sort and simplified the final reassembly logic.

Just removing the unnecessary whitespace and renaming the function to r saves 61 bytes. There are probably some tips from here that could help you save even more.

I just tried with 26 characters (the alphabet, obviously) and it's wayyyyyyyy faster than all the other answers. Great, it's O(N), it's pretty much the algorithm that I used.

Can you provide complexity of sort, used here? I might guess, that it is bigger, that O(N). @Thunda, you should not judge complexity by speed of evaluation. There is a definition for O-notation.

@DeadPossum It's definitely O(N) (as far as I can tell). It's a bunch of O(N) loops (and splice) with a couple O(1) functions sprinkled about. Could definitely do with an explanation though. If you go into the fiddle provided and copy paste a (ridiculous amount) of strings, then it would definitely be faster than the current best O(N^2 log n) solution.

@Thunda Same question again - name complexity of sort function

@DeadPossum The sort function isn't relevant here, as the N is about the number of elements, not the length of the strings in question (unless my big O is rusty). Sort will have O(n log n) where n is the length of the string.

@Thunda Sort used here three times in different context. I believe, that it might be used not only for strings but for lists too. Detailed explanation of code is needed first to decide anything.

@DeadPossum - I added some comments to Fiddle v5 (https://jsfiddle.net/n2Lmswxf/5/) in hopes of clearing things up. There are, as best as I can tell, a maximum of two sorts. But they could be expensive in and of themselves. I might be able to reduce one of them at the cost of code length.

Thank you. At least your 2nd special case won't work at O(n) as it sorts array of values just one shorter than input. And so the whole answer can't be treated as O(n)

@DeadPossum - So, O(n log n), then?

@Forty3 Yes, that would be right estimate

Based on the explanation on Fiddle, this algorithm looks to be the same efficiency as mine

Then back to -50%? God I really shouldn't have put these bonuses in

05AB1E, 10 8 bytes
œ{ûD¹k<è

Try it online!
Explanation
œ{           # get a list of sorted permutations of the input
  û          # append a reversed copy excepting the last element of the original
   D         # duplicate
    ¹k       # push the first index of the input in the list
      <      # decrement
       è     # index into the list with this

With esolang answers this short, I think I need to up the bonus for an O(n) solution. This is ridiculously slow.

@Thunda: Yeah. As it calculates all permutations, the computation time increases drastically the more strings there are in the input :P

Ruby, 55 41 bytes
->a{x=a.permutation.sort;x[x.index(a)-1]}

Explanation:

permutation.sort does exactly what is written on the box
find the original string
go back one step, if index is 0, wrap around to -1

Pip, 21 bytes
20 bytes of code, +1 for -s flag.
(YSSST*PMa^sy@?a-:1)

Takes input as a single, space-delimited string on the command line. Try it online!
Explanation
                      a is 1st cmdline arg; s is space (implicit)
                      Part 1:
         a^s           Split a on spaces
       PM              Get all permutations of a
    ST*                Map str() to each of them
                       Because of the -s flag, this joins each sublist on spaces
  SS                   Sort the list using string comparison
 Y                     Yank into the y variable
                      Part 2:
            y@?a       Find index of a in sorted list of permutations y
                -:1    Subtract 1 (using compute-and-assign for lower precedence than @?)
(                  )  Index into part 1 using part 2 (Pip's indexing is cyclical, which
                      takes care of the already-ordered-input case)
                      Print (implicit)

Python 2, 73,81 bytes
s=s.split()
import itertools as i
x=sorted(list(i.permutations(s[1:],int(s[0]))))

Try it online!
Edit:
Missed the lexicographical sort part of question.

Your solution should be function or full programm, so you need to specify input. Like s=input() or def f(s), etc. And it counts in bytes.

Also you missed part of question about sorting

My bad. Didnt notice that lexicographical order part. @DeadPossum Thanks.

If I use your header, it's supposed to output abc def hi instead of the permutations

Check on try it online ink I've shared along with answer! It does give the permutation sorted lexicographically.

@KeerthanaPrabhakaran I mean in the output tab, it should have abc def hi instead of the list of permutations that you currently have

Oh. Just the strings in new line is it?

Mathematica, 57 bytes
(a=Permutations@Sort@#)[[Max[1,Position[a,#][[1,1]]-1]]]&

Anonymous function. Takes a list of strings as input and returns a list of strings as output.

Mathematica doesn't have built-ins for everything!

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
2016 Time Capsule String: Coverage
Consider the 74 characters from the 2016 time capsule string (note the leading space):
 !!!!!#$$%&())))*+...1449:=@@@AHILOQQQTTZ\\^`````````eefmpxy{||||~~~~~~~~~

Your task is to write as many programs as possible (in the same language) using these characters. The output of each program must be nonempty. When all of the programs and their outputs are considered, it must only use each of the 74 above characters no more than once.
Your score is determined by the number of programs you have written, with the total length of the programs being a tie-breaker (greatest length wins).
Some more rules:

Each program must terminate.
Each program must be a full program and output in a reasonable format.
All output to STDERR is ignored.
You may not run your program with any flags, except those required to run the program. (E.g., a -e flag that executes program source.)
If the program has output that cannot be suppressed, you may ignore when considering the output. (E.g., you may ignore trailing newlines.)
Each program should be able to be executed with empty stdin.

Example
If I had programs 4 and T1~ that outputted 4 and 9 respectively, they would, when considered together, be:
44T1~9

Which can be seen to be a subset of the capsule string. However, if I had programs 4@|4 and |e+ that outputted 4 and f respectively, they would be:
4@|44|e+f

And, since there are 3 4s, it is not a subset.

Can be disregard ans = .. in the output from MATLAB? That's allowed by default, except for challenges like "Hello, world" and other challenges with a very strict format.

Programs are not expected to produce different outputs, or be different themselves, are they?

@StewieGriffin Yes, you can, I'll edit to reflect this.

@LuisMendo Each program should be able to be executed with empty stdin.

@SparklePony I wouldn't quite say "absurd".

@SparklePony It'd be 21 (22 minus the backslash), and length 23 (add a backslash before two of the programs).

ConorO'Brien, @ETHproductions Sorry, I must have misunderstood the challenge.

PHP, 22 programs
Yeah, I get it's kind of boring.
Programs (separated by single newline):
!
!
$
)
)
.
4
@
Q
T
\
`
`
`
`
e
|
|
~
~
~
~

Output and programs combined:
!!!!$$))))..44@@QQTT\\````````ee||||~~~~~~~~

You could add Carrot to the list (but \ outputs nothing)

And so does $ (this gets user input). So in all, in Carrot, you have 2 less programs (remove the one for $ and \)

@Kritixi Lithos Does it support ?

@RobertFraser All I can see is a square. But sure, it outputs it if it is the code. You can try it here

@KritixiLithos That's a carrot emoji: http://emojipedia.org/emoji/%F0%9F%A5%95/

Japt, 11 13 programs, length 61
\x:#).&~L // outputs 9  (41 & ~100)
~T+~Tf)p  // outputs 4  ((~0 + ~floor(0)) ** 2)
$~Q$ *\~Z // outputs 1  (~'"' * ~0)
I%A^O||@{=!(Hmy))  // outputs 4  (64 % 10 ^ {} || function(X,Y,Z) { return function() { return ((U = !(H.m("y")))) } })
`!        // outputs !
`!        // outputs !
`.        // outputs .
`@        // outputs @
`Q        // outputs Q
`e        // outputs e
`|        // outputs |
`~        // outputs ~
`~        // outputs ~

It's awfully hard to come up with an answer that isn't just a string literal and outputs something other than a number...
Output and programs combined:
 !!!!!#$$%&())))*+...1449:=@@@AHILOQQQTTZ\\^`````````eefmpxy{||||~~~~~~~~~

I think I got 'em all...

When stripped down to the bare minimum:
#)&~L
~T+~T)p
~Q*~Z
I%A
`!
`!
`.
`@
`Q
`e
`|
`~
`~

It leaves these chars for future programs/outputs:
 !$$()).:=@HO\\^fmxy{||

You can trade two of $, ), or | for two of any of the chars in the nine string literals; that is, two of any of !.@Qe|~.
Additionally, you can trade out the Q in the third program for H or O, and the Z for H, O, @, or {.

PowerShell, 2 programs, length 31
+!!($eefmpxy =9)

Try it online!
Outputs 1.
Works by setting the variable $eefmpxy to 9, encapsulating that in parens, taking the Boolean-not ! of that (which turns it to $False), then the Boolean-not of that (which turns it to $True), then casts as an integer with +, turning it to 1. That's left on the pipeline and output is implicit.

4*!$AHILOQQQTTZ

Try it online!
Outputs 4.
Works by initializing the variable $AHILOQQQTTZ to the default of $null, the Boolean-not ! of which is $True. That's implicitly cast to an integer 1 due to the multiplication of 4*, so the result of 4 is left on the pipeline and output is implicit.

We're really limited in PowerShell for other things, as though we have plenty of pipe characters | to pipeline commands together, we only have one { and no }; too many ) for the lone (; the backtick ` is used as a "line continuation marker" to interpret multiple lines as one (used for readability), but we have no linefeed to go with it; and the ~ and ^ characters are "Reserved for future use" and thus toss a syntax error when you try to use them. So, most of the characters are useless, which is a shame.
While the # character starts a comment (and everything after it is completely ignored), it feels cheaty to use it that way, so I didn't include it above.

05AB1E, 4 programs, length 19
Programs
)O!            # outputs 1    fac(sum([]))
A`\            # outputs y    2nd_last(alphabet)
THf`x          # outputs 4    last_primefactor(int(10,16))*2
TL`\           # outputs 9    2nd_last(range[1 ... 10])

Output and programs combined
!)149AHLOTT\\```fxy

Cardinal, 1 program, length 73
%#~~~~~~~~~!!!!!+=.*449eefmpxyAHLOQQQTTZ`````````@@@$$I\\^{|||| ())))&..:

Outputs 1
Try it online!
Cardinal can only have 1 valid program that will do anything as there is only 1 %.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Carve some ASCII jewels!
March 13 is recognized as National Jewel Day, which is the theme of this challenge. So, given an integer n where n is greater than 0, create an ASCII jewel. For example:
n = 1          n = 2             n = 3
                                       ______
                     ____             /      \
 __                 /    \            \      /
/  \                \    /             \    /
\  /                 \  /               \  /
 \/                   \/                 \/

The bottom is defined as the very bottom of the jewel to the highest pair of of \/. The rest is the top. For the above example where n = 1:
Bottom: \  /    Top:   __
         \/           /  \

As you can see, the bottom is made of n + 1 layers of \/ with (1 * lines from the bottom) * 2 spaces in between with a maximum of n lines from the bottom of the jewel. If we take the second jewel (n = 2), we can see that:
 ____
/    \
\    /  2 (or n) layers from the bottom with 1*2*2 or 4 spaces in between \/
 \  /   1 layer from the bottom with 1*1*2 or 2 spaces in between \/
  \/    The bottom (0 layers) with 1*0*2 spaces or 0 spaces in between \/

The top is made of one pair of /\ with n*2 spaces in between with n*2 underscores on top.
Rules

Must be able to take in any nonzero positive integers as user input
Must create a jewel with the specs defined above (restated here):

The top is made of one pair of /\ with n*2 spaces in between with n*2 underscores on top.
The bottom is made of n + 1 layers of \/ with (1 * lines from the bottom) * 2 spaces in between with a maximum of n lines from the bottom of the jewel.

Trailing newlines after the jewel, or trailing spaces on each line are allowed.
No standard loopholes allowed

Winning Criteria
Least bytes wins!

Strictly speaking "nonzero positive" is redundant -- if you wanted to include 0, you'd have to say "nonnegative".

Can the answer be in PETSCII?

As the number gets higher the "jewels" start to look less like jewels and more like pizza slices, or maybe that's just lunch time talking.

Charcoal, 17 bytes
Code:
ＮβＧ←β_↙↙¹→↘⁺β¹‖Ｍ→

Explanation:
Ｎβ                      # Place the input into β
   Ｇ←β_                 # Draw a line of length β with _ as the filling character
        ↙                # Move the cursor one down and one left
         ↙¹              # Draw a line from the cursor position to one position ↙
           →             # Move the cursor 1 to the right
             ⁺β¹         # Add one to the input and..
            ↘            # Create a line pointing ↘, with the size calculated above
                ‖Ｍ→     # Mirror to the right

A very neat command is ‖Ｍ, which also automatically mirrors / into \.
Uses the Charcoal encoding.
Try it online!

That mirror command is really cool! Does it mirror brackets and other characters too? And is there a way to override that behavior?

@DJMcMayhem Yes and yes :)

Lol, you made diamonds out of charcoals!

Python 2, 101 98 95 bytes
lambda n:'\n'.join([' '+'__'*n,'/'+'  '*n+'\\']+[' '*i+'\\'+'  '*(n-i)+'/'for i in range(n+1)])

Try it Online!
Anonymous function that takes in a positive integer and returns a string
Python 3.6, 92 bytes (Thanks to Ben Frankel)
lambda n:f' {"__"*n}\n/{"  "*n}\\\n'+'\n'.join(' '*i+'\\'+'  '*(n-i)+'/'for i in range(n+1))

I couldn't find an online interpreter for this version, but it is a bit shorter due to f-strings in v3.6

You can save three bytes in Python 3.6: lambda n:f' {"__"*n}\n/{"  "*n}\\\n'+'\n'.join(' '*i+'\\'+'  '*(n-i)+'/'for i in range(n+1)). Taking advantage of f-strings.

I am pretty sure repl.it has a test suite for Python 3

@AnthonyPham repl.it and TryItOnline both use Python 3.5, I've checked

Whoa, finally! I wonder what took Python so long. Every language deserves string interpolation ...

05AB1E, 27 20 bytes
ƒN·ð×…\ÿ/}Â¹·'_×)R.c

Try it online!
Explanation
ƒ                      # for N in range[0 ... n]
 N·ð×                  # push N*2 spaces
     …\ÿ/              # push the string "\ÿ/" with "ÿ" replaced by the spaces
         }             # end loop
          Â            # push a reversed copy of the top of the stack
                       # (the largest row of the bottom of the diamond)
           ¹·'_×       # push input*2 underscores
                )      # wrap the stack in a list
                 R     # reverse the list
                  .c   # join the list on newlines, padding each row to equal length

Haha, nice! I believe you can change D„/\„\/‡ to Â.

@Adnan: Yes, I just realized that myself while working on an improvement :P

PHP, 123 Bytes
echo($s=str_pad)(" ",$z=1+2*$a=$argv[1],_).$s("\n/",$z+1," ")."\\\n";for($i=0;$i<=$a;)echo$s($s("",$i)."\\",$z-$i++)."/\n";

143 Bytes first version
for(;$i<3+$a=$argv[1];$i++)echo 1-$i?str_pad("",$i?$i-2:1):"/",str_pad($i>1?"\\":"",$i<2?2*$a:2*($a-$i+2)+1,$i?" ":_),$i<2?$i?"\\":"":"/","\n";

Try it here!

Where can I try this?

@AnthonyPham Here.

You can make it 119 bytes: http://ideone.com/RPCVZe

@Tschallacka if I assume that I use only a Linux Sytem

Well, as long as you don't edit with notepad.exe most editors have linux line endings... http://i.imgur.com/QZsmf4r.png windows console will happily display \n as a real newline. So yea, y ou can shave a few bytes of your answer.

V, 28 27 26 bytes
1 bytes saved thanks to @DJMcMayhem by using > instead of É
Ài__<esc>É ÙÒ r/Á\Ùr\$r/òÙlxx>

<esc> is 0x1b
Try it online!
Hexdump:
00000000: c069 5f5f 1bc9 20d9 d220 722f c15c d972  .i__.. .. r/.\.r
00000010: 5c24 722f f2d9 6c78 783e                 \$r/..lxx>

Explanation
Top:
Ài__<esc>              " Write argument times __
É<space>               " Prepend a space to the line
Ù                      " Duplicate line below cursor, cursor also moves down
Ò<space>               " Replace every character with a space
r/                     " Change the first character in the line to a /
Á\                     " Append a \ to the end of the line

Bottom:
Ù                      " Duplicate
r\                     " Change the first character in the line to a \
$r/                    " Replace the last character with a /
ò                      " Until a breaking error occurs do:
  Ù                    "  Duplicate
  lxx                  "  Remove 2 middle characters (spaces)
  >                    "  Indent by one space (implicit ending >)
                       " Implicit ending ò

Nice answer! You can change É<space> to > which at the end of a macro is implicitly filled in to >>

@DJMcMayhem Nice suggestion! So the > indents one space instead of by one tab?

Yep! That's cause I have set expandtab and set shiftwidth=1

Röda, 71 bytes
f n{a=" ";[a,"__"*n,"
/",a*2*n,`\
`];seq n,0|[a*(n-_),`\`,a*2*_1,"/
"]}

Try it online!

JavaScript (ES6), 80 bytes

f=
n=>` ${"_".repeat(n*2)}
/${s=" ".repeat(n)}${s}\\`+s.replace(/|/g,"\n$`\\$'$'/")
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

C, 131 bytes
i;f(n){for(printf(" ",i=0);i++<n*2;)printf("_");for(printf("\n/%*c\n",n*2+1,92,i=0);i++<n+1;)printf("%*c%*c\n",i,92,(n-i)*2+3,47);}

Try it online!

Where can I test this?

@AnthonyPham Tio link added.

Nice approach using printf's width to fill in the spaces. You can save 9 more bytes if you create a macro for the printf, remove the first i=0 and add a new variable j instead of re-initializing i to 0 on the second run: i,j;f(n){for(p(" ");i++<n*2;p("_"));for(p("\n/%*c\n",n*2+1,92);j++<n+1;p("%*c%*c\n",j,92,(n-j)*2+3,47));}

@Claudiu Thanks, but then the function would produce correct output only when it is called for the first time, and IIRC that's against the rules here. The function should work no matter how many times it's called.

@Steadybox oh I see, sorry for that. Does this apply for all codegolf questions? Looking just at this specific question it doesn't seem that it wants multiple inputs.

@Claudiu Yes, it applies for all questions.

You can use %define printf( p and replace every printf( with p.

@CoolGuy Thanks, but since there's another C answer already doing that,  I'll leave my answer as it is, because the two answers would be basically the same.

Python 3, 107 105 Bytes
n,s=int(input())," "
print(s+n*"__","/"+n*2*s+"\\",*[i*s+"\\"+2*(n-i)*s+"/"for i in range(n+1)],sep="\n")

Takes an int from Stdin

MATL, 34 bytes
QE:qgOO(t~E3O(GQXy3*tPgEhv'_/\ 'w)

Try it at MATL Online!
Explanation
QE:qg   % Create array [0 1 1 ... 1 1] of size2*(n+1)
OO(     % Turns last 1 into a 0: [0 1 1 ... 1 0]
t~      % Duplicate and negate: [1 0 0 ... 0 1]
E3O(    % Multiply by 2, turn last 2 into 3: [2 0 0 ... 0 3]
GQXy    % Push identity matrix of size n+1
3*      % Multiply by 3
tPgE    % Duplicate, flip, turn 3 into 2
h       % Concatenate the two matrices horizontally
v       % Concatenate all arrays vertically into a matrix
'_/\ '  % Push this string
w)      % Index (modular, 1-based) with the matrix into the string. Implicitly display

PowerShell, 76, 74 bytes
param($n)" "+'_'*2*$n;"/$(' '*$n*2)\";$n..0|%{' '*($n-$_)+"\$(' '*$_*2)/"}

Note: the online example contains a bit of wrapping as a demonstration. Place in a PoSH function or script to execute.
Try it online!

Welcome to PPCG! Nice first answer, and nice to see another PowerSheller around! You can save a couple bytes by using an incrementing variable in the loop -- ' '*$i++ instead of ' '*($n-$_).

Pyth, 44 Bytes
+" "*Q"__"++\/**2Qd\\jm+++*d\ \\**2-Qd\ \/hQ

try it!
explanation
The code consists of 3 parts:
+" "*Q"__"               # pretty straightforward " "+input()*"__"
++\/**2Qd\\              # d is defined as " ":  "/"+2*input()*d+"\"
jm+++*d\ \\**2-Qd\ \/hQ  # The third part is a bit more complex so I'll explain it further:

jm                   hQ  # Map some lambda function onto range(input()+1) and join the result on newlines
  +++*d\ \\**2-Qd\ \/    # Here d is the lambda argument (so I can't use it for spaces -.-)
  +++*d\ \\**2-Qd\ \/    # In Python: d*" "+"\\"+2*(Q-d)*" "+"/"

Python3, 104 bytes
n=int(input());print(" "+"__"*n+"\n/"+"  "*n+"\\")
for i in range(n+1):print(" "*i+"\\"+"  "*(n-i)+"/")

The program takes an integer from STDIN and returns the jewel into STDOUT.

Batch, 152 bytes
@set s=
@for /l %%i in (1,1,%1)do @call set s=  %%s%%
@echo  %s: =_%
@echo /%s%\
@set s=\%s%/
:l
@echo %s%
@if %s:~-2%==/ set s=%s:\  = \%&goto l

Tests:
n = 1
 __
/  \
\  /
 \/

n = 2
 ____
/    \
\    /
 \  /
  \/

n = 3
 ______
/      \
\      /
 \    /
  \  /
   \/

I will need a test suite to test this out.

Pip, 43 bytes
42 bytes of code, +1 for -n flag.
Ps.'_Xa*2P"/\"JsXa*2sX_.'\.sXa-_X2.'/M,a+1

Takes input as a command-line argument. Try it online!
Explanation
Constructs the first two lines separately, then the rest of the jewel with a map operation:
Ps.'_Xa*2
      a*2  Cmdline arg, times 2
   '_X     That many underscore characters
 s.        Concatenated to a space character
P          Print (with newline)

P"/\"JsXa*2
        a*2  Cmdline arg, times 2
      sX     That many space characters
 "/\"J       Join the string "/\" with the above as the separator
P            Print (with newline)

sX_.'\.sXa-_X2.'/M,a+1
                  ,a+1  Numbers from 0 up to and including a
                 M      Map the following lambda function:
sX_                      Space, repeated (fn arg) times
   .'\                   Concatenate \
      .                  Concatenate:
       sXa-_              Space, repeated (a - (fn arg)) times
            X2            repeated twice
              .'/        Concatenate /
                         Print result list, newline separated (implicit, -n flag)

Another solution
Also 42+1 bytes, this time with the -l flag:
Ys.tAL'_.sX2+,a.0(yALRVyRXD1-_)R0'\R1'/ZDs

TIO

Pyth, 38 bytes
j[*yQ\_j*yQpd"/\\"jm+*\ dj*\ y-Qd"\/"h

C, 115 bytes
#define p printf(
i;j;f(n){for(p" ");i++<n;p"__"));for(p"\n/%*c",2*n+1,92);j<=n;p"\n%*c%*c",++j,92,n*2-j*2+3,47));}

Try it online!
C, 123 bytes
Though the challenge doesn't require it, at the expense of 8 bytes the function can be made reusable (the first solution saves 8 bytes by relying on the implicit initialization of global variables).
#define p printf(
i;f(n){for(i=0,p" ");i++<n;p"__"));for(i=0,p"\n/%*c\n",2*n+1,92);i<=n;p"%*c%*c\n",++i,92,n*2-i*2+3,47));}

Try it online!

C#, 187 bytes
I'm sure there is a more compact solution out there but this is my first attempt:
var a=" "+new string('_',2*n)+"\n/"+new string(' ',2*n)+"\\\n";for(int i=n;i>0;i--){a+=new string(' ',n-i)+"\\"+new string(' ',2*i)+"/\n";}a+=new string(' ',n)+"\\/";Console.Write(a);

Try it online..

I will need a test suite to test this out.

JavaScript (ES6), 93 bytes
n=>(` 0
/2\\`+`
1\\4/`.repeat(k=++n)).replace(/\d/g,c=>' _'[+!+c].repeat(c&1?k-n-2:+c+--n*2))

Demo

let f =

n=>(` 0
/2\\`+`
1\\4/`.repeat(k=++n)).replace(/\d/g,c=>' _'[+!+c].repeat(c&1?k-n-2:+c+--n*2))

console.log(f(1))
console.log(f(2))
console.log(f(3))

dc, 121 bytes
?d1+sa2*sb32P[0sq[lvPlq1+dsqlj>h]shlj0<h]srlbsj95svlrx2607Plbsj32svlrx[\]p0sd[ldsjlrx92Plbsjlrxlb2-sb[/]pld1+dsdla>k]dskx

Try it online!

 Perl 5 109 94 + 1 (for flag -p) = 95 Bytes
Try it Online!
$l=$_*2;$s=" "."_"x$l."\n/"." "x$l."\\\n";$s.=" "x$_."\\"." "x($l-$_*2)."/\n"for 0..$_;print$s

Can be run like so:
perl -p <name of file> <<< n

Ungolfed
$l=$_*2;
$s=" "."_"x$l."\n/"." "x$l."\\\n";
$s.=" "x$_."\\"." "x($l-$_*2)."/\n"for 0..$_;
print$s

Explanation
#Sets $l to twice the value of the input 'n'
$l=$_*2;

#Top 2 rows of jewel adding $l underscores then newline
#followed by '/' and $l spaces.  The '\\\n' is an escaped '\' and a newline
$s=" "."_"x$l."\n/"." "x$l."\\\n";

#The meat of the jewel generation.  It contains a for-loop
#that iterates from 0 to $_ (the input value 'n')
#The loop uses its iterator value ($_ (which overrides the outer $_))
#to determine how many leading spaces it needs to apply.
#Then it adds a '\' with '\\' followed by $l-$_*2 number of spaces
#(the inside of the jewel).  Again, while under the umbrella of the for-loop,
#the $_ refers to the iterator value of the for-loop.
#After the inner spaces, it goes on to add in the '/' and a new line
$s.=" "x$_."\\"." "x($l-$_*2)."/\n"for 0..$_;

#Lastly, it prints the compiled Scalar value $s.  (In Perl, Strings are Scalar values or references
print$s

I will need a test suite to test this out as not everyone quite understands or has the ability to run this the way you have stated

@AnthonyPham I added the Try It Online link

Vyxal, 29 bytes
ð₴d\_*,\/₴d\\꘍,›(n\\꘍₴nεd\/꘍,

Try it Online!
=== The top ===
ð₴d\_*,
ð       # ' '
 ₴      # Print without newline
  d     # (implicit input) doubled
   \_*  # That many underscores
      , # Output with newline
=== Line 2 ===
\/₴d\\꘍,
\/       # Forward slash
  ₴      # Print without newline
   d     # (implicit input) doubled
    \\꘍  # That many spaces, plus a backslash
       , # Output with newline
=== The rest ===
›(             # (implicit input) incremented times do...
  n            # Iteration number...
   \\꘍         # ...spaces plus a backslash
      ₴        # Print without newline
       nε      # Difference of iteration number and (implicit input)
         d.    # Doubled
          \/꘍  # That many spaces, plus a forward slash
             , # Output with newline

Canvas, 12 bytes
_× ；＋/∔⁸╵＼∔║

Try it here!
right tool for the job.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Deranged !Combinatorics: Compute the Subfactorial
The subfactorial or rencontres numbers (A000166) are a sequence of numbers similar to the factorial numbers which show up in the combinatorics of permutations. In particular the nth subfactorial !n gives the number of derangements of a set of n elements. A derangement is a permutation in which no element remains in the same position. The subfactorial can be defined via the following recurrence relation:
!n = (n-1) (!(n-1) + !(n-2))

In fact, the same recurrence relation holds for the factorial, but for the subfactorial we start from:
!0 = 1
!1 = 0

(For the factorial we'd have, of course, 1! = 1.)
Your task is to compute !n, given n.
Rules
Like the factorial, the subfactorial grows very quickly. It is fine if your program can only handle inputs n such that !n can be represented by your language's native number type. However, your algorithm must in theory work for arbitrary n. That means, you may assume that integral results and intermediate value can be represented exactly by your language. Note that this excludes the constant e if it is stored or computed with finite precision.
The result needs to be an exact integer (in particular, you cannot approximate the result with scientific notation).
You may write a program or a function and use any of the standard methods of receiving input and providing output.
You may use any programming language, but note that these loopholes are forbidden by default.
This is code-golf, so the shortest valid answer – measured in bytes – wins.
Test Cases
n     !n
0     1
1     0
2     1
3     2
4     9
5     44
6     265
10    1334961
12    176214841
13    2290792932
14    32071101049
20    895014631192902121
21    18795307255050944540
100   34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601

Related.

Funciton, 336 bytes
Byte count assumes UTF-16 encoding with BOM.
┌─╖┌─╖  ┌─╖
│f╟┤♭╟┐┌┤♭╟┐
╘╤╝╘═╝├┘╘═╝├────┐
 │┌─╖ │ ┌┐┌┘╔═╗╓┴╖
 ││f╟─┴┐└┴┼─╢0║║f║
 │╘╤╝  │  │ ╚═╝╙─╜
 │┌┴╖ ┌┴╖┌┴╖ ╔═╗
 ││+╟┐│×╟┤?╟┐║1║
 │╘╤╝│╘╤╝╘╤╝┘╚╤╝
 └─┘ └─┘  └───┘

This defines a function f which takes one integer and outputs another integer at a 90 degree turn to the left. It works for arbitrarily large inputs.
Try it online!
Considering this is Funciton it's even reasonably fast (n = 20 takes about 14 seconds on TIO). The main slowdown comes from the double-recursion, as I don't think the Funciton interpreter automatically memoises functions.
Unfortunately, some monospaced fonts don't correctly monospace the ♭ and/or insert small gaps between the lines. Here's a screenshot of the code from TIO in all its beauty:

I think it might be possible to golf this some more, e.g. by changing the condition from >0 to <1 and swapping the branches of the conditional, so that I could reuse the number literal, or maybe by using a completely different formula, but I'm quite happy with how compact it is already.
Explanation
This basically implements the recursion given in the challenge, although it uses the base case !(-1) = !0 = 1. n-1 and n-2 are computed with the predecessor function ♭, and the intermediate result n-1 is reused in three places. There isn't much more to it, so I'll just quickly go through the control flow:
               ─┐
               ╓┴╖
               ║f║
               ╙─╜

This is the function header which emits the function's input n long the attached line. This immediately reaches T-junction, which simply duplicates the value.
        ┌┐┌┘╔═╗
        └┴┼─╢0║
          │ ╚═╝

The 0 box is just a numeric literal. A 4-way junction computes two functions: the path that leads off the bottom computes 0 < n, which we'll use to determine the base case. The path that goes left separately computes 0 << n (a left-shift), but we discard this value with the Starkov construct.
         ┌┴╖ ╔═╗
         ┤?╟┐║1║
         ╘╤╝┘╚╤╝
          └───┘

We lead this into the three-way conditional ?. If the value is false, we return the constant result 1. The loose end right of the ? is the function output. I'm twisting it around by 180 degrees here, so that the relative orientation of input and output of f is more convenient in the rest of the program.
If the condition was true, then the other value will be used. Let's look at the path that leads to this branch. (Note that Funciton's evaluation is actually lazy so that this branch will never be evaluated if it's not needed, which makes the recursion possible in the first place.)
        ┌─╖
      ┐┌┤♭╟┐
      ├┘╘═╝
      │
     ─┴┐

In the other branch we first compute n-1 and then split the path twice so we get three copies of the value (one for the coefficient of the recurrence, one for the first subfactorial, the last for n-2).
┌─╖┌─╖
│f╟┤♭╟
╘╤╝╘═╝
 │┌─╖
 ││f╟
 │╘╤╝
 │┌┴╖
 ││+╟
 │╘╤╝
 └─┘

Like I said, we decrement one copy again with another ♭, then we feed both n-1 and n-2 recursively to f and finally add the two results together in the +.
       ┐
       │
      ┌┴╖
     ┐│×╟
     │╘╤╝
     └─┘

All that's left is to multiply n-1 by !(n-1) + !(n-2).

Oasis, 5 bytes
Uses the formula given by Martin. Code:
+n<*X

Dissected version:
+n<*

with a(0) = 1 and a(1) = 0.
Explanation, a(n) =:
+       # Add the previous two terms, a(n - 1) + a(n - 2).
 n<     # Compute n - 1.
   *    # Multiply the top two elements.

Try it online!

Nice trick using X :-) BTW, did you implement this yet? One of these days we won't be able to get away with just changing the initial values

@LuisMendo Yes I did! It's used as a command flag (here is a link to the info page). Thank you for the suggestion :).

Haskell, 25 bytes
f 0=1
f n=n*f(n-1)+(-1)^n

Try it online! Uses the other recurrence from the OEIS page.

Jelly, 7 bytes
R=Œ!Ḅċ0

This approach constructs the derangements, so it's rather slow.
Try it online!
How it works
R=Œ!Ḅċ0  Main link. Argument: n

R        Range; yield [1, ..., n].
  Œ!     Yield all permutations of [1, ..., n].
 =       Perform elementwise comparison of [1, ..., n] and each permutation.
    Ḅ    Unbinary; convert each result from base 2 to integer. This yields 0 for
         derangements, a positive value otherwise.
     ċ0  Count the number of zeroes.

Brachylog (2), 11 bytes
⟦₁{p:?\≠ᵐ}ᶜ

Try it online!
Explanation
This is basically just a direct translation of the spec from English to Brachylog (and thus has the advantage that it could easily be modified to handle small changes to the specification, such as finding the number of derangements of a specific list).
⟦₁{p:?\≠ᵐ}ᶜ
⟦₁           Start with a list of {the input} distinct elements
  {      }ᶜ  Then count the number of ways to
   p         permute that list
      \      such that taking corresponding elements
    :?       in {the permutation} and the list of distinct elements
       ≠     gives different elements
        ᵐ    at every position

Languages with built-in solutions
Following xnor's suggestion this is a CW answer into which trivial solutions based on a single built-in to compute the subfactorial or generate all derangements should be edited.
Mathematica, 12 bytes
Subfactorial

sigh Mathematica...

Python 3, 35 32 bytes
f=lambda n:n<1or(-1)**n+n*f(n-1)

This uses the recurrence relation !n = n !(n-1) + (-1)n from @Laikoni's Haskell answer, with base case !0 = 1.
Try it online!

I think you can also use the other equation given here, which would save two bytes: f=lambda n:n<1or n*f(n-1)+(-1)**n.

Three bytes with a little reordering. ;)

The fun part of this recurrence is that if you push the base case back to n=-1, it doesn't matter at all which value you use. That could be useful for some languages (e.g. in Mathematica you could actually leave it undefined if that saved any bytes).

MATL, 9 8 bytes
:tY@-!As

Similarly to @Dennis' Jelly answer, this actually builds the permutations and counts how many of them are derangements; so it is slow.
Try it online!
:     % Input n implicitly: Push [1 2 ... n]
t     % Duplicate
Y@    % Matrix of all permutations, each on a row
-     % Element-wise subtract. A zero in a row means that row is not a derangement
!     % Transpose
A     % True for columns that don't contain zeros
s     % Sum. Implicitly display

M, 9 bytes
o2!÷Øe+.Ḟ

As you can see by removing the Ḟ, M uses symbolic math, so there will be no precision issues.
Try it online! Not the shortest solution that has been posted, but fast.
How it works
o2!÷Øe+.Ḟ  Main link. Argument: n

o2         Replace input 0 with 2, as the following formula fails for 0.
  !        Compute the factorial of n or 2.
   ÷Øe     Divide the result by e, Euler's natural number.
      +.   Add 1/2 to the result.
        Ḟ  Floor; round down to the nearest integer.

Mathics, 21 bytes
Round@If[#>0,#!/E,1]&

I am very new to this and have no idea what I'm doing...
Try it online!

Two alternatives at the same byte count: Round[(#/. 0->2)!/E]& and ±0=1;±n_:=Round[n!/E] (although I don't know whether Mathics supports single-byte encodings for source files like Mathematica does).

The first one works well (I think I know what it does), but Mathics doesn't appear to support ± in the second one. It would work with f, but at the cost of two bytes.

Another at the same byte count: Round[#!/E]+1-Sign@#&. Annoying initial values...!

05AB1E, 8 bytes
ÎƒN*®Nm+

Try it online!
Explanation
Î         # initialize stack with 0 and input
 ƒ        # for N in range [0 ... input]:
  N*      # multiply top of stack with N
    ®Nm   # push (-1)^N
       +  # add

Ruby, 27 bytes
f=->n{n<1?1:n*f[n-1]+~0**n}

~0**n is shorter than (-1)**n!

CJam (10 bytes)
1qi{~*)}/z

Online demo.
This uses the recurrence !n = n !(n-1) + (-1)^n, which I derived from n! / e and then discovered was already in OEIS.
Dissection
The loop calculates (-1)^n !n, so we need to take the absolute value at the end:
1     e# Push !0 to the stack
qi{   e# Read an integer n and loop from 0 to n-1
  ~   e#   Bitwise not takes i to -(i+1), so we can effectively loop from 1 to n
  *   e#   Multiply
  )   e#   Increment
}/
z     e# Take the absolute value

Quipu, 73 bytes
\/1&1&2&1&
1&++++^^[]
++2&0&--1&
2&[][]1&++
??**%%??/\
  3&4&
  []==
  --
Attempt This Online!
Based on Aaroneous Miller's factorial answer.
Equivalent pseudocode:
  a = [0, 0, 0, 0, 0]    // implicitly
0:
  a[0] = input + 1
  goto 2
1:
  a[1] = (a[1] + 1) * a[2] - a[3]
2:
  a[2] = (a[2] + 1) % a[0]
  if a[2] == 0 goto 4
3:
  a[3] = 2 - a[3]
  goto 1
4:
  a[4] = a[1] + 1
  print a[4]

MATLAB, 33 bytes
@(n)(-1)^n*hypergeom([1 -n],[],1)

Anonympus function that uses the formula in Section 3 of Derangements and applications by Mehdi Hassani.
Example use:
>> @(n)(-1)^n*hypergeom([1 -n],[],1)
ans =
    @(n)(-1)^n*hypergeom([1,-n],[],1)
>> ans(6)
ans =
   265

JavaScript (ES6), 26 bytes
f=n=>!n||n*f(n-1)-(~n%2|1)

Uses the recurrence relation from @Laikoni's answer. In ES7 you can save a byte by using +(-1)**n instead of -(~n%2|1).

PostScript, 81 76 69 bytes
Here are implementations of both formulae.
n*f(n-1)+(-1)^n
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul exch 2 mod 2 mul 1 sub sub}ifelse}def
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def

That version outputs a float. If it's necessary to output an integer:
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp cvi add}ifelse}def

which weighs in at 73 bytes.
The other formula is a little longer: 81 bytes.
(n-1)*(f(n-1)+f(n-2))
/f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def

These functions get their argument from the stack, and leave the result on the stack.
You can test the functions, either in a file or at an interactive PostScript prompt (eg GhostScript) with
0 1 12{/i exch def [i i f] ==}for

output
[0 1]
[1 0.0]
[2 1.0]
[3 2.0]
[4 9.0]
[5 44.0]
[6 265.0]
[7 1854.0]
[8 14833.0]
[9 133496.0]
[10 1334961.0]
[11 14684570.0]
[12 176214848.0]

Here's a complete PostScript file which renders the output to the screen or a printer page. (Comments in PostScript start with %).
%!PS-Adobe-3.0

% (n-1)*(f(n-1)+f(n-2))
% /f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def

% n*f(n-1)+(-1)^n
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def

% 0 1 12{/i exch def [i i f] ==}for

/FS 16 def              %font size
/LM 5 def               %left margin
/numst 12 string def    %numeric string buffer

/Newline{currentpoint exch pop FS sub LM exch moveto}def
/Courier findfont FS scalefont setfont
LM 700 moveto

(Subfactorials) Newline
0 1 12{
    dup numst cvs show (: ) show f numst cvs show Newline
}for
showpage
quit

-1 3 2 roll exp is a fair bit shorter than exch 2 mod 2 mul 1 sub.

@PeterTaylor So it is! :) I forgot about exp :oops: However, it returns a float, and I think I need to output an integer to conform to the question.

I think you can still chuck in a cvi and make a saving. (Note: untested, but from reading the doc I think it should work).

@PeterTaylor Yes, cvi works, and it's still shorter than my previous version.

Raku, 22 bytes
1,{++$*$_+($*=-1)}...*

Try it online!
This is an expression for the infinite sequence of subfactorials.

Python 3, 27 bytes
f=lambda n:n<1or f(n-1)*n^1

Try it online!
Based on @Laikoni's formula and the observation that n and !n always have opposite parity.
Broken down:
n odd -> n x !(n-1) also odd -> adding (-1)^n=-1 is the same as unsetting the lowest bit
n even -> n x !(n-1) also even -> adding (-1)^n=1 is the same as setting the lowest bit
therefore flipping the lowest bit works in either case

PHP, 69 Bytes
function f($i){return$i>1?$i*f($i-1)+(-1)**$i:1-$i;}echo f($argv[1]);

use this way a(n) = n*a(n-1) + (-1)^n

You only need to give the function, not the full program, so you can drop the last 17 chars. There's a further saving by not special-casing input 1. I think the two savings take it down to 47 bytes.

PHP, 50 44
for(;$i++<$argn;)$n=++$n*$i-$i%2*2;echo$n+1;

Run with echo <n> | php -nR '<code>
The beauty of a(n) = n*a(n-1) + (-1)^n is that it depends only on the previous value. This allows it to be implemented iteratively instead of recursively. This saves a long function declarition.
-6 bytes by @Titus. Thanks !

-1 byte: $i++<$argv[1]. -2 bytes: for(;$i++<$argv[1];)$n=++$n*$i-$i%2*2;echo$n+1;. (-3 bytes with -R and $argn.)

@Titus someone got bored ? :D would you mind giving me an example for -R and $argn?

Not bored, but eager to golf. See php.net/manual/de/features.commandline.options.php: echo  | php -nR ''. example: http://codegolf.stackexchange.com/a/113046

@Titus did I get it right ? ;-)

Alice, 20 18 bytes
1/o
k\i@/&wq*eqE+]

Try it online!
Explanation
This uses the recursion from Laikoni's answer, !n = n !(n-1) + (-1)n. Similar to the Funciton answer, I'm using the base case !(-1) = 1. We put that 1 on the stack with 1.. Then this...
.../o
...\i@/...

... is just the usual decimal I/O framework. The main code is actually
&wq*eqE+]k

Broken down:
&w    Push the current IP address N times to the return address stack, which
      effectively begins a loop which will be executed N+1 times.
  q     Push the position of the tape head, which we're abusing as the
        iterator variable n.
  *     Multiply !(n-1) by n.
  e     Push -1.
  q     Retrieve n again.
  E     Raise -1 to the nth power.
  +     Add it to n*!(n-1).
  ]     Move the tape head to the right.
k     Jump back to the w, as long as there is still a copy of the return
      address on the return address stack. Otherwise, do nothing and exit
      the loop.

Julia 1.0, 21 bytes
!n=n<1||n*!~-n+(-1)^n

Try it online!
with the following formula from the OEIS page:
$$ a(0)=1,\ a(n) = n*a(n-1) + (-1)^n $$

TI-Basic, 12 19 bytes
Ans!∑((-1)^K/K!,K,0,Ans

with the following formula from the OEIS page:
$$ a(n) = n!*\sum_{k=0..n}(-1)^k/k! $$

previous answer (12 bytes)
round(Ans!/,0)+not(Ans

this is invalid because  (euler number) is stored with limited precision, which is explicitly forbiden by the challenge

05AB1E, 8 bytes
0Lλè+N<*

I know there is already a great 8 bytes 05AB1E answer, but this uses a completely different approach.
Try it online or verify all test cases.
Explanation:
  λ       # Start a recursive environment,
   è      # to output the (implicit) input'th value
0L        # Starting with a(0)=1 and a(1)=0
          # Where every following a(n) is calculated as:
    +     #  Add two values together
          #  (since + requires 2 arguments, it implicitly uses a(n-2) and a(n-1))
     N<*  #  Multiplied by n-1
          # (after which the result of a(input) is output implicitly)

Pari/GP, 26 bytes
n->n!*sum(k=0,n,(-1)^k/k!)

Try it online!

Pari/GP, 28 bytes
f(n)=if(n,n*f(n-1)+(-1)^n,1)

Try it online!

Pari/GP, 15 bytes (invalid because of finite precision)
n->n!\/exp(!!n)

Try it online!

Actually, 18 bytes
;!@ur⌠;!@0Dⁿ/⌡MΣ*≈

Try it online!
Explanation:
;!@ur⌠;!@0Dⁿ/⌡MΣ*≈
;                   duplicate input
 !                  n!
  @ur               range(0, n+1) (yields [0, n])
     ⌠;!@0Dⁿ/⌡M     for each i in range:
      ;               duplicate i
       !              i!
        @0Dⁿ          (-1)**i
            /         (-1)**i/i!
               Σ    sum
                *   multiply sum by n!
                 ≈  floor into int

A 12-byte version that would work if Actually had more precision:
;!╠@/1½+L@Y+

Try it online!
Unlike all of the other answers (as of posting), this solution uses neither the recursive formula nor the summation formula. Instead, it uses the following formula:

This formula is relatively easy to implement in Actually:
!╠@/1½+L
!         n!
 ╠        e
  @/      divide n! by e
    1½+   add 0.5
       L  floor

Now, the only problem is that the formula only holds for positive n. If you try to use n = 0, the formula incorrectly yields 0. This is easily fixed, however: by applying boolean negation to the input and adding that to the output of the formula, the correct output is given for all non-negative n. Thus, the program with that correction is:
;!╠@/1½+L@Y+
;             duplicate input
 !            n!
  ╠           e
   @/         divide n! by e
     1½+      add 0.5
        L     floor
         @Y   boolean negate the other copy of the input (1 if n == 0 else 0)
           +  add

Keeps giving negative answers for me...

@LeakyNun That's because of precision limits. For large inputs (around n = 100), (-1)**n/n! can't be represented with double-precision IEEE 754 floats. That's acceptable according to the challenge.

Even for n=4...

@LeakyNun Oh. I don't know why I was using floored division. Fixing it now.

16 bytes

C, 34 bytes
a(n){return n?n*a(n-1)-n%2*2+1:1;}

Explanation:
a(n){                            } define a function called a of n
     return                     ;  make the function evaluate to...
            n?                :1   set the base case of 1 when n is 0
              n*a(n-1)             first half of the formula on the page
                      -n%2*2+1     (-1)**n

Mathematica, 40 bytes
±0=1;±1=0;±n_:=(n-1)(±(n-1)+±(n-2))

Which comes in at 31 bytes under the default ISO 8859-1 encoding.

Stacked, 30 bytes
[:[#-::#-f\f+*]$not,\2<# !]@:f

Try it online!
Simple recursive function. Uses the fact that !n = not n for n < 2. Call as n f.

R, 47 bytes
n=scan();`if`(!n,1,floor(gamma(n+1)/exp(1)+.5))

Uses the same formula as Mego's answer.
Alternate method, 52 bytes using the PerMallows library
n=scan();`if`(!n,1,PerMallows::count.perms(n,n,'h'))


text:
Office Escape: Plan your way out!
It's the final sprint... and half your team is off ill. You're working late, just making your last commit for the day, looking forward to... why have the lights turned off? I don't remember the security guy coming around... oh no! I left my keys at home!
As the horror of the situation sinks in, you decide that you are going to escape.
Task Summary
To effect your escape, you need a plan! However, you know that any plan has a chance of failing, and different plans require different amounts of effort.
Being hungry, tired, and an engineer, you decide to write a short program to determine the best way to escape the complex, balancing the concerns of probability of success and the effort it will require.
You make a map of the building:
#######################
#                =    #
!                =    !    <-- window
#          !     =    #        (freedom!)
#################=    #
#    #           =    #
#    #           =    #
#    #           =    #
# o  !   # #  !  =    #
##|  !  ## #  !  =    #
#######################

  ^  ^           ^
  me my door     ludicrously high shelves
     (locked)    (climbable)

To escape the office, you will have to move yourself off the map. Here you see there are 2 windows (!), either one would lead you to freedom, but only one of them accessible.
We define 'off the map' as having your feet outside the bounds of the map
Cell types
  - empty, you can be here (i.e. the escapee can consume this cell)
# - solid (your desk, your in-tray), you can't be here, but you can stand on it
! - destructible, (co-worker's desk, door, window), you can't be here until you smash it first (turning it into an empty cell)
= - climbable, (fire ladder, filing cabinet, etc.), you can be here

The cells originally consumed by the escapee taken to be empty.
Action Specifications
You have a number of possible actions at your disposable. These are defined by simple state transitions with some integer success probability.
For example, for walking, you move the escapee one cell, which we represent with this transition:
Step
1 stp, 100%, mirror
 o.            o
 |.   -->      |
 #            #

The dots show cells that must be empty (or climbable, but not solid or destructible) either because we move into it or through it.
The 100% means you have an 100% chance of not hurting yourself and ending your daring escape. All probabilities will be integer percentages between 1% and 100% inclusive.
The first diagram shows the initial state (standing on something solid, standing next to some empty space).
The second diagram shows the terminal state (moved into the empty space).
There is no requirements for any unspecified cells (spaces, ) on the left (initial state) to be anything in particular.
Unspecified cells (space, ) on the right (terminal state) should be the same as they were prior (e.g whatever was behind the escapee, or whatever I happen to be walking onto (be it empty space or otherwise).
Note that all right-hand (terminal state) diagrams will only change cells from destructible to empty, no other changes can occur.
"1 stp" means it costs 1 stp: we define the "stp" as the amount of energy required to take a step.
"mirror" means this action has two forms. The "right" action is shown, the "left" action is an exact mirror, for example:
.o
.|
 #

is the mirror (Left) form of
o.
|.
#

The right action is called " Right" (e.g. "Step Right") The left action is called " Left" (e.g. "Step Left")
In these diagrams, the escapee is show by
o
|

when standing (2 units tall) and
%

when crouching (1 unit tall).
Cells that must be solid or destructible are indicated by a hash, #.
Cells that must not be solid or destructible are indicated by a dot ..
Cells that must be destructible are indicated by a bang !.
A newly created empty space is shown by an underscore _.
x is a reference point that doesn't move (it doesn't exist, no constraint on what that cell must be (like a space )).
Note: we ignore the issue of rapid deceleration when you hit the floor, and yes, in this game you can do totally epic jumps onto ladders)
Step
1 stp, 100%, mirror
 o.         o
 |.  -->    |
x#        x#

Climb off
1 stp, 100%, mirror
 =         =
 o.  -->    o
 |.         |
x=        x=

Shuffle
3 stp, 100%, mirror
 %.         %
x#   -->  x#

Clamber Up
10 stp, 95%, mirror
 o.         %
 |#  -->    #
x#        x#

Drop
0 stp, 100%
 o
 |  -->   o
x.       x|

Drop (Stand)
0 stp, 100%
 %        o
x.  -->  x|

Climb Up
2 stp, 100%
 =        o
 o  -->   |
x|       x

Crouch
2 stp, 100%
 o
 |  -->   %
x#       x#

Stand
4 stp, 100%
 .        o
 %  -->   |
x#       x#

Short Jump
4 stp, 95%, mirror
 o..          o
 |..  -->     |
x#         x#

Long Jump
7 stp, 75%, mirror
 o...           o
 |...  -->      |
x#          x#

High Jump
12 stp, 90%, mirror
 ..         o
 o.  -->    |
 |
x#        x#

Put your back into it!
20 stp, 80%, mirror
 o!.         _o
 |!.  -->    _|
x#         x#

Punch
8 stp, 90%, mirror
 o!        o_
 |   -->   |
x#        x#

Kick
8 stp, 85%, mirror
 o         o
 |!  -->   |_
x#        x#

Stamp
8 stp, 90%
 o        o
 |  -->   |
x!       x_

Plans
A plan is a sequence of the actions defined above. For example:
Step Left
High Jump Left
Crouch
Shuffle Left
Shuffle Left
Stand
Long Jump Left
Put your back into it! Left
Step Left

Note the inclusion of the drops. The rules should be set up to stop you doing anything but dropping, but you still have to plan for it!
Any plan has a required effort, which is the sum of the efforts for each step. There is also a success probability, which is the product of the success probabilities of each action. Simple example:
Step Right:          1stp,  100%
Long Jump Right:     7stp,  75%
Step Right:          1stp,  100%
Stamp:               8stp,  90%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Step Left:           1stp,  100%
Step Left:           1stp,  100%
High Jump Left:      12stp, 90%

Effort = 1+7+1+8+1+1+12 = 31
Success Probability = 75%*90*90% = 60.75%

A 'worked example' for the map at the top of page can be found as a gist.
Input
The input comes in two parts, an integer, and an array or string of characters.
The integer is your minimum acceptable (percent) probability of success. It is to be interpreted as a percentage, so 80 means your plan must succeed with probability no less than 80%.
A valid map is a rectangle that includes the standing escapee (minimum size of 1x2) and no unspecified symbols. All rows will be the same length. You may accept input as a 1-dimensional delimitated string (delimiter must be a single consistent character, or one of CRLF and LFCR pair), as a similar 1-dimensional array, or a 2-dimensional array. If your chosen input format does not indicate the width or height of the map in some way, you may accept additional arguments for these (you must clearly state this in your answer). You may mix command line arguments and standard input if it suits you (e.g. map from stdin, minimum success probability from argv). The following are example valid and invalid maps.
Valid:
o
|

Valid:
  #     #
  !   o #
  !   | #
#########

Invalid (no escapee):
  #     #
  !     #
  !     #
#########

Invalid (escapee always starts standing):
  #     #
  !     #
  !   % #
#########

Invalid (invalid symbol):
  #     #
  !  ~  #
  !     #
#########

Invalid (not a rectangle/different length rows):
  #     #
  !   o #
  !   | #
#########

You may assume your input is valid (I don't care what your program does if it is handed invalid input).
Output
Output is text (ASCII). May be returned as a string, or printed to standard output. The plan must be delimitated by a LF, CRLF, or LFCR. Similarly, there must be another LF, CRLF, or LFCR after the Required Effort. A trailing line break is optional.
You must output an optimal plan along with the effort it requires, or "There is no hope!" if no such plan exists. You do not need to output the probability of success. This text may or may not have trailing line break.
An optimal plan is defined as a plan (see above) requiring the minimum effort with at least the given probability of success. Note that you probability calculations must be exact, you may not assume that floating point is good enough (This is why I don't expect you to output them). I will try to design test cases to fairly test this (if you pass them and don't make any daft assumptions then you may consider your submission valid).
Format:
Required Effort: <effort>
<plan>

For example, for the input
50
  #     #
  !   o #
  !   | #
#########

An appropriate output would be:
Required Effort: 23
Step Left
Step Left
Step Left
Kick Left
Punch Left
Step Left
Step Left
Step Left
Step Left

The probability of success here is 76.5%.
For the same map, but a minimum probability of success of 80%, you would have to "Put your back into it", which would require more effort but fulfil the success probability criteria.
If the minimum probability of success were greater than 80%, you'd need to think a bit harder (either punch or kick through part of the door and shuffle out).
If the minimum probability of success were 100%, you'd have to print out "There is no hope!"
Examples
It is possible that there are more than one valid plans for an input, you're output doesn't need to be these exactly, but it must have the correct required effort, and be a valid plan. You can use the verifier to check your solutions (see below)
Input:
100
o
|

Output:
Required Effort: 0
Drop

Input:
5
# =      #
# =      !
# = !  ! !
# =#######
# =      #
# =   o  #
# = ! |  #
##########

Output:
Required Effort: 57
Step Left
Kick Left
Step Left
Step Left
Step Left
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
High Jump Right
Long Jump Right
Step Right
Drop
Kick Right
Crouch
Shuffle Right
Shuffle Right

Input:
60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

Output:
Required Effort: 58
Step Left
Kick Left
Crouch
Shuffle Left
Shuffle Left
Stand
Punch Left
Clamber Up Left
Shuffle Left
Drop (Stand)
Kick Left
Crouch
Shuffle Left
Shuffle Left

For the same map, but 80%, the output should be:
There is no hope!

For the same map, but 50%, the Required effort becomes 56 with a different plan)
Input:
50
#######################
#          #     =    #
!          #     =    !
#          #     =    #
######  #####!## =### #
#=   ##       #  =    #
#=#############  =    #
#=               =    #
#= o             =    #
#!!|             =    #
#######################

Output:
Required Effort: 121
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
Long Jump Left
Step Left
Step Left
Stamp
Drop
Drop
Crouch
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Stand
Clamber Up Left
Stand
Clamber Up Left
Stand
Step Left
Step Left
Step Left
Step Left
Punch Left
Clamber Up Left
Shuffle Left

Input:
66
######
#  ###
#o ! !
#| ! !
### ##
######

Output:
Required Effort: 37
Step Right
Put your back into it! Right
Kick Right
Crouch
Shuffle Right
Shuffle Right

Input:
This one is designed to check a number of false assumptions one may fall victim to, and consequently may look a bit odd
30
###################
# ## # # #   #  = #
! ## #   #   #  = #
#      #   #    = #
##  ############= #
# ## #         #= #
# =  #         #= #
! =  #         #= #
# =  #         #= #
#o=  !          ==#
#|=  !           =#
#!= # ==########==#
#   #    !   !!  =#
#   #    !!  !  = #
#   # !!!!#########
#   # #           #
#   # #           #
###################

Output with chance of success constraint 30:
Required Effort: 199
Long Jump Right
Put your back into it! Right
<snip>

Output with chance of success constraint 32:
Required Effort: 200
Long Jump Right
Punch Right
<snip>

Using the map at the top as an input, with probability of success constraint 1%, you should get a Required Effort of 116 (chance of success ~32%, this took about 20seconds to run in my test program).
Victory Criteria
This is code-golf, may the shortest code win.
To be eligible, your function or program must work and be able to solve each of the above testcases in under 30minutes on a reasonable machine. My solver does them each in under 30seconds. If the test script (below) runs in under 30minutes, you're certainly good to go.
Example Solver, Verifier, Test Script, and TestCases (with solutions)
C# code for a solver, and solution verifier, is available here as a gist. The gist also contains file.txt, which is a machine readable (enough) form of the actions described above, and is required for the program to run. Any discrepancy between that file and spec is not intentional.
The gist also contains a number of test cases (including all the examples above), and a PowerShell script to automatically run a submission against them. If the script tells you that a particular test has failed, you can run OfficeEscapeSolver.exe testcase<n>.txt outputFromYourProgram.txt to see more details. Example solutions for these test cases are in another Gist.
All the code is a complete mess (though ungolfed), but you shouldn't need to stray far from the static void Main(...) to change the amount of output (feel free to use this information, I've provided it for your benefit!).
Passing a test-case does not necessarily mean that your output is well formed, as the script and verifier are very generous. Your output must match the specification above for your submission to be valid.
If you think you've found a bug with the solver or testscript, an error in file.txt, or a dodgy testcase, then please comment on this post or otherwise ping me on SE Chat; I probably won't notice any other attempt to communicate.
I won't provide the test script in Bash or Batch, because I don't know them, but I'm happy to include a translation and will write a C# version if people want one.
Post Amble
Got questions? Don't delay, ask them today!
This task is meant to require effort, to give serious golfers something to sink their teeth into.
My thanks to ais523 for his feedback on Input/Output.
I can provide more testcases in the gist file if people want more (don't want this post to become any longer), or want to provide some of their own.

Great challenge! I will definitely give this a shot when I have time. :)

You know, the dangers of falling (or rather the rapid deceleration at the bottom) could have been modelled by giving the drop transition a probability of 95% or so. ;) Nice challenge!

can you escape though a sky light or tunnels? i.e. top and or bottom of field? or only left or right?

@Moogie you can indeed! So long as your feet are free, you are free (for example, see the 1x2 testcase, where the solution is just drop once). I'll add a small testcase to gist to test going off the ceiling.

@VisualMelon are ladders '=' deemed to be solid for the purposes of your action diagrams?

deleted. formatting...

I ask because you mention that you can jump onto ladders so does that mean that ladders are represented by '.' rather than '#' in your action diagrams? if so then you cannot perform any real action if you land on the top of a ladder as all the actions apart from drop or climb require that you be standing on a '#' or is it that a ladder acts as both a '#' and a '.' ?

@Moogie ladders/climbable things are represented by =. These are considered non-solid, and so can take the place of a . or '=' in the action diagrams, but not a '#'. I say you can jump onto ladders because you only have to have the = above to climb up, it doesn't matter whether you have just fallen a long distance, or jumped up from the floor. You cannot stand on/jump from/walk along ladders. Hope that somehow clarifies it! If you are confused about a particular situation you can feed it into the example solver, or ping me a gist in chat and I'll put it in the test cases.

@Moogie added a new testcase to the gist (testcase11) that tests no fewer than 3 jumping/dropping onto ladder situations, and the solution as a gist.

@VisualMelon thanks for the gist, however that particular test case does not really clarify my understanding for when the character performs a 'Step Right' and ends up such that immediately below the character is a '=' and ' ' immediately above. From my understanding of the allowed actions, only Drop is allowed. i.e. you cannot Step or perform any other action. is this the expected behavior?

@Moogie indeed, only Drop would be allowed ('=' can only substitute for '.' or '=') Is there a particular bit of the spec that is especially confusing (it's all confusing) that I should patch up? Perhaps we could discussion this in chat if you think it is unclear?

Let us continue this discussion in chat.

Added bounty to question. This is a great question that deserves answers.

Perl 5, 1425 1464 1481 1469 1485 1438 bytes
That was a fun challenge! And, shockingly, it looks like I have the shortest code so far at a little under 1.5kB! :)
Pretty sure I finally got this working. The delimiter used is :, and there is extra padding of two rows on top and one column on either side. So for your input of:
60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

my program would take: (NB: there must be a colon at the end, but not at the beginning!)
60
#########:# ! #   #:! ! ! o #:! # ! | #:#########:

I use regexes to translate from one map to another and solve by brute force. However, I don't add maps to the list if that map has already been reached with less effort and greater or equal probability. Maps are removed from the list once all possible movements from that point have been exhausted. The program ends successfully when it matches a regex that shows I have reached the side or the bottom and ends with "There is no hope!" when the list of maps is exhausted.
Unfortunately, there was a great deal of efficiency traded away to take off a few bytes, so the golfed version is rather slow ;) Perl seems to find the evals in particular to be quite painful.
Without further adieu,
chop($P=<>,$_=<>);s/:/ : /g;$w++until/:.{$w}:/;$z=$"x$w;$_="(.{".$w--."})"for($c,$h,$i,$j);$_="$z:$z: $_$z";$n="[ =]";$d="([!#])";@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp';@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15);sub M{$_=join":",map{join'',reverse split//}split/:/};push@M,[$_,0,100,$P];$B{$_}=100;@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8);@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10);$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/';do{sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}};die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M));$e=-1;while(++$e<@M){@t=@{$M[$e]};$m=$_=$t[0];die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/);for$x(0..15){$_=$m;$t=$t[2]*$P[$x];if($G==$E[$x]+$t[1]and$t>=$t[3]*100){&$x;eval"$z Right/";A;$_=$m;M;&$x;M;eval"$z Left/";A;}}}}

For the sake of sanity, here's the same thing with newlines and a few comments:
chop($P=<>,$_=<>); #Take input
s/:/ : /g; #Pad columns on either side so escapee can leave that way
$w++until/:.{$w}:/; #Find width
$z=$"x$w;#Setup a blank line for use in padding later
$_="(.{".$w--."})"for($c,$h,$i,$j); #Set up some generic capturing regexes for reuse
$_="$z:$z: $_$z"; #Pad the top and bottom so the escapee can leave those ways
$n="[ =]"; #Regex for nonsolid block
$d="([!#])"; #Regex for solid block
@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp'; #Movement names
@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";#Movement regexes
eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15); #Setup methods to apply regexes. Name of these methods are 0,1,2,3, etc, so we can easily call them in a loop
sub M{$_=join":",map{join'',reverse split//}split/:/}; #Method to mirror the map. All the regexes are right-moving, so the mirror effects are achieved by M;&$x;M
push@M,[$_,0,100,$P]; #Array for initial map position. Encodes: [Map,Effort value,Probability value 1,Probability value 2,Movements(initially undef)]. Two integers are used for the probability to avoid floating point (although after enough steps they overflow and are automatically converted to f.p.)
$B{$_}=100; #Hash map to hold best probability of reaching a map. A new map is never added if it requires at least as much effort and doesn't give a better probability.
@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8); #Effort values
@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10); #Probability values
$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/'; #Setup map values
do{ #Loop over all efforts. Do-while loop starts at undef, which is converted to zero automatically when used in a numeric context
    sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}}; #Method to add a map to list.
    die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M)); #Pares away maps that no longer can produce new maps, and prints "There is no hope!" to stderr if there are no maps left.
    $e=-1;
    while(++$e<@M){ #Loop over all maps. Note that this loops over even maps that are created during the loop
        @t=@{$M[$e]}; #Dereference info about each map
        $m=$_=$t[0]; $Setup map variables
        die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/); #Checks if escaped, and gives message if so.
        for$x(0..15){
            $_=$m; #Put map into $_
            $t=$t[2]*$P[$x]; #Probability calculation
            if($G==$E[$x]+$t[1]and$t>=$t[3]*100){ #If effort values are right and probability is over threshold
                &$x; #Run regex
                eval"$z Right/"; #Set up map info
                A; #Add map to list @M (only if probability works out right)
                $_=$m;
                M;&$x;M; #Same thing, but mirrored now (generates movement left)
                eval"$z Left/";
                A;
            }
        }
    }
}while(++$G)

I can already see a couple places to pare away a few more bytes, but I don't want to go through all the testing again yet. Later! :)
Edit: Added some padding below as well to fit your output more exactly when escaping through the floor. Removed some of the evals, so the code might run faster now, too!
Edit: Wasn't handling ladders and drops quite right. Still doesn't handle ladders quite right... Trying to fix that now.

Glad someone else have fun with it! I'm afraid that I can't accept this as it is currently, as you can't assume that the input with have those extra rows or padding at the top (but at ~1.5kB, just inserting straight away shouldn't hurt too much!). I don't have Perl on this machine, but I'll try and find a way to test this today, so I can check it works and runs in sensible time frame, and report back!

@VisualMelon No problem, I changed the input method and added the padding in manually. It does tend to blow up in the larger puzzles, but it runs in a reasonable time frame for most of your test cases.

Still not tested this, but I note you said that this uses a regex to detect when you go off the side or bottom, but you can also escape off the top (see testcase10 which was added for this purpose), just in case you missed this

@VisualMelon Ah, I assumed that to escape from the roof the escapee would have to get on top of the room and then walk to the side, off the roof. I see the relevant sentence now. I'll fix it :)

Nice job! This might get the bounty.

Unfortunately, this seems to be giving incorrect solutions... I've written a wrapper to run my tests on it, but it has failed testcases 0, 11, and 3 so far (passed 1, 10, and 2, currently running testcase 4). The wrapper (powershell) can be found as a gist. The issue might be with my wrapper, but it seems to work fine for some (e.g. testcase 2). testcase0 is producing "There is no hope!", and testcase 3 is attempting to "Drop" while crouched (which is illegal, it should "Drop (Stand)"). Shout if I can help atall!

@VisualMelon For the "Drop (Stand)" thing, that was intentional. I could have sworn you had it outputting "Drop" for both sorts of dropping... Whelp, that's easy enough to fix. I'll look into the rest... I don't really know powershell, so I'll just check those test cases with my code. If it is the wrapper I can just provide one for you ;)

My solver has always produced "Drop (Stand)", but it's not impossible that I've misstated something somewhere. You can find example solutions to all test cases in this gist. If you can provide a different wrapper (ideally in Perl or something else I can run under windows) I'll be glad to try it (all it does is replace the line-feeds with colons were appropriate, and direct stderr to stdout). I must now sleep, but good luck to you!

@VisualMelon I believe you! It's more than likely a failure in might reading skills! Anyway, sleep well :)

Could you add a TIO link?

This is still producing incorrect results: testcase0 passes!; testcase1 crashes my checker because the Required Output is missing (should print the 0 but doesn't), testcases 2, 3, and 10 pass, but testcase11 produces an invalid plan. The details are in this gist (see end of check file for where it fails), but the details are a 3k lines file, and seems to prefer to crash my browser than display. What happens is that it tries to Climb off Left at the bottom of the ladder, which is not allowed (must be a = beneath).

@VisualMelon Yeah, I noticed a major bug I'd introduced very shortly before you posted that. Got rid of the offending code, and trying to figure out how to more reasonably implement what it was doing now...

C#, 1814 1481 1395 bytes
What a slog!! I'm really rather pleased with this now!
using C=System.Console;using System.Linq;class S{string M,N="";int x,y,E,c;decimal P=1;static void Main(){int W=0,H=0,x,i,j,k,X,Y,f,m,P=int.Parse(C.ReadLine());string l,M="",B,R="There is no hope!";for(;(l=C.ReadLine())!=null;H++,M+=l)W=l.Length;x=M.IndexOf("|");var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();for(var N=D.ToDictionary(s=>R,s=>D);D.Count>0;D.Sort((z,w)=>z.E-w.E)){S s=D[f=0];D.Remove(s);var n=N[l=s.x+s.M+s.y+s.c]=N.ContainsKey(l)?N[l]:new S[0].ToList();if(n.All(o=>o.P<s.P|o.E>s.E)){n.Add(s);X=s.x;Y=s.y;if((X|Y|-X/W-Y/H)<0){R="Required Effort: "+s.E+s.N;break;}for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(',');f<26;){l=A[k=f*3%48];B=A[++k]+(f>15?" Right":f>9?"":" Left");M=A[++k];m=f++/16*2-1;var Q=s.M.ToArray();var K=s.P*l[4]>=P&s.c==l[k=0]%2;for(j=Y-3;j++<=Y;)for(i=X;i!=X+m*M.Length/4;i+=m)if((K&="==  *!!##*!*=*|*| o*o ".Contains(""+((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ')+M[k]))&M[k++]==33)Q[x]=' ';if(K)D.Add(new S{M=new string(Q),N=s.N+"\n"+B,x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100});}}}C.Write(R);}}

Try It Online
Complete program, takes input to STDIN, output's to STDOUT.
Essentially a re-write of my original solver, using a simple and inefficiently implemented BFS to find the optimal path.
It's reasonably fast, can't be much slower than my other implementation (I've not really timed it though), certainly runs within the time limit. Much of the cost is the Action table, which is encoded as comma separate values which record the name, 'match/smash' map, and other properties of each available action.
It starts by reading in the minimum probability of success and the map. Then it locates the escapee, removes him from the map, and creates a 'search state' containing this information.
Then, it performs the BFS, which repeatedly looks at the next due state with the least effort (ensuring it finds an optimal solution).
Before expanding the node, it compares it's effort and probability of success to previous nodes with the same map and escapee location, and rejects itself if a better route has been found to this state already.
If it survives this, it adds itself to the 'seen' table so it can reject state later on. This is all for performance, and without it the branching factor would be huge.
Then it checks if the escapee is off the map. If it is, then it wins! It back-tracks the state (each prior state is recorded with each state) and builds the plan (in reverse) before exiting the BFS loop.
Otherwise, it tries to apply every action, and adds any that can be applied to the due queue, before sorthing this queue so that we get the least effort state next iteration.
Formatted and commented code:
using C=System.Console;
using System.Linq;

// ascii
//   32
// ! 33
// = 61
// . 46
// * 42
// # 35
// | 124
// 0 48

class S // SearchState
{
    string M, // map
        N=""; // plan
    int x, // pos x
        y, // pos y
        E, // effort
        c; // crouching?
    decimal P=1; // chance (Probability)

    static void Main()
    {
        int W=0, // map width
            H=0, // map height
            x, // various temps
            i, // local x
            j, // local y
            k, // position in match/smash map
            X, // s.x
            Y, // s.y

            // action loop
            f, // T idx
            m, // A idx, action mirror (direction)

            P=int.Parse(C.ReadLine()); // probability of success constraint

        string l, // line, Act 'block' params, map hash, match pairs; all sorts!
            M="", // initial map
            B, // name of action
            R="There is no hope!"; // result string

        // read map
        for(;(l=C.ReadLine())!=null; // while there is input to read
            H++,M+=l) // increment height, and append to M
            W=l.Length; // record width

        // detect the escapee
        x=M.IndexOf("|");

        // create first state, and add it to Due list
        var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();

        // 'seen' table, stores all the states we've been in which looked similar
        for(var N=D.ToDictionary(s=>R,s=>D); // these values are meaningless (and necessarily can't interfere), we just use it to save having to spec the type
            D.Count>0; // keep going until we run out of states to expand (-> no escape)
            D.Sort((z,w)=>z.E-w.E)) // enforce Breadth First Search
        {
            // get next State to expand, and remove it from Due
            S s=D[f=0];
            D.Remove(s);

            // retrieve or create seen list
            var n=N[l=s.x+s.M+s.y+s.c]= // store it, and cache it, l is 'hash', containing map and escapee state
                N.ContainsKey(l)? // already got a seen list for ths map?
                N[l]: // then use it!
                new S[0].ToList(); // otherwise create a new (empty) one

            // perf: only proceed if we havn't seen this map with better Effort and Chance yet
            if(n.All(o=>o.P<s.P|o.E>s.E))
            {
                // record that we have been seen
                n.Add(s);
                X=s.x;
                Y=s.y;

                if((X|Y|-X/W-Y/H)<0) // check if we our outside the bounds - this took 2.5hour to write. 1 byte.
                { // quit if both are positive or both are negative
                    // freedom
                    R="Required Effort: "+s.E+s.N;

                    // finished
                    break;
                }

                // [Crouch,Effort,dx,dy,Probability],Name,MatchSmash (first 10 are mirrors)
                // 0110d,Step,*** * #*,
                // 0110d,Climb off,=** * =*,
                // 3310d,Shuffle,***** #*,
                // 2:1/_,Clamber Up,*** *##*,
                // 0420_,Short Jump,****  *  #**,
                // 0730K,Long Jump,*****   *   #***,
                // 0<1/Z,High Jump,  * **#*,
                // 0D20P,Put your back into it!,****! *! #**,
                // 0800Z,Punch,***!**#*,
                // 0800U,Kick,*****!#*,
                // 0001d,Drop,*** ,
                // 1001d,Drop (Stand),*** ,
                // 2200d,Crouch,***#,
                // 1400d,Stand,* *#,
                // 020/d,Climb Up,=***,
                // 0800Z,Stamp,***!

                // attempt to expand this node with every action
                for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(','); // Act string
                    f<26;) // read A into T // (cycle over first 10 twice, making them mirrors)  (very convieniently, 3*16==48=='0'==x!)
                {
                    // 'parse' next action
                    l=A[k=f*3%48]; // [Effort,Crouch,dx,dy,Probability]
                    B=A[++k]+(f>15?" Right":f>9?"":" Left"); // action name
                    M=A[++k]; // Match and Smash table (4x?, escapee at 0,2, #: solid, !: smashable (and is smashed), .: empty,  : don't care, =: climable)
                    //c=l[1]-48; // crouching transition (0: standing -> standing, 1: crouching -> standing, 2: standing -> crouching, 3: crouching -> crouching)
                    m=f++/16*2-1;

                    // this will be the new map
                    var Q=s.M.ToArray();

                    // K is whether we are allowed to apply this action
                    var K=s.P*l[4]>=P& // within chance limit
                        s.c==l[k=0]%2; // crouching matches

                    // compare the map to the Match/Smash map, to make sure we can apply this transform (and smash any ! we meet)
                    for(j=Y-3;j++<=Y;) // for the 4 rows
                        for(i=X;i!=X+m*M.Length/4;i+=m) // for each column (a.M has height 4, but variable width)
                            if((K&= // K still true?
                                "==  *!!##*!*=*|*| o*o ".Contains(""+ // check for an allowed pairing (cache pairing in M) (this includes the escapee, much cheaper to do this than remove him)
                                    ((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ') // we are within bounds and match, we are out of bounds (empty)
                                    +M[k])) // char from MatchSmash map
                                &M[k++]==33) // if it is destructible ('!' == 33)
                                Q[x]=' '; // then blank it out (x is necessarily set by the cell check)

                    if(K) // if K holds
                        D.Add(new S{M=new string(Q),N=s.N+"\n"+B, // assemble plan as we go (this will chew up memory, but none of the problems are big enough for it to matter)
                            x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100}); // add the resulting state to Due
                }
            }
        }

        C.Write(R);
    }
}

Nice job! It amuses me endlessly that your old score and new score are anagrams of each other... lol

Has C# beaten Perl?