Anti-Fire Fox

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type

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 \le N \le 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 \le M \le 5\,000 and 1 \le M \le 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 Specification

Line 1: Two integers – N and M.
The next M lines: The integer T_{i}, indicating that tree T_{i} is initially set on fire.

Output Specification

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

Sample Input

9 3

Sample Output



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.


There are no comments at the moment.