首页 > 代码库 > 【HackerRank】Manasa and Stones

【HackerRank】Manasa and Stones

2024-07-14 17:46:27   221人阅读

Change language :

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 here23          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 }

 


联系
我们