UVa 10853

From Algorithmist
Jump to navigation Jump to search

10853 - Pablito nailed a nail[edit]

Summary[edit]

Develop an efficient method to determine the winner of the game.

Explanation[edit]

The set S of all values of L for which the player A wins can be constructed as follows:

  1. .
  2. , , and , imply .

A sample solution, based on the above construction:

long long L, amin, amax, bmin, bmax;

char solve()
{
	long long d, q;

	if (L <= amax)
		return 'A';

	d = amax - amin + bmin - bmax;
	q = (L - 1) / (amin + bmax);

	if (d < 0 && q > ((bmax - bmin - amax + d + 1) / d))
		return 'B';

	return (((L - 1) % (amin + bmax)) < (amax + q * d)) ? 'A' : 'B';
}

Gotchas[edit]

Use 64-bit integers in calculations to avoid overflows.

Input[edit]

4
4 5 7 1 20
5 1 3 1 3
5 2 2 1 3
1000 1 3 1 3

Output[edit]

A
A
B
B