All submissions for this problem are available.
At Area-51, USA, there is an advanced biological laboratory with compartments (numbered 1 to M) forming a straight line segment. There are genetically modified monkeys present in the lab, which can communicate with each other as humans do. Compartments number i and i+1 are adjacent, and monkeys in adjacent compartments are called "neighbours." A wall with a window separates adjacent compartments, and neighbours can communicate through that window.
All monkeys live in peace until a monkey is released. When that happens, the released monkey's neighbours find out, and each communicates this to his other neighbour in their own language. That monkey passes it on to his other neighbour, and so on until they reach a monkey with no other neighbour (because he is in cell 1, or in cell M, or the other adjacent cell is empty). A monkey who discovers that another monkey has been released will angrily break everything in his cell, unless he is bribed with a banana. So, after releasing a monkey in cell A, all monkeys housed on either side of cell A - until cell 1, cell M or an empty cell - need to be bribed.
Assume that each compartment is initially occupied by exactly one monkey, and that only one monkey can be released per day. Given the list of Z monkeys to be released in Z days, find the minimum total number of bananas needed as bribes if the monkeys may be released in any order.
Note that each bribe only has an effect for one day. If a monkey who was bribed yesterday finds out about another released monkey today, then he needs to be bribed again.
The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is as:
where M is the number of compartments and Z is the number of monkeys to be released.
This will be followed by a line with Z distinct cell numbers (of the monkeys to be released), sorted in ascending order and space separated.
For each test case, output a line with the minimum number of bananas needed as bribes.
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 10000
- 1 ≤ Z ≤ 100
- Z ≤ M
- Each cell number is between 1 and M, inclusive.
Input: 2 8 1 3 20 3 3 6 14 Output: 7 35
|Time Limit:||0.204615 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions