DWITE Online Computer Programming Contest

Seating Arrangement

November 2010
Problem 2

It’s interesting to see where people sit when entering a room of other people that they do not know. One of the strategies is that when a person enters a room, they will sit at a location that maximizes the distance between themselves and the closest other person. If multiple seats are equally far, then the person will sit closer to the entrance of the room.

Here we will only be dealing with linear rooms. The seats are numbered from 1 to N, where 1 is the closest to the entrance and N is the furthest.

The input file DATA2.txt will contain 5 lines, each a pair of integers 1 ≤ N ≤ 1000 and 1 ≤ PN, separated by a single space. N is the number of seats in the room; P is the number of people entering this room.

The output file OUT2.txt will contain 5 lines, each an integer identifying the seat in which Pth person is seating.

Note: As the first person enters an empty room, every seat is equally far away from any other person, so they pick seat 1. For a room with 5 seats, with the entrance on the left, the seats will be filled up in the following order:

Sample Input (first 2 shown):
5 2
5 4
Sample Output (first 2 shown):