Anti-Fire Fox

One day, a terrible fire is started in the forest where the fox and wolf families live (probably by jealous, inferior humans). The animals can easily escape harm themselves - however, they wish to save as many trees as they can. Naturally, the foxen can put out fires with their tails, however this can only be done at a rate of one tree per minute.

The forest consists of a single row of N (1 ≤ N ≤ 1,000,000,000) trees, which the foxen have numbered from 1 to N from left to right. Each tree is in contact with the trees immediately to its left and right.

At the beginning, M (1 ≤ M ≤ 5000 and 1 ≤ M ≤ N) different trees are set on fire. At the end of every minute after that, each untouched tree that is next to any burning trees catches on fire itself. It takes one minute for a tree to burn down entirely.

During each minute (including right after the trees are initially set on fire), the foxen can choose a single tree to brush their tails. This tree stops burning immediately (if it's currently on fire), and due to the amazing properties of fox tails, becomes impervious to fire forever.

The process continues until not a single tree is on fire, at which point the foxen don't even need to count how many trees are still standing, seeing as they calculated it when they first detected the forest fire. The foxen have of course acted so as to maximize the number of trees preserved, so the question is… how many is that?

Input

Output

A single integer - the maximum number of trees that the foxen can save from being burnt down.

Sample Input

9 3
3
2
8

Sample Output

6

Explanation

The forest initially looks like this, with burning trees represented by '*', burnt-down trees by 'x', and protected trees by 'P':

1 * * 4 5 6 7 * 9

The foxen put out the fire at tree 8 during the first minute, while the other fires spread:

* x x * 5 6 7 P 9

The foxen now put out tree 4, and the other fire has nowhere to go:

x x x P 5 6 7 P 9

In the end, 3 trees have burned down, leaving 6 standing.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 20, 2009
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

This problem can be done greedily by assembling some sort of a strategy - which fire is it best to stop? Observe that some fires will soon run out of trees to spread to anyway (if they hit another fire or the edge of the forest), so it would seem that it's best to cut off the fires that are the most isolated first.

Also, N is far too big to deal with, so instead you should work with M, just storing the locations of each of the fires and the directions in which they're spreading.

Why foxes?

What is this "foxes"?

The plural of fox is foxen, and I'll answer your question with another - why NOT foxen?