Fantasy's World


  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  6 Posts :: 0 Stories :: 16 Comments :: 0 Trackbacks

Problem Statement



When a stone is thrown across water, sometimes it will land on the water and bounce rather than falling in right away. Suppose that a stone is thrown a distance of n. On each successive bounce it will travel half the distance as the previous bounce (rounded down to the nearest integer). When it can not travel any further, it falls into the water. If, at any point, the stone lands on an obstruction rather than water, it will not bounce, but will simply deflect and fall into the water. Please look at the figure for further clarification (with black, red and green cells representing banks, obstructions and free water respectively). So, if the stone is thrown a distance 7, it will bounce and travel a distance of 3, then finally a distance of 1, having travelled a total distance of 11 (the green path in the figure). If a stone is thrown a distance of 8, it will reach the opposite bank, and if thrown at distances of 2 or 6 it will hit an obstruction during its travel. These are the three red paths in the figure.

You are given a String water. An 'X' represents an obstruction, while a '.' represents water free from obstruction. You are to return an int representing the maximum distance a stone can travel and finally fall in the water, without hitting any obstructions, and without reaching the opposite bank (going beyond the end of the string). You may choose any initial distance for the throw, which starts from the left side of the string. A distance of 1 is the first character of the string, etc. If no initial throw will result in the stone landing in the water without hitting an obstruction, return 0.











Method signature:

int maxDistance(String water)

(be sure your method is public)







Obstructions are at water level, so the stone will not hit any obstructions while it's in the air.



water will contain between 1 and 50 elements, inclusive.


Each element of water will contain between 1 and 50 characters, inclusive.


Each character of each element of water will be 'X' or '.'.






Returns: 11

This is the example from the problem statement.





Returns: 3

If it weren't for the obstruction, we could start with a throw of distance 4, and go a total of 7. But, the best we can do is to throw the stone a distance of 2, and have it skip a distance of 1.





Returns: 22

12 + 6 + 3 + 1 = 22, is the best case.





Returns: 15

Here, an initial throw of 8 is the only way to avoid hitting an obstruction. Notice that the stone finally falls in the water just before reaching the opposite bank.




public class SkipStones
 public int sum;
 public int total;
 public int maxDistance(String water)
  for(int i=water.length();i>0;i--)
   int j=i;
   if(sum>water.length()) continue;
    int b=j-1;
     if(water.charAt(b)=='X') break;
    if(total==sum) break;
   if(total==sum) return sum;
   else return 0;
 public static void main(String[] args)
  SkipStones a=new SkipStones();
  System.out.println("The maxdistance is "+a.maxDistance("..X.....X..."));
posted on 2005-12-14 16:32 FinalFantasy 阅读(1652) 评论(5)  编辑  收藏 所属分类: 新闻


# re: Google编程挑战赛250分题目及答案 2005-12-14 16:48 吴淦
听你的口气,难道楼主冠军势在必得?  回复  更多评论

# re: Google编程挑战赛250分题目及答案 2005-12-14 19:07 luffy520
嗯...加油  回复  更多评论

# re: Google编程挑战赛250分题目及答案 2005-12-15 11:28 FinalFantasy
呵呵,很不巧的是比赛那天我发烧了,进去只把题目给拷了出来:(如果那天我没生病的话,我想通过入围赛是不成问题的,不过其它的就不敢说了,毕竟谁也不知道google的下一步会是怎样的:)  回复  更多评论

# re: Google编程挑战赛250分题目及答案 2005-12-15 13:32 Spirit

public class SkipStones {
private String water = "...X...";

public int maxDistance(String water) {
this.water = water;
int max = 0;
int sum = 0;
for (int initial = 1; initial < water.length() + 1; initial++) {
sum = bounce(0, initial);
max = (sum > max ? sum : max);
return max;

private int bounce(int startDistance, int bounceDistance) {
if (bounceDistance == 0)
return startDistance;

if ((startDistance + bounceDistance) > water.length())
return -1;

if (water.charAt(startDistance + bounceDistance - 1) == 'X')
return startDistance;

return bounce(startDistance + bounceDistance, bounceDistance / 2);

public static void main(String[] args) {
SkipStones skipStones = new SkipStones();
  回复  更多评论

# re: Google编程挑战赛250分题目及答案 2005-12-15 16:33 FinalFantasy
呵呵,谢谢Spirit了。其实刚开始的时候我也是想到用递归的,但是觉得用这种方法好理解一些,所以就造这种思路写出来了..........  回复  更多评论