john9's blog

By john9, 12 years ago, In English

how do we know in problem 317B - Ants an array of a[147][147] will suffice?? thanks in advance

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It isn't; I find for n=30000 I need a 111x111 array. Except if you only consider the top-right quadrant or something (in which 56x56 suffices).

To figure it out? Probably emulating it for n=30000 is the fastest way, and also note that the bounding box won't get smaller wwith larger n so you're sure n=30000 is worst case.