import java.util.*;
import java.lang.*;
import java.io.*;
/**
* @author Cosimo Damiano Prete
*/
class Ideone
{
{
int[] towers = {4, 2, 0, 0, 2, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{0, 1};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{1, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{1, 1};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{3, 0, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{3, 0, 0, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{3, 0, 0, 2, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{3, 0, 0, 1, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{4, 3, 0, 3, 1, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{3, 0, 2, 0, 1, 1, 1, 3, 0, 0, 5, 1, 2, 3, 4, 0, 1, 2, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{4, 0, 4, 0, 0, 0};
System.
out.
println(isHoppable
(towers
));
towers = new int[]{4, 0, 3, 0, 0, 0};
System.
out.
println(isHoppable
(towers
)); }
public static boolean isHoppable(int[] towers) {
if(towers == null || towers.length == 0 || towers[0] == 0) {
return false;
}
// These would be the nodes of the graph, but since we don't need to BSF
// or DSF it (the problem doesn't require to indicate the path) we don't
// need then to store the edges.
// In short, we need to store just the distances (or indexes) we can
// reach while "constructing" the graph.
indexes[0] = 0;
for(int i = 0; i < towers.length; i++) {
int currentIndex = indexes[i];
int heigth = towers[currentIndex];
for(int j = i + 1; j <= i + heigth; j++) {
if(j == towers.length) {
return true;
}
indexes[j] = j;
}
}
return false;
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKioKICogQGF1dGhvciBDb3NpbW8gRGFtaWFubyBQcmV0ZQogKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCWludFtdIHRvd2VycyA9IHs0LCAyLCAwLCAwLCAyLCAwfTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oaXNIb3BwYWJsZSh0b3dlcnMpKTsKCQkKCQl0b3dlcnMgPSBuZXcgaW50W117MCwgMX07CgkJU3lzdGVtLm91dC5wcmludGxuKGlzSG9wcGFibGUodG93ZXJzKSk7CgkJCgkJdG93ZXJzID0gbmV3IGludFtdezEsIDB9OwoJCVN5c3RlbS5vdXQucHJpbnRsbihpc0hvcHBhYmxlKHRvd2VycykpOwoJCQoJCXRvd2VycyA9IG5ldyBpbnRbXXsxLCAxfTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oaXNIb3BwYWJsZSh0b3dlcnMpKTsKCQkKCQl0b3dlcnMgPSBuZXcgaW50W117MywgMCwgMH07CgkJU3lzdGVtLm91dC5wcmludGxuKGlzSG9wcGFibGUodG93ZXJzKSk7CgkJCgkJdG93ZXJzID0gbmV3IGludFtdezMsIDAsIDAsIDB9OwoJCVN5c3RlbS5vdXQucHJpbnRsbihpc0hvcHBhYmxlKHRvd2VycykpOwoJCQoJCXRvd2VycyA9IG5ldyBpbnRbXXszLCAwLCAwLCAyLCAwfTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oaXNIb3BwYWJsZSh0b3dlcnMpKTsKCQkKCQl0b3dlcnMgPSBuZXcgaW50W117MywgMCwgMCwgMSwgMH07CgkJU3lzdGVtLm91dC5wcmludGxuKGlzSG9wcGFibGUodG93ZXJzKSk7CgkJCgkJdG93ZXJzID0gbmV3IGludFtdezQsIDMsIDAsIDMsIDEsIDB9OwoJCVN5c3RlbS5vdXQucHJpbnRsbihpc0hvcHBhYmxlKHRvd2VycykpOwoJCQoJCXRvd2VycyA9IG5ldyBpbnRbXXszLCAwLCAyLCAwLCAxLCAxLCAxLCAzLCAwLCAwLCA1LCAxLCAyLCAzLCA0LCAwLCAxLCAyLCAwfTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oaXNIb3BwYWJsZSh0b3dlcnMpKTsKCQkKCQl0b3dlcnMgPSBuZXcgaW50W117NCwgMCwgNCwgMCwgMCwgMH07CgkJU3lzdGVtLm91dC5wcmludGxuKGlzSG9wcGFibGUodG93ZXJzKSk7CgkJCgkJdG93ZXJzID0gbmV3IGludFtdezQsIDAsIDMsIDAsIDAsIDB9OwoJCVN5c3RlbS5vdXQucHJpbnRsbihpc0hvcHBhYmxlKHRvd2VycykpOwoJfQoJCglwdWJsaWMgc3RhdGljIGJvb2xlYW4gaXNIb3BwYWJsZShpbnRbXSB0b3dlcnMpIHsKCQlpZih0b3dlcnMgPT0gbnVsbCB8fCB0b3dlcnMubGVuZ3RoID09IDAgfHwgdG93ZXJzWzBdID09IDApIHsKCQkJcmV0dXJuIGZhbHNlOwoJCX0KCQkKCQkvLyBUaGVzZSB3b3VsZCBiZSB0aGUgbm9kZXMgb2YgdGhlIGdyYXBoLCBidXQgc2luY2Ugd2UgZG9uJ3QgbmVlZCB0byBCU0YgCgkJLy8gb3IgRFNGIGl0ICh0aGUgcHJvYmxlbSBkb2Vzbid0IHJlcXVpcmUgdG8gaW5kaWNhdGUgdGhlIHBhdGgpIHdlIGRvbid0IAoJCS8vIG5lZWQgdGhlbiB0byBzdG9yZSB0aGUgZWRnZXMuCgkJLy8gSW4gc2hvcnQsIHdlIG5lZWQgdG8gc3RvcmUganVzdCB0aGUgZGlzdGFuY2VzIChvciBpbmRleGVzKSB3ZSBjYW4gCgkJLy8gcmVhY2ggd2hpbGUgImNvbnN0cnVjdGluZyIgdGhlIGdyYXBoLgoJCUludGVnZXJbXSBpbmRleGVzID0gbmV3IEludGVnZXJbdG93ZXJzLmxlbmd0aF07CgkJaW5kZXhlc1swXSA9IDA7CgkJZm9yKGludCBpID0gMDsgaSA8IHRvd2Vycy5sZW5ndGg7IGkrKykgewoJCQlpbnQgY3VycmVudEluZGV4ID0gaW5kZXhlc1tpXTsKCQkJCgkJCWludCBoZWlndGggPSB0b3dlcnNbY3VycmVudEluZGV4XTsKCQkJZm9yKGludCBqID0gaSArIDE7IGogPD0gaSArIGhlaWd0aDsgaisrKSB7CgkJCQlpZihqID09IHRvd2Vycy5sZW5ndGgpIHsKCQkJCQlyZXR1cm4gdHJ1ZTsKCQkJCX0KCQkJCQoJCQkJaW5kZXhlc1tqXSA9IGo7CgkJCX0KCQl9CgkJCgkJcmV0dXJuIGZhbHNlOwoJfQp9