sheng_jianguo
发表于 2009-7-22 08:47:02
一个容易得到的上界是19，开始我猜 ...
shshsh_0510 发表于 2009-7-3 14:59 http://bbs.emath.ac.cn/images/common/back.gif
为什么上界是19呢？很容易得到？
nlrte13
发表于 2009-7-23 09:01:15
第六感……
mathe
发表于 2009-7-23 10:00:31
反证20个不行.
如果可以,根据第一个题目的答案可以将20人分成3组.人数最多的两组加起来不少于14人,而14人不能用5道题区分
mathe
发表于 2009-7-23 10:59:50
1# 东邪
这个题目主要等价状态很多.通过计算机可以考虑下面的算法:
对于给定的k道题目,每道题目3个答案(比如这里k=6),我们依次计算所有n个人构成的集合,其中n个人中任意3个人可以找到一道题目,3个人答案互不相同.
可以看出,n=1的时候,实际上只有一个集合,所有其它的情况都同这个情况等价.
我们的目标就是对于每个n个人构成的集合,在其中添加一个人,构成n+1个人的集合.然后在所有这些n+1个人的集合中,淘汰掉等价的数据.
为了能够淘汰等价的数据,我们需要对每个集合进行一种"标准化".
对于每道题目,其3个答案可以任意置换(只要所有人这个答案的结果同时置换就可以);同样,k道题目的顺序也可以任意置换.而n个人的位置也可以任意置换.
每个集合可以表示成一些k位3进制数.
我们可以对于每个这样的集合,首先计算出通过置换每一位的情况可以得出的集合;这样可以总共有$3^k$个不同的等价集合.
然后我们对这些集合中的n个k位3进制数各自进行排序.但是排序的顺序不是通常的顺序,而是那些各位数通过置换以后能够相互转换的数据要排在一起(也就是它们的顺序不管),比如顺序为
000000, =>0
111111, =>1
222222, =>2
{000001,000010,000100,001000,010000,100000}, =>3
{000002,000020,000200,002000,020000,200000}, =>4
{000003,000030,000300,003000,030000,300000}, =>5
{000012,000102,001002,...., 120000} =>6
...
当然,这样选择以后,$3^k$个集合有些集合会被映射到同样的结果,我们只保留按字典顺序最小的那些表示方式(很有可能只余下一个集合)
然后对于余下的结果,我们再置换k位(k!种不同的置换方式),(这个时候上面各组内部的顺序也要考虑了,找到那个按字典顺序最小的表达方式作为最终标准化结果)
sheng_jianguo
发表于 2009-7-23 14:53:06
本帖最后由 sheng_jianguo 于 2009-7-23 15:00 编辑
.........找到那个按字典顺序最小的表达方式作为最终标准化结果
mathe 发表于 2009-7-23 10:59 http://bbs.emath.ac.cn/images/common/back.gif
当K=6,n=19时，最终标准化的具体结果是怎样的呢？
nlrte13
发表于 2009-7-23 15:10:46
反证20个不行.
如果可以,根据第一个题目的答案可以将20人分成3组.人数最多的两组加起来不少于14人,而14人不能用5道题区分
mathe 发表于 2009-7-23 10:00 http://bbs.emath.ac.cn/images/common/back.gif
是的，5道题可以区分13人，{4, 4, 5}。人数最多的两组加起来 = 9，4题区分^^
shshsh_0510
发表于 2009-7-23 16:36:44
22# nlrte13
这个还不至于使用第6感把:)
mathe
发表于 2009-7-23 17:20:16
试验了一下,发现我上面的标准化过程太花时间了,所以总体上可能比直接重复搜索还要慢
nlrte13
发表于 2009-7-23 17:27:45
试验了一下,发现我上面的标准化过程太花时间了,所以总体上可能比直接重复搜索还要慢
mathe 发表于 2009-7-23 17:20 http://bbs.emath.ac.cn/images/common/back.gif
这个就是症结了;P
mathe
发表于 2009-7-24 06:45:31
5道题目搜索结果好像只有10人.
不过程序好像还有点问题,一到我的cygwin下编译,运行就出错.
谁有空来帮忙调试一下看看:
// muser.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <assert.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#include <string.h>
#include <ctype.h>
using namespace std;
#define K 6
#define KK (1*2*3*4*5*6) //K!
#define M (1<<(2*K))
#define MAX_DEPTH 20
#define TBS ((1<<K)*MAX_DEPTH) //MAX_DEPTH*2^K
int curlist;
int stdv1;
int stdv2;
int curbest=0;
int code;
int orders;
int indexs;
int tc;
int rord;
#ifdef NDEBUG
#define ASSERT(x)
#else
#define ASSERT(x) assert(x)
#endif
#define BEST_STD
int mycmp(const void *p, const void *q)
{
const int *pi=(const int *)p;
const int *qi=(const int *)q;
int i1=*pi,i2=*qi;
if(code!=code)
return code-code;
return i1-i2;
}
int tb;
int tb2;
char reorder={
{0,1,2},
{0,2,1},
{1,0,2},
{1,2,0},
{2,0,1},
{2,1,0}
};
void best_of_tb_item(int index, int output[], int count)
{
char a;
int i,j,t;
for(i=0;i<K;i++)a=i;
t=0;
do{
for(i=0;i<count;i++){
int u=0;
for(j=0;j<K;j++){
int c=(tb>>(2*j))&3;
u|=c<<(2*a);
}
tb2=u;
}
qsort(tb2,count,sizeof(tb2),mycmp);
t++;
}while(next_permutation(a,a+K));
t=0;
for(i=1;i<KK;i++){
for(j=0;j<count;j++){
if(tb2!=tb2)
break;
}
if(j<count&&indexs]<indexs])
t=i;
}
for(j=0;j<count;j++)output=tb2;
}
void gen_tb_item(int input[], int output[], int count, char ind[])
{
int i,j;
for(i=0;i<count;i++){
int u=0;
for(j=0;j<K;j++){
int c=(input>>(2*j))&3;
c=reorder];
u|=c<<(2*j);
}
output=u;
}
qsort(output,count,sizeof(output),mycmp);
}
int find_min_from_table(int total,int count)
{
int i,j;
int m=0;
for(i=1;i<total;i++){
for(j=0;j<count;j++){
if(code]!=code])
break;
}
if(j<count&&code]<code]){
m=i;
}
}
return m;
}
int moving_forward_min(int total,int mid, int count)
{
int i,j,k;
if(mid!=0){
for(j=0;j<count;j++)tb=tb;
}
k=1;
for(i=mid+1;i<total;i++){
for(j=0;j<count;j++){
if(code]!=code])
break;
}
if(j==count){
for(j=0;j<count;j++){
tb=tb;
}
k++;
}
}
return k;
}
int gen_tb(int input,int count)
{
char a;
int i,t,u=0;
for(i=0;i<count;i++){///The transform that the i'th input is zero
int v=input;
for(t=0;t<1<<K;t++){
int h;
for(h=0;h<K;h++){
int s;
for(s=0;s<6;s++){
if(reorder[(v>>(2*h))&3]==0)
break;
}
ASSERT(s<6);
if((t&(1<<h))!=0){
for(++s;s<6;s++){
if(reorder[(v>>(2*h))&3]==0)
break;
}
}
ASSERT(s<6);
a=s;
}
gen_tb_item(input,tb,count,a);
u++;
}
}
i=find_min_from_table(u,count);
return moving_forward_min(u,i,count);
}
void standardize(int input, int output, int count)
{
#ifdef BEST_STD
int best;
int cand = gen_tb(input,count);
best_of_tb_item(0,output,count);
int i,j;
for(i=1;i<cand;i++){
best_of_tb_item(i,best,count);
for(j=0;j<count;j++){
if(best!=output)
break;
}
if(j<count&&best<output){
for(j=0;j<count;j++)best=output;
}
}
#else
int i;
for(i=0;i<count;i++)output=input;
qsort(output,count,sizeof(output),mycmp);
#endif
}
void sort3(char c)
{
char d;
if(c>c){
d=c;c=c;c=d;
}
if(c>c){
d=c;c=c;c=d;
}
if(c>c){
d=c;c=c;c=d;
}
}
void init_order()
{
char a;
int i,t;
t=0;
for(i=0;i<K;i++)a=0;
do{
char c;
int u=0;
int v=0;
c=c=c=c=0;
for(i=0;i<K;i++){
c]++;
u|=a<<(2*i);
}
orders=u;
//u is original code
//v is standardized one code
ASSERT(c==0);
///move all 0 to the end of the number
for(i=c;i<c+c;i++){///
v|=1<<(2*i);
}
for(i=c+c;i<K;i++){
v|=2<<(2*i);
}
code=v;
for(i=K-1;i>=0;i--){
if(a<2){
a++;
break;
}else{
a=0;
}
}
if(i<0)break;
}while(1);
tc=t;
qsort(orders,tc,sizeof(orders),mycmp);
for(i=0;i<tc;i++){
indexs]=i;
}
for(i=0;i<MAX_DEPTH;i++){
int j;
for(j=0;j<tc;j++){
rord=j;
}
for(j=0;j<tc;j++){
int u=rand()%tc;
if(j!=u){
int x=rord;
rord=rord;
rord=x;
}
}
}
}
void dumpone(int x)
{
int i;
for(i=0;i<K;i++){
printf("%d",(x>>(2*i))&3);
}
}
void dump(int d)
{
int i;
printf("{ ");
for(i=0;i<d;i++){
dumpone(curlist);
printf(" ");
}
printf("}\n");
}
void dumpf(FILE *f, int d)
{
int i;
for(i=0;i<d;i++){
fprintf(f,"%d ",curlist);
}
fprintf(f,"\n");
}
void search_next(FILE *out, int depth)
{
int i,j,k,t;
for(i=0;i<tc;i++){
int u=orders;
bool p2=true;;
for(j=0;j<depth;j++){
if(curlist==u)break;
}
if(j<depth)continue;
for(j=0;j<depth&&p2;j++){
for(k=j+1;k<depth&&p2;k++){
bool pass=false;
for(t=0;t<K&&!pass;t++){
int a=(curlist>>(2*t))&3;
int b=(curlist>>(2*t))&3;
int c=(u>>(2*t))&3;
if(a!=b&&b!=c&&a!=c){
pass=true;
}
}
if(!pass)p2=false;
}
}
if(!p2)continue;
curlist=u;
standardize(curlist,stdv1,depth+1);
if(stdv1!=curlist)
continue;
dumpf(out,depth+1);
}
}
void search(int depth,int tt)
{
if(depth>curbest){
dump(depth);
curbest=depth;
}
if(depth<MAX_DEPTH-1){
int i,j,k,t;
for(i=tt;i<tc;i++){
int u=orders;
bool p2=true;;
for(j=0;j<depth&&p2;j++){
for(k=j+1;k<depth&&p2;k++){
bool pass=false;
for(t=0;t<K&&!pass;t++){
int a=(curlist>>(2*t))&3;
int b=(curlist>>(2*t))&3;
int c=(u>>(2*t))&3;
if(a!=b&&b!=c&&a!=c){
pass=true;
}
}
if(!pass)p2=false;
}
}
if(!p2)continue;
curlist=u;
standardize(curlist,stdv1,depth+1);
if(stdv1!=curlist)
continue;
search(depth+1,i+1);
}
}
}
void step_one()
{
FILE *f=fopen("f0","w");
fprintf(f,"0");
fclose(f);
}
char fname;
char line;
void step(int i)
{
int j;
sprintf(fname,"f%d",i-1);
FILE *in=fopen(fname,"r");
sprintf(fname,"f%d",i);
FILE *out=fopen(fname,"w");
while(fgets(line,1024,in)){
char *p=line;
while(isspace(*p))p++;
if(*p=='\0')break;
for(j=0;j<i;j++){
curlist=atoi(p);
while(isdigit(*p))p++;
while(isspace(*p))p++;
}
search_next(out, i);
}
fclose(in);
fclose(out);
}
#if 1
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(NULL));
init_order();
curlist=orders;
curbest=1;
search(1,1);
return 0;
}
#else
int main()
{
int i;
init_order();
step_one();
for(i=1;i<MAX_DEPTH-1;i++){
step(i);
}
}
#endif