Family Crisis Solver
unknown
java
a year ago
8.4 kB
12
Indexable
Never
import java.io.*; import java.nio.file.Files; import java.nio.file.Paths; import java.util.*; import java.util.stream.Collectors; /** * Created: 10/9/22 * Author: thucdx **/ class FamilyCrisis { static boolean DEBUG = true; static boolean IS_LOCAL = null != System.getenv("LOCAL_JUDGE"); static class Pair implements Comparable<Pair> { long state; int time; public Pair(long state, int step) { this.state = state; this.time = step; } @Override public int compareTo(Pair o) { return time - o.time; } } static class FamilyCrisisSolver { int n; int[] times; Map<Long, Integer> minStep; Map<Long, Long> prev; static int INF = (int) 1e9; private static boolean getBit(long state, int k) { return (state & (1L << k)) > 0; } private static List<Integer> getOnBit(long state, int minId, int maxId) { List<Integer> result = new ArrayList<>(); for (int i = minId; i < maxId; i++) { if (getBit(state, i)) { result.add(i); } } return result; } private static long setBit(long state, int k) { return state | (1L << k); } private static long reverseBit(long state, int k) { return state ^ (1L << k); } public FamilyCrisisSolver(int[] times) { this.times = times; this.n = times.length; } public List<Pair> nextState(Pair cur) { List<Pair> possibleStates = new ArrayList<>(); boolean hasLamp = getBit(cur.state, n); List<Integer> bitOn = new ArrayList<>(); for (int i = 0; i < n; i++) { if (getBit(cur.state, i) == hasLamp) { bitOn.add(i); } } // debug("cur state", cur.state); // debug(bitOn); if (hasLamp) { // choose up to 2 people for (int i = 0; i < bitOn.size(); i++) { for (int j = i + 1; j < bitOn.size(); j++) { long state = cur.state; state = reverseBit(state, bitOn.get(i)); state = reverseBit(state, bitOn.get(j)); // hasLamp = false state = reverseBit(state, n); int totalTime = cur.time + Math.max(times[bitOn.get(i)], times[bitOn.get(j)]); // debug("i, j, state, totalTime, curState: ", bitOn.get(i), bitOn.get(j), state, totalTime, cur.state); possibleStates.add(new Pair(state, totalTime)); } } } else { // Choose 1 person to bring lamp for (Integer bitNum : bitOn) { long state = cur.state; state = reverseBit(state, bitNum); state = reverseBit(state, n); int totalTime = cur.time + times[bitNum]; possibleStates.add(new Pair(state, totalTime)); } } return possibleStates; } public int solve() { int n = times.length; // state = n+1 bits, // has_lamp, person_0, person_1, .... person_n-1 long start = (1L << (n + 1)) - 1; long endState = 0; minStep = new HashMap<>(); prev = new HashMap<>(); Queue<Pair> q = new PriorityQueue<>(); q.add(new Pair(start, 0)); minStep.put(start, 0); while (!q.isEmpty()) { Pair cur = q.poll(); if (cur.state == endState) { List<Long> transitionStates = new ArrayList<>(); Long curState = cur.state; do { transitionStates.add(curState); curState = prev.get(curState); } while (curState != null); Collections.reverse(transitionStates); Writer writer = new OutputStreamWriter(System.out); try { printResult(transitionStates, cur.time, writer); writer.flush(); } catch (IOException e) { throw new RuntimeException(e); } return cur.time; } List<Pair> possibleStates = nextState(cur); for (Pair possibleState : possibleStates) { if (minStep.getOrDefault(possibleState.state, INF) > possibleState.time) { prev.put(possibleState.state, cur.state); q.add(possibleState); minStep.put(possibleState.state, possibleState.time); } } } return -1; } public void printResult(List<Long> transitionStates, int totalTime, Writer writer) throws IOException { writer.write("Finish in " + totalTime + " time units\n"); for (int i = 1; i < transitionStates.size(); i++) { StringBuilder cmd = new StringBuilder("Move "); Long diff = transitionStates.get(i) ^ transitionStates.get(i-1); List<Integer> onBits = FamilyCrisisSolver.getOnBit(diff, 0, n); cmd.append(onBits.stream().map(id -> "#" + id + " ").collect(Collectors.joining("and "))); cmd.append("from ").append(FamilyCrisisSolver.getBit(transitionStates.get(i), n) ? "left to right" : "right to left"); writer.write(cmd + "\n"); } } } public static void main(String[] args) { try { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); if (IS_LOCAL) { br = new BufferedReader(new InputStreamReader(Files.newInputStream(Paths.get("input/FamilyCrisis.inp")))); } FastReader fr = new FastReader(br); int n = fr.nextInt(); int[] times = new int[n]; for (int i = 0; i < n; i++) { times[i] = fr.nextInt(); } Arrays.sort(times); FamilyCrisisSolver solver = new FamilyCrisisSolver(times); int time = solver.solve(); } catch (Exception ex) { System.out.println(ex.getMessage()); ex.printStackTrace(); } } static void debug(List<Object> args) { if (IS_LOCAL && DEBUG) { System.out.println("\t[DEBUG] " + args.stream().map(Object::toString).collect(Collectors.joining(", "))); } } static void debug(Object... args) { if (IS_LOCAL && DEBUG) { System.out.println("\t[DEBUG] " + Arrays.stream(args).map(Object::toString).collect(Collectors.joining(", "))); } } static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader( new InputStreamReader(System.in)); } public FastReader(BufferedReader br) { this.br = br; } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine() { String str = ""; try { if (st.hasMoreTokens()) { str = st.nextToken("\n"); } else { str = br.readLine(); } } catch (IOException e) { e.printStackTrace(); } return str; } } }