Destroying Buildings in an Online Shooting Game

Two players participate in an online shooting game where $N$ buildings are arranged from left to right along a horizontal ground. The buildings are numbered from 1 to N and have distinct heights given by the sequence \(A_1, A_2, \dots, A_N\), which is a permutation of the integers \(1\) to \(N\).

The game proceeds in discrete time steps \(i \ge 1\). At each time step, both players simultaneously fire one bullet at a chosen integer height \(H\) (with \(1 \le H \le N+1\)). A bullet fired at height \(H\) will destroy the leftmost building (that has not been destroyed) satisfying \(A_j \ge H\). Note that if both players' bullets would target the same building (which happens if they choose the same firing height or if the building qualifies for both shots), then that building is destroyed only once.

The objective is to destroy all buildings in the minimum number of rounds. In each round, you must choose a pair \((H_1, H_2)\) representing the firing heights of the two players. One simple strategy is as follows: process the buildings in order from left to right. If it is possible to destroy two consecutive buildings in one round then choose firing heights that target them separately. In particular, if the current building has height \(A_i\) and the next building has height \(A_{i+1}\) with \(A_i < A_{i+1}\), then by choosing \(H_1 = 1\) (which always hits the leftmost building) and \(H_2 = A_i+1\) (which skips the first building, since \(A_i < A_i+1\), and targets the next building because \(A_{i+1} \ge A_i+1\)) the two buildings can be destroyed simultaneously. Otherwise, if pairing is not possible, both players fire with the same height, e.g. \(H = 1\), and only one building is destroyed in that round.

Your task is to implement the function:

vector< pair<int, int> > min_shooting_buildings(vector<int> A)

where the parameter A is an array of length \(N\) representing the building heights \(A_1, A_2, \dots, A_N\). The function should return an array of rounds. Each round is represented as a pair \((a, b)\) which indicates the firing heights for the two players. The number of rounds should be minimized so that all buildings are destroyed.

Note: Do not use any input/output functions in your submitted code. The function min_shooting_buildings will be called once directly.

inputFormat

The input is given as a vector (or array) of integers A of length \(N\), where each \(A_i\) (\(1 \le i \le N\)) denotes the height of the \(i\)-th building. The heights form a permutation of the integers \(1, 2, \dots, N\).

outputFormat

The function should return a vector (or list) of pairs (a, b) of length S where S is the minimum number of rounds needed to destroy all the buildings. Each pair denotes the firing heights chosen by the two players at that round.

sample

2
2 1

[(1, 1), (1, 1)]