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
#include "cielib.h"
#include <iostream>
#include <queue>

using namespace std;

struct Dimension {
    int i;
    int left;
    int right;
    int size;
};


struct DimensionCmp : binary_function <Dimension*,Dimension*,bool> {
    bool operator() (const Dimension* x, const Dimension* y) const { return x->size < y->size; }
};

static Dimension forest[500];

static priority_queue<Dimension*, vector<Dimension*>, DimensionCmp> pq;

static int d, k, r;

static int gps[500];

void update_search_area(int i, int left, int right) {
    Dimension &dim = forest[i];
    gps[i] = (right + left) / 2;
    dim.left = left;
    dim.right = right;
    dim.size = right - left;
    pq.push(&dim);
//    cerr << "Updated " << dim.i << " to [" << dim.left << "," << dim.right << "]=" << dim.size << endl;
}

bool move(int i, int cell) {
//    cerr << "Moving in " << i << " " << gps[i] << " -> " << cell << "... ";
    if (gps[i] == cell) {
//        cerr << "nonsense!" << endl;;
        return false;
    } else {
        gps[i] = cell;
        bool retval = czyCieplo(gps);
//        cerr << (retval ? "cieplo" : "zimno") << endl;;
        return retval;
    }
}


int shrink_area(Dimension &dim) {
    move(dim.i, dim.left);
    
    if (move(dim.i, dim.right)) {
        int shift = dim.size / 2;
        dim.left += shift ? shift : 1;
        update_search_area(dim.i, dim.left, dim.right);
    } else if (move(dim.i, dim.left)) {
        int shift = dim.size / 2;
        dim.right -= shift ? shift : 1;
        update_search_area(dim.i, dim.left, dim.right);
    } else if (dim.size == 1) {
//        cerr << "That awful case\n";
        move(dim.i, dim.left - 1);
        int p = (move(dim.i, dim.left)) ? dim.right : dim.left;
        update_search_area(dim.i, p, p);
    } else if (move(dim.i, dim.left+1)) {
        update_search_area(dim.i, dim.left + 1, dim.right);
//        shrink_area(dim);
    } else {
        update_search_area(dim.i, dim.left, dim.right - 1);
//        shrink_area(dim);
//        update_search_area(dim.i, dim.right - last_go_biggest_size, dim.left + last_go_biggest_size);
//ssss        update_search_area(dim.i, dim.left + dim.size / 2, dim.left + dim.size + dim.size / 2);
        
    }
    return dim.size;
}


int main(int argc, char **argv) {
    d = podajD();
    k = podajK();
    r = podajR();
    
    for (int i = 0; i < d; i++) {
        forest[i].i = i;
        update_search_area(i, 0, r);
    }
    

    while (pq.top()->size > 0) {
        Dimension &dim = *pq.top();
        pq.pop();
//        this_go_biggest_size = 0;

//        cerr << "State:";
//        for (int i = 0; i < d; i++) {
//            cerr << " [" << forest[i].left << "," << forest[i].right << "]=" << forest[i].size;
//        }
//        cerr << endl;

        shrink_area(dim);

//        for (int i = 0; i < d; i++) {
//            Dimension &dim = forest[i];
//            
//            if (!dim.size) { continue; }
        
//            this_go_biggest_size = shrink_area(dim);
//        }
        
//        int size = this_go_biggest_size;
//        this_go_biggest_size = this_go_biggest_size > size ? this_go_biggest_size : size;

    } //while (this_go_biggest_size);
    
//    cerr << "The answer is: " << gps << endl;
    znalazlem(gps);
}