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

bool solved(int min[], int max[], int d)
{
    for (int i = 0; i < d; ++i)
        if (min[i] != max[i]) 
            return false;

    return true;
}


void update_up(int min[], int max[], int i, int r)
{
    int new_min = (min[i] + max[i]) / 2; 
    while (max[i] - new_min < 2) {
        new_min--;
    }

    min[i] = new_min;
}

void update_down(int min[], int max[], int i, int r)
{
    int new_upper_bound;
    if ((max[i] - min[i] + 1) % 2 == 0) 
    {
        new_upper_bound = 1 + (min[i] + max[i]) / 2;
    } else {
        new_upper_bound = (min[i] + max[i]) / 2;
    }

    while (new_upper_bound - min[i] < 2) {
        new_upper_bound++;
    }

    max[i] = new_upper_bound;
}

void compute_average(int min[], int max[], int avg[], int d)
{
    for (int i = 0; i < d; ++i)
    {
        avg[i] = (min[i] + max[i]) / 2;
    }
}

int main()
{
    int d = podajD();
    int r = podajR();

    int min[d];
    int max[d];
    int avg[d];

    for (int i = 0; i < d; ++i) min[i] = 0;
    for (int i = 0; i < d; ++i) max[i] = r;

    int old_avg;

    while (!solved(min, max, d))
    {
        compute_average(min, max, avg, d);
        for (int i = 0; i < d; ++i)
        {
            if (max[i] == min[i] + 2) 
            {
                // special case for distance 2
                //make more jumps
                old_avg = avg[i];

                avg[i] = min[i];
                czyCieplo(avg);

                avg[i] = max[i];
                int one = czyCieplo(avg);

                avg[i] = min[i];
                int two = czyCieplo(avg);

                if (one) {
                    // upper
                    min[i] = max[i];
                } else {
                    if (two) {
                        // lower
                        max[i] = min[i];
                    } else {
                        max[i] = old_avg;
                        min[i] = old_avg;
                    }
                }

                avg[i] = old_avg;
            } else if (max[i] == min[i] + 1) 
            {
            } else 
            {
                // printf("nomralny case\n");
                old_avg = avg[i];

                avg[i] = min[i];
                czyCieplo(avg);

                avg[i] = max[i];

                if (czyCieplo(avg)) {
                    update_up(min, max, i, r);
                } else {
                    update_down(min, max, i, r);
                }

                avg[i] = old_avg;
            }
        }
    }

    compute_average(min, max, avg, d);
    znalazlem(avg);
}