Submit | All submissions | Best solutions | Back to list |
SCROLL - Spreadsheet scrolling |
Sruthi is looking at a spreadsheet containing N rows. Only K rows of the spreadsheet are visible at a time (If the top row is i, the bottom row will be i+K-1). In the beginning, rows 1 ... K are visible. Sruthi needs to read certain values from rows r1, r2 ... rM in that order. It is possible to scroll the spreadsheet so that the rows j ... j+K-1 can be viewed instead of the current i ... i+K-1. This operation counts as one scroll and its scroll length is defined as |j-i|
Find the minimum number of scrolls required so that Sruthi can read of all the M values in the given order. As there may be more than one way to do this, also find the minimum total scroll length required to do the reading in so many scrolls.
Input
The first line of the input contains the integer T (≤ 20), the number of test cases to follow.
The description of each test case begins with a line containing 3 integers N (≤ 108), K (≤ 108) and M (≤ 50000) as defined in the problem. Following this are M lines giving the row numbers from which values have to be read sequentially.
Output
Output two space separated integers in a line per test case : The minimum number of scrolls required and the minimum scroll length required for the minimum number of scrolls.
Example
Input: 2 20 10 2 10 20 20 10 2 10 7 Output: 1 10 0 0
Added by: | Raziman T V |
Date: | 2011-02-13 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | IOPC2011 |
hide comments
2014-02-18 16:18:38 Savan Popat
use long long instead of int |
|
2011-10-26 05:01:52 Raziman T V
Yes, do not assume any specific kind of ordering |
|
2011-03-21 10:22:12 Seshadri R
Can the M values in M lines be in any order (ascending, descending and random)? |