p250: 50 ants move in grid, when two or more meet at same point, they disappear. each move at speed 1, and no two start at same position. The problem asks for number of ants remaining. Coordinates are from -1000 to 1000.
The only problem I know how to solve, basically after some limit, if two ants still not meet, they will never meet. So just iterate some fixed number of steps. The question is, what is the limit?
Since ants could meet at half way of an integer position, you need to multiply all coordinately by 2 so that they all meet in integer position. The limit is then (1000 - (-1000))/0.5 = 4000, to be safe you can use 4010 or 5000.
exod40 uses a different check, if (ox[i],oy[i]), (ox[j],oy[j) becomes (ox[j],oy[j]) (ox[i],oy[i]), that is, if two ants swap position, then they have to meet. the converse is true as well. so you can check that instead of multiply coordidates by 2.
No comments:
Post a Comment