// Solver for CMOQR Problem 7:
// Is it possible for 7 people in a tournament to be put into two rooms
// in which neither room has a cyclic triple?

#include <iostream>
using namespace std;

// This is a triangular array:
// wins[a][b] is 1 if a beats b, otherwise -1.
// Only a>b is defined.
int wins[7][7];

// Did a beat b? 1 if yes, -1 if no
int won(int a, int b){
  if(a>b) return wins[a][b];
  if(a<b) return -wins[b][a];
  return 0;
}

// Does a set of numbers form a cyclic triple?
bool cyclic(int a, int b, int c){
  return won(a,b) == won(b,c) && won(b,c) == won(c,a);
}

// Do these four contain a cyclic triple?
bool cyclic4(int a, int b, int c, int d){
  if(cyclic(a,b,c)) return true; if(cyclic(b,c,d)) return true;
  if(cyclic(c,d,a)) return true; if(cyclic(a,b,d)) return true;
  return false;
}

// If you put a,b,c in one room, is it the case that at least one of
// the rooms does contain a triplet?
bool cyclic_(int a, int b, int c){
  if(cyclic(a,b,c)) return true;

  // Set d,e,f,g to the other four, ie [0..6] \ [a,b,c]
  int d,e,f,g;
  for(int i=0; i<7; i++) if(a!=i&&b!=i&&c!=i){d=i;break;}
  for(int i=0; i<7; i++) if(a!=i&&b!=i&&c!=i&&d!=i){e=i;break;}
  for(int i=0; i<7; i++) if(a!=i&&b!=i&&c!=i&&d!=i&&e!=i){f=i;break;}
  for(int i=0; i<7; i++) if(a!=i&&b!=i&&c!=i&&d!=i&&e!=i&&f!=i){g=i;break;}
  return cyclic4(d,e,f,g);
}

// Is it the case that no matter what, at least one room has a cyclic?
bool iscounterexample(){
  if(!cyclic_(0,1,2)) return false; if(!cyclic_(0,1,3)) return false; if(!cyclic_(0,1,4)) return false;
  if(!cyclic_(0,1,5)) return false; if(!cyclic_(0,1,6)) return false; if(!cyclic_(0,2,3)) return false;
  if(!cyclic_(0,2,4)) return false; if(!cyclic_(0,2,5)) return false; if(!cyclic_(0,2,6)) return false;
  if(!cyclic_(0,3,4)) return false; if(!cyclic_(0,3,5)) return false; if(!cyclic_(0,3,6)) return false;
  if(!cyclic_(0,4,5)) return false; if(!cyclic_(0,4,6)) return false; if(!cyclic_(0,5,6)) return false;
  if(!cyclic_(1,2,3)) return false; if(!cyclic_(1,2,4)) return false; if(!cyclic_(1,2,5)) return false;
  if(!cyclic_(1,2,6)) return false; if(!cyclic_(1,3,4)) return false; if(!cyclic_(1,3,5)) return false;
  if(!cyclic_(1,3,6)) return false; if(!cyclic_(1,4,5)) return false; if(!cyclic_(1,4,6)) return false;
  if(!cyclic_(1,5,6)) return false; if(!cyclic_(2,3,4)) return false; if(!cyclic_(2,3,5)) return false;
  if(!cyclic_(2,3,6)) return false; if(!cyclic_(2,4,5)) return false; if(!cyclic_(2,4,6)) return false;
  if(!cyclic_(2,5,6)) return false; if(!cyclic_(3,4,5)) return false; if(!cyclic_(3,4,6)) return false;
  if(!cyclic_(3,5,6)) return false; if(!cyclic_(4,5,6)) return false;
  return true;
}

// How to generate a list of {-1,1}^21? Why not iterate from 0 to 2^21-1
// then somehow convert these into binary?
void setcondition(int n){

  for(int i=0; i<7; i++) for(int j=0; j<7; j++) wins[i][j] = -1;

  // temporary array to store the 1 and -1's before transferring
  // over to the win matrix
  int array[21];
  for(int i=0; i<21; i++) array[i]=-1;

  // seek highest power of 2
  int p = 0, p_ = 1;
  while(p_*2 <= n){p_*=2; p++;}

  int k=1; while(k<n) k*=2; if(k>n) k/=2;
  while(k>0) {
    int bd;

    // extract a binary digit
    if(int(n/k)%2==0)bd=-1; else bd=1;
    array[p] = bd;
    p--;

    k/=2;
  }

  // copy array over
  int inx = 0;
  for(int i=1; i<7; i++) {
    for(int j=0; j<i; j++){
      wins[i][j] = array[inx];
      inx++;
    }
  }

}

int main(){

  // Loop over all possible combinations up to 2^21
  for(int i=0; i<2097152; i++){
    setcondition(i);
    if(iscounterexample()){
      cout << i << endl;
    }
  }

  return 0;
}