fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Solution {
  5.     public static int Solve(int N, String Xstr, List<Integer> A) {
  6.         long X = Long.parseLong(Xstr);
  7.         for (int v : A) if (v == X) return 0;
  8.  
  9.         Set<Long> targets = new HashSet<>();
  10.         long maxTarget = Long.MIN_VALUE;
  11.         for (int v : A) {
  12.             long t = X - v;
  13.             targets.add(t);
  14.             if (t > maxTarget) maxTarget = t;
  15.         }
  16.  
  17.         class State { 
  18.             long s; 
  19.             int last; 
  20.             int steps; 
  21.             State(long s, int l, int st) { this.s = s; this.last = l; this.steps = st; } 
  22.         }
  23.  
  24.         Queue<State> q = new ArrayDeque<>();
  25.         Set<String> visited = new HashSet<>();
  26.  
  27.         q.add(new State(0L, -1, 0));
  28.         visited.add("0," + -1);
  29.  
  30.         while (!q.isEmpty()) {
  31.             State cur = q.poll();
  32.             for (int j = 0; j < N; ++j) {
  33.                 if (j == cur.last) continue;
  34.                 long newS = 2L * cur.s + A.get(j);
  35.                 if (targets.contains(newS)) return cur.steps + 1;
  36.                 if (newS > maxTarget) continue;
  37.                 String key = newS + "," + j;
  38.                 if (!visited.contains(key)) {
  39.                     visited.add(key);
  40.                     q.add(new State(newS, j, cur.steps + 1));
  41.                 }
  42.             }
  43.         }
  44.         return -1;
  45.     }
  46.  
  47.     public static void main(String[] args) {
  48.         Scanner scan = new Scanner(System.in);
  49.         int N = Integer.parseInt(scan.nextLine().trim());
  50.         String X = scan.nextLine().trim();
  51.         List<Integer> A = new ArrayList<>();
  52.         for (int i = 0; i < N; i++) A.add(Integer.parseInt(scan.nextLine().trim()));
  53.         System.out.println(Solve(N, X, A));
  54.     }
  55. }
  56.  
Success #stdin #stdout 0.23s 58744KB
comments (?)
stdin
copy 
2
936302870394
243
42
stdout
copy 
33
https://ideone.com/dEZdOb
language:
Java (HotSpot 12)
created:
11 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!