毒酒问题(加强版)

mathe

最新的代码

1. #include <vector>
   
2. #include <set>
   
3. #include <stdio.h>
   
4. #include <string.h>
   
5. #include <stdlib.h>
   
6. #include <rdrand.h>
   
7. #include <time.h>
   
8. 
   
9. typedef unsigned int dtype;
   
10. typedef std::vector<dtype> DataState;
    
11. typedef std::set<dtype> UnionState;
    
12. #ifndef K
    
13. #define K 10
    
14. #endif
    
15. #define COUNT 100000
    
16. #if K==10
    
17. #define HK 5
    
18. #define UPBOUND 30
    
19. #define REPLACE_NUMS 5
    
20. #define LARGE_REPLACE_NUMS 8
    
21. #endif
    
22. #if K==11
    
23. #define HK 5
    
24. #define UPBOUND 60
    
25. #define REPLACE_NUMS 5
    
26. #define LARGE_REPLACE_NUMS 10
    
27. #endif
    
28. #if K==12
    
29. #define HK 6
    
30. #define UPBOUND 70
    
31. #define REPLACE_NUMS 5
    
32. #define LARGE_REPLACE_NUMS 11
    
33. #endif
    
34. #if K==13
    
35. #define HK 6
    
36. #define UPBOUND 100
    
37. #define REPLACE_NUMS 4
    
38. #define LARGE_REPLACE_NUMS 12
    
39. #endif
    
40. #if K==14
    
41. #define HK 7
    
42. #define UPBOUND 200
    
43. #define REPLACE_NUMS 6
    
44. #define LARGE_REPLACE_NUMS 13
    
45. #endif
    
46. #if K==15
    
47. #define HK 7
    
48. #define UPBOUND 350
    
49. #define REPLACE_NUMS 7
    
50. #define LARGE_REPLACE_NUMS 15
    
51. #endif
    
52. #if K==16
    
53. #define HK 7
    
54. #define UPBOUND 400
    
55. #define REPLACE_NUMS 7
    
56. #define LARGE_REPLACE_NUMS 15
    
57. #endif
    
58. #if K==17
    
59. #define HK 8
    
60. #define UPBOUND 400
    
61. #define REPLACE_NUMS 7
    
62. #define LARGE_REPLACE_NUMS 15
    
63. #endif
    
64. #if K==28
    
65. #define HK 13
    
66. #define UPBOUND 2000
    
67. #define REPLACE_NUMS 7
    
68. #define LARGE_REPLACE_NUMS 9
    
69. #endif
    
70. #if K==29
    
71. #define HK 13
    
72. #define UPBOUND 2000
    
73. #define REPLACE_NUMS 7
    
74. #define LARGE_REPLACE_NUMS 9
    
75. #endif
    
76. #if K==30
    
77. #define HK 13
    
78. #define UPBOUND 2000
    
79. #define REPLACE_NUMS 8
    
80. #define LARGE_REPLACE_NUMS 16
    
81. #endif
    
82. #if K==31
    
83. #define HK 13
    
84. #define UPBOUND 2000
    
85. #define REPLACE_NUMS 8
    
86. #define LARGE_REPLACE_NUMS 16
    
87. #endif
    
88. #if K==32
    
89. #define HK 14
    
90. #define UPBOUND 2000
    
91. #define REPLACE_NUMS 8
    
92. #define LARGE_REPLACE_NUMS 16
    
93. #endif
    
94. #define UB UPBOUND
    
95. #define MIN_EDGES (REPLACE_NUMS+LARGE_REPLACE_NUMS)
    
96. 
    
97. unsigned gen_rand_edge()
    
98. {
    
99.      unsigned d = 0;
    
100.      unsigned rd[K];
     
101.      int i;
     
102.      rdrand_get_n_32(K,rd);
     
103.      for(i=0;i<K;i++){
     
104.         if(rd[i]<1288490189){
     
105.             d|=1<<i;
     
106.         }
     
107.      }
     
108.      return d;
     
109. }
     
110. 
     
111. long update_bits(long v, long bits)
     
112. {
     
113.     int i;
     
114.     unsigned rd[K];
     
115.     rdrand_get_n_32(K,rd);
     
116.     for(i=bits+1;i<K;i++){
     
117.        if(rd[i]<1288490189){
     
118.            v|=1<<i;
     
119.        }
     
120.     }
     
121.     return v;
     
122. }
     
123. 
     
124. int should_we_change()
     
125. {
     
126.     unsigned d=0;
     
127.     rdrand_get_n_32(1,&d);
     
128.     d%=10;
     
129.     if(d==0)return 1;
     
130.     return 0;
     
131. }
     
132. 
     
133. UnionState tus;
     
134. DataState ds;
     
135. DataState best_result;
     
136. #define WORD_OF(x)        ((x)>>5)
     
137. #define INDEX_IN_WORD(x)  ((x)&31)
     
138. #define IS_SET(mask,x)     (mask[WORD_OF(x)]&(1<<INDEX_IN_WORD(x)))
     
139. #define SET(mask,x)        (mask[WORD_OF(x)]|=1<<INDEX_IN_WORD(x))
     
140. #define CLEAR(mask,x)      (mask[WORD_OF(x)]&=~(1<<INDEX_IN_WORD(x)))
     
141. 
     
142. void init()
     
143. {
     
144.     ds.clear();
     
145. }
     
146. int bitcount(dtype d);
     
147. int test_add(dtype d)
     
148. {
     
149.     UnionState ls;
     
150.     if(bitcount(d)>HK)return -1;
     
151. #ifdef STRICT
     
152.     if(tus.find(d)!=tus.end()){
     
153.          return -1;
     
154.     }
     
155.     ls.insert(d);
     
156. #endif
     
157.     int i;
     
158.     for(i=0;i<ds.size();++i){
     
159.         if(ds[i]==d)return -1;
     
160.         dtype u=d|ds[i];
     
161.         if(tus.find(u)!=tus.end()){
     
162.             return -1;
     
163.         }
     
164.         if(ls.find(u)!=ls.end()){
     
165.            return -1;
     
166.         }
     
167.         ls.insert(u);
     
168.     }
     
169.     return 0;
     
170. }
     
