Give this problem a try 1117 C. Magic Ship.
Approach
Example Code
import java.io.*;
import java.util.*;
public class Solution {
public static long[] direction(char d) {
if (d == 'U') return new long[]{0,1};
if (d == 'D') return new long[]{0,-1};
if (d == 'L') return new long[]{-1,0};
if (d == 'R') return new long[]{1,0};
return new long[]{0,0};
}
public static boolean check(long k, long x1, long y1, long x2, long y2, int n, long[][] pref) {
long cnt = k / n, rem = k % n;
x1 += cnt * pref[n-1][0] + (rem > 0 ? pref[(int)(rem-1)][0] : 0L);
y1 += cnt * pref[n-1][1] + (rem > 0 ? pref[(int)(rem-1)][1] : 0L);
long manhattan = Math.abs(x2-x1) + Math.abs(y2-y1);
return manhattan <= k;
}
public static long search(long x1, long y1, long x2, long y2, int n, long[][] pref) {
long max = (long) 1e18;
long days = max;
for (long m = max; m >= 1; m/=2) {
while (check(days-m, x1, y1, x2, y2, n, pref)) {
days -= m;
}
}
return days;
}
public static void main(String[] args) throws Exception {
// FastScanner io = new FastScanner("");
FastScanner io = new FastScanner();
long x1 = io.nextLong(), y1 = io.nextLong();
long x2 = io.nextLong(), y2 = io.nextLong();
int n = io.nextInt();
char[] s = io.next().toCharArray();
// prefix sum on net changes
long[][] pref = new long[n][2];
pref[0] = direction(s[0]);
for (int i = 1; i < n; i++) {
long[] dir = direction(s[i]);
pref[i] = new long[]{pref[i-1][0] + dir[0], pref[i-1][1] + dir[1]};
}
long answer = search(x1, y1, x2, y2, n, pref);
if (check(answer, x1, y1, x2, y2, n, pref)) io.println(answer);
else io.println(-1);
io.close();
}
/**
RESERVED NUMBERS
*/
public static int MOD = 1_000_000_007;
/**
DATA STRUCTURES
*/
static class MultiSet {
static TreeMap<Integer, Integer> multiset = new TreeMap<>();
static void add(int x) {
multiset.putIfAbsent(x, 0);
multiset.put(x, multiset.get(x)+1);
}
static void remove(int x) {
multiset.putIfAbsent(x, 0);
multiset.put(x, multiset.get(x)-1);
if (multiset.get(x) <= 0) multiset.remove(x);
}
}
/**
IO
*/
static class FastScanner extends PrintWriter {
private BufferedReader br;
private StringTokenizer st;
// standard input
public FastScanner() { this(System.in, System.out); }
public FastScanner(InputStream i, OutputStream o) {
super(o);
st = new StringTokenizer("");
br = new BufferedReader(new InputStreamReader(i));
}
// USACO-style file input
public FastScanner(String problemName) throws IOException {
super(problemName + ".out");
st = new StringTokenizer("");
br = new BufferedReader(new FileReader(problemName + ".in"));
}
// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
} catch (Exception e) { }
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
}
Complexity Analysis
- Time Complexity:
- Space Complexity:
Sign-off
Congratulations on making it this far! Best of luck in your future competitions!