// Author: Gordon V. Cormack; solves Subtask 4
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <stdlib.h>
#include "grader.h"
int t[50];
#define max(a, b) ((a)>(b)?(a):(b))
#define min(a, b) ((a)<(b)?(a):(b))
int fix(int end, int x) {
// returns value at x steps from end
if (end == 1) return x;
return end-x+1;
}
int midgame(int p, int a, int b) {
// returns Jill's number, assuming
// p = previous guess, [a .. b] = interval of remaining candidates
if (a == b) return a;
if (a > b) {
int t = a;
a = b;
b = t;
}
// a < b
int sz, mid=-999;
for (sz=3; b-a+1 > sz; sz = 2*sz+1);
if (p < b-sz+1) mid = b-sz/2;
else if (p > a+sz-1) mid = a+sz/2;
else if (p <= a) mid = p+sz/2;
else if (p >= b) mid = p-sz/2;
int q = mid + (mid-p);
int g = Guess(q); // compares to mid
if (g == 0) return mid;
if (q > mid && g > 0 || q < mid && g < 0) return midgame(q, min(mid+1, b), b);
return midgame(q, a, max(mid-1, a));
}
int endgame(int end, int n){
// returns Jill's number, assuming
// end = value on edge (1 or N); n = number of remaining candidate values
int z, g;
for (z=0; t[z]<n; z++);
if (n == 2) {
g = Guess(fix(end, 1));
if (g > 0) return fix(end, 1);
return fix(end, 2);
}
if (n == 3) {
g = Guess(fix(end, 1));
if (g > 0) return fix(end, 1);
if (g == 0) return fix(end, 2);
if (g < 0) return fix(end, 3);
}
if (n == 4 || n == 5) {
g = Guess(fix(end, 3));
if (g < 0) return fix(end, n);
if (g == 0) return fix(end, 4);
g = Guess(fix(end, 1));
if (g > 0) return fix(end, 1);
if (g == 0) return fix(end, 2);
if (g < 0) return fix(end, 3);
}
if (n == 6) {
g = Guess(fix(end, 1));
if (g > 0) {
g = Guess(fix(end, 3));
if (g > 0) return fix(end, 3);
if (g == 0) return fix(end, 2);
if (g < 0) return fix(end, 1);
}
g = Guess(fix(end, 9));
if (g > 0) return fix(end, 6);
if (g == 0) return fix(end, 5);
if (g < 0) return fix(end, 4);
}
if (n == 7) {
g = Guess(fix(end, 1));
if (g == 0) return fix(end, 4);
if (g > 0) {
int g = Guess(fix(end, 3));
if (g > 0) return fix(end, 3);
if (g == 0) return fix(end, 2);
return fix(end, 1);
}
g = Guess(fix(end, 11));
if (g > 0) return fix(end, 7);
if (g == 0) return fix(end, 6);
if (g < 0) return fix(end, 5);
}
g = Guess(fix(end, t[z-2]-2));
if (g == 0) return fix(end, (t[z-2]-2+n)/2);
if (g < 0) return midgame(fix(end, t[z-2]-2), fix(end, (t[z-2]-2+n)/2+1), fix(end, n));
// g > 0
g = Guess(fix(end, t[z-2]));
if (g < 0) return endgame(end, t[z-2]);
if (g == 0) return fix(end, t[z-2]-1);
return midgame(fix(end, t[z-2]), fix(end, t[z-2]), fix(end, (t[z-2]-2+n-1)/2));
return 0;
}
int HC(int N) {
// returns Jill's number
int i, mid;
if (!t[0]) {
t[0] = 1;
t[1] = 3;
t[2] = 7;
for (i=3; i<30; i++) t[i] = t[i-2] + (1l<<i);
}
if (N == 1) return 1;
if (N == 2) {
Guess(1);
i = Guess(2);
if (i > 0) return 2;
else return 1;
}
if (N == 3) {
Guess(1);
i = Guess(3);
if (i > 0) return 3;
if (i < 0) return 1;
return 2;
}
mid = (N+2)/2;
Guess(mid-2);
i = Guess(mid);
if (i == 0) return mid-1;
if (i < 0) return endgame(1, mid);
return endgame(N, N-mid+1);
}
Compilation message
hottercolder.cpp: In function 'int midgame(int, int, int)':
hottercolder.cpp:38:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (q > mid && g > 0 || q < mid && g < 0) return midgame(q, min(mid+1, b), b);
~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1060 ms |
8156 KB |
Output is partially correct - alpha = 1.000000000000 |
