Hola estuve viendo este problema y lo resolvi rápidamente, el problema es que cuando lo probe en el juez note que me excedia de tiempo. La complejidad que yo entiendo en la manera en la que yo lo resolvi es O(N.K). Entonces decidi ver las soluciones y vi la que hizo Agustin Gutierrez y la verdad es que no entiendo la logica que sigue.
Este es mi código:
int solitario(std::vector<int> c, long long N, int K)
{
std::deque<int> gameCards;
int j = 0;
for(int i = 0; i < N; ++i) {
gameCards.push_back(c[j < c.size()? j : j = 0]);
j++;
}
while(gameCards.size() > 1) {
gameCards.pop_back();
for(int i = 0; i < K; ++i) {
int v = gameCards.back();
gameCards.pop_back();
gameCards.push_front(v);
}
}
return gameCards[0];
}
Y este es el código de Agustin:
// Mata las cartas 0, K, 2K, 3K, ...
long long f(long long N, int K)
{
assert(1 <= N);
if (N == 1) return 0;
if (K == 1) return N-1;
long long restantes = N - 1 - (N-1) / K;
long long newIndex = f(restantes, K);
long long restoFinal = (N-1) % K;
long long siguienteMuerto = K - restoFinal;
long long indice = (siguienteMuerto + newIndex - 1 + restantes) % restantes;
// Indice es entre los que quedan vivos luego de borrar los multiplos de K: hay que ajustar eso
indice += 1 + indice / (K-1);
assert(0 < indice && indice < N);
return indice;
}
int solitario(vector<int> c, long long N, int K)
{
const int M = int(c.size());
assert(1 <= M);
assert(M <= 100000);
assert(0 <= K);
assert(K <= 100000);
assert(1 <= N);
assert(N <= 1000000000000000000LL);
long long indiceDesdeArriba = f(N, K+1);
long long indiceDesdeAbajo = N - 1 - indiceDesdeArriba;
return c[indiceDesdeAbajo % M];
}
Agradecería si alguno puede explicarme ese código.
