#include<stdio.h>
#include<stdlib.h>
//
//  problème
//
#define n 41     //  nombre de capteurs
#define D1 1     //  Les capteurs sont sur une ligne ou non.
#define bi 0     //  communication bidirectionnelle ou non.
int x[n],y[n],   //  Le capteur i est en (x[i],y[i])
    v[n][n],     //  v[i][0]=i,v[i][1], ... , v[i][n-1] est la liste des capteurs voisins de i rangés par distance croissante
    c[n][n],     //  c[i][r] est la contribution au coût du capteur i quand il atteint juste le capteur v[i][r]
    d[n][n],     //  d[i][j] est le nombre de capteurs atteints par le capteur i quand il atteint juste le capteur j.
    c1=1, c2=10; //  coefficients des coûts de réception et d'émission
//
//  sous-problème  (ou solution réalisable)
//
/* rm[i] et rM[i] rayons mimimal et maximal d'émission du capteur i.
  Le rayon est le nombre d'autres capteurs atteints. Le branchement se fait
  en émettant du capteur i avec un rayon minimal r, ou non  */
typedef struct { int cost, rm[n], rM[n], i, r; } sol;
sol opti, S; // meilleure solution réalisable trouvée, sous-problème courant
sol T, bonne;//une solution de S, bonne solution trouvée autrement (débogage)
#define Rm S.rm
#define RM S.rM
#define Cost S.cost
void affsol(sol S)
{ int i;
  for(i=0;i<n;i++) printf("%d[%d..%d] ",i,Rm[i],RM[i]);
  printf("%d %d[%d]\n",Cost,S.i,S.r);
}
int nbeval=0, nbeva=-1;  // compteur d'appels à eval(), et valeur pour
#define ifeva if(nbeval==nbeva) // laquelle eval() devient bavarde (débogage)
int checkbonne() //  return  bonne est dans S
{ int i;
  for(i=n;i--;) if(bonne.rm[i]-Rm[i]+0u>RM[i]-Rm[i]) return 0;
  if(Cost<=bonne.cost) return 1; // bonne est dans S et S.cost semble correct
  affsol(bonne);                 // Ça merde. On affiche tout et on arrête.
  affsol(T);
  affsol(S);
  printf("checkbonne erreur nbeval=%d\n",nbeval);
  if(1) exit(1);
  Cost=bonne.cost;
  return 1;
}
//
// arbres binaires de recherche
//
typedef struct noeud noeud, *abr;
struct noeud { sol S; abr fg,fd; } *lib=0;  //  liste des noeuds libres
void getmem()
{ int i=1000; for(lib=calloc(i--,sizeof(*lib));i--;) lib[i].fg=i+1+lib; }
#define A (*a)
void rotg(abr*a) {abr b=A; A=b->fd, b->fd=A->fg, A->fg=b;}//rotation à gauche
void rotd(abr*a) {abr b=A; A=b->fg, b->fg=A->fd, A->fd=b;}//rotation à droite
#define ifd(c) if(!A c) break; else if(A c->Cost<Cost)
#define ifg(c) if(!A c) break; else if(A c->Cost>Cost)
const int equi=0;   // active ou non l'équilibrage des arbres
void rangeabr(abr*a)  // on ajoute un nouveau noeud contenant S
{ if(Cost>=opti.cost) return;
  for(;equi;)        // on raccourcit la branche de l'arbre que l'on parcourt
   ifd() ifd(->fd) rotg(a), a=&A->fd;
         else ifd(->fd->fg) rotd(&A->fd), rotg(a), a=&A->fd->fg;
              else          a=&A->fd;
   else  ifg(->fg) rotd(a), a=&A->fg;
         else ifg(->fg->fd) rotg(&A->fg), rotd(a), a=&A->fg->fd;
              else          a=&A->fg;
  while(A) a=A->Cost>Cost?&A->fg:&A->fd;
  if(!lib) getmem(); // On crée un nouveau s'il n'y a pas d'ancien
  if(!lib) lib=calloc(1,sizeof(*lib));
  lib->S=S, lib->fd=0, A=lib, lib=A->fg, A->fg=0;
}
#undef ifd
#undef ifg
void oteminabr(abr*a)  // On supprime le noeud le plus à gauche
{ if(equi) while(A->fg) rotd(a); // et on met son contenu dans S.
  while(A->fg) a=&A->fg;
  A->fg=lib, lib=A, A=lib->fd, S=lib->S;
}
#undef A
//
//  évaluation
//
#define infini ((int)(~0u>>1)/n)
int min(int a,int b) { return a<b?a:b; }
int max(int a,int b) { return a>b?a:b; }
#define setmin(a,b) a=min(a,b)
#define setmax(a,b) a=max(a,b)
void afft(int*t,int i) { for(;i--;++t) if(*t==infini) printf(" inf"); else if(*t>infini/2) printf("  in"); else printf("%4d",*t); printf("\n"); }
void affm(int(*t)[n  ],int i) { printf("\n"); for(;i--;) afft(*t++,n  ); }
void affM(int(*t)[n*2],int i) { printf("\n"); for(;i--;) afft(*t++,n*2); }
#define Afft(nom,s)  printf(#nom),afft(nom,s)
#define Affm(nom,s)  printf(#nom),affm(nom,s)
#define AffM(nom,s)  printf(#nom),affM(nom,s)
void eval()
{ int i, j, k, ii, jj, r, a, b, *p, nbc=n-1, ppv[n*2], fus[n*2], sui[n*2],
      ori[n*2][n*2], C[n*2][n*2];
  nbeval++;
  for(i=n*2;i--;sui[fus[i]=i]=i-1) for(j=n*2;j--;) C[i][j]=infini;
  for(i=n;i--;) for(r=RM[i];r;r--) C[i][v[i][r]]=c[i][max(r,Rm[i])];
  if(bi) for(i=n;i--;) for(j=n;j--;) if(C[i][j]==infini) C[j][i]=infini;
  for(i=n;i--;ppv[i]=v[i][r-1]) for(r=T.rM[i]=1;r<n && C[i][v[i][r++]]==infini;) ;  // ppv[i] est le plus proche voisin de i
  do  // recherche d'une arborescence de poids minimal (Edmonds) en O(n²)
  { for(i=ii=nbc++;i=ppv[ppv[i]],i!=ii;ii=ppv[ii]) ; // ii est dans un cycle
    for(;fus[i=ppv[i]]=nbc,i!=ii;) ;//qui est réduit en un nouveau sommet nbc
    for(k=j=nbc;j=sui[jj=j],~j;) if(fus[j]!=j) sui[jj]=sui[j], j=jj; else
    { do    // calcul de C[nbc][.] et C[.][nbc]
      { if(a=C[i][j]-C[i][ppv[i]],a<=C[nbc][j]) C[nbc][j]=a, ori[nbc][j]=i;
        if(a=C[j][i]             ,a<=C[j][nbc]) C[j][nbc]=a, ori[j][nbc]=i;
      } while(i=ppv[i],i!=ii);
      if(ppv[j]=fus[ppv[j]], C[nbc][j]<C[nbc][k]) k=j; // calcul de ppv[nbc]
    }
  } while((ppv[nbc]=k)<nbc);
  if(Cost=infini, ~sui[nbc]) return; // non connexe
  if(!bi) for(i=nbc;i--;setmax(T.rM[j],d[j][k]))
          for(k=ppv[j=i];p=j>k?&j:&k,*p>=n;) *p=ori[j][k];
  for(i=nbc;i--;) 
  { while(ppv[i]>=max(i,n)) ppv[i]=ori[i][ppv[i]];
    if(i>=max(ppv[i],n)) ppv[ori[i][ppv[i]]]=ppv[i];
  }
  for(a=0,i=n;i--;) if(a+=C[i][j=ppv[i]], T.rm[i]=max(  Rm[i],d[i][j]), bi)
                                               setmax(T.rM[j],d[j][i]);
  if(Cost=T.cost=a,a>=opti.cost) return;
  for(a=0,i=n;i--;) b=c[i][r=T.rM[i]]-c[i][T.rm[i]], a=b>a?S.i=i,S.r=r,b:a;
  if(!a) opti=T; // la minoration est exacte
}
//
//  séparation
//
void sep1() { int r=S.r, a=c[S.i][r]; while(c[S.i][--r]==a) ;  RM[S.i]=r; }
void sep2() { int r=S.r             ;                          Rm[S.i]=r; }
void sepevalabr()
{ abr a=0; rangeabr(&a);
  sol T;
  while(a)
  { oteminabr(&a);
    int c=checkbonne();
    T=S, sep1(), eval(), c-=checkbonne(); if(Cost<opti.cost) rangeabr(&a);
    S=T, sep2(), eval(), c-=checkbonne(); if(Cost<opti.cost) rangeabr(&a);
    if(c) printf("erreur sepeval checkbonne c=%d\n",c), exit(1);
  }
}
void sepevalprof1()
{ if(S.cost>=opti.cost) return;
  sol T[2];
  T[1]=S, sep1(), eval(), T[0]=S;
  S=T[1], sep2(), eval(), T[1]=S;
  int i, j=T[0].cost<T[1].cost;
  for(i=2;i--;) S=T[i^j], sepevalprof1();
}
void swapS(sol *s) { sol t=*s; *s=S, S=t; }
void sepevalprof2()
{ if(S.cost>=opti.cost) return;
  sol T=S;   sep1(), eval();
  swapS(&T), sep2(), eval();
  if(T.cost<Cost) swapS(&T);
  sepevalprof2(), swapS(&T),
  sepevalprof2();
}
#define sepevalprof sepevalprof1
//
// programmation dynamique en O(n³) en dimension 1
//
#define CCC(i,j,k) ccc[i][j][d[i][k]]
#define C(i,j) c[i][d[i][j]]  // coût de l'arc i-->j
// ccc[i][j][r], CCC(i,j,k) ou cc[i][j] représentent
// le coût minimal d'un arbre couvrant les capteurs i..j avec
// rayon(i)>=r, rayon(r)>=d(i,k) ou contenant l'arête i<-->j.
void progdynD1bi()
{ int i, I, J, j, l, r, s, cc[n][n]; // [i..j]=[i..I]u[J..j]
  static int ccc[n][n][n];           // l=|j-i|  s=(j-i)/|j-i|=J-I
  for(i=n;i--;) for(j=n;j--;) for(r=n;r--;) ccc[i][j][r]=infini;
  for(i=n;i--;Rm[i]=1) for(r=n;r--;cc[i][r]=infini) ccc[i][i][r]=c[i][r];
  for(l=0;++l<n;) for(i=n;i--;) for(s=-1;s<2;s+=2) if(j=i+l*s,0u+j<n)
  { for(I=i;I!=j ;) setmin(cc[i][j]      ,CCC(i,I,j)+CCC(j,J=I+s,i)), CCC(i,j,J)=cc[i][I=J]+CCC(J,j,i)-C(J,i);
    for(r=n;--r>1;) setmin(ccc[i][j][r-1],ccc[i][j][r  ]                  );
    for(r=1;++r<n;) setmin(ccc[i][j][r  ],ccc[i][j][r-1]+c[i][r]-c[i][r-1]);
  }
  void oriccc(int i,int j,int r)
  { void oricc(int i,int j)
    { int I, J, s=i<j?1:-1;
      setmax(Rm[i],d[i][j]);
      setmax(Rm[j],d[j][i]);
      for(I=i;cc[i][j]!=CCC(i,I,j)+CCC(j,J=I+s,i);I=J) ;
      oriccc(i,I,d[i][j]),oriccc(j,J,d[j][i]);
    }
    int J;
    for(J=i;i!=j;) if(J+=i<j?1:-1,ccc[i][j][r]==cc[i][J]+CCC(J,j,i)-C(J,i)+max(c[i][r]-C(i,J),0)) oricc(i,J), r=d[J][i], i=J;
  }
  Cost=ccc[0][n-1][1]; oriccc(0,n-1,1);
  for(i=n;i--;) RM[i]=Rm[i];
  opti=S;
}
#undef CCC
//  cc[i]  coût minimal d'un graphe allant de i vers 0 et de 0 à i+1
//  ccc[i][r] coût minimal d'un graphe fortement connexe couvrant 0..i avec rayon(i)>=r
//  aa[i][j] coût minimal d'une arborescence allant de ]i..j] ou [j..i[ vers i.
void progdynD1mono()
{ int i, J, j, k, l, r, cc[n], ccc[n][n], aa[n][n];
  for(i=n;i--;aa[i][i]=Rm[i]=0,cc[i]=infini) for(r=n;r--;) aa[i][r]=ccc[i][r]=infini;
  for(l=0;++l<n;) for(i=0;j=i+l,j<n;i++) for(k=c1?l:1;k;k--)
   setmin(aa[i][j],aa[i][j-k]+aa[j][j-k+1]+C(j,j-k)),
   setmin(aa[j][i],aa[j][i+k]+aa[i][i+k-1]+C(i,i+k));
  for(r=n;r--;) ccc[0][r]=c[0][r];
  for(j=0;J=j+1,J<n;j=J)
  { for(i=0;i<J;i++) setmin(cc[j],ccc[i][d[i][J]]+aa[i][j]), ccc[J][d[J][i]]=cc[i]+aa[J][i+1]+C(J,i);
    for(r=n;--r>1;)  setmin(ccc[J][r-1],ccc[J][r  ]                  );
    for(r=1;++r<n;)  setmin(ccc[J][r  ],ccc[J][r-1]+c[J][r]-c[J][r-1]);
  }
  for(Cost=ccc[i=n-1][r=1];i;)
  { for(J=i;Rm[i]=r=max(r,d[i][j=J-1]),setmax(Rm[j],d[j][J]),ccc[i][r]!=cc[j]+c[i][r]+aa[i][J];J=j) ;
    for(i=J;r=d[--i][J],cc[j]!=ccc[i][r]+aa[i][j];) Rm[i]=d[i][i-1];
  }
  Rm[0]=r;
  for(i=n;i--;) RM[i]=Rm[i];
  opti=S;
}
#undef C
void progdynD1() { (bi?progdynD1bi:progdynD1mono)(); }
//
//  génération du problème
//
void aleat()
{ int i, j, s1=D1?1000:n<30?10:20, s2=D1?:s1;
  for (i=0;i<n;i+=i==j)
  { x[i] = rand()%s1; // On génère les coordonnées x et y du noeud i
    y[i] = rand()%s2;
    for(j=0;x[i]!=x[j] || y[i]!=y[j];j++) ;
  }
}
void setrac()
{ int i,j,l,s=0,r,a,b, d2[n][n];
  static int m=0;
  if(m!=n)
  { if(D1) for(i=n;i--;) for(j=i;j--;) if(x[i]<x[j]) a=x[i], x[i]=x[j], x[j]=a;  // tri des points en dimension 1
    for(i=n;i--;) for(j=n;j--;v[i][j]=j) a=x[i]-x[j], b=y[i]-y[j], d2[j][i]=a*a+b*b;  // calcul des distances
    for(l=n;--l;) if(729*729%(l/(l&-l))==0) for(i=n;i--;) for(r=n,s=n-l;r--,s--;)
     if(d2[i][a=v[i][r]]<d2[i][b=v[i][s]]) v[i][r]=b, v[i][s]=a; // tri des voisins par distance
    for(i=n;i--;) for(a=0,r=n;r--;c[i][r]=s*c1+a*c2) b=a, a=d2[i][j=v[i][r]], d[i][j]=s=r && a!=b?r:s; // calcul du coût pour chaque rayon
    Afft(x,n), Afft(y,n), Affm(d2,n), Affm(v,n), Affm(d,n), Affm(c,n);
  }
  for(i=m=n;i--;) RM[i]=n-1, Rm[i]=d[i][i];
  S.i=S.r=-1, Cost=infini, opti=S, eval();
}

int main() // On fait le calcul par plusieurs méthodes pour les comparer
{ aleat(), *bonne.rm=*bonne.rM=0;
  if(0)  setrac(), sepevalprof(), affsol(bonne=opti);
  if(1)  setrac(), sepevalabr (), affsol(bonne=opti);
  if(D1) setrac(), progdynD1  (), affsol(bonne=opti);
  return 0;
}