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

using namespace std;

int main()
{
    int D, R;
    D = podajD();
    R = podajR();
    //int k = podajK();

    // przedzialy poszukiwan Krotki: dla i-tego wymiaru Krotka jest w przedziale <pocz[i], kon[i]>
    vector<int> pocz(D, 0);
    vector<int> kon(D, R);
    vector<int> rozmiar(D, R+1); // rozmiar obszaru poszukiwan w kazdym kierunku

    vector<int> pozycja1(D, (R+1)/2), pozycja2(D, (R+1)/2);


    while (*max_element(rozmiar.begin(), rozmiar.end())>2)
    {
        // indeks wymiaru do redukcji - pierszy najwiekszy element z 'rozmiar'
        int wymiar = max_element(rozmiar.begin(), rozmiar.end()) - rozmiar.begin();
        bool przesuniecie=false;
        int odp1, odp2;

        // punkty do porownania
        pozycja2[wymiar] = pocz[wymiar];
        pozycja1[wymiar] = pocz[wymiar] + rozmiar[wymiar]/2; //srodek

        czyCieplo(pozycja1.data()); // inicjalizacja punktu poczatkowego

        odp1 = czyCieplo(pozycja2.data());
        odp2 = czyCieplo(pozycja1.data());
        //if (czyCieplo(pozycja2.data()))
        if (odp1)
        {
            // Krotka jest w pierwszej cwiartce (blizej poczatku niz srodka)
            kon[wymiar] = (pozycja1[wymiar] + pozycja2[wymiar] -1)/2;
        }
        //else if(czyCieplo(pozycja1.data())==0)
        else if(odp2==0)
        {
            // odleglosc w normie max Krotki od obu punktow jest taka sama
            // - Krotka jest w pierwszej polowie (z pozycja1 wlacznie)
            kon[wymiar] = pozycja1[wymiar];
        }
        else // Krotki nie ma w pierwszej cwiartce - sprawdzenie drugiej polowki
        {
            pozycja2[wymiar] = kon[wymiar];
            if (rozmiar[wymiar]%2 ==0) // nie istnieje idealny srodek
            {
                //pozycja1[wymiar] = kon[wymiar] - rozmiar[wymiar]/2;
                pozycja1[wymiar]--;
                czyCieplo(pozycja1.data()); // inicjalizacja nowej pozycji
                przesuniecie = true;
            }

            odp1 = czyCieplo(pozycja2.data());
            odp2 = czyCieplo(pozycja1.data());
            //if (czyCieplo(pozycja2.data()))
            if (odp1)
            {
                // Krotka jest w ostatniej cwiartce (blizej konca niz srodka)
                pocz[wymiar] = (pozycja1[wymiar] + pozycja2[wymiar])/2 +1;
            }
            //else if(czyCieplo(pozycja1.data())==0)
            else if (odp2==0)
            {
                // odleglosc w normie max Krotki od obu punktow jest taka sama
                // - Krotka jest w drugiej polowie (z pozycja1 wlacznie)
                pocz[wymiar] = pozycja1[wymiar];
            }
            else
            {
                // Krotka jest w srodkowej polowie
                kon[wymiar] = (pozycja1[wymiar] + pozycja2[wymiar])/2;
                pocz[wymiar] = (pocz[wymiar] + pozycja1[wymiar] +1 +przesuniecie)/2;
            }
        }

        //nowy rozmiar w wybranym wymiarze
        rozmiar[wymiar] = kon[wymiar] +1 -pocz[wymiar];

        // ustawienie pozycji kontrolnych na srodek nowego zakresu
        pozycja1[wymiar] = pocz[wymiar] + rozmiar[wymiar]/2;
        pozycja2[wymiar] = pozycja1[wymiar];
    }


    while (*max_element(rozmiar.begin(), rozmiar.end())>1)
        // dla czesci wymiarow rozmiar = 2 -> punkt startowy lezy na krawedzi
        // eliminacja zapetlenia przez przepytawanie "fikcyjnego punktu" "na prawo" od startowego
        // (punkt fikcyjny lezy poza kostka)
        // odpowiedz czyCieplo = 1 od punktu w kostce <=> Krotka jest w tym punkcie
        // odpowiedz czyCieplo = 1 przy powrocie z punktu fikcyjnego <=> Krotka w pierwszej polowie
        // odpowiedz czyCieplo = 0 przy powrocie z punktu fikcyjnego <=> Krotka w drugiej polowie
    {
        // indeks wymiaru do redukcji - pierszy najwiekszy element z 'rozmiar'
        int wymiar = max_element(rozmiar.begin(), rozmiar.end()) - rozmiar.begin();
        int odp1, odp2;

        // punkty do porownania
        pozycja2[wymiar] = pocz[wymiar];
        pozycja1[wymiar] = kon[wymiar]; //nie ma srodka; prawy brzeg

        czyCieplo(pozycja1.data()); // inicjalizacja punktu poczatkowego

        odp1 = czyCieplo(pozycja2.data());
        odp2 = czyCieplo(pozycja1.data());
        //if (czyCieplo(pozycja2.data()))
        if (odp1)
        {
            // Krotka znaleziona w pozycja2
            pocz.swap(pozycja2);
            break;
        }
        //else if(czyCieplo(pozycja1.data()))
        else if(odp2)
        {
            // Krotka znaleziona w pozycja1
            pocz.swap(pozycja1);
            break;
        }
        else if (kon[wymiar] <R) // punkt startowy nie lezy na krawedzi
        {
            pozycja2[wymiar] = kon[wymiar]+1; //punkt "na prowo" od kostki

            czyCieplo(pozycja2.data());
            odp2 = czyCieplo(pozycja1.data());
            //if (czyCieplo(pozycja1.data()))
            if (odp2)
            {
                // Krotka jest w pierwszej polowie
                kon[wymiar] = pocz[wymiar];
            }
            else
            {
                // Krotka jest w drgiej polowie
                pocz[wymiar] = kon[wymiar];
            }

            // redukcja rozmiaru
            rozmiar[wymiar] = 1;
            pozycja1[wymiar] = pocz[wymiar];
            pozycja2[wymiar] = pocz[wymiar];
        }
        else // kon[wymiar] == R - punkt startowy nie lezy na krawedzi
        {
            pozycja2[wymiar] = pocz[wymiar]-1; //punkt "na lewo" od kostki

            czyCieplo(pozycja2.data());
            odp2 = czyCieplo(pozycja1.data());
            //if (czyCieplo(pozycja1.data()))
            if (odp2)
            {
                // Krotka jest w drugiej polowie
                pocz[wymiar] = kon[wymiar];
            }
            else
            {
                // Krotka jest w pierwszej polowie
                kon[wymiar] = pocz[wymiar];
            }

            // redukcja rozmiaru
            rozmiar[wymiar] = 1;
            pozycja1[wymiar] = pocz[wymiar];
            pozycja2[wymiar] = pocz[wymiar];
        }
    }

    znalazlem(pocz.data());


    return 0;
}