E12.二分优化n分二分·优化·n分

在最坏情况的可行性，我们知道对于判断任意一个金币为假币的过程均对应着一个k元的序列（k为元数，此处等于步数）,将其记做（A1,A2,A3,…,A k），其中An可以等于三种不同值， An= ，对于1 n k 可知这个序列是唯一的，因为假设存在两个金币的序列相等，那么，同时开始做两个金币分别为假币的排除过程，显然每一步假币的存在范围都是相同的（注意：这里认为判断假币的算法过程是非随机化算法，由于随机化算法一定有能取到其相应的非随机化的最坏情况的可能，同时容易证明最坏情况下也不会差于其相应的非随机化算法，故在最坏分析中只讨论其非随机化算法，下同），直至该范围只有一个金币。而此时可推出两个金币为同一个，矛盾。 由乘法原理可知，此序列有小于等于3m种不同形式（m为元数的最大值，此处等于步数最大值）。于是，我们有3m 序列不同形式 N。因为m为整数，所以m EMBED Equation.KSEE3 \* MERGEFORMAT ，即不存在在最坏情况下比m= 更优的解。证毕！ 问题2.现在，我们进一步深入。将条件换为，轻重未知。 【问题分析】 这时由于我们不知道假币轻重，所以第一次称量如果不平衡，我们便不能确定假币处于哪个1/3中。然而，我们想起在第一节中给出的方法二中，可以通过几次称量确定出假币的相对轻重并且同时将问题规模缩小，之后便可将问题化归为问题1即知道轻重的问题。 在多次尝试和改进后，我们得到的最优解为两步确定假币的相对轻重并且将问题规模缩小到1/4（一个较紧的上界）。 下面展示探究改进过程： 第一阶段：直接运用第一节中梁晓军同学的方法，在确定了轻重之后，采取三分策略，这显然优于原来的方法，也在两步即确定了轻重，但是最坏情况下，问题只缩小到1/2。 第二阶段：由于“知道假币的相对轻重”条件下三分思想的应用，可以想到用类似于三分的思想来确定轻重。先将金币分为三份，如果有分不尽的情况则将剩下的1个或2个单独拿出，为了方便起见将三份标号为1、2、3，称量1、2，称量2、3，这时有五种不同情况（由于对称性，已将情况简化）。 1). 1<2, 2>3 =>假币重，在2中 2). 1<2, 2=3 =>假币轻，在1中 3). 1>2, 2=3 =>假币重，在1中 4). 1>2, 2<3 =>假币轻，在2中 5). 1=2, 2=3 =>假币在分剩的金币中（由于分剩组为1或2个，显然小于总体三分，可以在最坏分析下不考虑） 这样，最坏情况下问题规模可缩小到原问题的1/3，同时确定轻重。 第三阶段：假币分剩在原来一直在最坏分析时被忽略，但这里却能给我们很大的启示。在前面的二分法、三分法解决问题的过程中，一直在利用缩小各组间的差距来减少最坏情况的问题规模。那么在这里我们是不是可以适当增加分剩组的数量来增大最坏情况下问题规模的缩小幅度呢？答案是，可以的。但是我们无法准确确定究竟分剩组是多少时可以不影响最坏分析，那么我们不妨将金币分为4组，第四组可以适当小于前三组，但要求与其他组的差值尽可能的小，这样，就可以把问题规模缩小成 。但是，这样显然会影响影响最坏分析，不过类似极端原理，这却是一个较紧的下界。 当此步做完后，问题轻松化归到问题1（知道假币的相对轻重的情况），用 步解决剩下的金币。为了尊重可行性，下面利用第二阶段得到的方法分析： 这时对这种方法进行分析，有最大步数M： M= +2 = 又因为当且仅当存在k∈N*使得 3k< （即在上取整时跨越某个3的整数次幂，显然这是不可能的，下面给出数学证明）时 > ，然而， 假设存在这样的k，那么3k< ，3k∈N*，这与 的定义相矛盾！ 所以，M= +2 EMBED Equation.KSEE3 \* MERGEFORMAT = 综合前面的式子，有M= （这样变型，有利于后面的比较）-----------** 同理我们可以得出第三阶段分析的下界 ，可以看出两者相差极小，所以用此分析是有意义的。 然而，这时我们仍然无法证明此方法的最优性。这引起了我的思索，是否还存在有更优的方法呢？通过查阅相关资料，一种与我的分析思路所不同的方法出现了，下面是此方法的介绍以及我对其所做的分析。 【资料】（摘自Information Theory, Inference, and Learning Algorithms by David J.C. MacKay中第四章第一节p69 图4.2） Figure 4.2. An optimal solution to the weighing problem. At each step there are two boxes: the left box shows which hypotheses are still possible; the right box shows the balls involved in the next weighing. The 24 hypotheses are written 1+，……，12 +, with, e.g., 1+ denoting that is the odd ball and it is heavy. Weightings are written by listing the names of the balls on the two pans, separated by a line; for example, in the first weighing, balls 1, 2, 3, and 4 are put on the left-hand side and 5, 6, 7, and 8 on the right. In each triplet of arrow the upper arrow leads to the situation when the left side is heavier, the middle arrow to the situation when the right side is heavier, and the lower arrow to the situation when the outcome is balanced. The three points labeled * correspond to impossible outcomes. 【资料分析】 这种方法揭示了不知轻重称量的本质，即通过+、- 标志出2N中可能，然后步步三分，将1+与1-和2+做同样对待。而非像上文问题分析中那样，先确定出相对轻重（实际上是先二分），使得天平的三种状态没有的到充分利用。这也正是此方法的妙处——不知轻重时，仍然可以将情况缩小至1/3！即若天平不平衡（不妨设为右倾），则只可能在右边有重的假币或左边有轻的假币，虽然金币数只减少至2/3，但实际上每个1/3份只有原来所有可能性的一半。当然，大家可能会怀疑N*2后是否还保持这最优的性质，这点相信在看完后面的最优性证明后，会有更深的理解。 资料中是针对12个球的问题，与金币问题如出一辙，我们可以是否可以推广到N呢？ 如果可以，我们就能很简单得出步数M= = ，与上面的式（**）对比，可以看出这是优于我上面的做法的。 但是，这个差别还是很小的，当我们将N=27（甚至N=12）带入时是没有差别的，求得M=4。 通过设计程序，借助计算机运算，我们通过观察和计算机统计，对于任意的N两式差别小于等于1，对于大部分N两式相等，而随着N的增大，M变化的临界点对于我的方法是要比资料中方法略早出现的，在两个临界点之间的值是两者差1的部分，这个差值部分随着N的增大而增大（近似于指数级）。 其原因在于上取整时，对于越大的N，log的变化速度越小，于是常数的差别对于整体式子的影响就不断增加。i.e. 当log3N+log39/4到达一个整数时，log3N+log32要到达这个整数是靠log3N的增加来补偿的，由于两个常数差值一定，但是log3N增长速度变慢，所以N需要增长更多才能达到目标整数，其速度大约是log的反函数速度，即指数级。但是，由于原来两式相等，显然这个N的增长使得log3N的增长不会超过1，于是这时的两式开始相等。这实际上是证明了上述观察结论。 值得说明的是，在计算机中处理浮点数据的能力是有限，所以会在利用换底公式进行对数运算时，造成精度丢失，例如在c++中(ceil()表示上取整)，(int)ceil(log(ceil(N/4))/log(3))+2 (这里是阶段四中的上界分析)，当N=15时，算得我的方法需要步数为3优于了资料中方法。这导致了我长时间的困惑（认为上述分析和将要提出的证明出现了问题），但是通过观察式子的运算可以发现log(ceil(i/4))与log(3)的差值非常小，超过了c++中double浮点型的精度范围，导致两值在分步计算后出现了在double精度下相等的情况（同时等于1.09861），这使得其商等于1（正确值应为略微大于1），在ceil上取整后就与正确值相差了1.解决这一问题，我们可以利用数学对数的公式，将计算公式变形至(int)ceil(log(ceil(i*i/16))/log(9))+2，这样由于先经过乘方运算，两数差值变大，误差会减小，经过检验这种方法在减小误差方面是可行的。 改进前： 改进后 然而，这一切是建立在推广成立的基础上的，而且实际上我们只能保证资料中方法在N的一部分取值中该方法成立，下面我们来讨论这个问题： 【推广】（以下是对于N稍大的情况，N 4） 此问题的推广实际上是困难重重。例如，考虑N=4的情况，在第一步的称量中，我们无法找到找到一种方法使得最坏情况下问题规模缩小1/3（缩小到1/3是指对其问题规模最接近的3的整数次幂的1/3，显然这是三分所必须的）的方法。 不过值得庆幸的是，如果我们解决的第一步问题的三分，那么下面的所有步骤均能正常进行。这是因为用归纳法可以证明到，经过排除之后，拥有+号金币的集合（下简称“加集”）要么与-号金币的集合（下简称“减集”）相等，要么没有交集。对于前者，我们可以取其中2/3与已被排除的同等数量的金币称量，最坏情况下排除至原规模的1/3（这里可以是最接近1/3，利用与前面处理不能整分问题相同的方法，由于方法较多，且占篇幅较大，此处略去，下同.但是读者可以放心，这种方法是一定可以解决问题的，这在我做出的小程序（其中详细考虑了非整分的处理问题）得以验证）。对于后者，如果加集和减集元素数量的最小值大于或等于总问题规模的1/3，那么各取1/3总问题规模数量的加集元素和减集元素，尽量均匀地分到天平两侧，若不平衡，则显然有天平上有一半可能可以排除，没有称量的金币可以排除（e.g.1+ 2+ 3+ 4+ 5- 6- 7-，那么称量1.5vs2.6 若左倾，则只可能是1+，6-），若平衡则是没有称量的1/3部分情况具有可能；如果加集和减集元素数量的最小值小于总问题规模的1/3，那么一定存在一个集合元素数量大于总问题规模的2/3，那么将其分成两份，置于天平两侧，这样很容易就可排除至的1/3。 我们来看一下N=3k型问题，显然，将其等分为三组，称量其中两组，可以将问题规模化为原来的1/3。 对于N=3k+1型，可以以3k型作为原型，显然问题增加了2种可能，经过分析可知当且仅当3ceil(log32(3k+1))-1-6k/3 2,此3k+1型问题可以被正确解决（正确是指第一步能排除掉2/3的可能性） 6+6k=2[3(k+1)], log32[3(k+1)], = 这时问题化为，当且仅当此3k+1型问题理论推算出的步数等于它的下一个3k型问题的步数（即N增2），那么此3k+1型问题可以被此方法正确解决。我们可以通过计算机程序计算出的轻松找出可以解决的3k+1型问题，由于步数增长十分慢，所以这种方法可以解决绝大部分3k+1型问题（在后面会将绝大部分去掉，解决所有3k+1型问题）。 对于N=3k+2型问题，我们可以用类似的方法分析，得出与3k+1型问题相同的结论：当且仅当此3k+2型问题理论推算出的步数等于它的下一个3k型问题的步数（即N增1），那么此3k+2型问题可以被此方法正确解决。然而，我们可以根据（3k+3）*2-（3k+2）*2=2，（3k+2）*2=3（2k+1）+1≡1 mod 3，“1+2=3”，所以不小于（3k+3）*2、（3k+2）*2的最小的3的整数次幂一定相同，那么。 = 恒成立！也就是说3k+2型问题均可被正确解决。（在下面的测试程序(程序一,test.cpp/exe)中可以被得以验证。） 下面举几个例子： 366为3k型数，由于3k+1型数364理论步数不等于366，所以不能解决（读者可以验证），而3k+2型的365理论步数等于366，则可以解决。 10可以被解决！4不能被解决，5可以！ 【小程序（程序二,trisection.cpp/exe）】（文末附代码） 为了进一步验证和解决问题，我利用c++编程语言借助上述算法写出了一个称量小程序。它主要是为用户规划出每步称量方法，并且询问此步天平的平衡状态(左倾输入0，右倾输入1，平衡输入2)，进一步进行规划判断，直到判断出结果，屏幕输出。由于时间关系，这个程序只经过了十几次的测试，并且没有涉及错误数据（即不存在输入的称量情况，如只剩12-，1+两种可能时，12与2称量，输入了“左倾”）的判断。 程序运行时的部分截图: 【小结】 将N=27，无论带入哪个公式，都可得出M=4，就是说我们又推翻了原来所给出的第2个结论，同样，我们还无法断言其最优性（不过，无论如何这两种方法可谓各有千秋，问题都可以被高效地解决，在金币数为1000时也只用7次！由于对数函数的增长性质，数据越大，效果越明显）。证明之! 【理论推理】（方便起见，我们只讨论N稍大时的情况，N非常小时读者可以自己验证—另外当N=2时由于对称性，我们无法确定假币） 由上一次证明可以知道，每种可能性均对应着一个k元序列（k M,M为最坏情况下的步数），如果与上次证明相同，每种可能性对应着唯一的一个序列，那么会有，3M 不同的序列数 N*2，所以对于整数M我们可以得出M 。 但是，情况确实如此么？我们不能只凭主观臆想来判断问题。在一段时间的怀疑与试验中，我们找到了其中的反例。因为这里的每种可能是已经隐含的附带了对假币相对轻重的判断（如确定出1+，我们不光的得知1是假币，同时知道它是重于其他金币的），然而这并非题目要求必须做到的。所以，在所有可能性中是可以存在一组相等的序列的（证明：可以证明这样的组一定没有参与任何称量的，那么显然如果存在两组是不可能不称量这两组中任意一组，而找出其中假币的），只要这两种可能性对应着同一枚金币（如12-，12+）。于是，我们可以得出M EMBED Equation.KSEE3 \* MERGEFORMAT 。 显然当且仅当N*2-1=3k，k∈N*时， < 。而这样的N是存在的，因为3k(任意k∈N*)为正奇数，所以3k+1为正偶数，于是能用N=（3k+1）/2（k∈N*）构造出这样的N。 即M 当且仅当N不为（3k+1）/2（k∈N*）型数时成立。 【推翻部分结论】 根据上述讨论，我们得知N=（3k+1）/2（k∈N*）时，前面的 仍然不是最优。 然而由于指数函数的增速之快，对于这样的N实际是很少的（N 109范围内小于20个）。其实对于此情况以及前面3k+1部分无法解决情况是可以根据具体情况做以简单改变就可以实现向最优跨越的，其中后者在下一下节被解决。 【证明后的新发现】 我们在对唯一序列进行讨论后，知道了不一定要判断出假币的相对轻重，那么在对资料中方法的推广时有了新的思路——归并一组代表同一枚金币的可能性（如下图4+，4-），那么对于所有的3k+1型数可以当做3k型解决。例如：N=4时， 【小结】 至此，我们完满解决并证明了绝大多数N时的“天平问题”，对于极少数的情况（109小于20个）由于篇幅问题暂不讨论。 【天平问题反思】 实际上，天平是具有三分结构的，因为对于每步称量来说，天平总存在有三种状态。这点是问题优化的核心和本质，而对它的忽略也是原结论错误的主要原因。正如本节的题目所讲，三分方可用尽天平力，我们可以从判断的不同答案个数（对于天平是平衡状态）的排列与问题的子元素相对应的角度来看n分问题，这里三分法自然就是利用了三种天平状态与不同问题元素的对应来完成了问题优化和证明。这种n分问题的本质认识，对于证明的思路尤为重要！ 同时，我们也应该从两次错误中看到，数学证明的重要意义。在日常学习中，我们应该增加缜密思维的培养，提高探究意识。 解决一道算法与数学相结合的问题--Ordered Fractions 在这段难得的探究经历以后，我们的思维和技巧上有多少进步？ 这道题目上我们作为一道“测试”，检验一下我们的收获。同时，这是一篇并不常见的的对此题数学方法比较完整的分析。曾经在我的此题解决过程中，多次查阅过相关题解，但是没有找到一篇具有完整的分析、证明的文章。（当然，在“前辈”的文章中我得到了很大的启发。） 【问题描述】（题目选自usaco题库，中文版译题由nocow网站提供） 输入一个自然数N,对于一个最简分数a/b（分子和分母互质的分数）,满足1 b N,0 a/b 1,请找出所有满足条件的分数。 这有一个例子，当N=5时，所有解为： 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1 给定一个自然数N，1 n 160，请编程按分数值递增的顺序输出所有解。 注：①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。 【问题分析】（参考了IMO2000训练材料：法里数列，但是对其内容有较大的独创性改变，使其适应于本题的算法分析和证明） 由于本题的问题规模很小，所以直接运用枚举搜索，是一道非常简单的题目。 然而，在usaco的analysis中有一个非常吸引人的数学方法，后来经过查阅相关资料知道这种方法为法理数列的应用。 我们首先从0/1和1/1开始作为两个边界值，将两个边界值的分子相加作为新分数的分子、两个分界值的分母相加作为新分数的分母，我们把这个新的分数叫作这个区间（以0/1、1/1为边界的区间）“中点”。再次把由“中点”分为的两个区间，（递归地）做同样的处理，知道本区间内分母超过N。下图是一个例子： （图片摘自nocow网站的题解） 这个算法是高效而且巧妙的，然而我们会对此算法的正确性产生极大的怀疑。这时我们就需要相关的数学知识来提供支持，下面给出算法正确性的证明。 【定义】法理数列Fn：在区间[0，1]中分母小于n的既约分数的集合 中点：a/b,c/d∈Fn,则我们称a+c/b+d为a/b，c/d中点。 【引理1】中点大于左边界，小于右边界。（i.e. 0/1<1/2<1/1…）即a/b,c/d∈Fn且a/b1) c=ndk。于是， a+c/b+d=bk+ndk/b+d=k[(b+nd)/b+d] ---* 显然，我们只需找出(b+nd)/b+d大小关系即可。因为n>1, b+d/b+d=1 <(b+nd)/b+d< nb+nd/b+d=n 所以k1,m,n,k∈Z），则knc-kmd=1,nc-md=1/k,显然有nc-md∈Z，然而k>1且 k∈Z，矛盾！那么对于满足n max{b,d}的Fn，一定有a/b，c/d∈Fn 假设存在a/b0，cn-md>0,又因为bm,an,cn,md∈Z,所以bm-an 1,cn-md 1. 又因为bc-ad=1,所以nbc-nad=n => n=b(nc-md)+d(bm-an) b+d，这与n n+1处回溯，后者在b+d>n处回溯。显然前者比后者只多了分母b+d=n+1的情况。因为Fn是被正确解决的，那么对于任意两个连续（即不存在比较小者大，较大者小的分数）分数a/b,c/d，有b+d>n，max{b,d}=< n（由引理4），如果b+d=n+1,那么m/n=a+c/b+d，由引理3知道其满足bm-an=1,cn-md=1，又因为max{a，n}=max{n,b}=n，且m+b=b+d+b>n+b n+1，m+d=b+d+d>n+d n+1，所以在Fn+1，m/n与a/b，c/d之间没有其他分数；如果b+d>n+1,因为有 max{b,d}=< n using namespace std; int n; ofstream fout("frac1.out"); ifstream fin("frac1.in"); void find(int a[2][2]){ if((a[0][1]+a[1][1])>n) //a[i][0]记录分子，a[i][1]记录分母 return; int temp[2][2]; //temp记录中点分成的左侧区间 temp[i][0]记录分子，temp[i][1]记录分母 int temp2[2][2]; //temp2记录中点分成的右侧区间 temp[0][0]=a[0][0];temp[0][1]=a[0][1]; temp2[1][0]=a[1][0];temp2[1][1]=a[1][1]; temp[1][0]=a[0][0]+a[1][0];temp[1][1]=a[0][1]+a[1][1]; temp2[0][0]=a[0][0]+a[1][0];temp2[0][1]=a[0][1]+a[1][1]; find(temp); fout<>n; //输入金币数n int temp[2][2]={{0,1},{1,1}}; fout<<"0/1"< #include using namespace std; int qspace[2][10000],len[2]={0,0};//0=heavy 1=light int n; int de[10000],le=0; int timed=0; bool cequal(){ if(len[0]!=len[1]) return false; for(int i=0;i!=len[0];i++){ if(qspace[0][i]!=qspace[1][i]) return false; } return true; } void find(){ int res; //0=left 1 right 2 balanced if(n%3==0){ for(int i=1;i<=(n/3);i++){ cout<>res; timed++; if(res==2){ for(int i=0;i!=2;i++){ for(int k=0;k!=n/3;k++){ qspace[i][k]=qspace[i][(n/3)*2+k]; }len[i]=n/3; } for(int i=1;i<=n/3*2;i++){ de[le++]=i; } } if(res==0){ len[0]=n/3; for(int i=0;i!=n/3;i++){ qspace[1][i]=qspace[1][n/3+i]; } len[1]=n/3; for(int i=1;i<=n/3;i++){ de[le++]=i+n/3*2; } } if(res==1){ len[1]=n/3; for(int i=0;i!=n/3;i++){ qspace[0][i]=qspace[0][n/3+i]; } len[0]=n/3; for(int i=1;i<=n/3;i++){ de[le++]=i+n/3*2; } } } if(n%3==1){ if(ceil(log(2*n)/log(3))!=ceil(log(2*(n+2))/log(3))){ cout<<"NO!"<>res;timed++; if(res==2){ for(int i=0;i!=2;i++){ for(int k=0;k<=n/3;k++){ qspace[i][k]=qspace[i][(n/3)*2+k]; } len[i]=n/3+1; } for(int i=1;i<=n/3*2;i++){ de[le++]=i; } } if(res==0){ len[0]=n/3; for(int i=0;i!=n/3;i++){ qspace[1][i]=qspace[1][n/3+i]; } len[1]=n/3; for(int i=1;i<=n/3+1;i++){ de[le++]=i+n/3*2; } } if(res==1){ len[1]=n/3; for(int i=0;i!=n/3;i++){ qspace[0][i]=qspace[0][n/3+i]; } len[0]=n/3; for(int i=1;i<=n/3+1;i++){ de[le++]=i+n/3*2; } } } if(n%3==2){ if(ceil(log(2*n)/log(3))!=ceil(log(2*(n+1))/log(3))){ cout<<"NO!"<>res;timed++; if(res==2){ for(int i=0;i!=2;i++){ for(int k=0;k!=n/3;k++){ qspace[i][k]=qspace[i][(n/3)*2+2+k]; }len[i]=n/3; } for(int i=1;i<=n/3*2+2;i++){ de[le++]=i; } } if(res==0){ len[0]=n/3+1; for(int i=0;i<=n/3;i++){ qspace[1][i]=qspace[1][n/3+1+i]; } len[1]=n/3+1; for(int i=3;i<=n/3+2;i++){ de[le++]=i+n/3*2; } } if(res==1){ len[1]=n/3+1; for(int i=0;i<=n/3;i++){ qspace[0][i]=qspace[0][n/3+1+i]; } len[0]=n/3+1; for(int i=3;i<=n/3+2;i++){ de[le++]=i+n/3*2; } } } while(len[0]+len[1]>2){ if(cequal()){ int f=((int)ceil(len[0]/3.0*2)); for(int i=0;i!=f;i++) cout<>res;timed++; if(res==2){ for(int k=0;k!=2;k++){ for(int i=f;i!=len[k];i++){ qspace[k][i-f]=qspace[k][i]; }len[k]=len[k]-f; } } if(res==0){ len[1]=f; len[0]=0; } if(res==1){ len[0]=f; len[1]=0; } } else{ int f=(int)ceil((len[0]+len[1])/3.0); int w=(int)((len[0]+len[1])/3.0); if(len[0]<=w){ for(int i=0;i!=w;i++){ cout<>res;timed++; if(res==2){ for(int i=w*2;i!=len[1];i++) qspace[1][i-w*2]=qspace[1][i]; len[1]=len[1]-(w*2); } if(res==0){ for(int i=w;i!=w*2;i++) qspace[1][i-w]=qspace[1][i]; len[1]=w; len[0]=0; } if(res==1){ len[1]=w; len[0]=0; } } else if(len[1]<=w){ for(int i=0;i!=w;i++){ cout<>res;timed++; if(res==2){ for(int i=w*2;i!=len[0];i++) qspace[0][i-w*2]=qspace[0][i]; len[0]=len[0]-(w*2); } if(res==0){ len[0]=w; len[1]=0; } if(res==1){ for(int i=w;i!=w*2;i++) qspace[0][i-w]=qspace[0][i]; len[0]=w; len[1]=0; } } else{ int w=(int)((len[0]+len[1])/3.0); int f=(int)ceil((len[0]+len[1])/3.0); int m=0,n=1; if(len[0]>res;timed++; if(res==2){ for(int i=0;i!=len[m]-f;i++){ qspace[m][i]=qspace[m][f+i]; } len[m]=len[m]-f; for(int i=0;i!=len[n]-(w/2+(int)ceil(f/2.0)-(f-(int)ceil(f/2.0))+w/2);i++){ qspace[n][i]=qspace[n][w/2+(int)ceil(f/2.0)-(f-(int)ceil(f/2.0))+w/2+i]; } len[n]=len[n]-(w/2+(int)ceil(f/2.0)-(f-(int)ceil(f/2.0))+w/2); } if(res==0){ if(m==0){ len[0]=(int)ceil(f/2.0); for(int i=0;i!=w/2+(int)ceil(f/2.0)-(f-(int)ceil(f/2.0));i++){ qspace[1][i]=qspace[1][w/2+i]; } len[1]=w/2+(int)ceil(f/2.0)-(f-(int)ceil(f/2.0)); }else{ len[0]=w/2; for(int i=(int)ceil(f/2.0);i!=f;i++){//---------------- qspace[1][i-(int)ceil(f/2.0)]=qspace[1][i]; } len[1]=f-(int)ceil(f/2.0); } } if(res==1){ if(m==0){ len[1]=w/2; for(int i=0;i!=f-(int)ceil(f/2.0);i++){ qspace[0][i]=qspace[0][(int)ceil(f/2.0)+i]; } len[0]=f-(int)ceil(f/2.0); }else{ len[1]=(int)ceil(f/2.0); for(int i=0;i!=w/2+(int)ceil(f/2.0)-(f-(int)ceil(f/2.0));i++){ qspace[0][i]=qspace[0][w/2+i]; } len[0]=w/2+(int)ceil(f/2.0)-(f-(int)ceil(f/2.0)); } } } } } if(len[0]+len[1]==2){ if(len[0]==len[1]){if(qspace[0][0]==qspace[1][0]) {cout<<"result: "<=1){ cout<>res; timed++; if(res==2){len[0]--;if(len[0]>0) qspace[0][0]=qspace[0][1];} else if(res==0){cout<<"result:"<>res; timed++; if(res==2){len[1]--;if(len[1]>0) qspace[1][0]=qspace[1][1];} else{cout<<"result:"<>n; for(int i=0;i!=2;i++){ for(int k=1;k<=n;k++){ qspace[i][len[i]++]=k; } } find(); cout<