I did not solve problem B during the contest, so I read the solution by pashka
and annotated his code according.
The basic approach is to allocate empty rooms so as to maximize the number of
noisy walls they reduce, 4 walls removed,then 3 walls and finally 2 walls.
This is the code by pashka, I only added comments.
import java.io.*;
import java.util.StringTokenizer;
public class B {
private int solveTest() throws IOException {
int r = nextInt();
int c = nextInt();
if (r > c) {
int t = r;
r = c;
c = t;
}
int n = nextInt();
System.out.println(r + " " + c + " " + n);
if (r == 1) {
if (n <= (c + 1) / 2) {
return 0;
} else {
n -= (c + 1) / 2;
int res = n * 2;
if (c % 2 == 0) {
res--;
}
return res;
}
}
if (n <= (r * c + 1) / 2) {
return 0;
}
int res = (r - 1) * c + (c - 1) * r; // Number of walls (maximum result
achieved for n=r*c)
int p = (r - 2) * (c - 2); // Number of inner rooms (with 4 walls)
int h = r * c - n; // number of empty rooms
if (h <= (p + 1) / 2) { //all empty rooms can have 4 walls
return res - h * 4; //remove number of walls for empty rooms from
maximal result
}
if (p % 2 == 0) { //even number of inner rooms, at least one of r/c is
even
h -= p / 2;
res -= p / 2 * 4; //use p/2 rooms with 4 walls
if (h <= r + c - 4) {
return res - h * 3; // after making p/2 non adjacent inner
rooms empty, the rest of the empty rooms will only have 3 walls, placed on the
rim.
}
h -= r + c - 4; // allocate more empty rooms with only 3 walls
res -= (r + c - 4) * 3;
return res - 2 * h; //remaining empty rooms will have 2 walls
} else { //similar aproach with odd r,c
int hh = h;
int res1 = res;
hh -= (p + 1) / 2;
res1 -= (p + 1) / 2 * 4; //use as many as possible 4 walled empty
squares, starting at the corner of inner squares
if (hh <= r + c - 6) {
res1 -= hh * 3;
} else {
hh -= r + c - 6;
res1 -= (r + c - 6) * 3;
res1 -= hh * 2;
}
hh = h;
int res2 = res;
hh -= p / 2;
res2 -= p / 2 * 4; //allocate 4 walled empty squares at an offset
of 1, (end up using 1 less 4 walled empty square)
if (hh <= r + c - 2) { //this leaves more 3 walled empty squares if
we need them
res2 -= hh * 3;
} else {
hh -= r + c - 2;
res2 -= (r + c - 2) * 3;
res2 -= hh * 2;
}
return Math.min(res1, res2);
}
}
private void solve() throws IOException {
int n = nextInt();
for (int i = 0; i < n; i++) {
int res = solveTest();
System.out.println("Case #" + (i + 1) + ": " + res);
out.println("Case #" + (i + 1) + ": " + res);
}
}
BufferedReader br;
StringTokenizer st;
PrintWriter out;
String next() throws IOException {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
public static void main(String[] args) throws FileNotFoundException {
new B().run();
}
private void run() throws FileNotFoundException {
br = new BufferedReader(new FileReader(this.getClass().getSimpleName()
+ ".in"));
out = new PrintWriter(this.getClass().getSimpleName() + ".out");
try {
solve();
} catch (IOException e) {
e.printStackTrace();
}
out.close();
}
}
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/3b57a214-3f0d-4fff-a32d-44f6fe407645%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
