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
/*
(rysunki dla d==2, r==7)

dwoma zapytaniami możemy odrzucić około połowę przestrzeni:

. . . . . . . .   : : : : : : : :
. . . . . . . :   : : : : : : : .
. . . . . . : :   : : : : : : . .
. . . p . : : :   : : : p : . . .
. . . . q+: : :   : : : : q-. . .
. . . : : : : :   : : : . . . . .
. . : : : : : :   : : . . . . . .
. : : : : : : :   : . . . . . . .

w ten sposób możemy połowić przedział wzdłuż przekątnej sześcianu równoległej do wektora v=(1,...,1) aż dojdziemy do pojedynczej warstwy o wymiarze d-1 prostopadłej do tego wektora
stąd będziemy wiedzieć że sum(i=1...d,z[i])=a[1], gdzie z to pozycja Krotki, a a[1] to odległość znalezionej warstwy od wierzchołka (0,...,0) w metryce taksówkowej

a[1]=8
. . . . . . . .
. . . . . . . :
. . . . . . : .
. . . . . : . .
. . . . : . . .
. . . : . . . .
. . : . . . . .
. : . . . . . .

niektóre zapytania nie będą leżały na przekątnej, trzeba też uważać przy rogach żeby nie zadać zapytania spoza przestrzeni, najlepiej blisko rogów iść w ich stronę

. . . . . . . .   . . . . . . . .
. . . . . . . :   . . . . . . . :
. . . . . . : :   . . . . . . : :
. . . p . : : :   . . . . q-: : :
. . . . q+: : :   . . . . : p : :
. . . : : : : :   . . . : : : : :
. . : : : : : :   . . : : : : : :
. : : : : : : :   . : : : : : : :

teraz możemy powtórzyć powyższe postępowanie dla wektora (-1,1,...,1) i dostaniemy r-z[1]+sum(i=2...d,z[i])=a[2]

i dla kolejnych wektorów (-1,...,-1,1,...,1), dostaniemy wtedy że sum(i=1...j-1,r-z[i])+sum(i=j...d,z[i])=a[j]

aż do wektora (-1,...,-1,1), dla którego dostaniemy sum(i=1...d-1,r-z[i])+z[d]=a[d]

w ten sposób dostajemy układ d równań z d niewiadomymi

z[j] dla j<d możemy obliczyć z różnicy kolejnych 2 równań:

+|sum(i=1...j-1,r-z[i])+sum(i=j...d,z[i])=a[j]
-|sum(i=1...j,r-z[i])+sum(i=j+1...d,z[i])=a[j+1]

-r+z[j]+z[j]=a[j]-a[j+1]
z[j]=(a[j]-a[j+1]+r)/2

z[d] możemy obliczyć z sumy pierwszego i ostatniego równania:

+|sum(i=1...d,z[i])=a[1]
+|sum(i=1...d-1,r-z[i])+z[d]=a[d]

(d-1)*r+z[d]+z[d]=a[1]+a[d]
z[d]=(a[1]+a[d]-(d-1)*r)/2

limity:
2<=r<=10^9<2^30
1<=d<=500<2^9
k>=100*d

pojedynczy etap szukania to 2*log_2(r*d) zapytań (w każdym kroku 2 pytaniami połowimy przekątną która ma długość r*d w metryce taksówkowej)
daje to maksymalnie (30+9)*2=78 zapytań w etapie, czyli 78*d wszystkich zapytań, więc zawsze się powinno udać dojść do rozwiązania w nie więcej niż k kroków
*/

#include "cielib.h"
#include <stdio.h>
int main()
{
  int d = podajD();
  int r = podajR();
  int p[d];
  int q[d];
  int v[d];
  long long a[d];
  int z[d];

  for(int i=0; i<d; i++) v[i]=1;

  for(int j=0; j<d; j++)
  {
    long long l=0, h=1ll*r*d, m, n;
    int t;

    while(l<h)
    {
      m=(l+h+1)/2;
      n=m;
      t=m<1ll*r*d/2;
      n-=t;

      for(int i=0; i<d; i++)
      {
        q[i]=(1-v[i])/2*r+v[i]*(n/(d-i));
        p[i]=q[i]+(t*2-1)*v[i];
        n-=n/(d-i);
      }

      czyCieplo(p);
      if(czyCieplo(q)^t) l=m;
      else               h=m-1;
    }
    a[j]=l;

    v[j]=-1;
  }

//for(int j=0; j<d; j++) printf("a=%lld%c"+(j>0)*2,a[j],"\n "[j<d-1]);
  for(int j=0; j<d-1; j++) z[j]=(a[j]-a[j+1]+r)/2;
  z[d-1]=(a[0]+a[d-1]-(d-1)*r)/2;

  znalazlem(z);
}