/*************************************************************************
 *                                                                       *
 *                    XI Olimpiada Informatyczna                         *
 *                                                                       *
 *   Rozwiązanie zadania: PIN-kod                                        *
 *   Plik:                pin.c                                          *
 *   Autor:               Tomasz Czajka                                  *
 *************************************************************************/

#include "hsm.h"

int tab[10000][4];
int nposs;
int poss[10000];


void fillTab(void) {
  int i,j,k;
  for(i=0;i<10000;++i) {
    j=i;
    for(k=3;k>=0;--k) {
      tab[i][k] = j%10;
      j/=10;
    }
  }
}

// zwraca pin, dla ktorego maszyna maszyna zwroci TAK dla danego kodu i pytania
int check(int pin[4], int pyt) {
  int i,res;
  
  res=0;
  for(i=0;i<4;++i)
    if(pyt&(1<<pin[i]))
      res |= (1<<i);
  return res;
}

void zrobRuch(void) {
  int pyt,bestPin,bestA,bestv,v,p,i;
  int c[16];
  int a[16];
  int pin[4];
  int res;
  
  bestv = -1;
  for(pyt=0;pyt<1<<10;++pyt) {
    for(i=0;i<16;++i) c[i] = 0;
    for(i=0;i<nposs;++i)
      ++c[check(tab[poss[i]], pyt)];
    v=0;
    for(i=0;i<16;++i) if(c[i]>v) { v=c[i]; p=i; }
    if(nposs-v < v) v = nposs-v;
    if(v>bestv) { bestPin=p; bestA=pyt; bestv=v; }
  }
  
  for(i=0;i<16;++i) a[i] = (bestA>>(i%10))&1;
  for(i=0;i<4;++i) pin[i] = (bestPin>>i)&1;

  res = sprawdz(pin, a);
  
  i=0;
  while(i<nposs) {
    if((check(tab[poss[i]], bestA)==bestPin)!=res) {
      poss[i] = poss[nposs-1];
      --nposs;
    }
    else ++i;
  }
}

int main(void) {
  int i;
  
  fillTab();
  
  for(i=0;i<10000;++i) poss[i]=i;
  nposs = 10000;
  
  while(nposs>1) zrobRuch();
  
  wynik(tab[poss[0]]);
  
  return 0;
}
