毒酒问题(加强版)

mathe

1. #include <vector>
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. #include <rdrand.h>
   
6. 
   
7. typedef unsigned int dtype;
   
8. typedef std::vector<dtype> DataState;
   
9. #ifndef K
   
10. #define K 10
    
11. #endif
    
12. #if K==10
    
13. #define HK 5
    
14. #define UPBOUND 30
    
15. #define REPLACE_NUMS 5
    
16. #endif
    
17. #if K==11
    
18. #define HK 5
    
19. #define UPBOUND 60
    
20. #define REPLACE_NUMS 5
    
21. #endif
    
22. #if K==12
    
23. #define HK 6
    
24. #define UPBOUND 70
    
25. #define REPLACE_NUMS 5
    
26. #endif
    
27. #if K==13
    
28. #define HK 6
    
29. #define UPBOUND 100
    
30. #define REPLACE_NUMS 6
    
31. #endif
    
32. #if K==14
    
33. #define HK 7
    
34. #define UPBOUND 200
    
35. #define REPLACE_NUMS 6
    
36. #endif
    
37. #if K==15
    
38. #define HK 7
    
39. #define UPBOUND 350
    
40. #define REPLACE_NUMS 6
    
41. #endif
    
42. #define MASK_SIZE (1<<(K-5))
    
43. #define MIN_EDGES (2*REPLACE_NUMS)
    
44. 
    
45. unsigned gen_rand_edge()
    
46. {
    
47.      unsigned d = 0;
    
48.      unsigned rd[K];
    
49.      int i;
    
50.      rdrand_get_n_32(K,rd);
    
51.      for(i=0;i<K;i++){
    
52.         if(rd[i]<1288490189){
    
53.             d|=1<<i;
    
54.         }
    
55.      }
    
56.      return d;
    
57. }
    
58. 
    
59. int should_we_change()
    
60. {
    
61.     unsigned d=0;
    
62.     rdrand_get_n_32(1,&d);
    
63.     d%=10;
    
64.     if(d==0)return 1;
    
65.     return 0;
    
66. }
    
67. 
    
68. unsigned int gmask[MASK_SIZE];
    
69. DataState ds;
    
70. DataState best_result;
    
71. #define WORD_OF(x)        ((x)>>5)
    
72. #define INDEX_IN_WORD(x)  ((x)&31)
    
73. #define IS_SET(mask,x)     (mask[WORD_OF(x)]&(1<<INDEX_IN_WORD(x)))
    
74. #define SET(mask,x)        (mask[WORD_OF(x)]|=1<<INDEX_IN_WORD(x))
    
75. #define CLEAR(mask,x)      (mask[WORD_OF(x)]&=~(1<<INDEX_IN_WORD(x)))
    
76. 
    
77. void init()
    
78. {
    
79.     ds.clear();
    
80.     memset(gmask,0,sizeof(gmask));
    
81. }
    
82. int bitcount(dtype d);
    
83. int test_add(dtype d)
    
84. {
    
85.     unsigned int lmask[MASK_SIZE];
    
86.     memset(lmask,0,sizeof(lmask));
    
87.     if(bitcount(d)>HK)return -1;
    
88. #ifdef STRICT
    
89.     IS_SET(d){
    
90.          return -1;
    
91.     }
    
92.     SET(lmask, d);
    
93. #endif
    
94.     int i;
    
95.     for(i=0;i<ds.size();++i){
    
96.         if(ds[i]==d)return -1;
    
97.         dtype u=d|ds[i];
    
98.         if(IS_SET(gmask, u)){
    
99.             return -1;
    
100.         }
     
101.         if(IS_SET(lmask, u)){
     
102.            return -1;
     
103.         }
     
104.         SET(lmask, u);
     
105.     }
     
106.     return 0;
     
107. }
     
108. 
     
109. int bitcount(dtype d){
     
110.     int i,b=0;
     
111.     for(i=0;i<K;i++){
     
112.        if(d&(1<<i))b++;
     
113.     }
     
114.     return b;
     
115. }
     
116. 
     
117. void do_add(dtype d){
     
118.     int i;
     
119. #ifdef STRICT
     
120.     SET(gmask, d);
     
121. #endif
     
122.     for(i=0;i<ds.size();++i){
     
123.         dtype u=d|ds[i];
     
124.         SET(gmask, u);
     
125.     }
     
126.     ds.push_back(d);
     
127. }
     
128. 
     
129. void pop()
     
130. {
     
131.    int i;
     
132.    dtype d=ds.back();
     
133. #ifdef STRICT
     
134.    CLEAR(gmask, d);
     
135. #endif
     
136.    ds.pop_back();
     
137.    for(i=0;i<ds.size();++i){
     
138.        dtype u=d|ds[i];
     
139.        CLEAR(gmask, u);
     
140.    }
     
141. }
     
142. 
     
143. int cds;
     
144. unsigned long long cdc;
     
145. unsigned long long cdi;
     
146. void dumpg(const DataState& data)
     
147. {
     
148.     int i;
     
149.     if(data.size()<=cds){
     
150.         cdc++;
     
151.     }else{
     
152.         cdi=10;
     
153.         cdc=10;
     
154.         cds=data.size();
     
155.     }
     
156.     if(cdi<=10){
     
157.         cdi=10;
     
158.     }
     
159.     if(cdc<cdi){
     
160.          return;
     
161.     }
     
162.     if(cdi<10000000000000LL){
     
163.        cdi*=2;
     
164.     }
     
165.     cdc=0;
     
166.     printf("[%d]",(int)data.size());
     
167.     for(i=0;i<data.size();i++){
     
168.        printf("%x ",data[i]);
     
169.     }
     
170.     printf("\n");
     
171.     fflush(stdout);
     
172. }
     
173. 
     
174. unsigned getrand(int s)
     
175. {
     
176.     unsigned d=0;
     
177.     rdrand_get_n_32(1,&d);
     
178.     d%=(1<<K)-s;
     
179.     d+=s;
     
180.     return d;
     
181. }
     
182. 
     
183. unsigned getrande(int e)
     
184. {
     
185.     unsigned d=0;
     
186.     rdrand_get_n_32(1,&d);
     
187.     d%=e;
     
188.     return d;
     
189. }
     
190. 
     
191. void rsearch(int s)
     
192. {
     
193.     int i;
     
194.     while(1){
     
195.        for(i=0;i<10;i++){
     
196.            unsigned d = gen_rand_edge();
     
197.            if(test_add(d)==0){
     
198.                do_add(d);
     
199.                break;
     
200.            }
     
201.        }
     
202.        if(i==10){
     
203.           unsigned d = getrand(s);
     
204.        for(i=d;i<(1<<K);++i){
     
205.            if(test_add(i)==0){
     
206.                 do_add(i);
     
207.                 break;
     
208.            }
     
209.        }
     
210.        if(i==(1<<K)){
     
211.           for(i=s;i<d;++i){
     
212.              if(test_add(i)==0){
     
213.                  do_add(i);
     
214.                  break;
     
215.              }
     
216.           }
     
217.           if(i==d){
     
218.              return;
     
219.           }
     
220.        }
     
221.        }
     
222.     }
     
223. }
     
224. 
     
225. void search()
     
