// ////////////////////////////////////////////////////////
// # Title
// Stone Game
//
// # URL
// https://projecteuler.net/problem=260
// http://euler.stephan-brumme.com/260/
//
// # Problem
// A game is played with three piles of stones and two players.
// At her turn, a player removes one or more stones from the piles.
// However, if she takes stones from more than one pile, she must remove the same number of stones from each of the selected piles.
//
// In other words, the player chooses some `N>0` and removes:
//
// `N` stones from any single pile; or
// `N` stones from each of any two piles (`2N` total); or
// `N` stones from each of the three piles (`3N` total).
//
// The player taking the last stone(s) wins the game.
//
// A winning configuration is one where the first player can force a win.
// For example, (0,0,13), (0,11,11) and (5,5,5) are winning configurations because the first player can immediately remove all stones.
//
// A losing configuration is one where the second player can force a win, no matter what the first player does.
// For example, (0,1,2) and (1,3,3) are losing configurations: any legal move leaves a winning configuration for the second player.
//
// Consider all losing configurations `(x_i,y_i,z_i)` where `x_i <= y_i <= z_i <= 100`.
// We can verify that `sum{x_i+y_i+z_i} = 173895` for these.
//
// Find `sum{x_i+y_i+z_i}` where `(x_i,y_i,z_i)` ranges over the losing configurations with `x_i <= y_i <= z_i <= 1000`.
//
// # Solved by
// Stephan Brumme
// August 2017
//
// # Algorithm
// Every position `(0,0,s)` is won because the current player will take all `s` stones from the third pile and win immediately.
// Every position `(0,s,s)` is won because the current player will take all `s` stones from the second and from the third pile and win immediately.
// Every position `(s,s,s)` is won because the current player will take all `s` stones from all three piles and win immediately.
// More specifically, these positions are won because there is a transition from the current state to the final state `(0,0,0)`.
//
// If the player to move has position `(x_i,y_i,z_i)` then he/she must avoid to take stones in such a way that his/her opponent has a won position.
// For example, taking 3 stones from the largest pile of `(0,2,5)` will yield `(0,2,2)` and the opponent can will immediately.
//
// A position is lost when all transitions lead to a position where the opponent wins.
// A position is won when there is at least one transition leading to a position where the opponent loses.
//
// I only need to consider moves where one pile becomes empty:
// - if that is a winning position, then the current player will play that move
// - if it turns out to be a losing position, then the opponent will enforce that move by mirroring
//
// My program walks through all possible pile sizes `x <= y <= z` and looks at every potential move which "empties" one or more piles.
// Only if all of them lead to a won position (==> the opponent wins), then ''count'' is incremented by ''x + y + z''.
//
// # Alternatives
// The logic becomes much simples if I replace the three containers ''one'', ''two'' and ''all'' by a single container with three indices.
// Unfortunately it needs `1001^3 approx 1` trillion (= is 128 MByte RAM); my solution needs less than 0.5 MByte and typically runs inside the L2/L3 CPU cache.
#include
#include
unsigned int maxPileSize = 1000;
// compute linear index from two offsets
unsigned int id(unsigned int a, unsigned int b)
{
return a * (maxPileSize + 1) + b;
}
int main()
{
std::cin >> maxPileSize;
// the current position is only lost if every possible move leads to a position
// where the opponent wins
// that means: no matter how many stones I pick from one, two or three piles,
// the follow-up state must not be lost
const bool Won = false;
const bool Lost = true;
// assume each position is potentially won - unless proven otherwise
std::vector one((maxPileSize + 1) * (maxPileSize + 1), Won);
std::vector two((maxPileSize + 1) * (maxPileSize + 1), Won);
std::vector all((maxPileSize + 1) * (maxPileSize + 1), Won);
// count x+y+z for each lost position
unsigned int count = 0;
for (unsigned int x = 0; x <= maxPileSize; x++)
for (unsigned int y = x; y <= maxPileSize; y++)
{
// copy this condition from the inner loop (and keep there for the sake of completeness, though it's redundant)
if (one[id(x,y)] == Lost)
continue;
for (unsigned int z = y; z <= maxPileSize; z++)
{
// can current player win by clearing one pile ?
// check if (0,y,z) or (x,0,z) or (x,y,0) wins
// take x stones from first pile: check (x-x, y, z ) = (0, y, z)
// take y stones from second pile: check ( x, y-y, z ) = (x, 0, z)
// take z stones from third pile: check ( x, y, z-z) = (x, y, 0)
if (one[id(y,z)] == Lost ||
one[id(x,z)] == Lost ||
one[id(x,y)] == Lost)
continue; // opponent can be forced into a lost position
// can current player win by clearing one pile
// and removing the same number of stones from a second pile ?
// take x stones from first and second pile: check (x-x, y-x, z ) = (0, y-x, z )
// take y stones from first and second pile: check ( x, y-y, z-y) = (x, 0, z-y)
// take x stones from first and third pile: check (x-x, y, z-x) = (0, y, z-x)
// (note that x <= y <= z, therefore can't take z stones)
if (two[id(y-x, z)] == Lost ||
two[id(z-y, x)] == Lost ||
two[id(z-x, y)] == Lost)
continue; // opponent can be forced into a lost position
// can current player win by clearing the first pile
// and removing the same number of stones from the second and third pile ?
// note that x <= y <= z
// take x stones from all piles: check (x-x, y-x, z-x) = (0, y-x, z-x)
if (all[id(y-x, z-x)] == Lost)
continue; // opponent can be forced into a lost position
// current player lost, opponents wins all follow-up positions
count += x + y + z;
// mark all reachable positions as lost
// (same indices and arrays as used in the if-conditions above)
one[id(y, z)] = Lost;
one[id(x, z)] = Lost;
one[id(x, y)] = Lost;
two[id(y-x, z)] = Lost;
two[id(z-y, x)] = Lost;
two[id(z-x, y)] = Lost;
all[id(y-x, z-x)] = Lost;
}
}
// and done !
std::cout << count << std::endl;
return 0;
}