Family Crisis Solver
unknown
java
2 years ago
8.4 kB
13
Indexable
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;
}
}
}