Skip to Content
CTRL K

Luxury River Cruise

Análisis oficial (C++) 

Explicación

Como n⋅mn \cdot m es razonablemente pequeño, podemos construir un grafo donde tenemos una arista a→ba \rightarrow b si empezamos en el puerto aa y terminamos en el puerto bb después de recorrer toda la secuencia de direcciones.

Este nuevo grafo que armamos sigue siendo un grafo funcional. Así, nuestro problema se puede reducir a uno un poco más fácil.

Dado un grafo funcional, ¿cuál es nuestro destino final después de kk movimientos si empezamos en el nodo 11?

Para resolver este problema, podemos considerar lo siguiente:

  • Si k<nk < n, podemos simular directamente cada uno de nuestros movimientos
  • Si k≥nk \geq n, terminaremos en un ciclo y repetiremos el mismo conjunto de movimientos dentro de él

En un ciclo, la cantidad de movimientos que hay que hacer se puede reducir tomando el resto de los pasos restantes módulo la longitud del ciclo. Así, una vez que simulamos suficientes movimientos para hallar un ciclo, podemos tomar módulo de los movimientos restantes por el tamaño del ciclo y simular los movimientos finales.

Como alternativa, se puede usar binary lifting, que es un poco más fácil de implementar pero requiere conocimientos más avanzados.

Implementación

Complejidad temporal: O(NM)\mathcal{O}(NM)

#include <bits/stdc++.h>
 
using ll = long long;
 
int main() {
	std::ifstream read("cruise.in");
 
	int n, m, k;
	read >> n >> m >> k;
	std::vector<std::array<int, 2>> adj(n);
	for (auto &[l, r] : adj) {
		read >> l >> r;
		l--, r--;
	}
 
	std::vector<int> moves(m);
	for (int i = 0; i < m; i++) {
		char c;
		read >> c;
		moves[i] = c == 'R';
	}
 
	std::vector<int> next(n);
	for (int i = 0; i < n; i++) {
		int curr = i;
		for (int j = 0; j < m; j++) { curr = adj[curr][moves[j]]; }
		next[i] = curr;
	}
 
	int curr = 0;
	if (k < n) {
		for (int i = 0; i < k; i++) { curr = next[curr]; }
	} else {
		int ptr = 0;
		std::map<int, int> seen;
		while (!seen.count(curr)) {
			seen[curr] = ptr++;
			curr = next[curr];
		}
 
		int cycle_len = seen.size() - seen[curr];
 
		k = (k - seen[curr]) % cycle_len;
		for (int i = 0; i < k; i++) { curr = next[curr]; }
	}
 
	std::ofstream("cruise.out") << curr + 1 << std::endl;
}
import java.io.*;
import java.util.*;
 
public class Cruise {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("cruise.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("cruise.out"));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
 
		int[][] adj = new int[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			adj[i][0] = Integer.parseInt(st.nextToken()) - 1;
			adj[i][1] = Integer.parseInt(st.nextToken()) - 1;
		}
 
		st = new StringTokenizer(br.readLine());
		int[] moves = new int[m];
		for (int i = 0; i < m; i++) { moves[i] = st.nextToken().equals("R") ? 1 : 0; }
 
		int[] next = new int[n];
		for (int i = 0; i < n; i++) {
			int curr = i;
			for (int j = 0; j < m; j++) { curr = adj[curr][moves[j]]; }
			next[i] = curr;
		}
 
		int curr = 0;
		if (k < n) {
			for (int i = 0; i < k; i++) { curr = next[curr]; }
		} else {
			Map<Integer, Integer> seen = new HashMap<>();
			int ptr = 0;
			while (!seen.containsKey(curr)) {
				seen.put(curr, ptr++);
				curr = next[curr];
			}
 
			int cycleLen = ptr - seen.get(curr);
			k = (k - seen.get(curr)) % cycleLen;
 
			for (int i = 0; i < k; i++) { curr = next[curr]; }
		}
 
		pw.println(curr + 1);
		pw.close();
	}
}
with open("cruise.in") as read:
	n, m, k = map(int, read.readline().split())
	adj = []
	for _ in range(n):
		l, r = map(int, read.readline().split())
		adj.append((l - 1, r - 1))
 
	moves = [1 if c == "R" else 0 for c in read.readline().split()]
 
next = [0] * n
for i in range(n):
	curr = i
	for j in range(m):
		curr = adj[curr][moves[j]]
	next[i] = curr
 
curr = 0
if k <= n:
	for _ in range(k):
		curr = next[curr]
else:
	seen = {}
	ptr = 0
	while curr not in seen:
		seen[curr] = ptr
		ptr += 1
		curr = next[curr]
 
	cycle_len = ptr - seen[curr]
	k = (k - seen[curr]) % cycle_len
	for _ in range(k):
		curr = next[curr]
 
print(curr + 1, file=open("cruise.out", "w"))
Fundamentos