171. 
     
172. int bitcount(dtype d){
     
173.     int i,b=0;
     
174.     for(i=0;i<K;i++){
     
175.        if(d&(1<<i))b++;
     
176.     }
     
177.     return b;
     
178. }
     
179. 
     
180. void do_add(dtype d){
     
181.     int i;
     
182. #ifdef STRICT
     
183.     tus.insert(d);
     
184. #endif
     
185.     for(i=0;i<ds.size();++i){
     
186.         dtype u=d|ds[i];
     
187.         tus.insert(u);
     
188.     }
     
189.     ds.push_back(d);
     
190. }
     
191. 
     
192. void pop()
     
193. {
     
194.    int i;
     
195.    dtype d=ds.back();
     
196.    ds.pop_back();
     
197. #ifdef STRICT
     
198.    tus.erase(d);
     
199. #endif
     
200.    for(i=0;i<ds.size();++i){
     
201.        dtype u=d|ds[i];
     
202.        tus.erase(u);
     
203.    }
     
204. }
     
205. 
     
206. int cds;
     
207. unsigned long long cdc;
     
208. unsigned long long cdi;
     
209. void dumpg(const DataState& data)
     
210. {
     
211.     int i;
     
212.     printf("[%d]",(int)data.size());
     
213.     for(i=0;i<data.size();i++){
     
214.        printf("%x ",data[i]);
     
215.     }
     
216.     printf("\n");
     
217.     fflush(stdout);
     
218. }
     
219. 
     
220. unsigned getrande(int e)
     
221. {
     
222.     unsigned d=0;
     
223.     rdrand_get_n_32(1,&d);
     
224.     d%=e;
     
225.     return d;
     
226. }
     
227. 
     
228. void rsearch(int s)
     
229. {
     
230.     int i;
     
231.     while(1){
     
232.        for(i=0;i<100;i++){
     
233.            unsigned d = gen_rand_edge();
     
234.            if(test_add(d)==0){
     
235.                do_add(d);
     
236.                break;
     
237.            }
     
238.        }
     
239.        if(i==100){
     
240.           return;
     
241.        }
     
242.     }
     
243. }
     
244. 
     
245. int search(int c, clock_t quit_time)
     
246. {
     
247.     int i,j;
     
248.     if(ds.size()>best_result.size()){
     
249.         best_result = ds;
     
250.         dumpg(best_result);
     
251.         return 1;
     
252.     }
     
253.     if(clock()>quit_time)return -1;
     
254.    
     
255.     for(i=1;i<c;++i){
     
256.        unsigned d = gen_rand_edge();
     
257.        if(test_add(d)==0){
     
258.            do_add(d);
     
259.            int r = search(2*c, quit_time);
     
260.            if(r!=0){
     
261.                pop();
     
262.                return r;
     
263.            }
     
264.            pop();
     
265.        }
     
266.     }
     
267.     return 0;
     
268. }
     
269. 
     
270. int largest_bit(long v)
     
271. {
     
272.     int i;
     
273.     for(i=31;i>=0;i--){
     
274.        if(v&(1<<i))return i;
     
275.     }
     
276.     return -1;
     
277. }
     
278. 
     
279. int count = 0;
     
280. #if K==28
     
281. #define MIN_TIME (5*CLOCKS_PER_SEC)
     
282. #else
     
283. #define MIN_TIME (30*CLOCKS_PER_SEC)
     
284. #endif
     
285. int cur_time_interval=MIN_TIME;
     
286. 
     
287. int main(int argc, const char *argv[])
     
288. {
     
289.     int i;
     
290.     int orbits[UPBOUND];
     
291.     if(argc>1){
     
292.         init();
     
293.         int bits=0;
     
294.         for(i=1;i<argc;i++){
     
295.             char *endp=NULL;
     
296.             long v=strtol(argv[i],&endp, 16);
     
297.             int lbits=largest_bit(v);
     
298.             if(lbits>bits)bits=lbits;
     
299.         }
     
300.         for(i=1;i<argc;i++){
     
301.             char *endp=NULL;
     
302.             long v=strtol(argv[i],&endp, 16);
     
303.             v=update_bits(v,bits);
     
304.             if(test_add(v)==0){
     
305.                 do_add(v);
     
306.             }else{
     
307.                 printf("invalid input %s\n",argv[i]);
     
308.                 return -1;
     
309.             }
     
310.         }
     
311.     }else{
     
312.         do{
     
313.             init();
     
314.             rsearch(1);
     
315.         }while(ds.size()<MIN_EDGES);
     
316.     }
     
317.     fprintf(stderr,"Init state:\n");
     
318.     dumpg(ds);
     
319.     for(i=0;i<ds.size();i++){
     
320.         best_result.push_back(ds[i]);
     
321.     }
     
322.     do{
     
323.         int replace_num = REPLACE_NUMS;
     
324.         for(i=0;i<best_result.size();i++)orbits[i]=0;
     
325.         for(i=0;i<replace_num;i++)orbits[i]=1;
     
326.         for(i=0;i<replace_num;i++){
     
327.               int j=getrande(best_result.size());
     
328.               int t=orbits[i];
     
329.               orbits[i]=orbits[j];
     
330.               orbits[j]=t;
     
331.         }
     
332.         init();
     
333.         for(i=0;i<best_result.size();i++){
     
334.               if(orbits[i]==0){
     
335.                    do_add(best_result[i]);
     
336.               }
     
337.         }
     
338.         if(search(200, clock()+cur_time_interval)==1){count=0;cur_time_interval = MIN_TIME;}else{cur_time_interval+=MIN_TIME;}
     
339.     }while(1);
     
340.     return 0;
     
341. }
     

复制代码

小铃铛

mathe 发表于 2018-3-23 13:33
29人[1184]11a1009c 908c904 1418d8 5989301 4455561 1001e628 54960c 18160480 10817924 10ea1429 242443e ...

谢谢分享！。经检测，700336个结果都是唯一的，辛苦，期待28的1000的突破

mathe

mathe 发表于 2018-3-23 15:11
最新的代码

