DWITE '10 R2 #2 - Seating Arrangement

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
DWITE Online Computer Programming Contest, 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 will contain 5 lines, each a pair of integers 1 \le N \le 1000 and 1 \le P \le N, 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 will contain 5 lines, each an integer identification of the seat in which P^\text{th} person is seated.

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:

H:*****
H:1****
H:1***2
H:1*3*2
H:143*2
H:14352

Sample Input

5 2
5 4

Sample Output

5
2

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.