226. {
     
227.     int i,j;
     
228.     if(ds.size()>best_result.size()){
     
229.         best_result = ds;
     
230.         dumpg(best_result);
     
231.     }else if(ds.size()==best_result.size()){
     
232.         if(should_we_change()){
     
233.             best_result = ds;
     
234.             dumpg(best_result);
     
235.         }
     
236.     }
     
237.     for(i=1;i<1<<K;++i){
     
238.        if(test_add(i)==0){
     
239.            do_add(i);
     
240.            search();
     
241.            pop();
     
242.        }
     
243.     }
     
244. }
     
245. 
     
246. int main(int argc, const char *argv[])
     
247. {
     
248.     int i;
     
249.     int orbits[UPBOUND];
     
250.     DataState ld;
     
251.     do{
     
252.         init();
     
253.         rsearch(1);
     
254.     }while(ds.size()<MIN_EDGES);
     
255.     fprintf(stderr,"Init state:\n");
     
256.     dumpg(ds);
     
257.     for(i=0;i<ds.size();i++){
     
258.         best_result.push_back(ds[i]);
     
259.     }
     
260.     do{
     
261.         for(i=0;i<best_result.size();i++)orbits[i]=0;
     
262.         for(i=0;i<REPLACE_NUMS;i++)orbits[i]=1;
     
263.         for(i=0;i<REPLACE_NUMS;i++){
     
264.               int j=getrande(best_result.size());
     
265.               int t=orbits[i];
     
266.               orbits[i]=orbits[j];
     
267.               orbits[j]=t;
     
268.         }
     
269.         init();
     
270.         for(i=0;i<best_result.size();i++){
     
271.               if(orbits[i]==0){
     
272.                    do_add(best_result[i]);
     
273.               }
     
274.         }
     
275.         search();
     
276.     }while(1);
     
277.     return 0;
     
278. }
     

复制代码

mathe

程序使用intel的rdrand指令产生随机数https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide
代码中宏K代表人数。
首先用函数rsearch随机产生一个不是太差的解，然后每次从当前解中随机淘汰掉REPLACE_NUMS瓶酒，然后穷举添加酒找更优的解，一直迭代下去，而如果产生一个同样好的解，会以一定概率替换原先的解(现在是1/10),不过里面各种参数不知道如何设置效果会最好。而同样的程序同时运行多个版本得出的结果也可能不尽相同。现在对于K=10,11,12的效果不错，但是13以上好像效果就不佳了。大家有空闲机时可以试着修改参数运行一下看，通常需要运行数小时才能看到效果

mathe

毒酒滴冻鸭 发表于 2014-11-20 16:40
请问64桶酒，其中两瓶有毒，16人能试出来吗？我只能想到17人的解法。。。

另外16桶酒，最少应该确定是9 ...

现在程序表明15人已经可以识别70桶酒了，其中两瓶有毒。
3093 1c8a 4913 2d80 7c1 6c08 2a48 2605 400 4a30 1624 1028 3141 2832 889 487 1918 139 e5 5290 c61 a2d 294a ce 489c 1619 44a8 5842 200b 1107 4a81 2728 700e a06 904 7114 450b 4360 e50 6805 4444 32a8 41d1 407a 164a 64c2 4c26 14d0 1255 4558 7b00 5c01 1436 5b4 6b0 388 6431 5049 4012 2506 2dc 2210 114c 5223 2263 38c4 3460 9a2 60a4 51a1
当然这估计还远远不是最优结果

mathe

13个人可以找到49瓶毒酒的结果:
10 1800 b04 a90 28c 381 2c2 d10 82c 854 125 509 146 831 461 72 81a 48a a3 4b 1330 1348 1264 16a0 1650 1e08 1702 1229 1a41 1a22 217 9e0 111c 1584 10b4 1438 10d8 144c 1151 112a 1192 1491 1c05 10c5 1889 1426 1886 1c42 1903
1 1800 107 a03 885 861 c9 c09 911 216 8e 24a 50a 924 b4 78 a30 1443 10a3 101b 1055 22d 1341 1581 1431 1291 1066 1c06 8d2 182a 1622 1382 1132 1a44 144c 11c4 181c 1684 1514 1948 1650 1560 12e0 1f00 1ca0 1a88 1498 1318 11a8
1 1800 807 40d 20b 891 a41 c9 c21 909 36 4e 486 924 d2 a12 1b0 168 155 10a5 1413 1063 1183 1039 1681 1321 1306 1294 181c 18c4 1464 1e04 122c 118c 111a 1642 1942 1522 8aa 1258 1870 1630 1d10 1498 12e0 1c48 15c0 1b80 1708
1 1800 909 885 191 861 a03 407 c11 6a 138 10e a0c f0 96 846 108b 1229 5d 14a1 12c1 1033 1125 1143 1701 10ac 18c8 1498 1388 1c28 181a 160a 1548 9a2 14c2 1a90 1684 11c4 1226 1834 1630 1464 1360 1512 1252 1e40 1d04 1950 1314
1 1800 981 c05 813 131 a21 849 443 96 88c 1a4 4e 21a 72 168 1285 10d1 ab 101d 1107 1065 1611 1509 1341 14c4 1a90 14b0 1198 1c82 18e0 1780 12c8 11c2 1234 954 1826 1606 142c 130c 1838 1512 1458 1e08 1d20 1a42 190a 1660 1322
4 1800 1b 223 20d 69 291 c05 a41 1c1 80e aa 192 36 162 988 894 550 a24 944 1883 1443 1107 1489 1055 931 1701 10a5 150a 1852 1612 1c22 1b02 2c6 1a18 141c 10d8 1c48 1628 1348 112c 14b0 1270 1314 1e80 18e0 1584 1464 13a0
4 1800 2a1 a84 303 28a 8b0 cc0 851 131 864 905 149 3a c06 84a 81c 10e 1270 1690 13c0 1e01 1a12 1642 1314 b28 1219 1245 1226 160c 1d10 1461 1581 1152 10e2 1982 1522 1434 1458 1198 1544 11a4 14a8 1823 1889 10cc 97 140b 102d
4 1800 c0c a60 b02 a84 807 944 834 81a 603 219 b1 1e0 185 8b 78 14a 1e10 1c81 1c42 1851 1990 18a2 929 18c8 16a0 1704 1648 1541 1530 1582 1415 1464 1498 142a 12c1 1350 1232 1225 1388 120e 1063 1113 d6 1126 104d 111c 10ac
8 1800 93 40b 63 819 825 231 4d 80e 342 c6 894 c28 b20 988 944 390 1903 1207 1415 1151 1701 14a1 1185 1129 ac1 1a12 1c42 18a2 105a 1622 1582 128a 136 1d10 1870 1e04 1618 14d0 1254 10b8 1548 148c 1464 130c 12a4 1268 11e0
8 1800 a3 a03 40b 53 107 891 909 35 2c2 81a 8a8 e4 c0c a48 914 270 344 12c 11c1 28d 1c21 1845 1641 1511 1321 1069 1886 1492 118a 1702 1426 122a 1216 104e 962 1cc0 1b80 16a0 1584 10d8 11b0 1e10 1a24 1454 1548 1438 1318
14个人可以59瓶毒酒:
2000 1080 36 2086 104c 831 429 168 413 458 10e 21a0 28c0 1130 1803 1214 1406 524 a05 a12 918 60c c0a 3408 1601 b40 e3 208d 2055 10a5 10aa 1099 10d2 2e4 8ac 2d1 1d4 2ca 3062 2432 2238 281c 6a2 389 c94 5c2 1845 3141 2922 2311 2550 2642 1984 1382 1a88 d81 790 1c60 3f00
2000 1080 3a 208a 104c 831 425 164 413 454 10e 21a0 28c0 1130 1803 1218 140a 528 a09 60c c06 3404 1601 b40 e3 208d 2059 10a9 10a6 1095 10d2 2e8 8ac 2d1 1d8 2c6 3062 2432 2234 281c 6a2 385 c98 994 5c2 1849 3141 2922 2311 2550 2a12 2642 1a84 1382 1988 d81 790 1c60 3f00
800 3000 1054 6c a14 b4 245 125 1d c6 1026 20e 407 2940 1c8 2830 1520 518 2809 1409 1031 581 289 5a 2882 1282 702 232 143 2b 93 3604 310c 2c24 248c 2384 2116 34c0 3260 2648 22d0 e50 3218 30a8 1990 e88 b28 2451 20e1 ac1 2621 2311 1b01 2462 1862 3412 9a2 1352 2d0a
800 3000 11c0 341 2842 1442 c6 451 63 1058 6c 2a80 702 b04 283 485 107 1308 2811 1111 10a4 c24 20d 100e 416 2828 330 1029 42a b2 9c 1b 35 cc1 3244 24e0 1a60 d50 20c9 a4a 2154 1e01 3504 3488 2590 da0 2509 2621 21a1 218a 188a 3122 290c 1914 2226 e18 3430 2b12 16a2
800 3000 264 243 462 151 1448 4e 10c4 628 1222 1601 215 33 125 2920 5a0 100b 8d 1811 280a 1118 9a 2884 1016 194 b48 3250 2740 ec0 2069 878 20f0 9c1 21c8 3142 c54 22a1 2309 320c 2a12 2690 2306 1b80 c29 203c 18a8 3430 8a6 2419 2407 2183 d03 250c 3482 2512 1906 116c 2e24
800 3000 581 407 219 2b 10d 2841 1141 131 283 53 1025 245 498 140a 14a0 c84 1068 2c8 280a 14a 1e 2a80 2830 1032 1214 914 74 306 a6 3411 2621 1a21 8e1 2095 2708 d48 244c 1c0c 3640 f10 2612 2522 3504 2c24 3118 9a8 222c 3320 18d0 30c2 2262 2192 1982 b42 21c4 2c89 1391
15个人可以70瓶毒酒:
4000 601 181 46 38 6440 344 110a 180c a88 5111 7021 6105 42c2 4170 5a40 49c0 5086 5418 448c 6814 60b0 4c24 81b 2f 515 295 1521 206a a62 3248 3850 14d0 cc4 2512 1216 28a2 2c28 218c 2624 1d04 5053 4271 640b 4929 4c91 4654 419a 4e0a 7902 6328 522c 7680 4e3 3149 144d 2961 3c03 e07 2619 1aa1 95c 6e8 30e4 228e 1c32 5a6 11b8 2b90 f30
4000 601 181 46 38 6440 344 110a 180c a88 5111 7021 6105 42c2 4170 5a40 49c0 5086 5418 448c 6814 60b0 4c24 81b 2f 515 295 1521 206a a62 3248 3850 14d0 cc4 2512 28a2 2c28 218c 2624 1d04 5053 4271 640b 4929 4c91 4654 419a 4e0a 7902 6328 522c 7680 4e3 3149 144d 2961 3c03 e07 2619 1aa1 65a 95c 6e8 30e4 228e 1c32 5a6 11b8 2b90 f30