没关系，参数s现在不用了，忘了删除了，rsearch就是随机搜索一个不差得离谱的解即可。
开始可以没有任何参数，也可以将我上面的一些结果作为输入，去掉前面的 [数目] 即可

mathe

比如K=28时（28个人），程序名字为evolution,可以直接运行
./evolution
也可以从一个973瓶酒的解开始
./evolution e0111a0 3451018 4189126 18302d 213a550 485a520 12d2ac0 32606e1 9245e02 23d8441 17c2811 c821512 53204a3 aa5025 5021198 1284852 82216d0 129481c 9100d1e a92609 95ca00c 8ba6400 9008ec8 6a3218 113 9a644 c40e600 2b51c0 710404a a0ee0c 1561402 503b0b0 6840433 61428c2 a6041a9 107664 a203924 8862988 c3c0904 26a544 1080ec5 c1c0201 a080d38 980c83c 48c594 54264d0 589816 1c12108 1042310 10888cb 62c424c 4e500c5 124408a 8508403 a120e07 8766202 b050501 45181e4 449310a 3041506 ac620c4 207287 80148a 5114028 6c8000e 5a10c03 9016066 8142645 1401870 4151008 1a48c11 1007498 240a602 717408c 2640039 2c51242 8421421 c40428d 50a1c4e 5c2017a 4236c0a 4980c40 182303a 640d948 34413a 20819ca 5508074 862c816 c48004b 7061206 8023352 3f00581 982038d 11120f0 e210c05 7880608 b30d100 10b0482 4d1c06 9278081 d142189 958846 e6c0e f808b c638260 14d01ca 1ba902 2f2460 804c4a2 a154043 dc0410a c225509 5e0443 914c884 f042013 7033400 70c9220 5229809 e82428 ec186a0 7055044 158d00b 2780388 10e024f a402b08 92024a8 875282 384b4e0 3001603 434b2 ac00196 a1c4406 80b8246 204c94b 250ca05 2c421a8 95d0450 d29628 23a20a 8d48114 8d013c 4280b32 1113d1 9500866 41c2094 9815630 81c948 a00a91 8218591 c0a4411 c00b712 7462142 1604429 d404831 ca10086 1941c14 f94008a 3411c5 2823444 4e006d0 b110c8a 3881852 3207250 d104b1 51b0045 c0c3a03 c80888a 5608e0 250e0a1 88848a3 408b834 6202855 8ac8a80 c8c10c2 8062c2 2909c42 1875051 417840a 40b228d ab02451 8005110 e2055c4 a5d1540 4602534 1b0514a 5c83b 9486520 2630891 2a84190 4a20d4 3812e0 3065301 b845092 4c68026 41e4124 52e60c0 6164830 98e4300 8cd2803 8448a60 b4570 6805c03 832921 b6024c 4195401 891087 6502503 60f1800 2051cc1 9092e08 20860b8 414e411 893c12 6290207 160b908 8c4232 a002cc0 8a41424 808e909 c011219 2d2306 8189ac0 24c01b4 5220b9 2984702 52a3280 18300d9 2017442 8683620 e64d000 a142854 1a45a6 692215 901b811 a6900d1 2924988 110a0e b0c9c00 a218402 ce04860 1470228 242022b 8a84324 d8a6802 206048f 49f00c0 690e1 9a42440 888177 a11004c 8f1001a c24922a 2049f9 151652 b92c24 c06f90 a0d0a51 e00b43 3904144 803c380 8b182 241a68 a43c802 404a2b8 9902a00 840cdd 24488ae 1490780 a4c08c 8ec046 468c211 2d0ab01 8320391 40000 c225802 4202c42 3e101c 290e414 2b61320 1003524 6329420 4623820 8010643 1d14311 89814b0 4094144 484a4d 1121d80 320cc10 60800e1 98c0905 5582250 4454928 1cd2060 7c08819 335130 123d002 2246821 284a890 a27900 8411a83 4310550 2704424 a2708c 110018f 6820304 a234008 28a8cc8 461a88 2020874 d8a1240 8124185 6a5a00 80829d2 9364140 8910885 303c90 8990a28 2e02d05 48e2118 8828561 6450209 1a9043 4a06016 5012d54 90f1084 c4104a8 a086a22 6c01425 4012296 40c82d9 6122181 3c04600 8043450 cf02048 5a1d4 83804d8 5208786 7089844 40c4883 6003695 4c42c24 a2210a2 102277 429ac80 8213845 52c1c8 9030e44 3421123 8128059 80082f8 28a1510 15052c8 c6c912 a452c12 21246e4 c880b9 d920500 4400965 4e30c10 4840454 9e032 956380 4044c5a 902a10e 1750002 170819 c01a083 36010cc 1d82084 2803023 4a04cb0 8440684 1154b02 8a8a60 6258888 803142a 881a2a4 11c0da d1a45 abe0108 208a426 f18a009 fe00520 152d030 864c049 4402e11 c149280 180d280 be20880 1126a08 dc90010 10552b b608608 6914130 d004359 4f08004 105c500 e130460 d010c5 1900530 d152805 40a30d9 a6f0202 8510702 1860e01 d144130 4810274 964b0a0 27e30 20390c0 1017ca 40642a9 d2b100 8c9098 e0c50b0 926a012 466214 9500b40 44d146 16e2202 94a0460 2523e00 c104880 1894514 a0e6040 b800062 82e2405 1a23b4 ec840a0 44156c 9810916 16400b4 5910142 40361a0 6134290 6209140 1c87404 cc9a41 3d4005a 91912c 82c51a2 871748 498842d a2509a0 8208396 3854b a200a9 a912020 62a7004 4039116 44c9109 905041a 1430485 169148 1514cc0 bb64800 6616028 805ce0 4960807 8a40692 1246445 43c8818 31c0aa0 b280214 d08c006 6940216 1038033 9862248 4144781 5006a14 4520244 b1200b2 41064a8 4dca208 b4a8801 a416015 c44103c 4042aa 94241a0 1211a92 2d480c0 b20934 20c4e10 d030125 170810a 8014c2e 3328821 405206a 6350182 9482aa 424540a 5285230 10aa028 8503610 21c0488 2a04107 20084c6 4c24488 d0402ca 6815022 82807 e270210 c140a1c 501c043 6402e62 1790a20 3224522 c185050 4161b01 940a30 a0062c9 810d805 c238901 5402221 8d80640 139b048 680089c d810481 824f201 2882586 84a0d15 bbc0 1184698 103e401 6d45808 4e30203 304f019 b50110c 10c21a5 a48c468 8160328 20b2340 b8901c0 4c90a80 3818c04 c09411 18fa800 12c0469 380600e 470950 180182f 4803151 201164d 18e241 8130372 3990061 e809408 4661660 5b0348 a40007e a48a01a 6410d00 4a81128 811d414 6b01083 33c 184c189 afb 78c448 259d 4412449 57b1 a1208e1 314321 4448350 6b2d d60d 5340207 f05c 6c88a4 f1e3 5212618 15ec6 3d00230 83504c1 1853a 1384404 1ce34 1e352 255ec 27b1040 4c0a102 28e8b 2c5d2 101e7 2224309 778110 288a7 868818c 5160c50 168e1 cd11006 8a01948 2e64444 1ba8080 32c5a 34ab2 3650c 2ab8100 eb080a 1948490 aa40a25 2aa11 4906606 3f920 6a08013 5868c 401305 18601d2 61d38 2372201 67013 1034da8 14a9940 312a480 c806421 8b0b020 68434 1f289 4683041 c116418 9c0c901 718b1 81c59 4564518 5108633 206c642 8ec81 2268092 8309123 97166 b100478 31b509 8400b1f a16a4 b46064 a5923 a6648 ac12d 50019b1 c1467 9c11a0 c0a0022 760a802 704813 1287c1 c0a31c 134446 92908a5 2289c88 70a0456 a921103 14358c 14620e 8858164 14f107 805a406 15ba10 160cc6 18067a 4580131 188b18 e6980 6c66020 1abc20 f202602 1d10d4 1d2431 1ea20d 20130e c844018 59131 e0e882 7084182 a287080 7c805 c5b0c d229c 12ab24 111e840 e50488 1304bc 15a029 1d8304 2010b5 334800c 9700432 430c129 291a112 10ee8 7388202 6301b10 b4303 c815e ce008c 255a420 1620154 201c4f 3c282a0 5301a2 2981047 2217110 20a8e5 46a8844 20cda4 218251 da05001 21e468 222224 227461 1673000 22845e c644005 22c495 a815284 2194230 240d89 c74611 243701 22c2158 259883 275107 680a068 74490 2321216 1808b42 cf4c2 1a6c8a0 146c23 18619a 188721 1d402a 248ad4 280ca2 28c020 a5a2802 4a40241 2a1452 d84109 2e0231 8818418 4416360 2a53081 17c1300 f101085 ea90024 d210328 188a014 90d4800 48328c4 5518c08 a8a0441 50150d2 cc8500 6920621 9209b81 3c0d014 90301e8 4419603 2416580 b50941 9000055 d91a104 270a015 12a0b01 a092089 d20c460 e0e8908 2f4900a 2cd0054 a80a025 1458045 c30002c 849d080 c6001a2 1d98022 56012a8 3642482 130340a 1412b24 2409052 2423910 2240742 30302c8 e00410c 2165082 168c242 72d0030 1125245 6192200 4a0c445 1681183 78120ac 1330258 e108924 4684d02 c021a24 5704200 2b89014 a090c0b c407044 6020843 2484422 2e81821 3350d00 4f05502 a02e430 444849c 304e380 4192b0 94a80aa a42b0a 5281c28 80d04a6 6040985 81828a4 9203a34 528e841 1941208 e844b00 465c090 5c40602 d482304 91a1800 8a30113 318620 a04320c 2061135 7913002 2204a84 25e9004 e0a0258 8503009 e142524 9600c4c c790080 5812015 1423a46 d2200d1 3a11300 1024626 5087101 505f00 526081a 6981104 8c24503 6083d80 c9a081 8802819 641b004 a0a02a 34cc101 8890252 c16886 3148241 8450848 aca0290 4815b10 91ad80 1ca4220 bc6201 58a3520 9024cb 6018030 5004417 e06095 886060a 8c21944 2015829 5109542 c8d800c 1a60168 925014 30281e9 60a82c4 64a59 1019262 b31a04 5803812 492ca00 2c00a49 8c60032 643080d 2660d14 4005476 886100d 2180315 1a10939 28a200b 30c8042 2842b24 53c084 8095049 4888985 6c10d2 da98042 680d180 300ca28 11d5440 6020e80 c00c72 c01c4d0 e068221 7008a90 2604058 350f040 11c0d08 508928 e09064 c902878 9621604 7cc3000 3000aae 8546060 b024213 60c570 6630141 7400545 830c218 b831004 4d52a20 2430234 2302560 9438602 d042620 a112318 e401811 409091b 404614d a022382 142202f 3034912 8048147 58108aa c402190 2899221 818c091 590a041 1d32440 2126052 8306d02 8b0218a 3422432 94d060 9118890 8704146 a908310 1504998 2645841 a8204a4 102ac8c 447a080 6888490 ad34001 24b1026 e88c840 2111079 3202a09 8c1a440 3ca5009 652862 2195108 da4062 601c085 4231348 9002a86 b203842 104d803 8c88930 21b2885 280486c b28a401

