1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
import java.util.Arrays;

public class cie {

	static int len;
	static int maxNum;
	static int maxQuestNum;

	public static void main(String[] args) {
		len = cielib.podajD();
		maxNum = cielib.podajR();
		maxQuestNum = cielib.podajK();

		solve();
	}

	private static void solve() {
		int ourFirstDigit = maxNum / 2;

		int[] number = new int[len];
		Arrays.fill(number, ourFirstDigit);

		Boolean[] goUp = new Boolean[len];
		Arrays.fill(goUp, null);

		boolean problems = false;
		for (int i = 0; i < len; i++) {
			unifyDiff(number, goUp, i);
			if (goUp[i] == null) {
				problems = true;
			}
		}

		// we checked all the digits already
		if (problems) {
			// if there were problems
			// make one step for every number without problems
			makeStep(number, goUp, 1);
			// repeat the search for those with problems
			for (int i = 0; i < len; i++) {
				if (goUp[i] == null) {
					unifyDiff( number, goUp, i);
				}
			}
		}

		// step by step come to the solution
		if (test(number, goUp, 0)) {
			int left = 0;
			int right = maxNum;
			while (left + 1 < right) {
				int middle = (left + right)/2;
				if (test(number, goUp, middle)) {
					left = middle;
				} else {
					right = middle;
				}
			}
			makeStep(number, goUp, right);
		}

		// report founding
		propose(number);
	}

	private static boolean test(int[] number, Boolean[] goUp, int n) {
		makeStep(number, goUp, n);
		ask(number);
		makeStep(number, goUp, 1);
		boolean result = ask(number) == 1;
		makeStep(number, goUp, -n-1);
		return result;
	}

	/**
	 * Makes a number of steps in proper direction for digits with direction
	 * marked.
	 * 
	 * @param number
	 * @param goUp
	 * @param noOfSteps
	 */
	private static void makeStep(int[] number, Boolean[] goUp, int noOfSteps) {
		for (int i = 0; i < number.length; i++) {
			if (goUp[i] != null) {
				number[i] += goUp[i] ? noOfSteps : -noOfSteps;
			}
		}
	}

	static boolean testSearchUnified(int[] number, int index, int n, int direction){
		number[index] = n;
		ask(number);
		number[index] = n+direction;
		return ask(number) == 1;
	}
	
	static int searchUnifiedFromZero(int[] number, int index){
		if (!testSearchUnified(number, index, 0, 1)) return -1;
		
		int left = 0;
		int right = maxNum;
		
		while (left +1 < right) {
			int middle = (left+right)/2;
			if (testSearchUnified(number, index, middle, 1)) {
				left = middle;
			} else {
				right = middle;
			}
		}
		return right;
	}
	
	static int searchUnifiedFromMax(int[] number, int index){
		if (!testSearchUnified(number, index, maxNum, -1)) return -1;
		
		int left = 0;
		int right = maxNum;
		
		while (left +1 < right) {
			int middle = (left+right)/2;
			if (testSearchUnified(number, index, middle, -1)) {
				right = middle;
			} else {
				left = middle;
			}
		}
		return left;
	}
	/**
	 * Unifies all digits so they have the same distance to the corresponding
	 * digits in the solution. In case it is not possible leaves the digits as
	 * it was and direction is not marked.
	 * 
	 * @param maxNum
	 * @param hasMiddle
	 * @param number
	 * @param goUp
	 * @param index
	 * @return
	 */
	private static void unifyDiff( int[] number, Boolean[] goUp, int index) {
		// start from 0
		int resultDigit = searchUnifiedFromZero(number, index);

		if (resultDigit != -1) {
			goUp[index] = true; // we need to go up - increase the number
			number[index] = resultDigit;
			return;
		}

		// check other direction
		resultDigit = searchUnifiedFromMax(number, index);
		if (resultDigit != -1) {
			goUp[index] = false; // we need to go down - decrease the number
			number[index] = resultDigit;
			return;
		}

		// no direction suits
		// this means there is in the solution at least one border digit
		number[index] = maxNum / 2;
	}

	static int askCounter;
	private static int ask(int[] num) {
		if (outOfRange(num, maxNum)) {
			return 0;
		}
		return cielib.czyCieplo(num);
	}

	private static void propose(int[] num) {
		cielib.znalazlem(num);
	}

	private static boolean outOfRange(int[] num, int maxNum) {
		for (int n : num) {
			if (n < 0 || n > maxNum) {
				return true;
			}
		}
		return false;
	}

}