Magic Ship
Explicación
Empezamos calculando cómo el viento nos desplaza a lo largo de una cantidad dada de días, y luego comprobamos si podemos cubrir la distancia restante con nuestro propio movimiento diario en esa misma cantidad de tiempo. En concreto, hallamos el cambio neto de un ciclo completo de viento, lo multiplicamos por cuántos ciclos completos caben en nuestra cantidad candidata de días, y por último consideramos los días restantes hallando el cambio del ciclo parcial. Nótese que el cambio del ciclo parcial tomará más días, lo cual está bien porque siempre podemos llegar a destino y seguir contrarrestando el viento.
Si conocemos la cantidad candidata de días que viajamos, podemos medir el cambio total del viento calculando cuántos ciclos completos de viento caben en esa cantidad de días. Aplicamos ese desplazamiento a nuestra posición inicial y luego medimos la distancia al destino. Si la distancia de Manhattan al destino no es mayor que la cantidad de días, significa que podríamos haber usado algunos de esos días para cubrir la distancia con nuestros propios movimientos, así que llegar al destino es posible para ese día.
Hacemos búsqueda binaria sobre la cantidad de días para hallar el menor tiempo para el cual esta comprobación de alcanzabilidad es verdadera. Si sabemos que una cantidad candidata de días nos permite llegar a destino a tiempo, podemos recortar el espacio de búsqueda y buscar una cantidad candidata menor. En caso contrario, buscamos una cantidad candidata mayor. Por último, imprimimos el menor día válido o concluimos que es imposible, en cuyo caso imprimimos .
Implementación
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
bool reachable(std::pair<long long, long long> start,
std::pair<long long, long long> end, std::string wind, long long time) {
long long wind_x = 0;
long long wind_y = 0;
for (const char &w : wind) {
switch (w) {
case 'U':
wind_y++;
break;
case 'D':
wind_y--;
break;
case 'L':
wind_x--;
break;
case 'R':
wind_x++;
break;
}
}
/*
* para acelerar, podemos saltarnos todos los ciclos repetitivos y
* multiplicar por la cantidad total de ciclos completos
*/
wind_x *= time / wind.length();
wind_y *= time / wind.length();
long long remainder = time % wind.length();
for (long long i = 0; i < remainder; i++) {
switch (wind[i]) {
case 'U':
wind_y++;
break;
case 'D':
wind_y--;
break;
case 'L':
wind_x--;
break;
case 'R':
wind_x++;
break;
}
}
start.first += wind_x;
start.second += wind_y;
return std::abs(start.first - end.first) + std::abs(start.second - end.second) <=
time;
}
int main() {
std::pair<long long, long long> at_pos;
cin >> at_pos.first >> at_pos.second;
std::pair<long long, long long> destination;
cin >> destination.first >> destination.second;
long long wind_len;
cin >> wind_len; // no se usará
std::string wind_cycle;
cin >> wind_cycle;
long long lo = 0;
long long hi = INT64_MAX / 2;
long long valid = -1;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
if (reachable(at_pos, destination, wind_cycle, mid)) {
valid = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << valid << endl;
}import java.io.*;
import java.util.Arrays;
public class MagicShip {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
long[] atPos = Arrays.stream(read.readLine().split(" "))
.mapToLong(Long::parseLong)
.toArray();
long[] destination = Arrays.stream(read.readLine().split(" "))
.mapToLong(Long::parseLong)
.toArray();
read.readLine(); // la longitud del viento no se usará
char[] winds = read.readLine().toUpperCase().toCharArray();
if (!reachable(atPos, destination, Long.MAX_VALUE / 2, winds)) {
System.out.println(-1);
System.exit(0);
}
long lo = 0;
long hi = Long.MAX_VALUE / 2;
long valid = -1;
while (lo <= hi) {
long mid = lo / 2 + hi / 2;
if (reachable(atPos, destination, mid, winds)) {
valid = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
System.out.println(valid);
}
private static boolean reachable(long[] from, long[] to, long time,
char[] windPattern) {
long windX = 0;
long windY = 0;
// calculamos el cambio neto del viento en un ciclo
for (char w : windPattern) {
switch (w) {
case 'U':
windY++;
break;
case 'D':
windY--;
break;
case 'L':
windX--;
break;
case 'R':
windX++;
break;
}
}
/*
* para acelerar, podemos multiplicar
* la cantidad soplada por la cantidad de ciclos completos
*/
windX *= time / windPattern.length;
windY *= time / windPattern.length;
long remainder = time % windPattern.length;
for (int i = 0; i < remainder; i++) { // calculamos el viento restante
switch (windPattern[i]) {
case 'U':
windY++;
break;
case 'D':
windY--;
break;
case 'L':
windX--;
break;
case 'R':
windX++;
break;
}
}
return manhattanDist(new long[] {from[0] + windX, from[1] + windY}, to) <= time;
}
private static long manhattanDist(long[] from, long[] to) {
return Math.abs(from[0] - to[0]) + Math.abs(from[1] - to[1]);
}
}from typing import List
def reachable(start: List[int], end: List[int], wind: str, time: int) -> bool:
start = start.copy()
# contamos los cambios netos después de un ciclo de viento
wind_x = wind.count("R") - wind.count("L")
wind_y = wind.count("U") - wind.count("D")
cycle_num = time // len(wind)
# aceleramos multiplicando por la cantidad de ciclos completos en el tiempo
wind_x *= cycle_num
wind_y *= cycle_num
remainder = time % len(wind)
wind = wind[:remainder] # tenemos en cuenta el viento restante
wind_x += wind.count("R") - wind.count("L")
wind_y += wind.count("U") - wind.count("D")
# aplicamos los cambios y vemos si la distancia de Manhattan es menor o igual que el tiempo
start[0] += wind_x
start[1] += wind_y
return abs(start[0] - end[0]) + abs(start[1] - end[1]) <= time
at_pos = [int(i) for i in input().split()]
destination = [int(i) for i in input().split()]
input()
wind_cycle = input()
lo = 0
hi = 2 * 10**14
valid = -1
while lo <= hi:
mid = (lo + hi) // 2
if reachable(at_pos, destination, wind_cycle, mid):
valid = mid
hi = mid - 1
else:
lo = mid + 1
print(valid)