Manasa 和 她的朋友出去徒步旅行。她发现一条小河里边顺序排列着带有数值的石头。她开始沿河而走,发现相邻两个石头上的数值增加 a 或者 b. 这条小河的尽头有一个宝藏,如果Manasa能够猜出来最后一颗石头上的数值,那么宝藏就是她的。假设第一个石头的上数值为0,找出最后一个石头的可能的所有数值。
输入格式
第一行包含整数 T, 代表测试数据的组数。
每组数组包含三行:
第一行包含 n,代表石头的个数
第二行包含 a
第三行包含 b
输出格式 升序输出最后一颗石头上所有可能的数值, 用空格隔开。
取值范围
1 ≤ T ≤ 10
1 ≤ n, a, b ≤ 103
题解:
对于第二个石头,可能的取值是0*a+b或者a+0*b;
对于第三个石头,可能的取值是0*a+2*b,1*a+1*b,2*a+0*b;
.....
对于第n个石头,可能的取值是0*a+(n-1)*b,1*a+(n-2)*b,......,(n-1)*a+0*b;
所以只要枚举a和b的系数就可以算出所有的可能了。
另外,java中的hashset是无需的,treeset是有序的。
代码如下:
1 import java.io.*; 2 import java.util.*; 3 4 5 public class Solution { 6 7 public static void main(String[] args) { 8 Scanner in = new Scanner(System.in); 9 int t = in.nextInt(); 10 for(int i = 0; i < t; i++){ 11 Set<Long> answer= ManasaandStones(in.nextLong(), in.nextLong(), in.nextLong()); 12 Iterator<Long> iterator = answer.iterator(); 13 while(iterator.hasNext()){ 14 System.out.printf("%d ",iterator.next()); 15 } 16 System.out.println(); 17 } 18 } 19 20 private static Set<Long> ManasaandStones(long n, long a, long b){ 21 22 //Write code to solve each of the test over here 23 if(a > b){ 24 long temp = b; 25 b = a; 26 a = temp; 27 } 28 Set<Long> hs = new TreeSet<Long>(); 29 for(int i = 0;i <= n-1;i++){ 30 hs.add(i*b+(n-1-i)*a); 31 } 32 return hs; 33 } 34 35 36 }
【HackerRank】Manasa and Stones,布布扣,bubuko.com
原文:http://www.cnblogs.com/sunshineatnoon/p/3876141.html