Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.*;
  4.  
  5. public class Solution {
  6.  
  7. static Scanner in;
  8. public static void main(String[] args) {
  9. in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  10. int t = Integer.parseInt(in.nextLine()); // Scanner has functions to read ints, longs, strings, chars, etc.
  11. for (int i = 1; i <= t; ++i) {
  12. solve(i);
  13. System.out.flush();
  14. }
  15. }
  16.  
  17. public static void solve(int caseid) {
  18. int antCount = Integer.parseInt(in.nextLine());
  19.  
  20. Iterator<Long> antWeights = Arrays.stream(in.nextLine().split(" ")).map(Long::parseLong).iterator();
  21. //Store length of stack and best weight
  22. HashMap<Integer, Long> records = new HashMap<>();
  23. records.put(0, 0L);
  24.  
  25. //Loop through ants
  26. while(antWeights.hasNext()) {
  27. long antWeight = antWeights.next();
  28. //Check against all current records
  29. for(Map.Entry<Integer, Long> record : clone(records).entrySet()) {
  30. //Check if ant can be put below stack
  31. if(record.getValue() <= 6 * antWeight) {
  32. //Check if putting ant below stack improves solution
  33. long oldWeight = records.getOrDefault(record.getKey() + 1, Long.MAX_VALUE);
  34. long newWeight = record.getValue() + antWeight;
  35. if(newWeight < oldWeight) {
  36. //Save new record
  37. records.put(record.getKey() + 1, newWeight);
  38. }
  39. }
  40. }
  41. }
  42.  
  43. //Find optimal solution
  44. int best = 0;
  45. for(Map.Entry<Integer, Long> record : records.entrySet()) {
  46. if(record.getKey() > best) {
  47. best = record.getKey();
  48. }
  49. }
  50. System.out.println("Case #" + caseid + ": " + best);
  51. }
  52.  
  53. public static<K,V> Map<K,V> clone(Map<K,V> original) {
  54. Map<K,V> copy = new HashMap<>();
  55. copy.putAll(original);
  56. return copy;
  57. }
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement