L. Vittorio Plays with LEGO Bricks

Vittorio is playing with his new LEGO Duplo bricks. All the bricks have the shape of a square cuboid with a \(2 \times 2\) square base and a height of 1. They can be arranged in the 3D space to build structures, provided that the following rules are met: 1. No two bricks can intersect, but they can touch on their faces. 2. The corners of every brick must have integer coordinates (so bricks are ax\(is-al\)igned) and the \(z\) coordinates of all corners must be n\(on-ne\)gative. 3. The square bases of every brick must be parallel to the ground (i.e. the plane \(z = 0\)). 4. The lower base of any brick that is not touching the ground must touch the upper base of some other brick in a region of positive area (when this happens, the two bricks stay attached to each other thanks to small studs). For example, this is a valid structure: Vittorio wants to build a structure that includes purple bricks in the following \(n\) positions: (\(x_{1}\), 0, h), (\(x_{2}\), 0, h), . . . , (\(x_{n}\), 0, h) — these are the coordinates of the centers of their lower bases; note that all of these bricks have \(y\) coordinate equal to 0 and \(z\) coordinate equal to \(h\). Vittorio will use additional bricks of other colors to support the purple bricks. He is willing to place bricks only in positions where the center of the lower base has \(y\) coordinate equal to 0. What is the minimum number of additional bricks needed? It can be shown that a valid construction always exists. Problem L: Vittorio Plays with LEGO Bricks SWERC \(2022-2023\)

The first line contains two integers \(n\) and \(h\) (\(1 \le n \le 300\), \(0 \le h \le 10^{9}\)) — the number of purple bricks and their common \(z\) coordinate. The second line contains \(n\) integers \(x_{1}\), \(x_{2}\), . . . , \(x_{n}\) (\(1 \le x_{i} \le 10^{9}\), \(x_{i}+1 < x_{i+1}\)) — the \(x\) coordinates of the purple bricks (centers of the bases), given in increasing order.

Print the minimum number of additional bricks needed.

생성자가 기록되지 않았습니다.

출처 ICPC SWERC 2022