Find the optimal nim move

Pyth, 23 bytes

eSs.em*,kd!xxxFQb-bdSbQ

Try it online: Demonstration

This iterates over all possible moves and even does sorting. Therefore it has a time-complexity of O(N*log(N)) and a memory complexity of O(N), where N is the sum of the input list or the number of items.

Because of the bad time complexity, this might not be a valid answer. Though it solves all games, that you can play in real life with real objects, instantly.

Explanation:

                          implicit: Q = input list
   .e                 Q   map each (index k, item b) of Q to:
     m              Sb      map each d of [1, 2, ..., b] to:
       ,kd                      the pair (k, d)
      *                       multiplied by
             xFQ                xor of all numbers in Q
            x   b               xor with b
           x     -bd            xor with b-d
          !                     not (1 if xor==0 else 0)

So the input [1, 2, 0, 0, 5] gives [[[]], [[], []], [], [], [[], [4, 2], [], [], []]]

  s                       add all lists to one big list
 S                        sort

Now it looks like this: [[], [], [], [], [], [], [], [4, 2]]

e                         pick the last element and print

Pyth, 33 22 21 20 19 bytes

eS.e*<JxxFQbb,k-bJQ

You can try it in the online compiler here.

Thank you to Jakube for removing 12 bytes and Maltysen for removing an additional byte!

This prints a winning move from the current position. If there are no winning moves, it doesn't print anything.

I used the algorithm on wikipedia. Here is the breakdown:

  .e              Q    While enumerating every element in the input:
      J                    Assign variable J to:
        xFQ                 Every element of the input bitwise xor'ed together,
       x   b                bitwise xor'ed with the current element of the input
             ,             Create a tuple containing:
              k             The index of the current element, and
               -bJ          the difference between the current element and J
    *<J     b              Put that tuple into a list if J < b, otherwise put an empty tuple
 S                     Sort the list
e                      Print the last element of the list

CJam, 21 20 bytes

Saved a byte compared to original version, and error handling also works now:

l~__:^f^.-_:g1#_@=S\

Try it online

Input is a CJam array, e.g.:

[1 2 3 4 5]

If no solution is found, it prints -1 0, which meets my understanding of the output requirements.

Explanation:

l~      Get input.
__      Make two copies for following operations.
:^      Reduce with xor operator, producing xor of all columns.
f^      xor all input values with the result. For each column, this calculates
        the value that the column would have to change to make the overall
        xor zero. Consider this the "target values".
.-      Subtract the target values from the input values.
_:g     Per element signum of difference between target value and input value.
1#      Find index with value 1, which is the first positive value.
_@=     Get the value at the index.
S\      Put a space between index and value.