emu in blogjava

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks

SkipStones 
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.

给予一个 String 输入:water. 其内’X'字符代表礁石,’.’ 代表无礁石水面。你的程序
返回一个整数int,表示该石头在最终落入水中的情况下运行的总最大距离,触礁、撞岸的
情形都必须排除。其中撞岸表征为 (字符串访问越上界). 你可以选择任何初始的投掷距离
,出发点为字符串最左侧。距离为1则抵达字符串的第一个字符,依此类推。如果没有投掷
距离,石头被当作直接入水,返回量为0。

定义:

Class:
SkipStones
Method:
maxDistance
Parameters:
String
Returns:
int
Method signature:
int maxDistance(String water)
(确保你的函数为公共类型 public)

注:
礁石处在水面,所以不存在石头入水后撞礁的情形。

限制条件:-
water 字符串包含1到50个元素[即礁石或水面],1、50包含在内。
water的每个元素包含1到50个字符, 1、50包含在内。
water的每个元素的每个字符要么是’X',要么是 ‘.’.

测试例子

0)

“..X…..X…”
返回: 11
该例正如题目中(绿色轨迹)所图示。

1)

“…X…”
返回: 3
假如没有该礁石,可以扔一距离4,从而总距离为7。但在有礁石情形下,最佳则是扔出距离2

,再跳1而停止。

2)

“….X….X…XXXX.X…..”
返回: 22
12 + 6 + 3 + 1 = 22, 为最佳结果.

3)

“XXXXXXX.XXX.X..”
返回: 15

posted on 2005-12-13 13:39 emu 阅读(2824) 评论(4)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: google中国编程挑战赛资格赛真题 -- SkipStones (朋友转过来的时候顺便给翻译了) 2005-12-13 14:38 Btw0
上个星期开始看 Thinking in Java,书还没看完~~~
我的解:

public class SkipStones {
public int maxDistance(String water) {
int maxDistance = 0;
int lastDistance = 0;
int totalDistance = 0;
for (int i=0; i<water.length(); i++) {
if (water.charAt(i) == 'X') {
maxDistance = 0;
} else {
int distance = (i + 1);
totalDistance = distance;
while (distance/2 >= 1) {
distance = (int)distance/2;
totalDistance += distance;
if ((totalDistance > water.length()) || (water.charAt(totalDistance-1) == 'X')) {
maxDistance = 0;
break;
} else {
maxDistance = totalDistance;
}
}
}
maxDistance = (maxDistance > lastDistance) ? maxDistance : lastDistance;
lastDistance = maxDistance;
}
return maxDistance;
}
public static void main(String[] args){
System.out.println(new SkipStones().maxDistance("..X.....X..."));
System.out.println(new SkipStones().maxDistance("...X..."));
System.out.println(new SkipStones().maxDistance("....X....X...XXXX.X....."));
System.out.println(new SkipStones().maxDistance("XXXXXXX.XXX.X.."));
}
}  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- SkipStones (朋友转过来的时候顺便给翻译了) 2006-07-30 14:00 eyaswoo
如果倒过来想,从water的最后一个开始,假设是落水点,可以倒跳1,23,4567,就是一个二叉树,遍历之,若符合一定条件就跳出,当有一次遍历可以到达起始岸就成功,这时的n就是这个最远距离。  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- SkipStones (朋友转过来的时候顺便给翻译了) 2006-07-30 14:01 eyaswoo
不知道逻辑有没有问题啊  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- SkipStones (朋友转过来的时候顺便给翻译了) 2008-09-22 16:07 hejian
感觉这种穷举的办法,还不如正着来得快  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: