Created
April 9, 2015 21:15
-
-
Save mickeypash/28f867c4547774acee19 to your computer and use it in GitHub Desktop.
Google Code Jam Winning solution Round 3 - Magical, Marvelous Tour
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.BufferedWriter; | |
import java.util.InputMismatchException; | |
import java.util.NoSuchElementException; | |
import java.math.BigInteger; | |
import java.io.OutputStream; | |
import java.io.PrintWriter; | |
import java.io.Writer; | |
import java.io.IOException; | |
import java.io.FileInputStream; | |
import java.util.Arrays; | |
import java.io.InputStream; | |
import java.io.FilenameFilter; | |
import java.util.Locale; | |
import java.io.OutputStreamWriter; | |
import java.util.Comparator; | |
import java.io.FileOutputStream; | |
import java.io.File; | |
/** | |
* Built using CHelper plug-in | |
* Actual solution is at the top | |
* @author Egor Kulikov (egor@egork.net) | |
*/ | |
public class Main { | |
public static void main(String[] args) { | |
Locale.setDefault(Locale.US); | |
InputStream inputStream; | |
try { | |
final String regex = "B-(small|large).*[.]in"; | |
File directory = new File("."); | |
File[] candidates = directory.listFiles(new FilenameFilter() { | |
public boolean accept(File dir, String name) { | |
return name.matches(regex); | |
} | |
}); | |
File toRun = null; | |
for (File candidate : candidates) { | |
if (toRun == null || candidate.lastModified() > toRun.lastModified()) | |
toRun = candidate; | |
} | |
inputStream = new FileInputStream(toRun); | |
} catch (IOException e) { | |
throw new RuntimeException(e); | |
} | |
OutputStream outputStream; | |
try { | |
outputStream = new FileOutputStream("b.out"); | |
} catch (IOException e) { | |
throw new RuntimeException(e); | |
} | |
InputReader in = new InputReader(inputStream); | |
OutputWriter out = new OutputWriter(outputStream); | |
TaskB solver = new TaskB(); | |
int testCount = Integer.parseInt(in.next()); | |
for (int i = 1; i <= testCount; i++) | |
solver.solve(i, in, out); | |
out.close(); | |
} | |
} | |
class TaskB { | |
public void solve(int testNumber, InputReader in, OutputWriter out) { | |
int dianaHit = in.readInt(); | |
int towerHit = in.readInt(); | |
int count = in.readInt(); | |
int[] health = new int[count]; | |
int[] gold = new int[count]; | |
IOUtils.readIntArrays(in, health, gold); | |
int[][] answer = new int[count + 1][2000]; | |
ArrayUtils.fill(answer, Integer.MIN_VALUE); | |
answer[0][1] = 0; | |
for (int i = 0; i < count; i++) { | |
int towerKill = (health[i] + towerHit - 1) / towerHit; | |
for (int j = 0; j < 2000; j++) { | |
if (answer[i][j] == Integer.MIN_VALUE) | |
continue; | |
for (int k = 0; k < towerKill; k++) { | |
int remaining = health[i] - k * towerHit; | |
int dianaKill = (remaining + dianaHit - 1) / dianaHit; | |
if (dianaKill <= k + j) | |
answer[i + 1][k + j - dianaKill] = Math.max(answer[i + 1][k + j - dianaKill], answer[i][j] + gold[i]); | |
} | |
answer[i + 1][j + towerKill] = Math.max(answer[i + 1][j + towerKill], answer[i][j]); | |
} | |
} | |
out.printLine("Case #" + testNumber + ":", ArrayUtils.maxElement(answer[count])); | |
} | |
} | |
class InputReader { | |
private InputStream stream; | |
private byte[] buf = new byte[1024]; | |
private int curChar; | |
private int numChars; | |
private SpaceCharFilter filter; | |
public InputReader(InputStream stream) { | |
this.stream = stream; | |
} | |
public int read() { | |
if (numChars == -1) | |
throw new InputMismatchException(); | |
if (curChar >= numChars) { | |
curChar = 0; | |
try { | |
numChars = stream.read(buf); | |
} catch (IOException e) { | |
throw new InputMismatchException(); | |
} | |
if (numChars <= 0) | |
return -1; | |
} | |
return buf[curChar++]; | |
} | |
public int readInt() { | |
int c = read(); | |
while (isSpaceChar(c)) | |
c = read(); | |
int sgn = 1; | |
if (c == '-') { | |
sgn = -1; | |
c = read(); | |
} | |
int res = 0; | |
do { | |
if (c < '0' || c > '9') | |
throw new InputMismatchException(); | |
res *= 10; | |
res += c - '0'; | |
c = read(); | |
} while (!isSpaceChar(c)); | |
return res * sgn; | |
} | |
public String readString() { | |
int c = read(); | |
while (isSpaceChar(c)) | |
c = read(); | |
StringBuilder res = new StringBuilder(); | |
do { | |
if (Character.isValidCodePoint(c)) | |
res.appendCodePoint(c); | |
c = read(); | |
} while (!isSpaceChar(c)); | |
return res.toString(); | |
} | |
public boolean isSpaceChar(int c) { | |
if (filter != null) | |
return filter.isSpaceChar(c); | |
return isWhitespace(c); | |
} | |
public static boolean isWhitespace(int c) { | |
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; | |
} | |
public String next() { | |
return readString(); | |
} | |
public interface SpaceCharFilter { | |
public boolean isSpaceChar(int ch); | |
} | |
} | |
class OutputWriter { | |
private final PrintWriter writer; | |
public OutputWriter(OutputStream outputStream) { | |
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); | |
} | |
public OutputWriter(Writer writer) { | |
this.writer = new PrintWriter(writer); | |
} | |
public void print(Object...objects) { | |
for (int i = 0; i < objects.length; i++) { | |
if (i != 0) | |
writer.print(' '); | |
writer.print(objects[i]); | |
} | |
} | |
public void printLine(Object...objects) { | |
print(objects); | |
writer.println(); | |
} | |
public void close() { | |
writer.close(); | |
} | |
} | |
class IOUtils { | |
public static void readIntArrays(InputReader in, int[]... arrays) { | |
for (int i = 0; i < arrays[0].length; i++) { | |
for (int j = 0; j < arrays.length; j++) | |
arrays[j][i] = in.readInt(); | |
} | |
} | |
} | |
class ArrayUtils { | |
public static void fill(int[][] array, int value) { | |
for (int[] row : array) | |
Arrays.fill(row, value); | |
} | |
public static int maxElement(int[] array) { | |
return maxElement(array, 0, array.length); | |
} | |
public static int maxElement(int[] array, int from, int to) { | |
int result = Integer.MIN_VALUE; | |
for (int i = from; i < to; i++) | |
result = Math.max(result, array[i]); | |
return result; | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment