// Sharks are simple, aggressive and reflex driven
class Shark0 extends Strategy
{
	public int initial_turn()
	{
		return 4;
	}
	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		int s = 0, h;
		for (int i = 1; i < opponents; i++)
		{
			s += last_turns[i];
		}
		if (Math.random() > 0.5 )
		{
			h = (s + opponents-2) / (opponents - 1);
		}
		else
		{
			h = (2*s + opponents-2) / (opponents - 1);
		}
		// A way out to stop inflation :-)
		if ( h > maxPlayableNumber && Math.random() < 0.3 )
			return 0;
		return Math.min(maxPlayableNumber,h);
	}
}

class Shark1 extends Strategy
{
	public int initial_turn()
	{
		return 1;
	}
	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		if ( last_turns[0] == 1 )
		{
			return Math.min(turn_no / opponents + 4,maxPlayableNumber);
		}
		else return 1;

	}
}

class Shark2 extends Strategy
{
	public int initial_turn()
	{
		return 1;
	}
	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		int i, i0;

		if ( Math.random() < 0.3 ) return 0;

		// Ineffiziente methode, den zweithoechsten
		// rauszukriegen.
		i0 = 0;
		for (i = 0; i < opponents; i++)
		{
			if ( last_turns[i] > last_turns[i0] )
			{
				i0 = i;
			}
		}
		last_turns[i0] = -1;
		i0 = 0;
		for (i = 0; i < opponents; i++)
		{
			if ( last_turns[i] > last_turns[i0] )
			{
				i0 = i;
			}
		}
		// Second highest of last_turn + 1
		return Math.min(last_turns[i0] + 1,maxPlayableNumber);
	}
}

class Shark3 extends Strategy
{
	public int initial_turn()
	{
		return 0;
	}
	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		int i, i0;

		// Ineffiziente Methode, den hoechsten
		// rauszukriegen.
		i0 = 1;
		for (i = 1; i < opponents; i++)
		{
			if ( last_turns[i] > last_turns[i0] )
			{
				i0 = i;
			}
		}
		// Nur hoch spielen war ein Problem!
		if ( last_turns[i0] == maxPlayableNumber && Math.random() < 0.2 ) return 0;

		return Math.min(last_turns[i0] + 1, maxPlayableNumber);
	}
}

class Shark4 extends Strategy
{
	public int initial_turn()
	{
		return 0;
	}
	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		int i, i0;

		// This shark takes small and large bytes!
		if ( Math.random() < 0.5 ) return 1;

		// Ineffiziente methode, den hoechsten
		// rauszukriegen.
		i0 = 1;
		for (i = 1; i < opponents; i++)
		{
			if ( last_turns[i] > last_turns[i0] )
			{
				i0 = i;
			}
		}
		return Math.min(last_turns[i0] + 2,maxPlayableNumber);
	}
}

// Play the number which would have made highest
// gain in last turn.
class Shark5 extends Strategy
{
	public int initial_turn()
	{
		return 1;
	}

	int eval(int turns[], int carry, int scores[])
	{
		int i, j, sum, t, parts, t0;

		sum = carry;
		parts = 0;
		t0 = 0;
		for (i = 0; i < opponents; i++) if ( scores[i] > 0 )
		{
			if ( turns[i] > 0 )
			{
				sum  += turns[i];
				t = 0;
				for (j = 0; j < opponents; j++)
				{
					if ( turns[j] > 0 && turns[i] >= turns[j] ) t++;
				}
				if (i == 0) t0 = t;
				parts   += t;
			}
		}
		sum += stepBonus;
		return (int) ( sum * t0 ) / parts - turns[0];
	}

	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		int i, i0, w, w0;

		w0 = - maxPlayableNumber;
		i0 = 0;
		for (i = 0; i <= maxPlayableNumber; i++)
		{
			last_turns[0] = i;
			w = eval(last_turns, carryOver, scores);
			if ( w > w0 )
			{
				w0 = w;
				i0 = i;
			}
		}
		return i0;
	}
}

// Play the number which would have made highest
// gain in last 2 turns.
class Shark6 extends Shark5
{
	public int initial_turn()
	{
		return 0;
	}

	int lt[];

	void priv_init()
	{
		lt = new int[opponents];
	}

	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		int i, i0, w, w0;

		if ( turn_no <= 1 )
		{
			i0 = 0;
		}
		else
		{
			w0 = - maxPlayableNumber;
			i0 = 0;
			for (i = 0; i <= maxPlayableNumber; i++)
			{
				last_turns[0] = i;
				lt[0] = i;
				w = eval(last_turns, carryOver, scores)
				   +eval(lt,carryOver, scores);
				if ( w > w0 )
				{
					w0 = w;
					i0 = i;
				}
			}
		}
		for (i = 0; i < opponents; i++) lt[i] = last_turns[i];
		return i0;
	}
}

// Like Shark6 but plays the higher of two equivalent turns!
class Shark7 extends Shark6
{
	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		int i, i0, w, w0;

		if ( turn_no <= 1 )
		{
			i0 = 0;
		}
		else
		{
			w0 = - 4*maxPlayableNumber;
			i0 = 0;
			for (i = 0; i <= maxPlayableNumber; i++)
			{
				last_turns[0] = i;
				lt[0] = i;
				w = 2*eval(last_turns, carryOver, scores)
				   +eval(lt,carryOver, scores);
				if ( w >= w0 )
				{
					w0 = w;
					i0 = i;
				}
			}
		}
		for (i = 0; i < opponents; i++) lt[i] = last_turns[i];
		return i0;
	}
}

// Like Shark7 but more cautious
class Shark8 extends Shark6
{
	public int turn(int last_turns[], int scores[],
					int carryOver, int turn_no)
	{
		int i, i0, w, w1, w0;

		if ( turn_no <= 1 )
		{
			i0 = 0;
		}
		else
		{
			w0 = - maxPlayableNumber;
			i0 = 0;
			for (i = 0; i <= maxPlayableNumber; i++)
			{
				last_turns[0] = i;
				lt[0] = i;
				w = eval(last_turns, carryOver, scores);
				w1= eval(lt,carryOver, scores);
				// Double caution: weight the lower result,
				// take the smallest turn! WAS BAD!
				// So revert to Single Caution!
				w = Math.min(w, w1) * 2 + Math.max(w, w1);
				if ( w >= w0 )
				{
					w0 = w;
					i0 = i;
				}
			}
		}
		for (i = 0; i < opponents; i++) lt[i] = last_turns[i];
		return i0;
	}
}