NPC2015F - Eefun and Doors
Eefun is a nomad who like to explore dungeons. On each dungeons, there's a valuable treasure waiting for him. However, Eefun should pass some obstacles to get the treasure.
In the dungeon, there are N doors which moves every second. These doors have width equal one and the dungeon has M width. When Eefun enters the dungeon (pass the first door), the timer start and the doors will start moving. The door will move to the right initially. When a door reach the end of the dungeons (at position M), then the door will change direction to left until reaching the leftmost position again (position 1). Eefun knows the initial position of all doors.
To pass a door, Eefun need to have same position with the door and he needs a second to pass a door. If next door has different position with Eefun, he can stay at the current position or move a position to the left or right.
After trying many dungeons, Eefun gets dizzy because he sees moving door everywhere. Therefore, he wants to know the minimum number of seconds to get the treasure. Eefun can obtain the treasure after he pass all the doors.
Input
First line contains 2 numbers, N and M.
Second line contains N numbers, the initial position of each doors.
Output
Output a single number, the minimum time Eefun needs to obtain the treasure.
Example
Input 1: 3 5
1 4 3 Output 1: 5 Input 2: 5 5
1 1 1 1 1 Output 2: 18
Explanation
For the first testcase, the initial doors are like picture below:|P****|
|-----|
|***P*|
|-----|
|**P**|
First, Eefun will enter the dungeon at time = 1 and the doors will start moving|*P***|
|E----|
|****P|
|-----|
|***P*|
|***P*|
|--E--|
|**P**|
|-----|
|***P*|
Then, Eefun will pass the second door which take one second.
|****P|
|-----|
|*P***|
|--E--|
|**P**|
Constraints:
- 1 ≤ Position of each door ≤ M
- 1 ≤ N ≤ 1.000.000
- 1 ≤ M ≤ 10.000
hide comments
Arianto Wibowo:
2015-12-25 11:33:36
@Bhargav Golla:
|
|
Bhargav Golla:
2015-10-28 02:22:29
Hi
|
Added by: | Louis Arianto |
Date: | 2015-10-10 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | NPC Schematics 2015 |