1 2 import java.io.*; 3 import java.util.*; 4 import java.awt.*; 5 import java.text.*; 6 import java.math.*; 7 8 /** 9 * Solution for The Ninja Way 10 * 11 * This program will use a Greedy algorithm. First, it'll assume that the trees are 12 * laid out right next to each other, as tightly as possible. Then, it'll find the 13 * positions of the smallest and largest trees - let's say s and t - and then try to 14 * stretch the gap between s and s+1 as far as possible, then the gap between s+1 and s+2, 15 * then s+2 and s+3, all the way up to t-1 and t. It will look at all pairs of trees that 16 * are adjacent height-wise (that the Ninjas would jump between) that span each of those gaps, 17 * to see how far the gaps can be stretched. 18 * 19 * The only way the Greedy algorithm can fail is if stretching an early gap limits your 20 * options of stretching a later gap. I'm not going to go through a convoluted argument, 21 * but it's true. It's left as an exercise to the reader to confirm! 22 */ 23 class ninjaway 24 { 25 public Scanner sc; 26 public PrintStream ps; 27 28 public String toString() 29 { 30 return "ninjaway"; 31 } 32 33 /** 34 * The main method 35 */ 36 public void doit() throws Exception 37 { 38 sc = new Scanner( System.in ); // new Scanner( new File( "ninjaway.judge" ) ); 39 ps = System.out; // new PrintStream( new FileOutputStream( "ninjaway.solution" ) ); 40 41 for(;;) 42 { 43 // Read in n & d, exit if at end 44 int n = sc.nextInt(); 45 int d = sc.nextInt(); 46 if( n==0 ) break; 47 48 // The trees, in order of input 49 int trees[] = new int[n]; 50 51 // An array to sort the trees by height 52 int sorted[] = new int[n]; 53 54 // Read in the trees 55 for( int i=0; i<n; i++ ) 56 { 57 trees[i] = sc.nextInt(); 58 sorted[i] = trees[i]; 59 } 60 Arrays.sort( sorted ); 61 62 // position[i] is the position, in the input order, of the ith shortest tree. 63 // So, position[0] is the position of the shortest tree, and 64 // position[n-1] is the position of the tallest tree. 65 int position[] = new int[n]; 66 for( int i=0; i<n; i++ ) 67 { 68 int p = Arrays.binarySearch( sorted, trees[i] ); 69 position[p] = i; 70 } 71 72 // start and finish will be our limits - the positions of 73 // the shortest and tallest trees, with start<finish 74 int start = position[0]; 75 int finish = position[n-1]; 76 if( finish<start ) 77 { 78 int t = start; 79 start = finish; 80 finish = t; 81 } 82 83 // dist[i] is the distance between the ith shortest 84 // tree and the i+1st shortest tree. It's the distance 85 // the ninjas must jump to get from tree i to the next tree in height. 86 // We'll start with the assumption that the trees are packed 87 // as tightly as possible. If this distance, under those conditions, 88 // is greater than D, then it's impossible to find a solution. 89 int dist[] = new int[n]; 90 boolean failed = false; 91 for( int i=0; i<n-1; i++ ) 92 { 93 dist[i] = Math.abs( position[i+1]-position[i] ); 94 if( dist[i]>d ) failed=true; 95 } 96 97 // This'll be our answer 98 int total; 99 100 // if we failed, then the answer is -1 101 if( failed ) 102 { 103 total = -1; 104 } 105 else 106 { 107 // OK, it gets a little confusing here. We're going to have two indexing schemes. 108 // i is going to represent height order (i==0 is the smallest tree), and 109 // j is going to represent order on the ground (j==0 is the first tree in the input) 110 // This will hold true throughout the rest of the code. 111 // 112 // spans[i][j] is true if the space between trees i and i+1 spans gap j. 113 // That is, if the space between trees i and i+1 (in height order) crosses 114 // the gap between trees j and j+1 (on the ground), then span[i][j] is true. 115 boolean spans[][] = new boolean[n][n]; 116 for( int i=0; i<n; i++ ) 117 { 118 Arrays.fill( spans[i], false ); 119 } 120 for( int i=0; i<n-1; i++ ) 121 { 122 int lo = Math.min( position[i], position[i+1] ); 123 int hi = Math.max( position[i], position[i+1] ); 124 for( int j=lo; j<hi; j++ ) 125 { 126 spans[i][j] = true; 127 } 128 } 129 130 // At first, before stretching any gaps, this is the distance. 131 total = finish-start; 132 133 // Now, we'll go through all of the gaps between the start and the finish, 134 // and stretch them as far as we can. 135 for( int j=start; j<finish; j++ ) 136 { 137 // Find the biggest distance of all (i,i+1) pairs 138 // that cross this gap. That's a limiting condition. If 139 // we stretch this gap too much, that distance is in danger of 140 // getting to be >D. 141 int maxdist = 0; 142 for( int i=0; i<n-1; i++ ) if( spans[i][j] ) 143 { 144 if( dist[i]>maxdist ) 145 { 146 maxdist=dist[i]; 147 } 148 } 149 150 // The best we can do is to stretch that biggest 151 // gap to be D. 152 int stretch = d-maxdist; 153 154 // Add in the amount of this stretch 155 total += stretch; 156 157 // OK, stretch that gap! That means stretching ALL of 158 // the (i,i+1) pairs that span the gap! 159 for( int i=0; i<n-1; i++ ) if( spans[i][j] ) 160 { 161 dist[i] += stretch; 162 } 163 } 164 } 165 166 // That's it! Now, just print the total. 167 ps.println( total ); 168 } 169 } 170 171 public static void main(String[] args) throws Exception 172 { 173 long starttime = System.currentTimeMillis(); 174 new ninjaway().doit(); 175 System.out.println( System.currentTimeMillis() - starttime ); 176 } 177 }