The Java Program: F_ninja/ninjawayYiu.java
1
2
3
4
5
6
7
8
9 import java.io.*;
10 import java.util.*;
11
12 public class ninjawayYiu
13 {
14 public final int oo = 1000000000 + 1000;
15
16 public Scanner in = new Scanner(System.in);
17 public PrintStream out = System.out;
18
19 public int n, D;
20 public Tree[] v;
21 public int[] L, R;
22
23 private class Tree implements Comparable<Tree>
24 {
25
26
27 public int i, h;
28 public Tree(int ii, int hh) { i = ii; h = hh; }
29 public int compareTo(Tree u) { return h - u.h; }
30 }
31
32 public void main()
33 {
34 int i, j, k, x;
35
36 n = in.nextInt();
37 while(n > 0)
38 {
39 D = in.nextInt();
40
41 v = new Tree[n];
42
43
44 L = new int[n];
45 R = new int[n];
46
47 for(i=0;i<n;++i)
48 {
49 v[i] = new Tree(i, in.nextInt());
50 L[i] = -oo;
51 R[i] = oo;
52 }
53
54
55 Arrays.sort(v);
56
57
58 L[v[0].i] = R[v[0].i] = 0;
59
60 boolean done, poss;
61
62 done = false;
63 poss = true;
64
65 while(!done && poss)
66 {
67 done = true;
68
69
70 for(i=0;i+1<n;++i) if(L[i]+1 > L[i+1])
71 {
72 L[i+1] = L[i]+1;
73 done = false;
74 }
75
76
77 for(i=n-1;i-1>=0;--i) if(R[i]-1 < R[i-1])
78 {
79 R[i-1] = R[i]-1;
80 done = false;
81 }
82
83
84 for(x=0;x+1<n;++x)
85 {
86 i = v[x].i;
87 j = v[x+1].i;
88 if(L[i] - D > L[j])
89 {
90 L[j] = L[i] - D;
91 done = false;
92 }
93
94 if(R[i] + D < R[j])
95 {
96 R[j] = R[i] + D;
97 done = false;
98 }
99 }
100
101
102
103
104 for(x=n-1;x-1>=0;--x)
105 {
106 i = v[x].i;
107 j = v[x-1].i;
108
109 if(L[i] - D > L[j])
110 {
111 L[j] = L[i] - D;
112 done = false;
113 }
114
115 if(R[i] + D < R[j])
116 {
117 R[j] = R[i] + D;
118 done = false;
119 }
120 }
121
122 for(i=0;i<n;++i) if(L[i] > R[i]) poss = false;
123 }
124
125 if(poss)
126 {
127 i = v[n-1].i;
128
129
130 out.println(Math.max(Math.abs(L[i]), Math.abs(R[i])));
131 }
132 else
133 {
134 out.println(-1);
135 }
136
137 n = in.nextInt();
138 }
139 }
140
141
142
143 public static void main(String[] args)
144 {
145 long startTime = System.currentTimeMillis();
146 (new ninjawayYiu()).main();
147 long endTime = System.currentTimeMillis();
148
149 System.err.println("Time = "+(endTime - startTime)+"(ms)");
150 }
151 }