mathe

这个进化的程序对于比较大的人数应该无法找到最优解，但是的确可以找到比其它算法都优秀的结果，比如可以找到
30个人1041瓶毒酒的方案
[1041]810a042 8720010 340860 40553 19a28001 123065 1107379 1669c240 29c94090 3494800c 3d52001 519614 38658a1 980c290 15021188 19018a18 14c0a204 104c7252 1c18886a 145c1108 11282315 12011890 103242da 6842870 415044c 26486450 80021cb 308a8013 e650213 1201983 18492101 c4b40 35389002 20c4278c 1d00ee 21046427 3c00c8b0 54c868 84e8120 10413e28 11c82407 c141082 1c464014 12b40116 2d210507 34422153 406590c 278161b 10541896 21299015 d11c4a4 20c6782c e62008b 10894391 16a84030 2e02014 802a25c 30c61 22b54028 8bf481 620b618 69282d 26a8209 130232c0 148a24ca 683316 1d20014a 885548 2a414740 9a8040b 18016618 18424e4 182c09a 14a10484 c250a50 2600a30c 14425506 206e1a20 d820167 11f0021d 1291208 3022a01d 800e906 18665190 21142c91 10606968 34dc810 10a98b1 36642120 a45032 645805 2200323d 1c280826 cb8e002 c84442e 85e0f0 4d0e581 38911c 2b20c808 6a409d0 14104723 30658881 2421d80a 28452751 20614483 4c9433 2b05a100 220cd8c 3950416 1308d85 18d82440 711081c 212470c4 218ed0a 1b318220 299101a 24601861 a12a88 5120f02 2441ae2 130a1134 24c3161 4344432 455109b 381a2648 8608b6a 291a0a08 20611a28 201c23c2 844301b 42a1013 28268b80 1221617 3d890002 b112014 10015d42 1000d11d 1a45a009 64a0292 4412ca4 25100c46 1a890044 2095e09 cb6502 38007261 33100902 138a74 5020ef2 60102ca 30e449a0 2cc4380 22030dc0 f29a802 390102cc e0c8310 4304c6d c2160c0 19181158 2a000d6e 310a043a 12188a8a 10982809 49c7006 2e100887 1260490e 230d08c2 241492a0 a942311 2ec06088 248a381e 2c2e406 86d1818 10671023 1b808803 9220d8a 2041c09f 552265 d658121 12823113 911041a 635449 39c11428 1c0310e0 1444963 105ac2e0 18a02483 180c1c4 7a02661 31036892 143d0604 33000073 18503db0 289a4690 892c80c 2011487 b500497 ea0c602 36838044 14102760 16086823 294130b0 218c0a14 39081a03 905131 2a05204b 301d2060 621c0b4 8c31883 146c350 1a58930 2c28900 1198ce 24485a42 6075414 288d2880 1d1000b1 206b8424 290d104c c889562 2069085 210ac960 1a226321 4c04b88 20180379 11150383 30a60e21 4721c3 6af14 50c8523 8c2b088 20442917 2132102e 722e44 23321200 54322a3 ac18841 2c10c188 3006a902 306a0606 e50025 19660141 2214f210 b29c88 2c3011ca 20432b52 c869804 640a8b0 22d92410 7401522 22543c40 30910349 254b5001 5b50030 12421462 2c130812 800cc93 38b2a08 2c5082a4 a2a0e50 c0aa507 3ac84a8 3b600a9 b470825 4661c30 6a8d 18134911 581182c 23a41500 1ea88042 d003721 845d22b 9c1262b 2c201a19 10ba0068 22c5520c 4f38104 14303199 2dc3101a 21d89804 1169a128 14608035 32215100 250405cc 150005e2 82a7808 2d03a9 28b08225 c106231 102cc10 2285012b 26228245 168d421 5701706 81d0c21 10e504e2 2843525 7b09809 21860159 20058287 28510d04 25f84082 2681728 2043d5a 1bc22850 125a420a 17004c8 4d43300 10b0022f b03442 29186114 f2404 8b20421 34844062 1241c033 5203510 70a9007 9013609 18340d11 2441148e 28468608 10d44232 1141900c 10c27418 12151184 1e810088 23908641 310851ba 14e920a 892985 301a4042 2bc02020 1288c0cc 1e044600 38882250 73a981 1c096054 2d394220 1054100 1818109d 39c32009 28704c98 33010420 b0a1521 302424c 3c2060a9 11024185 8406b39 1c0402ba 4202e12 18289405 23015d8 38a8115 284a80d2 2203a862 86401a6 398801e4 e5b4000 1199d020 2009861e 20224099 2a025a04 780808b 214c8448 10902c34 1184550 224221b4 9209874 120a9c41 182c1032 3081408d 5250c09 10e21074 20686138 44380d5 2242703a ab020ad 24a1119 3070e03 24ca811c 14e2287 3090b7 14279108 114081b8 108d2443 1a904418 1a260b8 141640a0 f03a680 14ea0004 2012256a 17480414 141a855c a008e4d 658c48 2005ae08 54d2108 122b4a0 1780a12 28980920 10f0a050 354ac1 242208fa 112e014e 12750042 180a3910 8188d10 8e44305 e088009 866e801 8888a02 b4c0322 15a8c300 81d6008 3898860 50a1a04 60a34c0 80a4c4c 90294c4 3c0144c4 342c004b 19d6821 1298840e 28a85830 8b3b f8888b0 908cf80 1428965 39498810 5c03835 20c78050 2c02919c 1404104d 40b3924 1281017a 2020c44e 20a46286 250e207 28ba440 63008c9 9257423 2c40482 28208696 495028c 2c442c25 60e8980 10839015 24187140 16011ca9 2c149500 8c05248 1907e40 10b593 a5048ae cd98089 117a8640 21016c89 8201ea4 9666221 28909156 180182a5 1013209a 19c298 3210620d 102f4822 15862208 445b901 c282b42 8283650 18304e 26341017 306c2940 81000 1132000b 32d9442 2a21352 27003002 34009312 210cc324 818f401 c90b0a 17582202 2884987 214419b0 14287980 2f85084 38384a2 9c90604 481a0a3 4296864 90cf041 14e38d0 28305c04 1088cb04 300c84a5 1294522 2a6c0502 8b04a26 2a90180 3023c402 a5b20c 462281c e44a022 20258249 1944239 1c89260 42108a2 10933544 26543284 2c3d0410 12051826 3413808a c645008 a05031e c893104 333670 2210917 18810b16 19391820 22b0184c 14066294 519e006 b42d610 12462a0e a410166 a9410e0 32499108 b860c10 2902a8a6 1320070a 17200e28 203a07a4 14211e36 7538842 8a13245 17604681 22a222a4 7c3550 3e0a0249 12742411 6053a01 b0800a7 22b44145 282c732 20009b64 68842e5 2c900684 a1a5cc0 85078c1 d130074 2246208 8ec061 1d11a03 1040a8e5 424ad5 10390661 24619083 2c85215 28f2c300 b40b816 184469f0 12989281 515a80a 27026910 3a10da01 b58552 24308666 2b214162 208c8516 1e0a45c0 21910142 26b1410 205d5120 1949831 31229381 101cd228 d072029 2496a402 248050aa 66c006c 7056544 278001b2 20a03911 204c108d 5181986 291025c2 2a771 280c0971 9283806 244d0190 d024a20 21a0898a 2a142168 1706314 28e2002d 6988268 36410645 188815b0 90466c8 5808074 1491090c 14223154 e24c13 a0ae024 10003d8e 29121508 3a80928 a708c80 221e002a 24281cc 30580081 8330781 34304124 1c20f89 3002941 200142ea 19cc118 14640554 3d042085 2881850c 1444648c 200e158 84254a8 2e90003c 18b80cc 10a8a0b8 60e1a13 1d214025 7c82981 5e1a042 10101e4a 1108a519 2544844 18571412 3034820a 2041b432 31183a6 51748c0 6ac210c 2026c033 14430fa0 187480c8 39005d04 1c500628 218c0462 8202a4c 10ce1c02 b380201 38c00862 c257145 1ada0800 25021c6 318208a4 1222d050 31880e09 39275200 4156826 20a00aa3 280078e4 201701a1 2e0468 100060d2 5304389 33194010 6430150 18e0d01 ce8238 250c03d1 8211b94 1a14458 1c03a421 29020e4d 2124a801 162388c0 2a540192 81908f2 460b817 10414a4b 1680849 752a84 28049815 a14c802 320407c3 25a10813 2630640a a606520 1382360 15415388 94e4044 2cc410c2 280a4651 28320370 840ad89 1c258540 2119d009 904b164 4835041 5141bc 32150224 1044f29 32908818 801a8d1 10a240e1 a0b4071 14c8f840 6390141 8e0c022 430d0d0 c4a0c05 22a124e0 1058824c 201b6ac0 1e119101 e80b024 9048622 22429504 39808c58 2287088c 632c042 284ea204 f809b4 20482a45 21e1a0c 19444c51 2391482 28102ea8 5133081 14641181 71030d2 43c91d 2080d4a0 3124480 141b0049 25aa8428 b900d08 c090665 28721083 34873440 329b2015 11560424 20221578 34206310 2603e008 6c04d01 cc08345 111440bc e08524e 13e20284 2c081125 b903891 11302082 228a2303 14d20831 2100bc0c 26500a21 3d1a400c 144ba80a 2098b121 2a621908 1103226 6920110 14209a21 b404098 20162256 59a116 813960 12641c 620d865 22e281 34070522 21285c80 90d41ae 18180502 32860602 228a3d8 1180c481 3004c492 270c5009 334c02a0 3081cb28 210cb21 8069243 29c0430a 28d03802 6648091 28424831 38424988 2c345052 293c202 22c0ca90 340085c1 2c601538 2aa10a4a 2460414c 250500bc 20291192 2031e204 4459270 2c23a301 193e6410 103e8412 11d40828 ad601a c0e2418 f100b44 21019712 c946184 2208459c 5c18888 20858c90 31011144 2334b088 5984040 30c2584 882b5c 14000eb a2d3070 23611b4 a4c4431 b2441b0 3c30c0a 396104c 68e4604 320646c8 9454485 40888a8 13041213 3218401 9865028 3182964 88c1074 28935000 6608172 1450312c 42402d5 19582016 30c91805 30096026 2d18131 7c13280 4872760 2e498802 234331 19843630 324121e8 110508a 813107b 28015919 24127288 a80d0a9 aabc008 36518030 500ec6 a818320 3ba00121 2098222a 12288546 380210c5 184d3480 14829489 846050e 18a0829c 20ae1450 20c204c7 8a2510a cb4470 502690 2d00a009 ed28021 26a07900 1a950900 3505a0c3 20200156 2a84a714 a00ab52 21610246 2d17128 20532038 101c8c3 4407424 14a90950 480436b 226d4089 c806445 11d4a240 12cc089 1824a4a1 84056a3 6805290 1754011 2b106a01 111a9806 224804e1 1cb80281 2800d458 29a64402 418d02b 307a2d4 288ba1c0 202f9080 114450c0 2812c04d 5805740 24284084 40b8144 24882f48 1252854 11149400 670934 10858406 148482a 40b0e10 41f190 1990a224 80b6984 440c4c7 6b22580 1064560b 12065428 30c8c910 4088c51 2410e36 3c6481 390e0040 2ad0246 33301405 1a05128a 2c199080 21514c15 120b4601 251ba102 2a811aa0 1dd00104 81c021a 2a00acf0 20806439 d84184a 30394a14 e221484 2360c1a0 222b301 23c20342 d3a9400 14142059 208e4b0 2542080a 4a26a29 24518240 1701c124 24660462 2cb100e 5180c9a 9284455 1a1194a0 100671c0 18311055 180a5288 108058b5 11901581 2206030d 44853d0 308e2291 118b0708 2ad20013 240b0d3 20271807 355902 8212514 8c9ce08 250560c 1ac9140 1c08a02c 31400d21 24e81230 1884203c 3505000a 227ad00 201ca24 2a238188 4084314 b4e106 26c04542 12322894 12008f41 a834d 6e001e 2a01202c 809c528 1c145a01 4817c02 100d9940 21931c12 1b162600 1d052312 2a21c410 1301e04c 4a0e914 f181045 23090036 4545590 2116021c 35045230 288d5011 11d2800a 260216a2 18400cde d6c3080 2490a840 6e7100 45e4808 c23e804 3e4b108 484d36 3d041682 2940b500 abc03 1020db86 8030bb 28802a92 a805324 2302605 1006e264 ec89600 17078011 3900ab88 aa614c 1cc01910 8991a8 1d880908 3098cc02 12272105 4898492 a0043f1 20041699 2950d040 a483c0a 3a002f2 8114a0d 8264434 10c06b50 210045da a178440