mathe

考虑到K太大时由于考虑到性能，我们总是只能随机添加数据，必然会有很多遗漏数据没有被使用的
所以我试着将K=28的一个解再依次顺序添加所有可以加进去的集合，结果一下子就超过了1024，所以28个人已经足够检测1024瓶以上的毒酒了
不过一趟完整的扫描也至少需要一个小时，我们还是再等等看最终结果是多少，难道还要考虑27个人？

mathe

28个人一下子增加到
[1260]e0111a0 321a188 3451018 4189126 18302d 213a550 485a520 12d2ac0 32606e1 9245e02 23d8441 17c2811 c821512 53204a3 aa5025 5021198 1284852 82216d0 129481c 9100d1e a92609 95ca00c 8ba6400 9008ec8 6a3218 113 9a644 c40e600 2b51c0 710404a a0ee0c 503b0b0 6840433 61428c2 a6041a9 107664 a203924 8862988 c3c0904 26a544 1080ec5 c1c0201 a080d38 980c83c 48c594 54264d0 589816 1c12108 1042310 10888cb 62c424c 4e500c5 124408a 8508403 a120e07 8766202 b050501 45181e4 449310a 3041506 ac620c4 207287 80148a 5114028 6c8000e 5a10c03 9016066 8142645 1401870 4151008 1a48c11 1007498 240a602 717408c 2640039 2c51242 8421421 c40428d 50a1c4e 5c2017a 4236c0a 4980c40 182303a 640d948 34413a 20819ca 5508074 862c816 e21394 c48004b 7061206 8023352 3f00581 982038d 11120f0 e210c05 b30d100 10b0482 4d1c06 9278081 d142189 958846 e6c0e f808b c638260 14d01ca 1ba902 2f2460 804c4a2 a154043 dc0410a c225509 5e0443 914c884 f042013 7033400 70c9220 5229809 e82428 ec186a0 7055044 158d00b 2780388 10e024f a402b08 92024a8 875282 384b4e0 3001603 434b2 ac00196 a1c4406 80b8246 204c94b 250ca05 2c421a8 95d0450 d29628 23a20a 8d48114 8d013c 4280b32 1113d1 9500866 41c2094 9815630 81c948 a00a91 8218591 c0a4411 c00b712 1604429 ca10086 1941c14 f94008a 3411c5 2823444 4e006d0 b110c8a 3881852 3207250 d104b1 51b0045 c0c3a03 c80888a 5608e0 250e0a1 88848a3 408b834 6202855 8ac8a80 c8c10c2 8062c2 2909c42 1875051 417840a 40b228d ab02451 8005110 e2055c4 a5d1540 4602534 1b0514a 5c83b 9486520 2630891 2a84190 4a20d4 3812e0 3065301 b845092 4c68026 41e4124 52e60c0 6164830 98e4300 8cd2803 8448a60 b4570 6805c03 832921 b6024c 4195401 891087 6502503 60f1800 2051cc1 9092e08 20860b8 414e411 893c12 6290207 160b908 8c4232 a002cc0 8a41424 808e909 c011219 2d2306 8189ac0 24c01b4 5220b9 2984702 52a3280 18300d9 2017442 8683620 e64d000 a142854 1a45a6 692215 901b811 a6900d1 2924988 110a0e b0c9c00 a218402 ce04860 1470228 242022b 8a84324 d8a6802 206048f 49f00c0 690e1 9a42440 888177 a11004c 8f1001a c24922a 2049f9 151652 b92c24 c06f90 a0d0a51 3904144 803c380 8b182 241a68 a43c802 404a2b8 9902a00 840cdd 24488ae 1490780 a4c08c 8ec046 468c211 2d0ab01 8320391 40000 c225802 4202c42 3e101c 290e414 2b61320 1003524 6329420 4623820 8010643 1d14311 89814b0 4094144 484a4d 1121d80 320cc10 60800e1 98c0905 5582250 4454928 1cd2060 7c08819 335130 123d002 2246821 284a890 a27900 8411a83 4310550 2704424 110018f 6820304 a234008 28a8cc8 461a88 d8a1240 8124185 6a5a00 80829d2 9364140 8910885 303c90 2e02d05 48e2118 8828561 6450209 5108a48 1a9043 4a06016 5012d54 90f1084 c4104a8 a086a22 6c01425 4012296 40c82d9 6122181 3c04600 8043450 cf02048 5a1d4 83804d8 5208786 7089844 40c4883 6003695 4c42c24 a2210a2 102277 429ac80 8213845 52c1c8 9030e44 3421123 8128059 80082f8 28a1510 15052c8 c6c912 a452c12 21246e4 c880b9 d920500 4400965 4e30c10 4840454 9e032 4044c5a 902a10e 1750002 170819 c01a083 36010cc 1d82084 2803023 4a04cb0 8440684 1154b02 8a8a60 6258888 803142a 881a2a4 11c0da d1a45 abe0108 208a426 f18a009 152d030 864c049 4402e11 c149280 180d280 be20880 1126a08 28212e2 dc90010 10552b b608608 6914130 d004359 4f08004 105c500 e130460 d010c5 1900530 d152805 40a30d9 424a242 a6f0202 8510702 1860e01 4810274 964b0a0 27e30 20390c0 1017ca 40642a9 d2b100 8c9098 e0c50b0 926a012 466214 9500b40 44d146 16e2202 94a0460 2523e00 c104880 1894514 a0e6040 b800062 82e2405 1a23b4 ec840a0 44156c 9810916 16400b4 5910142 40361a0 6134290 6209140 1c87404 cc9a41 3d4005a 91912c 82c51a2 871748 498842d a2509a0 8208396 3854b a200a9 a912020 62a7004 4039116 44c9109 905041a 1430485 169148 1514cc0 bb64800 6616028 805ce0 4960807 8a40692 1246445 43c8818 31c0aa0 b280214 d08c006 6940216 1038033 9862248 4144781 5006a14 4520244 b1200b2 41064a8 4dca208 b4a8801 a416015 c44103c 4042aa 94241a0 1211a92 2d480c0 b20934 20c4e10 d030125 170810a 8014c2e 3328821 405206a 6350182 9482aa 424540a 5285230 10aa028 8503610 21c0488 2a04107 20084c6 4c24488 d0402ca 6815022 82807 e270210 c140a1c 501c043 6402e62 1790a20 3224522 c185050 4161b01 940a30 a0062c9 810d805 c238901 5402221 8d80640 139b048 680089c d810481 824f201 2882586 84a0d15 bbc0 1184698 103e401 6d45808 4e30203 304f019 b50110c 10c21a5 a48c468 8160328 20b2340 b8901c0 4c90a80 3818c04 c09411 18fa800 12c0469 380600e 470950 180182f 4803151 201164d 18e241 8130372 3990061 e809408 4661660 5b0348 a40007e a48a01a 6410d00 811d414 6b01083 33c 184c189 afb 78c448 259d 4412449 57b1 a1208e1 314321 4448350 6b2d d60d 5340207 f05c 6c88a4 41a8ca f1e3 5212618 15ec6 3d00230 83504c1 1853a 1384404 1ce34 1e352 255ec 27b1040 4c0a102 28e8b 2c5d2 101e7 2224309 778110 288a7 868818c 5160c50 168e1 cd11006 8a01948 2e64444 1ba8080 32c5a 34ab2 3650c 2ab8100 eb080a 1948490 aa40a25 2aa11 4906606 3f920 6a08013 5868c 401305 18601d2 61d38 2372201 67013 1034da8 14a9940 312a480 c806421 8b0b020 68434 1f289 4683041 c116418 9c0c901 718b1 81c59 4564518 5108633 206c642 8ec81 2268092 8309123 97166 b100478 31b509 8400b1f a16a4 b46064 a5923 a6648 ac12d 50019b1 c1467 9c11a0 c0a0022 760a802 704813 1287c1 132888 c0a31c 134446 92908a5 2289c88 70a0456 a921103 14358c 14620e 8858164 14f107 805a406 15ba10 160cc6 18067a 4580131 188b18 e6980 1abc20 f202602 1d10d4 1d2431 1ea20d 20130e c844018 59131 e0e882 7084182 a287080 7c805 c5b0c d229c 111e840 e50488 1304bc 15a029 1d8304 2010b5 334800c 9700432 430c129 291a112 10ee8 7388202 6301b10 b4303 c815e ce008c 255a420 1620154 201c4f 3c282a0 5301a2 2981047 2217110 20a8e5 46a8844 20cda4 218251 da05001 21e468 222224 227461 1673000 22845e c644005 22c495 a815284 2194230 240d89 c74611 243701 22c2158 259883 275107 680a068 74490 2321216 1808b42 cf4c2 1a6c8a0 146c23 18619a 188721 1d402a 248ad4 280ca2 28c020 a5a2802 4a40241 d84109 2e0231 8818418 4416360 2a53081 17c1300 f101085 ea90024 d210328 188a014 90d4800 48328c4 5518c08 a8a0441 50150d2 cc8500 6920621 9209b81 3c0d014 90301e8 4419603 2416580 b50941 9000055 d91a104 270a015 12a0b01 a092089 d20c460 e0e8908 2f4900a 2cd0054 a80a025 1458045 c30002c 849d080 c6001a2 1d98022 56012a8 3642482 130340a 1412b24 2409052 2423910 2240742 30302c8 e00410c 2165082 168c242 72d0030 1125245 6192200 4a0c445 1681183 78120ac e108924 4684d02 c021a24 5704200 2b89014 a090c0b c407044 6020843 2484422 3350d00 4f05502 a02e430 444849c 304e380 4192b0 94a80aa a42b0a 5281c28 80d04a6 6040985 81828a4 9203a34 528e841 1941208 e844b00 465c090 5c40602 d482304 91a1800 8a30113 318620 a04320c 2061135 7913002 2204a84 25e9004 e0a0258 8503009 e142524 9600c4c c790080 5812015 d2200d1 3a11300 1024626 5087101 505f00 526081a 6981104 8c24503 6083d80 c9a081 8802819 641b004 a0a02a 34cc101 8890252 c16886 3148241 8450848 aca0290 4815b10 1ca4220 bc6201 9024cb 6018030 5004417 e06095 886060a 8c21944 2015829 5109542 c8d800c 1a60168 925014 30281e9 60a82c4 1019262 b31a04 5803812 492ca00 2c00a49 8c60032 643080d 2660d14 4005476 886100d 2180315 1a10939 28a200b 30c8042 2842b24 53c084 8095049 4888985 6c10d2 da98042 680d180 300ca28 11d5440 6020e80 c00c72 c01c4d0 e068221 7008a90 2604058 350f040 11c0d08 508928 e09064 c902878 9621604 7cc3000 3000aae 8546060 b024213 60c570 6630141 7400545 830c218 b831004 4d52a20 2430234 2302560 9438602 d042620 a112318 e401811 409091b 404614d a022382 142202f 3034912 8048147 58108aa c402190 2899221 818c091 590a041 1d32440 2126052 8306d02 8b0218a 3422432 94d060 9118890 8704146 a908310 1504998 2645841 a8204a4 102ac8c 447a080 6888490 ad34001 24b1026 e88c840 2111079 3202a09 8c1a440 3ca5009 652862 2195108 da4062 601c085 13021d2 a741408 4003a0a 8c03c1 3a20010 c62c08 89009d0 10449c4 487302 88f988 52101c9 5019f00 8848cc 908148d 3063218 14e0919 9c15042 6007628 6c28121 b226a0 4489660 a4411c0 2302086 58a4814 39be 9e38 22578 2936c 2ba06 45992 47174 4984d 64a59 78c68 99da0 a3d45 ac951 b0c14 b4055 100be4 10ac1d 112f40 1152a6 124d01 1ac412 2023ea 2130ac 21469a 215b41 22491c 230784 24cb00 25290d 254870 2826b0 29901b 30083f 320a22 34d202 350c16 38016b 3c1c03 3c284a 3f6100 400fa3 411592 41181c 425c0a 4270a4 42a507 42c25a 439a42 4422cb 442551 44a217 453380 498921 4a2709 4a4838 4c04f8 4c6029 580b22 5c0c25 6044c3 6078c4 61600e 620292 62a1c1 631029 680446 709a0c 712a09 722984 7e0604 803269 8086b7 80c612 810715 83218e 84e251 85620d 88d528 8eb401 905658 922312 92420b a09c21 a1f050 a38843 a52130 a8141c a82962 aa0a86 aa4250 aa4c81 aca192 c0164e c28e84 c58782 c940f0 d1e200 d4040d d85211 e101c2 e45204 100a9b0 1013143 1017225 101c24c 102388b 1024176 104d803 10502b3 108103e 10c1744 10e1410 10fa250 1181282 11e2832 1209138 124a026 12805f0 130a289 1344011 140ac61 141c618 1444a91 1456602 148a2c8 1512216 178a120 18d1821 1937080 19400e3 198a505 1a051a0 1a11444 1a38308 1c41e80 1d25801 1e08984 201821b 2031720 20348d4 2050e92 205298a 20a1093 20a4168 20d284c 211c824 21d2103 2249274 2285411 23080e8 242a82c 2485930 24a0a16 2622245 262d400 268a940 26e2081 2813848 2814451 28407e0 284a509 29008b6 2936c00 2a32422 2c4c118 2c81328 3022a60 3058960 309002c 3111494 3191205 32404d8 34040e4 348241c 38028c5 4001d2c 4020bc8 40312a3 4054e05 40632c4 40a8588 40c0712 40c2548 40edc00 4120196 412a2e2 41b0852 42040ee 4233011 43006c9 43a400b 44300ca 4463504 450d08a 4511ca0 458148c 4594206 48441a2 4868809 4881622 4900b23 4a0b290 4ac3020 4c7100c 4f11801 500e309 5010b84 5050134 5380522 5409c22 54c0c90 5611824 58006cc 5822c20 598c8a0 5a44510 6280409 6344c40 640238e 6446804 6780860 6821698 6984019 7222148 7580901 7a50048 7b00824 80414b9 804614a 80710d8 8116186 8141da0 8153102 817c210 8201516 822e844 8281a0d 8286213 82c8130 83322c0 840ba21 850d320 8651810 86c4c00 880c261 8871802 8924831 8988002 89900e8 8a14a06 8ca8148 8e83042 9048b0e 9088524 9125068 9229449 9400e25 9480293 9941822 9d18841 a099910 a20d224 a594012 ac21068 b019082 b028700 b180c11 b203046 bd00203 c00a549 c093430 c148c01 c24a580 c5600a1 c62a008 c822066 cd01130 ce00309 d109604 e002705 e0502c4 e12b010 e568002 f008152 f014821

