Ideone.com

fork download

copy

 
// 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;
}

Ci8vIFNvbHZlciBmb3IgQ01PUVIgUHJvYmxlbSA3OgovLyBJcyBpdCBwb3NzaWJsZSBmb3IgNyBwZW9wbGUgaW4gYSB0b3VybmFtZW50IHRvIGJlIHB1dCBpbnRvIHR3byByb29tcwovLyBpbiB3aGljaCBuZWl0aGVyIHJvb20gaGFzIGEgY3ljbGljIHRyaXBsZT8KCiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIFRoaXMgaXMgYSB0cmlhbmd1bGFyIGFycmF5OgovLyB3aW5zW2FdW2JdIGlzIDEgaWYgYSBiZWF0cyBiLCBvdGhlcndpc2UgLTEuCi8vIE9ubHkgYT5iIGlzIGRlZmluZWQuCmludCB3aW5zWzddWzddOwoKLy8gRGlkIGEgYmVhdCBiPyAxIGlmIHllcywgLTEgaWYgbm8KaW50IHdvbihpbnQgYSwgaW50IGIpewogIGlmKGE+YikgcmV0dXJuIHdpbnNbYV1bYl07CiAgaWYoYTxiKSByZXR1cm4gLXdpbnNbYl1bYV07CiAgcmV0dXJuIDA7Cn0KCi8vIERvZXMgYSBzZXQgb2YgbnVtYmVycyBmb3JtIGEgY3ljbGljIHRyaXBsZT8KYm9vbCBjeWNsaWMoaW50IGEsIGludCBiLCBpbnQgYyl7CiAgcmV0dXJuIHdvbihhLGIpID09IHdvbihiLGMpICYmIHdvbihiLGMpID09IHdvbihjLGEpOwp9CgovLyBEbyB0aGVzZSBmb3VyIGNvbnRhaW4gYSBjeWNsaWMgdHJpcGxlPwpib29sIGN5Y2xpYzQoaW50IGEsIGludCBiLCBpbnQgYywgaW50IGQpewogIGlmKGN5Y2xpYyhhLGIsYykpIHJldHVybiB0cnVlOyBpZihjeWNsaWMoYixjLGQpKSByZXR1cm4gdHJ1ZTsKICBpZihjeWNsaWMoYyxkLGEpKSByZXR1cm4gdHJ1ZTsgaWYoY3ljbGljKGEsYixkKSkgcmV0dXJuIHRydWU7CiAgcmV0dXJuIGZhbHNlOwp9CgovLyBJZiB5b3UgcHV0IGEsYixjIGluIG9uZSByb29tLCBpcyBpdCB0aGUgY2FzZSB0aGF0IGF0IGxlYXN0IG9uZSBvZgovLyB0aGUgcm9vbXMgZG9lcyBjb250YWluIGEgdHJpcGxldD8KYm9vbCBjeWNsaWNfKGludCBhLCBpbnQgYiwgaW50IGMpewogIGlmKGN5Y2xpYyhhLGIsYykpIHJldHVybiB0cnVlOwoKICAvLyBTZXQgZCxlLGYsZyB0byB0aGUgb3RoZXIgZm91ciwgaWUgWzAuLjZdIFwgW2EsYixjXQogIGludCBkLGUsZixnOwogIGZvcihpbnQgaT0wOyBpPDc7IGkrKykgaWYoYSE9aSYmYiE9aSYmYyE9aSl7ZD1pO2JyZWFrO30KICBmb3IoaW50IGk9MDsgaTw3OyBpKyspIGlmKGEhPWkmJmIhPWkmJmMhPWkmJmQhPWkpe2U9aTticmVhazt9CiAgZm9yKGludCBpPTA7IGk8NzsgaSsrKSBpZihhIT1pJiZiIT1pJiZjIT1pJiZkIT1pJiZlIT1pKXtmPWk7YnJlYWs7fQogIGZvcihpbnQgaT0wOyBpPDc7IGkrKykgaWYoYSE9aSYmYiE9aSYmYyE9aSYmZCE9aSYmZSE9aSYmZiE9aSl7Zz1pO2JyZWFrO30KICByZXR1cm4gY3ljbGljNChkLGUsZixnKTsKfQoKLy8gSXMgaXQgdGhlIGNhc2UgdGhhdCBubyBtYXR0ZXIgd2hhdCwgYXQgbGVhc3Qgb25lIHJvb20gaGFzIGEgY3ljbGljPwpib29sIGlzY291bnRlcmV4YW1wbGUoKXsKICBpZighY3ljbGljXygwLDEsMikpIHJldHVybiBmYWxzZTsgaWYoIWN5Y2xpY18oMCwxLDMpKSByZXR1cm4gZmFsc2U7IGlmKCFjeWNsaWNfKDAsMSw0KSkgcmV0dXJuIGZhbHNlOwogIGlmKCFjeWNsaWNfKDAsMSw1KSkgcmV0dXJuIGZhbHNlOyBpZighY3ljbGljXygwLDEsNikpIHJldHVybiBmYWxzZTsgaWYoIWN5Y2xpY18oMCwyLDMpKSByZXR1cm4gZmFsc2U7CiAgaWYoIWN5Y2xpY18oMCwyLDQpKSByZXR1cm4gZmFsc2U7IGlmKCFjeWNsaWNfKDAsMiw1KSkgcmV0dXJuIGZhbHNlOyBpZighY3ljbGljXygwLDIsNikpIHJldHVybiBmYWxzZTsKICBpZighY3ljbGljXygwLDMsNCkpIHJldHVybiBmYWxzZTsgaWYoIWN5Y2xpY18oMCwzLDUpKSByZXR1cm4gZmFsc2U7IGlmKCFjeWNsaWNfKDAsMyw2KSkgcmV0dXJuIGZhbHNlOwogIGlmKCFjeWNsaWNfKDAsNCw1KSkgcmV0dXJuIGZhbHNlOyBpZighY3ljbGljXygwLDQsNikpIHJldHVybiBmYWxzZTsgaWYoIWN5Y2xpY18oMCw1LDYpKSByZXR1cm4gZmFsc2U7CiAgaWYoIWN5Y2xpY18oMSwyLDMpKSByZXR1cm4gZmFsc2U7IGlmKCFjeWNsaWNfKDEsMiw0KSkgcmV0dXJuIGZhbHNlOyBpZighY3ljbGljXygxLDIsNSkpIHJldHVybiBmYWxzZTsKICBpZighY3ljbGljXygxLDIsNikpIHJldHVybiBmYWxzZTsgaWYoIWN5Y2xpY18oMSwzLDQpKSByZXR1cm4gZmFsc2U7IGlmKCFjeWNsaWNfKDEsMyw1KSkgcmV0dXJuIGZhbHNlOwogIGlmKCFjeWNsaWNfKDEsMyw2KSkgcmV0dXJuIGZhbHNlOyBpZighY3ljbGljXygxLDQsNSkpIHJldHVybiBmYWxzZTsgaWYoIWN5Y2xpY18oMSw0LDYpKSByZXR1cm4gZmFsc2U7CiAgaWYoIWN5Y2xpY18oMSw1LDYpKSByZXR1cm4gZmFsc2U7IGlmKCFjeWNsaWNfKDIsMyw0KSkgcmV0dXJuIGZhbHNlOyBpZighY3ljbGljXygyLDMsNSkpIHJldHVybiBmYWxzZTsKICBpZighY3ljbGljXygyLDMsNikpIHJldHVybiBmYWxzZTsgaWYoIWN5Y2xpY18oMiw0LDUpKSByZXR1cm4gZmFsc2U7IGlmKCFjeWNsaWNfKDIsNCw2KSkgcmV0dXJuIGZhbHNlOwogIGlmKCFjeWNsaWNfKDIsNSw2KSkgcmV0dXJuIGZhbHNlOyBpZighY3ljbGljXygzLDQsNSkpIHJldHVybiBmYWxzZTsgaWYoIWN5Y2xpY18oMyw0LDYpKSByZXR1cm4gZmFsc2U7CiAgaWYoIWN5Y2xpY18oMyw1LDYpKSByZXR1cm4gZmFsc2U7IGlmKCFjeWNsaWNfKDQsNSw2KSkgcmV0dXJuIGZhbHNlOwogIHJldHVybiB0cnVlOwp9CgovLyBIb3cgdG8gZ2VuZXJhdGUgYSBsaXN0IG9mIHstMSwxfV4yMT8gV2h5IG5vdCBpdGVyYXRlIGZyb20gMCB0byAyXjIxLTEKLy8gdGhlbiBzb21laG93IGNvbnZlcnQgdGhlc2UgaW50byBiaW5hcnk/CnZvaWQgc2V0Y29uZGl0aW9uKGludCBuKXsKCiAgZm9yKGludCBpPTA7IGk8NzsgaSsrKSBmb3IoaW50IGo9MDsgajw3OyBqKyspIHdpbnNbaV1bal0gPSAtMTsKCiAgLy8gdGVtcG9yYXJ5IGFycmF5IHRvIHN0b3JlIHRoZSAxIGFuZCAtMSdzIGJlZm9yZSB0cmFuc2ZlcnJpbmcKICAvLyBvdmVyIHRvIHRoZSB3aW4gbWF0cml4CiAgaW50IGFycmF5WzIxXTsKICBmb3IoaW50IGk9MDsgaTwyMTsgaSsrKSBhcnJheVtpXT0tMTsKCiAgLy8gc2VlayBoaWdoZXN0IHBvd2VyIG9mIDIKICBpbnQgcCA9IDAsIHBfID0gMTsKICB3aGlsZShwXyoyIDw9IG4pe3BfKj0yOyBwKys7fQoKICBpbnQgaz0xOyB3aGlsZShrPG4pIGsqPTI7IGlmKGs+bikgay89MjsKICB3aGlsZShrPjApIHsKICAgIGludCBiZDsKCiAgICAvLyBleHRyYWN0IGEgYmluYXJ5IGRpZ2l0CiAgICBpZihpbnQobi9rKSUyPT0wKWJkPS0xOyBlbHNlIGJkPTE7CiAgICBhcnJheVtwXSA9IGJkOwogICAgcC0tOwoKICAgIGsvPTI7CiAgfQoKICAvLyBjb3B5IGFycmF5IG92ZXIKICBpbnQgaW54ID0gMDsKICBmb3IoaW50IGk9MTsgaTw3OyBpKyspIHsKICAgIGZvcihpbnQgaj0wOyBqPGk7IGorKyl7CiAgICAgIHdpbnNbaV1bal0gPSBhcnJheVtpbnhdOwogICAgICBpbngrKzsKICAgIH0KICB9Cgp9CgppbnQgbWFpbigpewoKICAvLyBMb29wIG92ZXIgYWxsIHBvc3NpYmxlIGNvbWJpbmF0aW9ucyB1cCB0byAyXjIxCiAgZm9yKGludCBpPTA7IGk8MjA5NzE1MjsgaSsrKXsKICAgIHNldGNvbmRpdGlvbihpKTsKICAgIGlmKGlzY291bnRlcmV4YW1wbGUoKSl7CiAgICAgIGNvdXQgPDwgaSA8PCBlbmRsOwogICAgfQogIH0KCiAgcmV0dXJuIDA7Cn0K

Success #stdin #stdout 2.32s 2728KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/HCV6e

language:

C++ (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language