mathe

29人
[1027]190a0aa4 11a1009c 148812c8 84990c2 d0d0580 606922 908c904 319a02 4c06cc 29310b1 47a4888 1418d8 18264e04 5989301 4455561 1011b821 1001e628 5104ce0 1c600c86 19111c22 32ec340 484d410 1068a918 13c00988 5291825 2cccc80 9605211 54960c 22c98e0 18160480 a076821 10470219 1a788010 2c5019 8098466 9821c8a 10817924 10ea1429 242443e 13e81011 122601a2 8018901 1380096 10838a1a 832248c 50001c2 b51122 f072 a121e9 38c0209 b03620 74e1082 15462164 1a81a130 85d00ac 44a11f 2629828 3024780 2119163 8145325 8263441 e008e88 112e2c05 e8d0028 49051b9 1860a432 1a09180 23c40c6 4875a2 5745a 151c1b0 1d068510 200f900 e008391 5602880 814407d c071130 2155007 b4a0611 c2271 3781030 505040 90cb81 1828840b 143c0438 1102a4f d09584 b2220a1 ba1045 5530c30 52ec058 44008f4 2222606 11c83100 148200b7 269c8 2d01a28 ec5002 a86087 d884811 b871410 40806c3 4114c53 4b82d80 189e0062 104144ae cb28806 1a028683 19108b65 4033234 401a00e a0002b4 8e44e20 1024216a ca98a10 186c05 bdc9100 9428465 2824951 4b61380 14136602 540029f 1c004830 1c708082 81502c8 10223073 807a109 2782c21 4c240c7 f154608 185208a2 38401cb 41b8223 10c632 e2c90b 3950e81 4123094 445a852 15109453 605c51 aa15c0 d0a3814 17804095 17208712 6763028 524bc90 4020556 d41c022 a710d02 22c817c 18780248 e2088a2 12103932 101416b9 5be4003 13274400 14606181 101b0348 6140ca3 10421b68 100a08d8 12083482 12288d02 89908e 17031009 a59605 144c4a30 b186604 201d250 101cd264 10443a02 16029222 cc84424 12840aa6 16844240 681a242 41a034b 1b341028 20e0cd0 1944218a 9481881 5d12806 a011617 b034809 1c504027 ba2c1c0 2401e0d ce50c 18022b00 b0d4130 100a8862 1209c4c4 d105506 f020c02 2a4a462 34f4288 9250202 14482086 ed132 180a355 20e4f08 4c02451 4007245 1e480f04 b042d9 e016502 a48f420 203818c 110c405a 1b848420 820019b b081300 889084a 1884589 ce70008 3803c20 258e0c2 4514908 4128708 c4c4160 9888950 93a3009 2386c2 85114d 152420d0 43e3830 e78244 10bc2018 10781126 20b7428 124205ca 9881878 80084db 1900608c 1902920b 28920c8 4874002 f465004 144a803a 14890826 c001863 1b00c64 43a11a3 21d241c 6016882 1c2c18a 12158830 5161842 2480327 3217001 4083794 3622149 9348a04 203290b 100d6014 1880432c ac64c00 1e2000a9 fa60086 14206ac 1019e046 94b248 8b46150 128c2882 3184b90 16e04030 4711860 a8c04c9 8a17a4 224d083 12002d35 106a690 b944308 b59044 1b1a0422 18b924 66026e0 1122148d 1016a66 21e0824 b0c8861 88e4c0 8f1818 4a1b480 14d5602 1b310100 10b80684 84028d9 32510 5900487 16204194 100e4a44 13009548 12947042 1352c006 1418388a c33d201 14a8168 9109231 81a4823 18a64181 6830e20 70402f8 5301209 852d502 a0c6c 11909832 1326311 6c23006 1238189 18212985 88325c8 10d10583 1cd0426 2383411 10053631 de02024 54194d4 1418a901 278825 b9b0008 c108d22 905051b 101780d4 cc08986 4a4c842 e990086 505c605 60b8e 55aa028 14077005 100e68a 1103181 1a84b1 18912d00 2e1095a 4060a89 92a0943 108c9281 122c818 10490412 2810359 13adc 2312093 5330222 1acc6 10448721 aa42e80 916a822 1141808d e260460 cc8250 2a910a 1082d78 507108c 14630440 142380c 1d41010a a4d5021 e003414 10506219 1d19024 756044 3d0160 1312a19 10372221 1120803a a140152 b442c07 0 8442c14 8016384 15104203 12210e11 1714a284 18118226 6254212 5d42030 2218c6 4246303 10e10305 10ab085 118e2111 8235328 3470a8 188a5940 291d11 400ca1c 13304c1 18223303 ec06802 1072960 680813a 1c18d400 2942521 806a165 182a1c18 58a1220 418e64c 4681f00 a72108 8027c40 46c071 684890c 1c281922 cf00301 306a221 882c462 1a43b08 3c2910c 1c84800b 12446151 ba162c0 10130889 1c4f0900 16401c4 1d0055a 1cc2000d 43e814 a33a800 10014596 1060c4 6b6c000 228b014 886ca03 1180d4a1 d58064c 4213423 4b28a8 12918048 10a8a092 10c17881 931823 20482d6 a0e2980 1a820194 5202724 1a7a0 404e262 9590213 e61004c 1e028248 a610194 16c01429 923a85 c1442 6280c89 1905a142 48510e1 181d3880 1014b580 2284334 140323b 1801482d 681294 e880c1 850181a 2b00c18 c024731 10853098 80ae64 4484d02 829259 12a458 2d03a6 2062313 1940cb08 11004445 12518101 d26026 10c0d022 aa40924 1404c384 10f2206 86304a0 88409f1 22d9a08 a29511 a5e2004 15002966 d130904 80b6843 180642c3 144c1105 3117e00 1a095800 db81400 8d50310 1428452a 1070249c 6889511 42d164 180cc308 3328452 13c20220 82c48d2 92825b0 818128b c22278 5e0544 844e468 4c28860 1110ac90 5405125 82414b0 218111f 12621500 14411a8 cb0114c 30440a4 2850a35 221668a 4184012 8129016 858c205 d200169 1a41a082 84043c9 5a03015 49e0048 c9480cc b490046 be0215 2080dc6 16034160 91414c5 16082149 118203c0 820362d 1210520d 93c208 a195180 1399c0 a824648 64c0c20 14085896 1090c14 5a70124 14810815 80d6482 28a6098 1196e100 8371402 2302e42 1a90021e 48ba005 878143 d444154 a412018 e805708 c822e90 2d4d84 63a3 a0310d2 1220e400 a481952 b90283 a2ba01 aa0401c c30a56 2443120 c24065e 102181a3 1824a0d1 c412a09 1148a02b 6c21490 19814020 10b045a2 8c3122c 68c9023 1d100610 100173c 2a50582 181809b 4218984 14e82208 2d38032 a22c610 19643801 8e502c 1b0002ca 190c8811 43c140c 11321a80 80a30e8 4b20171 15401046 3e400a2 447b004 d0c6a08 122c524 7004e44 4022069 9500076 4a4a194 5460758 2c94824 11531102 a990988 73d0040 993890 568404d 6482056 1388650 48872e 2c0c20b 11286270 1c0e11 1a102033 12149d0 12058e44 8681423 1089156 108851 182044a4 c0c095 3581e 3898920 1d1a6000 821aa16 d011c58 301c2e2 14845a03 354ea00 1b571080 458495 15029381 1c26283 2271018 d017024 11020523 e0649a 4801f05 461426 c0c08a5 1c084292 17a10a42 8122420 8580a8 a282b04 a8522e0 54a48c2 9274098 ca50007 52192a0 9022058 2252885 bd204 a9404a8 1c311520 9204172 2008573 2905482 d87013 19023128 10861160 3083063 6141592 18802593 8d40c5 25549 1006c027 1d330a 12850057 9043435 9114140 b526092 470280c 11908d09 4308837 1845c010 1844c1a4 1088a247 1489414a 8593044 84a9045 10013268 948ba00 860a001 c22580a 1500500c 8c98f 128c3204 b5202d8 4842d0a 428a1c0 208504c 4640238 8a10229 e0580c1 10089809 1080a2 4c57102 1822a868 2d2655 669d010 10801f51 102414c4 18b10870 3d08680 48a1c84 18492441 8491168 12400664 a899012 240135 100c84a8 10611908 26a01d8 12039055 a084a4e cc010a0 3320838 16510405 e42412a 880a0ae 151504 10520603 19d118 14a08224 1a404742 140a835 745a040 14140d40 480640c 114e2448 8226290 c03062a 91830a4 2325078 1601c221 6030136 3170640 140742e b221c04 c993208 1aca0803 40994b 439e001 63004ca 10740510 19092a01 6660102 4b20492 100323aa 15694004 40a24ac 44264b1 682750 7e00289 10459b80 30c808c 4090215 10e0d884 120d0819 12645620 16600813 280a5d 1702042 6a23208 160c1090 16340704 1849a20 10a10f32 400e72 6180936 17290380 530aca 10c648c0 601407a 33003a8 10416e04 1210c298 1980cc40 881c508 190b4c2 148a4504 c82a2e0 924e144 4582511 1444dc2 988d602 17242a08 b8ed20 28344c4 1201dd d219018 12501c80 2245928 9a2022c 11718060 a25830 3124560 148c001e 1a5990 1225492 a042b62 832824b 168f0050 404822d 3290508 db001c 88e0096 9645406 9c48e8 8015634 10694e0 6188b40 3650011 810ca3 a04c103 8009e68 d3124c0 20719a1 c448342 c448480 1080044e a5116c2 3301204 8c14853 13061043 831270 20ac8a0 82e048a 11935400 10e004e8 1c924141 1422213c 1598c01 13484300 1007404e 18a2a114 4086438 a8286c 83110e1 100aa5 12303184 8088ac0 1052420e c11cd0 c24b00b c941602 4cc09b0 6803941 1f160001 184101c4 1426024b b601a90 100122d2 1e42a11 181081ca 488092b 11bc1024 c300d1 8187490 5056054 12888638 1494058 6481268 6a05164 4248593 18319210 1a100a41 556021 8c5391 8a8e808 13a22803 15144910 18c10648 248418 1819c089 2506914 3a20071 70b80a0 840e16 11048a05 14938280 18501015 121444c 1d013442 38a1848 6d02304 914166 54a0051 38100f2 1430b10 34c354 1848051c 112002f 7300421 9a830 4154a8a 151800a0 1410667 1f08a404 1500a20a 12b8506 12041783 1a80841 9810601 1081b106 3022874 1191242c 3042408 13682114 fd08030 a04745 2164229 2d01212 8900b92 8b98100 11821c14 790025 1a6b2200 8e00542 19944881 c138085 110e208b 18208cc 10d0003c 369088 1284d068 2485091 1820082e 8b8571 211202b 4220b40 1c52843 1904d10 d469208 1c050760 5420c48 11ca0086 86612a ac05101 2b4808 614a2c 518c84a 2c31a80 1660321 15026850 3510884 1c01c244 11192180 14200601 24805 212c0c3 6265424 1208b13 28011b2 4154589 4c16390 910a885 250852c 1958801e 100caa9 40d1a07 10341c68 12404e3 81ca602 801240f 2093305 12885061 1a00b284 480469 8422216 12c0a0c6 522d81 18c00213 1a2a9001 5601b41 a21b102 97ae0 c0a9d0 8320a15 190c52c0 c4ac210 965461 9418864 11000916 1d221040 2909805 c904aa0 1a313408 514d004 4c0c640 18850884 268a468 11843844 a64802a 22910a9 f00030e 18c028c2 18ce3008 25c8314 10096a 15a080e0 1160413 4ad0114 c82b82 1e20c40c 16c80245 50c102a 180031d0 262e240 182c1206 bcb02 6828890 10691a44 10142aca 11a02430 9059294 14232822 c428ae cac0141 8728140 4843891 26007d1 16128560 11851451 134a040c 1906829 10165710 22a410e 8984070 10491680

