fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class Ideone
  8. {
  9.     static final int GOAL = 100;
  10.  
  11.     public static void main(String[] args)
  12.     {
  13.         int[] red = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 99 };
  14.         int[] blue = { 90, 80, 70, 60, 50, 40, 30, 20, 10, 1, };
  15.  
  16.         Result result = solve(red, blue);
  17.         System.out.println(result);
  18.     }
  19.  
  20.     static class Result
  21.     {
  22.         int distance = Integer.MAX_VALUE;
  23.         int[] move;
  24.  
  25.         @Override
  26.         public String toString()
  27.         {
  28.             return String.format("%d %s", distance, Arrays.toString(move));
  29.         }
  30.     }
  31.  
  32.     public static Result solve(int[] red, int[] blue)
  33.     {
  34.         Result result = new Result();
  35.         solve(0, 0, 0, red, 0, blue, 0, new int[red.length + blue.length + 2], 0, result);
  36.         return result;
  37.     }
  38.  
  39.     static void solve(int pos, int dir, int distance, int[] red, int r, int[] blue, int b, int[] move, int m, Result result)
  40.     {
  41.         if (red.length == r && blue.length == b)
  42.         {
  43.             distance += Math.abs(GOAL - pos);
  44.             if (distance >= result.distance) return;
  45.             int g_dir = Integer.signum(GOAL - pos);
  46.             if (g_dir != dir) move[m++] = pos;
  47.             move[m++] = GOAL;
  48.             result.move = Arrays.copyOf(move, m);
  49.             result.distance = distance;
  50.             return;
  51.         }
  52.  
  53.         if (red[r] == blue[b])
  54.         {
  55.             solve(pos, red[r], dir, distance, red, r + 1, blue, b + 1, move, m, result);
  56.             return;
  57.         }
  58.  
  59.         int r_dir = Integer.signum(red[r] - pos);
  60.         int b_dir = Integer.signum(blue[b] - pos);
  61.         if (r_dir == b_dir)
  62.         {
  63.             if (Math.abs(pos - red[r]) < Math.abs(pos - blue[b]))
  64.                 solve(pos, red[r], dir, distance, red, r + 1, blue, b, move, m, result);
  65.             else
  66.                 solve(pos, blue[b], dir, distance, red, r, blue, b + 1, move, m, result);
  67.             return;
  68.         }
  69.         solve(pos, red[r], dir, distance, red, r + 1, blue, b, move, m, result);
  70.         solve(pos, blue[b], dir, distance, red, r, blue, b + 1, move, m, result);
  71.     }
  72.  
  73.     static void solve(int pos, int next, int dir, int distance, int[] red, int r, int[] blue, int b, int[] move, int m, Result result)
  74.     {
  75.         while(r < red.length && next == red[r]) r++;
  76.         while(b < blue.length && next == blue[b]) b++;
  77.         distance += Math.abs(next - pos);
  78.         if (distance >= result.distance) return;
  79.         int n_dir = Integer.signum(next - pos);
  80.         if (n_dir != dir) move[m++] = pos;
  81.  
  82.         if (red.length == r) { red = blue; r = b; }
  83.         if (blue.length == b) { blue = red; b = r; }
  84.  
  85.         solve(next, n_dir, distance, red, r, blue, b, move, m, result);
  86.     }
  87. }
  88.  
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
278 [0, 90, 1, 100]
https://ideone.com/lHFW4d
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

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!