Industrial Nim is the problem C of beta contest #15. Here I present and explain in detail an efficient solution of the problem that runs in time linear in n, which is at most 10⁵.

First of all, notice that the problem statement mentions ‘a well-known game Nim’. It also describes the rules but not the winning strategy; yet you are asked to determine which player wins. All of this means that if you do not know anything related to the winning strategy, you can simply look up the Nim game on Wikipedia and see if it has any useful information. It indeed does; specifically, you need to know that the winner in the Nim game, assuming both players play perfectly, is uniquely defined by the exclusive-or (XOR) sum of the stone heap sizes: if the sum is zero, then the first player loses, otherwise the first player wins. If you did not know this beforehand, you could have looked or, however unlikely, logically devised this on your own. I am not sure I can prove this fact, so I will just say the Wikipedia article includes a proof in case you are interested in it.

Now we have a straightforward solution of the problem: just XOR together the number of stones in every dumper and output ‘bolik’ if the sum is zero and ‘tolik’ otherwise. XOR is supported as an atomic operation in all programming languages I program in (in particular, in languages with syntax inspired by C, including C itself, two integers can be XOR’ed using the ^ binary operator), so there should be no problem in implementing this. However, the limits imposed on input data make this solution extremely slow: indeed, there can be up to 10⁵ quarries, and every quarry can have up to 10¹⁶ dumpers, so in total we can be required to calculate the XOR sum of 10⁵ × 10¹⁶ = 10²¹ integers, which is, well, quite many. So we are now in dire need of a fast way to XOR together all these 10²¹ integers.

Now it is the time to notice that these are not just any arbitrarily chosen integers: to remind you, we have a number of quarries and each consists of dumpers with x, x + 1, x + 2, ..., x + m - 1 stones. Put in other words, each quarry has all integers from x to x + m - 1 inclusive, or, in other words yet again, all integers up to x + m - 1 except all integers up to x - 1. What if we could somehow add together all positive integers up to x + m - 1 and subtract the sum of all integers up to x - 1, only substituting exclusive disjunction (XOR) for addition? And indeed we can. To understand this, you have to notice two nice properties that exclusive disjunction has: it is associative, meaning that (where the operator denotes XOR), and it is the inverse of itself, meaning that . The first property justifies our addition-subtraction approach itself, while the second one gives the definition for XOR subtraction: it is the very same XOR. Combining all this, we have:

where $f(x)$ is the XOR sum of all positive integers up to x inclusive. The conclusion we should draw from this is that if we can quickly calculate f(x - 1) for a given x, we can simply calculate for every quarry and take the XOR sum of all these values. As the number of quarries is just 10⁵, this should yield a very fast solution of the problem.

The last trick is to notice that f(x - 1) itself follows a nice pattern as x changes; for every four consecutive values of x starting with zero (assuming the XOR sum of an empty set it zero), this sum is equal to 0, x - 1, 1 and x. For example, f(1 - 1) = 1 - 0 = 0, f(9 - 1) = 9 - 1 = 8, f(10 - 1) = 1; the general form is easily provable by mathematical induction. We also have to take care to avoid integer overflows but no dumper has more than 10¹⁶ + 10¹⁶ - 1 ≈ 2^54.15 stones, so we only need 55 bits to store any XOR sum we ever calculate. Thus, 64-bit integers are more than sufficiently long, and the final code in C looks thus:

#include <stdio.h>
long long xorsum_1_to_x_but_1(long long x)
{
  switch (x % 4)
  {
  case 0:
    return 0;
  case 1:
    return x — 1;
  case 2:
    return 1;
  case 3:
    return x;
  }
}
int main(void)
{
  long long xorsum = 0;
  int i;
  scanf("%u",&i);
  while (i--) // repeat i times in total
  {
    long long x, m;
    scanf("%I64u%I64u", &x, &m);
    xorsum ^= xorsum_1_to_x_but_1(x) ^ xorsum_1_to_x_but_1(x + m);
  }
  puts(xorsum ? "tolik" : "bolik");
  return 0;
}

Finally, another implementation note. Unfortunately, Ruby’s long integer input is too slow even for this solution to finish before the time limit, so Ruby is not an appropriate programming language choice this time (notice how there is no Ruby submission in the submission list for this problem), but other languages work just fine. You might also have luck with emulating long integers in Ruby on your own; I am going to try this myself sometime.