有多少人参加考试

sheng_jianguo · 发表于 2009-7-22 08:47:02

一个容易得到的上界是19，开始我猜 ... shshsh_0510 发表于 2009-7-3 14:59

为什么上界是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

当K=6,n=19时，最终标准化的具体结果是怎样的呢？

nlrte13 · 发表于 2009-7-23 15:10:46

反证20个不行. 如果可以,根据第一个题目的答案可以将20人分成3组.人数最多的两组加起来不少于14人,而14人不能用5道题区分 mathe 发表于 2009-7-23 10:00

是的，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

这个就是症结了

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[MAX_DEPTH];
int stdv1[MAX_DEPTH];
int stdv2[MAX_DEPTH];
int curbest=0;
int code[M];
int orders[M];
int indexs[M];
int tc;
int rord[MAX_DEPTH][M];
#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[i1]!=code[i2])
return code[i1]-code[i2];
return i1-i2;
}
int tb[TBS][MAX_DEPTH];
int tb2[KK][MAX_DEPTH];
char reorder[6][3]={
{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[K];
int i,j,t;
for(i=0;i<K;i++)a[i]=i;
t=0;
do{
for(i=0;i<count;i++){
int u=0;
for(j=0;j<K;j++){
int c=(tb[index][i]>>(2*j))&3;
u|=c<<(2*a[j]);
}
tb2[t][i]=u;
}
qsort(tb2[t],count,sizeof(tb2[t][0]),mycmp);
t++;
}while(next_permutation(a,a+K));
t=0;
for(i=1;i<KK;i++){
for(j=0;j<count;j++){
if(tb2[i][j]!=tb2[t][j])
break;
}
if(j<count&&indexs[tb2[i][j]]<indexs[tb2[t][j]])
t=i;
}
for(j=0;j<count;j++)output[j]=tb2[t][j];
}
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[i]>>(2*j))&3;
c=reorder[ind[j]][c];
u|=c<<(2*j);
}
output[i]=u;
}
qsort(output,count,sizeof(output[0]),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[tb[i][j]]!=code[tb[m][j]])
break;
}
if(j<count&&code[tb[i][j]]<code[tb[m][j]]){
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[0][j]=tb[mid][j];
}
k=1;
for(i=mid+1;i<total;i++){
for(j=0;j<count;j++){
if(code[tb[i][j]]!=code[tb[0][j]])
break;
}
if(j==count){
for(j=0;j<count;j++){
tb[k][j]=tb[i][j];
}
k++;
}
}
return k;
}
int gen_tb(int input[MAX_DEPTH],int count)
{
char a[K];
int i,t,u=0;
for(i=0;i<count;i++){///The transform that the i'th input is zero
int v=input[i];
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[s][(v>>(2*h))&3]==0)
break;
}
ASSERT(s<6);
if((t&(1<<h))!=0){
for(++s;s<6;s++){
if(reorder[s][(v>>(2*h))&3]==0)
break;
}
}
ASSERT(s<6);
a[h]=s;
}
gen_tb_item(input,tb[u],count,a);
u++;
}
}
i=find_min_from_table(u,count);
return moving_forward_min(u,i,count);
}
void standardize(int input[MAX_DEPTH], int output[MAX_DEPTH], int count)
{
#ifdef BEST_STD
int best[MAX_DEPTH];
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[j]!=output[j])
break;
}
if(j<count&&best[j]<output[j]){
for(j=0;j<count;j++)best[j]=output[j];
}
}
#else
int i;
for(i=0;i<count;i++)output[i]=input[i];
qsort(output,count,sizeof(output[0]),mycmp);
#endif
}
void sort3(char c[3])
{
char d;
if(c[0]>c[1]){
d=c[0];c[0]=c[1];c[1]=d;
}
if(c[0]>c[2]){
d=c[0];c[0]=c[2];c[2]=d;
}
if(c[1]>c[2]){
d=c[1];c[1]=c[2];c[2]=d;
}
}
void init_order()
{
char a[K];
int i,t;
t=0;
for(i=0;i<K;i++)a[i]=0;
do{
char c[4];
int u=0;
int v=0;
c[0]=c[1]=c[2]=c[3]=0;
for(i=0;i<K;i++){
c[a[i]]++;
u|=a[i]<<(2*i);
}
orders[t++]=u;
//u is original code
//v is standardized one code
ASSERT(c[3]==0);
///move all 0 to the end of the number
for(i=c[0];i<c[0]+c[1];i++){///
v|=1<<(2*i);
}
for(i=c[0]+c[1];i<K;i++){
v|=2<<(2*i);
}
code[u]=v;
for(i=K-1;i>=0;i--){
if(a[i]<2){
a[i]++;
break;
}else{
a[i]=0;
}
}
if(i<0)break;
}while(1);
tc=t;
qsort(orders,tc,sizeof(orders[0]),mycmp);
for(i=0;i<tc;i++){
indexs[orders[i]]=i;
}
for(i=0;i<MAX_DEPTH;i++){
int j;
for(j=0;j<tc;j++){
rord[i][j]=j;
}
for(j=0;j<tc;j++){
int u=rand()%tc;
if(j!=u){
int x=rord[i][j];
rord[i][j]=rord[i][u];
rord[i][u]=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[i]);
printf(" ");
}
printf("}\n");
}
void dumpf(FILE *f, int d)
{
int i;
for(i=0;i<d;i++){
fprintf(f,"%d ",curlist[i]);
}
fprintf(f,"\n");
}
void search_next(FILE *out, int depth)
{
int i,j,k,t;
for(i=0;i<tc;i++){
int u=orders[i];
bool p2=true;;
for(j=0;j<depth;j++){
if(curlist[j]==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[j]>>(2*t))&3;
int b=(curlist[k]>>(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[depth]=u;
standardize(curlist,stdv1,depth+1);
if(stdv1[depth]!=curlist[depth])
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[i];
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[j]>>(2*t))&3;
int b=(curlist[k]>>(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[depth]=u;
standardize(curlist,stdv1,depth+1);
if(stdv1[depth]!=curlist[depth])
continue;
search(depth+1,i+1);
}
}
}
void step_one()
{
FILE *f=fopen("f0","w");
fprintf(f,"0");
fclose(f);
}
char fname[20];
char line[1024];
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[j]=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[0]=orders[0];
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

复制代码

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 有多少人参加考试