mathe

现在基本上27人可以解决1000人应该没有悬念了，可以看出我们方法离最优解还是挺远的，现在的问题在于我们到底可以找到多少人
也许再找到一个不错的解以后，可以先将所有可以添加到当前解里面的单个集合都找出来，然后穷举(或如果复杂度太高可以随机选取)它们最多有多少个集合可以一起添加进去会有一个不错的解，我现在工作的机器网络断开了，暂时就先到此为止

小铃铛

以1024桶酒为基准，求出极限的最少囚徒人数，太令人振奋了，mathe,加油

王守恩

mathe 发表于 2018-3-23 19:25
现在基本上27人可以解决1000人应该没有悬念了，可以看出我们方法离最优解还是挺远的，现在的问题在于我们到 ...

     \(1\)瓶毒酒。在\(0——2^n\)的整数中，找一串数：使这串数中的每\(1\)个数，都不相同。
这串数是\(0，1，2，3，4，5，6，......\)
     \(2\)瓶毒酒。在\(0——2^n\)的整数中，找一串数：使这串数中的每\(2\)个数相加，和都不相同。
这串数是\(......\)
     \(3\)瓶毒酒。在\(0——2^n\)的整数中，找一串数：使这串数中的每\(3\)个数相加，和都不相同。
这串数是\(......\)
     \(4\)瓶毒酒。在\(0——2^n\)的整数中，找一串数：使这串数中的每\(4\)个数相加，和都不相同。
