優勝者プログラム（by 池辺 貞郎，梅津 高朗（六甲高等学校））


（注）石の重さなどの桁数が大きいのでそのままでは普通の計算機では動
      かないかもしれない．

#include <stdio.h>
#include <malloc.h>

#define IN 40            石の総数
#define UPPER 1048576    
#define LOWER 1048576
#define PN 10            問題数
#define NF 2400000       ハッシュにつかう魔法の数！？
#define NM 4             重なりの上限値（3 でもよかった？？！！）

const unsigned stbl[IN] = {
    3665308701534, 7330617403068, 506241270389, 2845136891545, 1361758541367,
    70690921978, 804588384145, 196489340090, 1142459568191, 7939847458483,
    6088562083931, 6400576036950, 3637880320065, 1381744556, 3698108030974,
    4727806475348, 6119818214606, 3931881946355, 988458873198, 4929222032268,
    4210741949677, 5384036277020, 5342995695171, 986163840917, 7870495621557, 
    4329276825246, 2347204856362, 2959434526322, 3048315069154, 4949991960816,
    3300216382790, 278119293989, 278784520727, 2817416522030, 5660250136005,
    571646958192, 84846673295, 6191302978762, 6372669810753, 263849911287 };

int utbl[UPPER];     21...40 番までの石の重さでできる重さの表
int ltbl[LOWER];     1 ...20 番までの石の重さでできる重さの表
int atbl[NF][NM];    ハッシュ表

char* sz_default_problem_file = "problem.in3";

int
main(int argc, char **argv)
{
  char* sz_problem_file;
  int problem[10];

  /* set filename */
  if(argc<2){
    sz_problem_file = sz_default_problem_file;
  } else {
    sz_problem_file = argv[1];
  }

  /* file read */
  {
    FILE* fp;
    char buf[256];
    int i;
    fp = fopen(sz_problem_file, "rt");
    if(!fp) {
      perror(sz_problem_file);
      return(-1);
    }
    for(i=0; i<PN; i++){
      fscanf(fp, "%d", &problem[i]);
    }
  }
  
  /* make table */
  {
    int i;
    #pragma _CRI taskloop private(i) shared(utbl, stbl) vector
    for(i=0; i<UPPER; i++){
      utbl[i]=
	((i&0x00001)?stbl[20]:0)+
	((i&0x00002)?stbl[21]:0)+
	((i&0x00004)?stbl[22]:0)+
	((i&0x00008)?stbl[23]:0)+
	((i&0x00010)?stbl[24]:0)+
	((i&0x00020)?stbl[25]:0)+
	((i&0x00040)?stbl[26]:0)+
	((i&0x00080)?stbl[27]:0)+
	((i&0x00100)?stbl[28]:0)+
	((i&0x00200)?stbl[29]:0)+
	((i&0x00400)?stbl[30]:0)+
	((i&0x00800)?stbl[31]:0)+
	((i&0x01000)?stbl[32]:0)+
	((i&0x02000)?stbl[33]:0)+
	((i&0x04000)?stbl[34]:0)+
	((i&0x08000)?stbl[35]:0)+
	((i&0x10000)?stbl[36]:0)+
	((i&0x20000)?stbl[37]:0)+
	((i&0x40000)?stbl[38]:0)+
	((i&0x80000)?stbl[39]:0);
    }
    #pragma _CRI taskloop private(i) shared(ltbl, stbl) vector
    for(i=0; i<LOWER; i++){
      ltbl[i]=
	((i&0x00001)?stbl[ 0]:0)+
	((i&0x00002)?stbl[ 1]:0)+
	((i&0x00004)?stbl[ 2]:0)+
	((i&0x00008)?stbl[ 3]:0)+
	((i&0x00010)?stbl[ 4]:0)+
	((i&0x00020)?stbl[ 5]:0)+
	((i&0x00040)?stbl[ 6]:0)+
	((i&0x00080)?stbl[ 7]:0)+
	((i&0x00100)?stbl[ 8]:0)+
	((i&0x00200)?stbl[ 9]:0)+
	((i&0x00400)?stbl[10]:0)+
	((i&0x00800)?stbl[11]:0)+
	((i&0x01000)?stbl[12]:0)+
	((i&0x02000)?stbl[13]:0)+
	((i&0x04000)?stbl[14]:0)+
	((i&0x08000)?stbl[15]:0)+
	((i&0x10000)?stbl[16]:0)+
	((i&0x20000)?stbl[17]:0)+
	((i&0x40000)?stbl[18]:0)+
	((i&0x80000)?stbl[19]:0);
    }
  }
  /* Table Make */
  {
    int i,j;
    int a[LOWER];

    for(j=0;j<NM;j++){
      #pragma _CRI taskloop shared(atbl) private(i) value(j) vector
      for(i=0;i<NF;i++){
        atbl[i][j]=LOWER;
      }
    }

    #pragma _CRI taskloop shared(ltbl, a) private(i) vector
    for(i=0;i<LOWER;i++){
      a[i]=ltbl[i]%NF;
    }

    #pragma _CRI taskloop shared(atbl, a) private(i)
    for(i=0;i<LOWER;i++){
      if(atbl[a[i]][0]==LOWER){
        #pragma _CRI guard
        atbl[a[i]][0]=i;
        #pragma _CRI endguard
      }else if(atbl[a[i]][1]==LOWER){
        #pragma _CRI guard
        atbl[a[i]][1]=i;
        #pragma _CRI endguard
      }else if(atbl[a[i]][2]==LOWER){
        #pragma _CRI guard
        atbl[a[i]][2]=i;
        #pragma _CRI endguard
      }
    }
  }
  /* Solve */
  {
    int i, j, k, l;
    int a,ta;

    #pragma _CRI taskloop shared(problem, atbl, utbl, ltbl) \
                          private(i, j, k, l, a, ta)
    for(i=0;i<PN;i++){
      a=problem[i]%NF;

      for(j=0;j<UPPER;j++){
	ta=a-utbl[j]%NF;
	if(ta<0) ta+=NF;
	
	for(k=0;k<NM;k++){
	  if(atbl[ta][k]==LOWER){
	    break;
	  }
	  if(ltbl[atbl[ta][k]]+utbl[j]==problem[i]){
	    #pragma _CRI guard
	    printf("No. %2d: target weight = %15d\n"
		   ">>> Found Exactly!!\n"
		   ">>> Answer:",
		   i, problem[i]);
	    for(l=0; l<20; l++){
	      if((atbl[ta][k]>>l)&1) printf(" %d,", l+1);
	    }
	    for(l=0; l<20; l++){
	      if((j>>l)&1) printf(" %d,", l+21);
	    }
	    puts("\n");

	    #pragma _CRI endguard
	    goto FIND;
	  }
	}
      }
    FIND:;
    }
  }

  return 0;
}