lib/Documentation/docs-sonyckson/11318.cpp

   1 //  PROBLEMITA DE LAS CANICAS....: UNO CLKW y el otro ANTICLOCK.... :)
   2 #include <cstdio>
   3 #include <cstdlib>
   4 #include <algorithm>
   5 using namespace std;
   6 #define ll long long
   7 ll arr[50001];
   8 int n;
   9 ll distd(int k, int ind){
  10         if( ind > k ) return ind-k;
  11         return n-k+ind;
  12 }
  13 ll disti(int k, int ind){
  14         if( k > ind ) return k-ind;
  15         return n-ind+k;
  16 }
  17 int M = 40000000;
  18 int main(){
  19         int i,j ,k, ind, vaux;;
  20         int casos;scanf("%i", &casos);
  21         ll sumi, sumd, a1[50001], a2[50001];
  22         for(int h=0;h<casos;h++){
  23                 scanf("%i", &n);
  24                 for(i=0;i<n;i++) scanf("%lld", &arr[i]);
  25                 sumi=0, sumd=0, ind = 0, vaux = 0;
  26                 a1[0] = 0;
  27                 for(i=1;i<n;i++) a1[i] = arr[i]*i+a1[i-1];
  28                 a2[n-1] = arr[n-1];
  29                 for(i=n-2;i>=0;i--) a2[i] = arr[i]*(n-i)+a2[i+1];
  30                 a2[0] = 0;
  31                 ll canicasd=0, canicasi=0;
  32                 ind=0;
  33                 while(a1[(ind+1)%n] < a2[(ind+2)%n])ind=(ind+1)%n;
  34                 ind = (ind+1)%n;
  35                 if( a1[ind] != a2[(ind+1)%n]){
  36                         ll a = a1[ind-1];
  37                         ll b = a2[(ind+1)%n];
  38                         ll p = (b+(arr[ind]*disti(0,ind))-a)/n;
  39                         for(i=1;i<ind;i++) canicasd+=arr[i];
  40                         canicasd+=p;
  41                         sumd = a1[ind-1]+p*ind;
  42                         for(i=n-1;i>ind;i--)canicasi+=arr[i];
  43                         canicasi+=(arr[ind]-p);
  44                         sumi = a2[(ind+1)%n]+(arr[ind]-p)*disti(0,ind);
  45                         vaux = p;
  46                 }else{
  47                         vaux = arr[ind];
  48                         for(i=1;i<=ind;i++) canicasd+=arr[i];
  49                         sumd = a1[ind];
  50                         for(i=n-1;i>ind;i--)canicasi+=arr[i];
  51                         sumi = a2[(ind+1)%n];
  52                 }
  53                 ll res = 0, nsol=0;
  54                 if( sumi == sumd ) res+=sumi, nsol++;
  55                 for(k=1;k<n;k++){
  56                         if( k != ind ){
  57                                 canicasi+=arr[k-1];
  58                                 sumi+=canicasi;
  59                                 sumd-=canicasd;
  60                                 canicasd-=arr[k];
  61                         }else{
  62                                 canicasi+=arr[k-1];
  63                                 sumi+=canicasi;
  64                                 sumd-=canicasd;
  65                                 canicasd-=vaux;
  66                                 canicasi-=(arr[k]-vaux);
  67                                 sumi-=(arr[k]-vaux)*n;
  68                                 ind=(ind+1)%n;
  69                                 vaux = 0;
  70                         }
  71                         canicasd+=(arr[ind]-vaux);
  72                         sumd+=(arr[ind]-vaux)*distd(k,ind);
  73                         canicasi-=(arr[ind]-vaux);
  74                         sumi-=(arr[ind]-vaux)*disti(k,ind);
  75                         vaux = arr[ind];
  76                         while(    sumd     <      sumi     ){
  77                                 ind=(ind+1)%n;
  78                                 sumd+=arr[ind]*distd(k,ind);
  79                                 canicasd+=arr[ind];
  80                                 sumi-=arr[ind]*disti(k,ind);
  81                                 canicasi-=arr[ind];
  82                                 vaux = arr[ind];
  83                         }
  84                         if( sumd != sumi ){
  85                                 sumd-=arr[ind]*distd(k,ind);
  86                                 canicasd-=arr[ind];
  87                                 ll a = sumd;
  88                                 ll b = sumi;
  89                                 ll p = (b+(arr[ind]*disti(k, ind))-a)/n;
  90                                 canicasd+=p;
  91                                 sumd+=p*distd(k,ind);
  92                                 canicasi+=arr[ind]-p;
  93                                 sumi+=(arr[ind]-p)*disti(k,ind);
  94                                 vaux = p;
  95                         }
  96                         if( sumi == sumd){
  97                                 res+= sumi, nsol ++;
  98                         }
  99                 }
 100                 printf("%lld %lld\n", nsol, res);
 101         }return 0;
 102 }