这串数是\(......\)

mathe

26个人现在只能找到769瓶毒酒，基本进入瓶颈了，所以突破1000可能性不大，但是27个人已经进化到989人了，突破目标问题不大。
下面是26人现在找到的答案
[769]41aaa0 3000908 550b2 5282ae 37280a e82750 8a8749 f80625 bc4043 cb0d11 212aa13 240ba09 21a040e 1611685 2092430 8e88aa 34cb000 2323042 760404 4d1a05 22c1262 d02905 2802172 1202b00 d01f5 66720c 17010a9 a3d100 2929022 946111 3818492 2b91cc0 2a08a4a 15820c1 285c8c1 1260d18 120a242 c10354 31622a 20656c2 2170a1c 243024 321549 3285300 394a044 24954a0 3032428 2c03059 2c68201 103e098 10d511c 2904621 3289a50 820a9e 41c143 3549228 288b990 2226180 689c42 3420d03 c4b2c 1463681 91d207 3c04690 50c51d 50a234 a0a692 206f60 243918a 1b20590 100e132 649301 22a2823 b34118 88a216 c24189 1539d0 3310152 93a414 174450 2475802 3b30640 3261212 b18901 1405b0e 112529a 152644 1c09110 2138c38 104b059 c02ec0 25504e5 434685 1060a56 1001006 1202d1 2292240 9d810c 1c60950 11c0994 380a1a4 683122 1010135 1406d41 c03433 c15211 20113e2 8129d8 3742a10 2c85804 310b0c 1480b62 ca2622 1d28c2 890863 1822827 2058158 6c4b4 34c0489 114d016 2a28226 111a00b 24e0d08 83b082 147aa4 2619602 698f10 44026c 342a60 1331380 242685 1116854 13f0041 28c1846 c2a028 298233 1902a8a 7500c8 3e00462 2a111 a3461 48529 11a1854 1304a2 e33044 1017a12 1826a40 1a1204f 58a6c0 c50886 d6608 678170 260c240 484a03 c295a0 34880c8 115382 3021370 3b40428 200c02c 14b2248 2948112 30039a1 61d802 24aa844 cd200c 18c8350 f8840 84a926 d91030 9300c3 11c1511 c2a47 48402d 82b698 2098204 101a7a 130e8c0 a09b20 990544 238c04 456904 2872129 71c00c 4004a6 254488c 140824d 1db000 2b80123 1507920 58a80a 20084e9 8f0052 11e7600 2a2208a 407871 1202ea8 34810b0 a85286 c28c05 1c5828 24a22a4 14a1023 202005f 249005c 160c968 174823 18402a1 2051221 992a14 a68841 21036b0 e9a002 928246 2478a24 3c0000b 3054041 1029941 2d28308 e06e4 924072 62b09 1a8a4c0 2a0680e 2406187 1300163 72c89 1051494 ca520b 112d80c 19e1a10 180209 368412 14aa7 18097 2f000c3 1470861 4d3820 31089b 1100230 108074c 7009f4 2408527 1a83841 9b822c 3050956 38c8024 1915822 10e918 121b600 1027219 1a10631 3840e30 712311 961902 18c2b2 4d2141 1926205 1344188 ed4010 558047 10488e2 2ca502 a03580 2488292 cec890 fc1080 20c0183 20241f9 10d0472 1279044 8f70 622639 2065a10 244445 1010a5 2388c02 551700 12c4550 7a00e6 170d007 32442b2 1063832 2093e84 202b514 c8e304 1131425 2a101a8 100a8ec 309a81 17015c2 1853418 e30a7 1160700 4094c4 1600648 104a72a 2220870 2660881 10b4162 138084c 1024459 3020327 a80d09 211a041 640e0d 1224308 538260 86440c 2084879 290bc00 450c11 296a480 20d9491 1d85408 821313 10ac207 1801666 3e50080 120490d 1246013 180188d 10a1868 308c042 2814102 2048c10 21052d8 da0098 32080a6 10060f1 14c0271 1588491 2b0246 261451 e0603 2ca811 d254a 29b882 183005c 280c037 481147 3d04240 8de00 2488cf0 60638 28a290c 2981892 34a1601 2214c82 15c400c 104d2c0 1731a1 2185c40 88c0e1 4948a 1744c10 3320009 d10419 185406b 280c5c8 207956 151c74 2201174 21c0f10 e20142 2484461 1847220 3805482 250c0d4 6b3009 3420064 124003f 324962 4ec001 2a14209 1044345 1c04035 2301650 42c872 10a30ca a40326 2521094 391d008 3b4a00 250202b 44259c 3042484 1550e22 2114aa0 a89424 6218c8 189da0 1232086 2f20411 4c1058 10565a0 2126d8 4352c0 21c2421 2a83818 284809c 1009f82 1101c33 2a44d0 12702e0 3646098 28524c 2826049 3821c04 181b41 138a026 7d8202 2c909a1 b78024 122c521 3520848 262070c 2288700 1c82c06 280b340 5c17 24c826 80c328 1894984 1583302 da4044 b421c 2260cac 128c09 a024a9 1d401c4 1a68200 10000 259e28 20ad820 14f300 2118322 2398298 2441390 1043168 20be810 1622034 40720a 2846080 16a4084 cb94 2412295 18b5024 90d581 460117 1424e04 2831238 1f30c00 42332c 18c3070 9f060 9e8408 148301e 88b125 2c5a210 2142803 538980 106435 2c8008d 3110688 504d02 2690405 61041e 102838a 38cc60 1244606 30b8c08 424130 1209e8 4d851 1d62018 148a508 11b2902 14b010e 853e0 2a01688 110805a 2461c20 628c5 1b208d 1039214 210434c 3aa0130 94529 a04a12 220541a 8360c0 8c8e80 321a903 c0d61 10c0a8a 184685 2034c05 2313886 1c4181c 1a28148 114420b 2881a1 1d99 12a8902 2002a26 2c10cd 468b9 843d2a 13942c0 262852 114280d 1e021a5 1ae4081 2e08834 1514191 312a0b1 351930 1261e5 20c46a8 2109546 32c384 268811a 17c48 1503249 3c702 958281 5c2492 2240a15 a908b0 2c5c80 205e421 e18098 3340124 87c00f 2882619 8902e8 532412 49238a 2996820 2830ce8 30491a8 b14460 21334a 2f2110 2131901 5a1053 81aa31 871648 817524 28a13c0 1c344c 1084891 9030d4 e80a60 9023a0 2888945 e002c4 2618184 c8c219 7d08c 288157 2e01d40 a2220c 2645029 22c650c 983d c0d05c 101cd0a d80c48 1ac2e 3c99014 38090d1 2562268 a3c16 20a81f4 10829d2 14040d7 1108534 590c84 128587 480656 9103e 380cc01 396409 1a22890 2729800 2511581 282944a 22e4048 2428613 2486150 2c61012 2b14034 222828d 4807c1 2001ad3 14a28a0 2c00c2c a048ec 1427005 16d0500 8c5462 2900951 d21470 781918 1298928 4455e0 805e54 b0006d 318e208 2018e61 2c90e02 204820f 2174024 720121 8824b4 386d0 189a201 10a2690 b25c20 4a9891 642146 c621a2 108e054 3c16c00 214c483 206b80a 821e81 101a264 a00359 2b32281 1146192 134a401 2430540 1906450 466251 412132 283b84 281906c 10780a6 3780204 c76801 120f028 3250403 1a11052 3c41141 20cd309 21d10e0 1c48402 11504b 10351e 1980002 a9b08 b5103 80e40d 3a30a02 574608 240c4e 58906c 7019b 3584901 190114c 1201c54 2a846a 1285821 26584a0 84485a 38240d4 205191 140c4b8 5d4812 184ca08 14400fa 2b60a8 90a870 a43ac0 21038a8 18a0c51 d9544 62d281 20a8886 20a0c35 1cb8181 3e1104 4c262 146c104 2606534 780817 3c20216 1200ccb 824ea2 219019 2224016 89ab 919150 184e0aa 164a980 1c16086 44b152 22f06 2387030 f2a050 acc421 44dc4 3002a78 616890 54112a 3a54900 3002701 208908f 30e7044 22442f 52600e 33605 1013550 891c08 1720312 348da 30d6025 1d00496 d08703 1410f09 186642 121cd 81090f 190c906 3472100 258007a 110708c 2f422 28a0a69 18ca109 1c59801 296844 e4c064 60a06b 34a08c 1a118b 1089443 1c851c0 225201d 8d1306 1e0300a 1910303 d3c0a0 a0a11c 6142e1 e46230 24130c0 c6d03 21420da 240c949 230d484 4b286 39a0081 1410c46 2114538 2241992 442c70 3341045 2850614 16c2220 884516 14111a0 149115 be124 329108a 22203e1