fork download 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4.  class Solution {
  5.     static class State {
  6.         long s;
  7.         int last;
  8.         int steps;
  9.         State(long s, int last, int steps) { this.s = s; this.last = last; this.steps = steps; }
  10.     }
  11.  
  12.     public static int Solve(int N, String Xstr, List<Integer> A) {
  13.         long X = Long.parseLong(Xstr);
  14.         for (int v : A) if (v == X) return 0;
  15.  
  16.         Set<Long> targets = new HashSet<>();
  17.         long maxTarget = Long.MIN_VALUE;
  18.         for (int v : A) {
  19.             long t = X - v;
  20.             targets.add(t);
  21.             if (t > maxTarget) maxTarget = t;
  22.         }
  23.  
  24.         HashMap<Long, ArrayList<Integer>> posMap = new HashMap<>();
  25.         for (int i = 0; i < N; ++i) {
  26.             long val = A.get(i);
  27.             posMap.computeIfAbsent(val, k -> new ArrayList<>()).add(i);
  28.         }
  29.  
  30.         ArrayDeque<State> q = new ArrayDeque<>();
  31.         HashMap<Long, BitSet> visited = new HashMap<>();
  32.         final int NONE_IDX = N;
  33.  
  34.         q.add(new State(0L, -1, 0));
  35.         BitSet bs0 = new BitSet(N + 1);
  36.         bs0.set(NONE_IDX);
  37.         visited.put(0L, bs0);
  38.  
  39.         while (!q.isEmpty()) {
  40.             State cur = q.poll();
  41.             long curS = cur.s;
  42.             int curLast = cur.last;
  43.             int curSteps = cur.steps;
  44.  
  45.             for (int j = 0; j < N; ++j) {
  46.                 if (j == curLast) continue;
  47.                 long newS = 2L * curS + A.get(j);
  48.                 if (newS > maxTarget) continue;
  49.  
  50.                 long needed = X - newS;
  51.                 ArrayList<Integer> positions = posMap.get(needed);
  52.                 if (positions != null && !positions.isEmpty()) return curSteps + 1;
  53.  
  54.                 BitSet bs = visited.get(newS);
  55.                 int idxToSet = j;
  56.                 if (bs == null) {
  57.                     bs = new BitSet(N + 1);
  58.                     bs.set(idxToSet);
  59.                     visited.put(newS, bs);
  60.                     q.add(new State(newS, j, curSteps + 1));
  61.                 } else if (!bs.get(idxToSet)) {
  62.                     bs.set(idxToSet);
  63.                     q.add(new State(newS, j, curSteps + 1));
  64.                 }
  65.             }
  66.         }
  67.  
  68.         return -1;
  69.     }
  70.  
  71.     public static void main(String[] args) {
  72.         Scanner scan = new Scanner(System.in);
  73.         int N = Integer.parseInt(scan.nextLine().trim());
  74.         String X = scan.nextLine().trim();
  75.         List<Integer> A = new ArrayList<>();
  76.         for (int i = 0; i < N; i++) A.add(Integer.parseInt(scan.nextLine().trim()));
  77.         System.out.println(Solve(N, X, A));
  78.     }
  79. }
  80.  
Success #stdin #stdout 0.12s 54688KB
comments (?)
stdin 
4
7
2
11
6
55
stdout 
-1
https://ideone.com/g51lc2
language:
Java (HotSpot 12)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!