mathe

现在29人进化到1180瓶酒，28人进化到951人了。看来28人也有希望，不过快到极限了

mathe

29人[1184]11a1009c 908c904 1418d8 5989301 4455561 1001e628 54960c 18160480 10817924 10ea1429 242443e 122601a2 1380096 832248c b03620 1a81a130 44a11f 3024780 8145325 e8d0028 1860a432 4875a2 1d068510 5602880 814407d b4a0611 505040 143c0438 1102a4f ba1045 52ec058 11c83100 ec5002 a86087 d884811 104144ae 1a028683 8e44e20 1024216a 9428465 14136602 1c708082 4c240c7 f154608 185208a2 10c632 e2c90b 4123094 17208712 4020556 d41c022 18780248 14606181 10421b68 12288d02 17031009 681a242 20e0cd0 1944218a 5d12806 b034809 ce50c b0d4130 f020c02 2a4a462 ed132 820019b ce70008 4514908 e78244 10bc2018 9881878 80084db 1900608c f465004 144a803a 1b00c64 6016882 1c2c18a 5161842 4083794 203290b fa60086 8b46150 128c2882 16e04030 a8c04c9 106a690 18b924 66026e0 b0c8861 88e4c0 14d5602 84028d9 12947042 1352c006 c33d201 9109231 81a4823 852d502 a0c6c 1326311 6c23006 1238189 18212985 10d10583 1cd0426 10053631 1418a901 c108d22 101780d4 cc08986 14077005 18912d00 2e1095a 4060a89 1acc6 10448721 1141808d e260460 2a910a 507108c 14630440 e003414 3d0160 10372221 1120803a 8016384 6254212 5d42030 118e2111 8235328 291d11 400ca1c 13304c1 18223303 1c18d400 4681f00 a72108 1c281922 cf00301 3c2910c 1c84800b 1d0055a 1cc2000d d58064c 4213423 4b28a8 12918048 5202724 404e262 181d3880 850181a 4484d02 829259 12a458 2062313 12518101 10c0d022 86304a0 22d9a08 a29511 80b6843 180642c3 1a095800 db81400 8d50310 5e0544 30440a4 2850a35 221668a 4184012 84043c9 49e0048 c9480cc 2080dc6 14085896 14810815 80d6482 2302e42 c822e90 b90283 a2ba01 aa0401c 2443120 c24065e 1824a0d1 1148a02b 8c3122c 1b0002ca 43c140c 3e400a2 447b004 d0c6a08 9500076 5460758 6482056 1388650 11286270 8681423 c0c095 1d1a6000 821aa16 14845a03 354ea00 1c26283 2271018 11020523 e0649a 461426 1c084292 8122420 a282b04 a8522e0 9274098 ca50007 52192a0 9022058 2252885 9204172 2905482 d87013 6141592 18802593 25549 9114140 b526092 470280c 1489414a 860a001 128c3204 b5202d8 1822a868 669d010 102414c4 18b10870 3d08680 10611908 a084a4e cc010a0 16510405 19d118 14a08224 1a404742 c03062a 2325078 1601c221 b221c04 c993208 1aca0803 40994b 10740510 6660102 4b20492 15694004 44264b1 10459b80 16600813 280a5d 160c1090 1849a20 10a10f32 530aca 33003a8 148a4504 924e144 4582511 988d602 1201dd d219018 2245928 9a2022c 11718060 a25830 a042b62 168f0050 3290508 88e0096 9c48e8 8015634 a04c103 20719a1 8c14853 831270 20ac8a0 10e004e8 1c924141 83110e1 8088ac0 1f160001 b601a90 1e42a11 488092b 11bc1024 5056054 1494058 4248593 556021 8c5391 248418 1819c089 840e16 11048a05 14938280 6d02304 1430b10 34c354 1848051c 1f08a404 1500a20a 12041783 9810601 1081b106 3042408 8b98100 11821c14 790025 8e00542 10d0003c 369088 1284d068 8b8571 1904d10 5420c48 11ca0086 2b4808 518c84a 1c01c244 212c0c3 6265424 910a885 250852c 1958801e 40d1a07 12404e3 81ca602 2093305 12885061 c0a9d0 190c52c0 11000916 1d221040 c904aa0 1a313408 11843844 22910a9 18ce3008 25c8314 1160413 c82b82 1e20c40c 180031d0 bcb02 6828890 11a02430 9059294 cac0141 8728140 4843891 1906829 8984070 10491680 1219490a 3405069 140c5c28 130f9000 1b44409 b14d48 c0a05a2 11bc8202 825a530 649330 3158064 450ac88 2c46405 2a802b0 4c68e1 892f002 12b18a80 2158382 c10e134 10160147 1082a6c8 200217c 1d898100 1211254a 101c4320 1218a61 532d060 c882188 a854011 134420e 12810300 6342006 104115b0 1b442403 19d09080 9408d1a 829a08c 10144c26 8038e84 980522b 305904a 10ba4620 11052812 8804d07 11424035 804f0b1 2c241a0 144c9c 1333010 11168620 a08c448 420091a 7800214 4a203a6 3b120b4 2a030c0 60160b9 109a94a 1c544204 1048a689 8882565 894534 6009906 18040f49 2f04350 27a4209 70c883 100ab030 d0c1413 13304c30 9541022 310153 e1828c 5102b28 8706308 121cc080 874305 60941ac 8530124 14894610 1007360c 9a820c2 18846409 18280ba8 ed00821 291e001 d2b0211 11803680 16c300c 6412c2 8434581 90068b2 16288130 11025286 450815e 14482860 10431025 19004119 1312080a 454ca09 11518504 392218 55cb042 486c580 11264851 5148071 407bc40 d8340c2 81c0668 68180f4 1064d5 8c621c0 c0a081e 423b24 95a027 18637002 48b0318 12010c0e 1e911090 180c212c 1402c8d 1a502c8 14421c01 1210822b 73a1088 659401 1018a444 1461b 12080085 442a285 1040d50a 3090195 1081498 d40b012 9048c6 503665 181a1404 1420334a 4470614 110705e 30b6241 1103e10 271ec40 6104849 89e9200 2496690 2610a70 51e0906 10290217 101a2290 1a002619 15029300 90194c9 202036a 12920065 18899480 8283059 1b982010 4326d90 d060a07 226440b 1581a54 98811a2 1029302a 7a20580 1e014440 aaa006a 898aa11 12c13420 914a102 10942a24 49504d0 14a91101 1b10505 805884c 28097c0 1242a541 60c483c 1444d0c0 1886888c 15a92003 10062486 1b080054 2c00da2 322a105 18190c28 12ef 1035480c 8295006 4031664 72045b eaa0c0 40e7422 8807c40 7821a8 125810b9 88c0704 64090a5 842d019 c0c0436 4228091 1a24242 120512a4 1a241049 10228149 24300ab fc4084 178000e4 a40198c 4261781 aa01307 f205140 5190035 184003e 18109116 1a608064 96a0038 1de4840 45040b8 3052701 193a0102 2041d2e 2811404 18880262 18a04322 15832 160a4421 18010c55 12414112 1ec814 10a548a0 4b1a408 4818145 12484921 11406a2a 14442144 120ca848 105c5401 41026a2 10fa06 17014007 2c41a02 408e08b 6908b2 c460023 114412a8 26cca0 40604bc eb00684 8161a68 1124a322 3215024 f240490 14204474 180e8 4094b81 18b020a0 1059c224 14a1161a 10524e30 18300447 5901894 5283212 b0c2243 41480c2 1750084 f408804 83c0808 1a100ce0 18c08845 7cac000 1c284009 114f2020 18226440 1e84481 180644b 14a4620 55005b2 6d440c 1144b818 12864412 1984308 1c850984 10a04198 f211003 4a1c028 14011d6 6581888 5890c41 962700 1030ac81 6cb1401 11d6440 1e00aa c561290 1400652a 12418dc0 1c0055a1 8ca8434 1222e081 e842034 14000379 a284603 2d40228 12120e05 1000000 2f28401 10d8a222 11014589 1a782080 10945805 18ae0440 2e68b b4884a0 468c51 ad0c058 4e01c38 183e084 4040a53 12988854 10020232 d212146 e036023 50708b0 222c194 14404256 17407a00 812c288 c029121 c099241 4d080b c82c0b2 1084e90c 9c98061 5a0da1 e0b454 a42a1b0 1952c14 8454086 12057480 81aa08 8043229 12511851 10b1c450 83819c0 1342198 146a9800 1380c414 1047084c 10e7824 8075640 6258c00 1882a72 da3848 40e6181 4923113 2380921 ca807 2889c00 e22804a 1c442809 15be002 4c41825 15c09014 10511208 8547404 8408607 a1012a3 aa00c28 5c48918 103245c2 1664a200 12f4280 85a2d08 881b468 14009964 182d0e02 1e93 8541541 a440435 2f8e 172052a 110cc124 154000da e02370 d0c8380 786d a01d1a0 10098413 b800570 14188a0c ad63 31812c0 12d82a08 2c28b44 107b6 14a904a2 1433000e a4b2284 1394e 150d7 4914661 1c0284a4 23a5c c682612 1481a8e0 280e824 286e1 a3991 a621262 29574 502030d 17c14680 1a002853 35cc0 36164 422fa 142a870 924004f 1580051a 44931 47348 4874e 4293150 4c89a c401b50 14340861 c12ac11 504300d e598004 59115 104a0150 28882ac 840bd 1e391 13046032 244b880 4c2e4 a185105 c45418 2513182 390a2 56c52 8e269 151024c0 90a5008 84c01e1 12d40084 16105411 789098 52e2182 a251b a8314 a2a40c4 134104b2 1cd018a 28938 83642 e00ad01 128a1980 18a10892 9a3c020 84353 57048e0 ac1609 96129 2140989 b5605 c29d4 1030380b 1181133 c9960 10a23d 2448819 10644207 e0112c8 3090806 1106dc 11291d 1604c14 2e49041 118c0b 8622c5 13122089 18851818 1668301 124b61 1606c022 2daa100 1b0a00e 119402a3 6492108 13a980 31a8032 3d02025 4800bc8 6ee08 150246 161ab4 16521b 17b220 dc60302 4967120 54a6842 1b75 8702b9 1c542 5016d 54f04 9840095 e4a46 1226b0a 21b0622 3470184 8283688 81d0014 3b50402 1c25005 221b204 11c04210 a08b01c 117103 9412941 189051 16801622 190f45 c40021d 6ab4100 700c80f 1ad1a10 7441501 311181c 203932 140b2a2 203ca9 20d8b1 196a041 1c106844 c2109a 22a3cc 5011740 4b0116 10116950 2156a0 23a602 14d68120 246907 10328812 250322 25b142 11d649 1910ca 25e024 84f4001 e744800 286e30 2881e6 28d0c5 2a022b 2a2ca2 2aa841 c1780a1 132408e0 300987 1682a108 37c100 11c202e0 39b080 3c1d02 408a66 420a9c 42218d 85a90a1 c300d1 86c6102 120f0801 c38c08 435342 445b0c 44a4d6 4581a3 45a241 48703c 489c16 884c0d0 8cc0a01 49184d 14807082 c0b1890 18bf08 3a4aa4 4e8980 512c26 34c5840 5147c0 5400af 574012 12471c 507710 580aa3 59807c 5e4303 4c10e82 1a86a04 52c8922 6020a6 614b2c 140c143 62906c 631163 511c95 68004f a828041 68158a 6a1281 6b2500 10cd212 405dd8 e4d0081 6c4119 9821101 14892024 190818a4 52020d5 709a00 81118d 1e02085c 81d05a 11584182 8219aa 844b4a c027401 84a0a0 16106100 85d886 878686 722017 88815f 8a4994 8a902d 8f2222 a54a908 9084c5 a861184 8d2d01 6824444 aaa1410 60085e8 914a95 91d941 92028f 970c0e 16203184 980406 998260 998892 9d5050 4311a90 3aa170 a00063 a0c289 15190288 a428d2 642e8a 3813160 a66822 a91e84 b08ad4 b580b1 15085128 c06a68 c24f20 c54154 c60964 c81ce0 c94862 604a110 a10a00b a61e00 d190b4 d96104 e10a19 e14520 f8c04a 1002507 100486e 720442a 1009657 100c5cc 1011883 10269e8 102e431 1061538 198ac010 1085b41 1b2b0024 10a3215 10c4027 10d3180 14109658 f212a2 1033159 111832a 11206ca 11300e4 1c064948 12542049 11459a2 118c281 11e3481 11f011a 1205479 1241343 1249814 124a829 39a0019 60c1a41 4c43442 1280c1c0 15101824 14322920 14c36008 8482220 a249602 14900189 a30b520 15058442 3c21221 10991a02 17013030 f808142 18401650 91280a6 1c2cb000 21c2d04 1aea0204 14032829 50b8520 6100272 10120c19 c00920e 109642c0 4012410 8921914 b003200 10626800 4b94804 6700441 998b048 61e1064 19600921 420b01b 3402366 12109443 12009490 3461250 e2830a2 7862240 b612120 d004685 a48c812 a266200 1c0028b8 40c2670 1412006b 1c4a0388 32a0110 208138e 13840144 9911c20 83014d2 8c8110b c043064 1941080a ca41488 11216205 a80c296 6230650 a523001 2102cb8 6886481 280224f 9303104 51403c4 628022c 1b131180 7f05004 124e0488 a029808 1404b281 813001f 6d09208 14288a86 5c01258 3864803 2831311 9847010 12302341 13009189 5a12a42 a0a4950 3a17008 c5a4442 5825054 1089c2a 12008c6d 620a123 1c364014 7830820 84aa00e 1b900644 2093a62 50404cd c212668 a026c18 c28e8a0 18412014 19330252 10259250 1230a414 213222c 41804e5

mathe

其实我现在用的算法很简单。这道题目是寻找尽量多的集合使得两两之并都不同。
考虑到对于好的结果，去掉若干个集合之后，能够随机重新加入的集合数目应该比其它集合多，也就是较优秀的解会有近似性
可以采用随机算法，先随机构造一个尽可能大的解
然后接下去每次从当前最优解中随机去掉少量集合，然后继续穷举（或随机添加）尽可能多的集合，看能否找到更好的解，
反复迭代即可，结果效果很好。
这个方法有点类似生物的单性繁殖，所以可以看成是一种进化过程

现在的程序应该是有些参数设计不够优秀，有时会卡在某些解上，这时可以再启动另外一个程序，用前面搜索的结果作为参数输入即可

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. }
     

复制代码