Do I need to consider Java’s recursion limit? I saw sometime DFS is implemented by recursion, sometime by stack. I am wondering if the USACO needs to worry about Java’s recursion, should I always use BFS with Queue? Thanks.
1 Like
Looks like there isn’t an explicit recursion limit. You should be fine as long as you fit within time/memory.
(Seems that Java is always given over a gigabyte …)
/** Simple yet moderately fast I/O routines.
*
* Example usage:
*
* Kattio io = new Kattio();
*
* while (io.hasMoreTokens()) {
* int n = io.nextInt();
* double d = io.nextDouble();
* double ans = d*n;
*
* io.println("Answer: " + ans);
* }
*
* io.close();
*
*
* Some notes:
*
* - When done, you should always do io.close() or io.flush() on the
* Kattio-instance, otherwise, you may lose output.
*
* - The nextInt(), nextDouble(), and nextLong() methods will throw an
* exception if there is no more data in the input, so it is generally
* a good idea to use hasMoreTokens() to check for end-of-file.
*
* @author: Kattis
*/
import java.util.*;
import java.io.*;
class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st = new StringTokenizer("");
private String token;
// standard input
public Kattio() { this(System.in,System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(new FileWriter(problemName+".out"));
r = new BufferedReader(new FileReader(problemName+".in"));
}
private String peek() {
if (token == null)
try {
while (!st.hasMoreTokens()) {
String line = r.readLine();
if (line == null) return null;
st = new StringTokenizer(line);
}
token = st.nextToken();
} catch (IOException e) { }
return token;
}
public boolean hasMoreTokens() { return peek() != null; }
public String next() {
String ans = peek();
token = null;
return ans;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
public class ha {
static Kattio io;
static {
try {
io = new Kattio("mowing");
} catch(IOException e) {}
}
public static void dfs(int x) {
if (x == 44000000) return;
// System.out.println(x+" ");
dfs(x+1);
}
public static void main(String[] args) {
dfs(0);
io.println(117);
io.flush();
}
}
2 Likes