GoogleCodeJam_SavingTheUniverseAgain [source code]
import java.io.*;
public class GoogleCodeJam_SavingTheUniverseAgain {
static
/******************************************************************************/
// import java.io.*;
// import java.util.*;
public class Solution {
Scanner in_scan = new Scanner (System.in);
PrintStream out = System.out;
boolean DEBUG = false;
private String solve (String test_case) {
return solve2 (test_case);
}
private String solve2 (String line) {
String[] tokens = line.split ("\\s+");
int D = Integer.parseInt (tokens[0]);
StringBuilder P = new StringBuilder (tokens[1]);
Deque<Integer> charges = new ArrayDeque<> (), powers = new ArrayDeque<> ();
int cur_power = 1, total_damage = 0;
for (int i = 0; i < P.length (); i++) {
if (P.charAt (i) == 'C') {
cur_power <<= 1;
charges.push (i);
powers.push (cur_power);
} else {
total_damage += cur_power;
}
}
if (DEBUG) System.err.printf ("\ntotal_damage:(%d), D:(%d), P:(%s)\ncharges: %s\npowers: %s\n", total_damage, D, P.toString (), charges, powers);
int min_swap = 0;
if (total_damage > D) {
if (charges.isEmpty ()) {
min_swap = -1;
} else {
int end = P.length () - 1;
boolean success = false;
loop1: while (!charges.isEmpty ()) {
int charge = charges.pop (), power = powers.pop ();
if (DEBUG) System.err.printf ("charge:(%d), power:(%d), end:(%d), min_swap:(%d)\n", charge, power, end, min_swap);
if (charge == end) {
end = charge - 1;
continue;
}
for (int swap_i = charge + 1; swap_i <= end; swap_i++) {
total_damage -= power / 2;
min_swap++;
if (total_damage <= D) {
success = true;
break loop1;
}
}
end--;
}
if (!success)
min_swap = -1;
}
}
return String.format ("%s", min_swap >= 0 ? min_swap + "" : "IMPOSSIBLE");
}
void swap (StringBuilder sb, int i , int j) {
char tmp = sb.charAt (i);
sb.setCharAt (i, sb.charAt (j));
sb.setCharAt (j, tmp);
}
int count (StringBuilder program) {
int power = 1, res = 0;
for (int i = 0; i < program.length (); i++) {
if (program.charAt (i) == 'C')
power <<= 1;
else
res += power;
}
return res;
}
private void run () throws Exception {
int t = Integer.parseInt (in_scan.nextLine ());
for (int i = 1; i <= t; i++)
out.printf ("Case #%d: %s\n", i, solve (in_scan.nextLine ()));
in_scan.close ();
out.close ();
}
public static void main (String args[]) throws Exception {
new Solution ().run ();
}
}
/******************************************************************************/
static String data_path = "data/google-code-jam-2018/qualification-round/saving-the-universe-again/";
public static void main(String[] args) throws Exception {
File[] input_files = new File (data_path + "/input").listFiles ((d, name) -> name.startsWith ("input")), output_files = new File (data_path + "/output").listFiles ((d, name) -> name.startsWith ("output"));
if (input_files.length != output_files.length) {
System.out.println ("different input and output files count, aborting");
System.exit (1);
}
PrintStream system_out = System.out;
OutputStream bao = new ByteArrayOutputStream ();
for (int i = 0; i < input_files.length; i++) {
System.setIn (new FileInputStream (input_files[i]));
String file_name_suffix = input_files[i].getName ().substring (5);
PrintStream ps = new PrintStream (bao = new ByteArrayOutputStream ());
System.setOut (ps);
Solution.main (args);
System.setOut (system_out);
Scanner output_scan = new Scanner (output_files[i]), my_scan = new Scanner (bao.toString ()), input_scan = new Scanner (input_files [i]);
input_scan.nextLine ();
System.out.printf ("TEST SET %s\n", file_name_suffix);
while (output_scan.hasNextLine ()) {
String true_output = output_scan.nextLine (), my_output = my_scan.nextLine ();
System.out.printf ("%s\n%s\n%s\n\n", input_scan.nextLine (), true_output, Printer.wrap (my_output, my_output.equals (true_output) ? 92 : 91));
}
System.out.println ("\n");
}
}
}
直接忽略了easy的test, 直接按照复杂的情况来做, 结果做出来反而直接把所有的test都过了; 之前单纯针对visible设计的代码反而是连easy的都过不了;
另外, 最后里面swap的部分, 实际上是可以直接数学计算, 而不是用一个for循环来做的; 不过还是那句话, 第一遍不要想太多, 能work再说. 不要Premature Optmization;
后面反正过了, 也懒得改了;
最后回头想想这个题目还是很好的, 是一个典型的greedy的算法题目, 是可以用来面试考的一个算法题目;
Problem Description
Saving The Universe Again
Problem
An alien robot is threatening the universe, using a beam that will destroy all algorithms knowledge. We have to stop it!
Fortunately, we understand how the robot works. It starts off with a beam with a strength of 1, and it will run a program that is a series of instructions, which will be executed one at a time, in left to right order. Each instruction is of one of the following two types:
- C (for "charge"): Double the beam's strength.
- S (for "shoot"): Shoot the beam, doing damage equal to the beam's current strength.
For example, if the robot's program is SCCSSC, the robot will do the following when the program runs:
- Shoot the beam, doing 1 damage.
- Charge the beam, doubling the beam's strength to 2.
- Charge the beam, doubling the beam's strength to 4.
- Shoot the beam, doing 4 damage.
- Shoot the beam, doing 4 damage.
- Charge the beam, increasing the beam's strength to 8.
In that case, the program would do a total of 9 damage.
The universe's top algorithmists have developed a shield that can withstand a maximum total of D damage. But the robot's current program might do more damage than that when it runs.
The President of the Universe has volunteered to fly into space to hack the robot's program before the robot runs it. The only way the President can hack (without the robot noticing) is by swapping two adjacent instructions. For example, the President could hack the above program once by swapping the third and fourth instructions to make it SCSCSC. This would reduce the total damage to 7. Then, for example, the president could hack the program again to make it SCSSCC, reducing the damage to 5, and so on.
To prevent the robot from getting too suspicious, the President does not want to hack too many times. What is this smallest possible number of hacks which will ensure that the program does no more than D total damage, if it is possible to do so?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing an integer D and a string P: the maximum total damage our shield can withstand, and the robot's program.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is either the minimum number of hacks needed to accomplish the goal, or IMPOSSIBLE if it is not possible.
Limits
1 ≤ T ≤ 100.
1 ≤ D ≤ 10^9.
2 ≤ length of P ≤ 30.
Every character in P is either C or S.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
Test set 1 (Visible)
The robot's program contains either zero or one C characters.
Test set 2 (Hidden)
No additional restrictions to the Limits section.
Sample
Input
Output
6
1 CS
2 CS
1 SS
6 SCCSSC
2 CC
3 CSCSS
Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 2
Case #5: 0
Case #6: 5
Note that the last three sample cases would not appear in test set 1.
In Sample Case #1, the President can swap the two instructions to reduce the total damage to 1, which the shield can withstand.
In Sample Case #2, the President does not need to hack the program at all, since the shield can already withstand the 2 total damage it will cause.
In Sample Case #3, the program will do more damage than the shield can withstand, and hacking will do nothing to change this. The universe is doomed.
Sample Case #4 uses the program described in the problem statement. The statement demonstrates one way to reduce the total damage to 5 using two hacks. It is not possible to reduce the damage to 6 or less by using only one hack; remember that the President can only swap adjacent instructions.
In Sample Case #5, the robot will never shoot, and so it will never do any damage. No hacking is required.
In Sample Case #6, five hacks are required. Notice that even if two hacks swap the instructions at the same two positions, they still count as separate hacks.