Circular Barn

Análisis oficial (C++, Python) 

Explicación

Primero, consideremos el caso $N=1$, cuando ambos granjeros quitan vacas de una sola habitación.

Cada granjero puede quitar $1$, $2$, $3$, pero no $4$ ni ningún múltiplo de 4. Esto nos motiva a considerar $a_1 \bmod 4$ en nuestro juego. El jugador que empieza con $a_1\bmod 4\neq 0$ debería tomar $a_1\bmod 4$ vacas para forzar al otro jugador a $a_1\bmod 4=0$, quien siempre le dará al primer jugador un $a_1\bmod 4\neq 0$, ya que no puede tomar ningún múltiplo de $4$ para mantener el resto $0$. El primer jugador ahora puede repetir el proceso hasta que $a_1 = 0$, lo que resulta en una victoria.

Por tanto, cuando $a_1 \bmod 4 \neq 0$, el Granjero John gana. En caso contrario, gana el Granjero Nhoj.

Ahora consideramos el caso $N>1$. Como cada habitación es independiente, tratamos el juego global como $N$ juegos individuales. Para cada habitación, definimos al atacante como el ganador garantizado y al defensor como el perdedor garantizado.

El siguiente par de movimientos en una habitación solo se hará cuando se hayan visitado todas las demás habitaciones. Así, los jugadores usan las siguientes estrategias:

• El atacante de una habitación reduce la cantidad de vacas lo más rápido posible para volver a esta habitación y potencialmente ganar antes.
• El defensor preferiría que esto se juegue lento para maximizar las chances de ganar temprano en otra habitación. Sea $T_i$ la cantidad total de operaciones para terminar la habitación $i$ de forma individual. El ganador del juego será el ganador de la habitación con el mínimo $\left\lceil\frac{T_i}2\right\rceil$ (si hay empate, la de menor número de habitación).

Para minimizar la cantidad de rondas, el atacante puede usar una versión modificada de su estrategia cuando $N=1$. En lugar de quitar $a_i\bmod 4$ vacas, puede quitar cualquier cantidad $p\equiv a_i\mod 4$ de vacas siempre que $p$ sea primo y menor que $a_i$. Para calcular el mayor $p<x$ tal que $p\equiv x\mod 4$, primero usamos una criba para hallar todos los primos, y mantenemos un arreglo $t_i$ con $0\leq i<4$ para el primo más reciente $t_i=p$ que encontramos donde $p\bmod 4=i$. Al iterar sobre valores de $x$, guardamos $m_x=t_{x\bmod 4}$ para representar el primo equivalente más grande.

Por otro lado, el defensor puede bloquear esta aceleración aprovechando que no hay primos $p>4$ que cumplan $p\bmod 4=2$, lo que implica que no hay aceleraciones cuando $a_i\bmod 4=2$. Si el defensor toma $2$ vacas de su $a_i\bmod 4=2=0$ y devuelve $a_i\bmod 4=2$ cada vez, el atacante ya no podrá acelerar el juego.

Así:

• Cuando $a_i\bmod4\in\{1,3\}$, la única aceleración que el atacante puede aplicar es quitar $m_{a_i}$ al inicio, lo que da $T_i=1+\frac{a_i-m_{a_i}}2$.
• En caso contrario, no hay aceleraciones y $T_i=\frac{a_i}2$.

Primero calculamos $T_i$ para cada habitación, y luego hallamos el mínimo de $\left\lceil\frac{T_i}2\right\rceil$ (si hay empate, con el menor $i$), y emitimos el ganador de esa habitación.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
 
constexpr int MAX_NUMBER = 5e6;
constexpr int MAX_INT = 2e9;
 
int main() {
 
	vector<bool> is_prime(MAX_NUMBER + 1, true);
	// Esto es m[] en la explicación.
	vector<int> largest_prime_equiv(MAX_NUMBER + 1);
	is_prime[1] = false;
	// 1 se considera primo en este problema, aunque
	// no lo cribemos; así que asignamos 1 al inicio.
	// Esto es t[] en la explicación.
	int largest_prime_mod[] = {-1, 1, -1, -1};
	largest_prime_equiv[1] = 1;
	// Algoritmo de criba
	for (int i = 2; i <= MAX_NUMBER; i++) {
		if (is_prime[i]) {
			largest_prime_mod[i % 4] = i;
			for (int j = i; j < MAX_NUMBER; j += i) is_prime[j] = false;
		}
		largest_prime_equiv[i] = largest_prime_mod[i % 4];
	}
 
	int test_cases;
	cin >> test_cases;
	for (int t = 0; t < test_cases; t++) {
		int n;
		cin >> n;
 
		// Mínimo de turnos, es decir, operaciones / 2
		int min_turn = MAX_INT;
		// Cantidad de operaciones en la habitación de turnos mínimos.
		int min_turn_ops = MAX_INT;
 
		for (int i = 1; i <= n; i++) {
			int cows;
			cin >> cows;
 
			int operations;
			if (cows % 2 == 0) {
				operations = cows / 2;
			} else {
				operations = 1 + (cows - largest_prime_equiv[cows]) / 2;
			}
 
			if (operations / 2 < min_turn) {
				min_turn = operations / 2;
				min_turn_ops = operations;
			}
		}
 
		cout << ((min_turn_ops % 2 != 0) ? "Farmer John" : "Farmer Nhoj") << endl;
	}
	return 0;
}