/*** プログラムの名前は決めかねているので適当につけてください ***/
/*
 * 「全問題を見るまで挑戦し続ける」をKAISU回シミュレートし、
 * その結果を出力する
 * 全問題数: ZENBU、1度の挑戦で出題される問題数: IKKAI
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define KAISU 40
#define ZENBU 50 /* ZENBU > IKKAI     */
#define IKKAI 13 /*         IKKAI > 0 */

#define TRUE -1
#define FALSE 0

int kiroku[ZENBU]; /* すでに見た問題を保持 */
int mondai[ZENBU+1]; /* 1度の挑戦でまだ出されていない問題を保持; +1は「番兵」 */

int myrand(int);
int check();
void challenge(int);
void reinit_mondai();
void init_kiroku();

int main()
{
	int result[KAISU]; /* 各KAISUで要した挑戦回数を保持 */
	int i, max;
	int *bunpu; /* 結果出力用 */
	
	max=0;
	
	for(i=0;i<KAISU;i++)
	{
		result[i]=0;
	}
	for(i=0;i<=ZENBU;i++)
	{
		mondai[i]=-1;
	}
	
	init_kiroku();
	
	for(i=0;i<KAISU;i++)
	{
		int j=0;
		fprintf(stderr, "processing %d\n", i);
		init_kiroku();
		while(!check()) /* 全問題を見るまでchallenge()し続ける */
		{
			j++;
			fprintf(stderr, "\ttrying %d\n", j);
			reinit_mondai();
			challenge(IKKAI);
		}
		result[i]=j;
		if(j>max){max=j;}
	}
	
	/* 結果出力: 各挑戦回数が何度あったか */
	bunpu=(int *)malloc(sizeof(int)*max);
	for(i=0;i<max;i++)
	{
		bunpu[i]=0;
	}
	
	for(i=0;i<KAISU;i++)
	{
		bunpu[result[i]-1]++;
	}
	for(i=0;i<max;i++)
	{
		printf("%d\t\t%d\n", i+1, bunpu[i]);
	}
	return 0;
}

/* i<taneのループは非常に時間がかかる */
int myrand(int dice)
{
	long int i,tane;
	time_t dummy;
	
	srand(time(&dummy));
	tane=rand();
	for(i=0;i<tane);i++){tane=rand(); srand(time(&dummy));}
	return(rand() % dice);
}

/* kirokuを調べ、全要素がTRUEならTRUEを返す */
int check()
{
	int i;
	fprintf(stderr, "checking ");
	for(i=0;kiroku[i]==TRUE;i++){fprintf(stderr, "%d ", kiroku[i]);}
	fprintf(stderr, "\n");
	return (i==ZENBU)? TRUE: FALSE;
}

/* 再帰; IKKAI分だけ再帰で呼び出し続ける */
void challenge(int ikkai)
{
	int i, deme;
	
	if(ikkai==0){return;}
	deme=myrand(ZENBU-(IKKAI-ikkai)); /* 1問ずつ減らしてサイコロを振る */
	kiroku[mondai[deme]]=TRUE;
	fprintf(stderr, "\t\tdeme %d\n", mondai[deme]); /* deme=出目 */
	
	/* 1度の挑戦中、出せる問題は1題ずつ減っていく。それを忠実に
         * シミュレート(統計的に影響するかもしれないので)。
         * 出た問題を消して、それ以後を1つずつ前にずらしていく。
         * mondaiは1つ余計に要素を持ち、最後のものは-1にセットされている。
         */
	for(i=deme;mondai[i]!=-1;i++)
	{
		mondai[i]=mondai[i+1];
	}
	challenge(--ikkai); /* 再帰 */
}

void reinit_mondai()
{
	int i, shuffle;
	for(i=0;i<ZENBU;i++){mondai[i]=i;}
	shuffle=myrand(ZENBU);
	for(i=0; i<shuffle; i++)
	{
		int i, j, temp;
		i=myrand(ZENBU); j=myrand(ZENBU);
		temp=mondai[i];
		mondai[i]=mondai[j];
		mondai[j]=temp;
	}
}

void init_kiroku()
{
	int i;
	for(i=0;i<ZENBU;i++){kiroku[i]=FALSE;}
}