第四版杀拉五题串烧

42929

19天，数字代表房间号，按顺序1 3 2 4 3 5 4 6 5 7 9 8 10 9 11 10 12 11 13
补充:22天，1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13
补充:91天， 13天+ 12天+  11 天 +10 天+9 8 7 6 5 4 3 2 1

22568

1.分成44和1974两堆,然后把44的都反过来.
2.改成每根都是1然后需要确定1/32吧..
第一根两头烧同时剩下的都烧一头..1/2后第一根烧完剩下的都剩1/2..
同理第二根烧两头,使剩下的剩1/4..
同理烧完第三根,第四五根剩1/8..
同理烧完第四根,第五根剩1/16..
同理烧完第五根,这段时间就是1/32..
3.(推广为总共n(n>2且2|n-1)间.)显然2,3,...,n-1,n-1,n-2,...,2为一个可行解,对应天数为2n-4.
下面证明这是最优解.

记n个位置为S={1,2,...,n}.
显然,通过查询,我们会获取到"对方某时刻不可能在某些位置"这样的信息.
于是,任何时刻之前的查询获得的信息可以等价于S的一个子集,表示此时对方有可能存在的位置.
(进一步,这个子集也是充分的,只要推理出的结论一样,之前经过多少次/哪些查询对后续的策略没有影响.)
记a[k]为第k次查询的位置,P[k]为第k次查询后所有对方此时可能存在的位置组成的集合.
记f(X)={x±1|x∈X}∩S.
显然P[k+1]=f(P[k])\{a[k+1]},P[0]=S.目标是求最小的k使得存在a[k]使得|P[k]|=1.
记Q[k]={x|x∈P[k]∧2|x},R[k]={x|x∈P[k]∧2|x-1},p[k]=|P[k]|,q[k]=|Q[k]|,r[k]=|R[k]|.
记所求最小值为m.

引理I.|f(Q[k])|≥q[k]+1.
记Q[k]={u[1],u[2],...,u[t]},2≤u[1]<u[2]<...<u[t]≤n-1,则1≤u[1]-1<u[1]+1<u[2]+1<...<u[t]+1≤n,且{u[1]-1,u[1]+1,u[2]+1,...,u[t]+1}⊆f(Q[k]).
显然等号成立当且仅当2=u[2]-u[1]=u[3]-u[2]=...=u[t]-u[t-1].

引理II.若R[k]≠{1,3,...,2a+1},则|f(R[k])|≥r[k].
记R[k]={u[1],u[2],...,u[t]},v∈{1,3,...,n}\R[k],u[1]<...<u[i]<v<u[i+1]<...<u[t],则2≤u[1]+1<...<u[i]+1<v<u[i+1]-1<...<u[t]-1,且{u[1]+1,...,u[i]+1,u[i+1]-1,...,u[t]-1}⊆f(R[k]).

由引理I和II,若R[k]≠{1,3,...,n},则p[k+1]+1≥|f(P[k])|=|f(Q[k])|+|f(R[k])|>q[k]+r[k]=p[k],p[k+1]≥p[k].
若R[k]={1,3,...,n},则|f(R[k])|=|{2,4,...,n-1}|=r[k]-1,p[k+1]+1≥|f(P[k])|=|f(Q[k])|+|f(R[k])|≥q[k]+r[k]=p[k],p[k+1]≥p[k]-1.

综上,p[k+1]-p[k]≥-1,等号成立当且仅当R[k]={1,3,...,n}∧Q[k]={2a,2a+2,...,2b}∧a[k+1]∈f(P[k])(记为条件H[k]).
此时,P[k+1]=f(P[k])\{a[k+1]}={2,4,...,n-1}∪{2a-1,2a+1,...,2b-1,2b+1}\{a[k+1]}.
若H[k+1]仍成立,则Q[k]={2,4,...,n-1}∧a[k+1]∈{2,n-1}∧(P[k+1]=S\{2}∨P[k+1]=S\{n-1}),故p[k+1]=n-1.

综上,p[k+1]-p[k]≥-1,且若p[k+1]≠n-1,则p[k+1]-p[k]和p[k+2]-p[k+1]不同时为-1.

由p[0]=n,p[m]=1知{k|p[k]=n-1}≠∅.
记t=max{k|p[k]=n-1}≥1.
由p[t]=n-1,p[m]=1知p[t+1]-p[t],p[t+2]-p[t+1],...,p[m]-p[m-1]中至少有(n-2)个-1,且其中没有相邻的-1.
故其中至少有(2n-5)个数,即m-t≥2n-5,m≥2n-5+t≥2n-4.

21457

第三题由Rubp和天马行空答对了
22天
查询方式是：2,3,4,5,...12,12,11,10...3,2


下面放出第四题

21457

A、B两人分别在两座岛上。B生病了，A有B所需要的药。C有一艘小船和一个可以上锁的箱子。C愿意在A和B之间运东西，但东西只能放在箱子里。只要箱子没被上锁，C都会偷走箱子里的东西，不管箱子里有什么。如果A和B各自有一把锁和只能开自己那把锁的钥匙，A应该如何把东西安全递交给B？

45480

A把药放进箱子，用自己的锁把箱子锁上。B再在箱子上加上自己的锁。运向A，A取下自己的锁。运向B，取出药物。

38004

如果挂锁的那个地方可以同时锁上两个锁的话
A先锁上，C送给B，B再把自己的锁锁上，C再送给A，A把自己的锁打开，C再送去给B

21457

果然这次的题目都更简单了
很快就到了第五题压轴
第四题回答正确

下面这是第五题
有40个苹果，其中有39个“好”苹果，1个“坏”苹果。有一台天平， 但没有砝码。
所有“好”苹果的重量都是一样的，“坏”苹果的重量和“好”苹果重量微小的区别。如何称4次，将“坏”苹果找出？
（该区别可以用天平称出）
（天平上一次可放多个苹果）

附加项：然而称出了问题，只有在所有称重都完成的情况下，才可以看到4次称重结果。

45480

3组14，14，12。编号1，2，3组
1，2称。（第一次称）
1)1，2不平衡。假设1轻
取1的苹果，分为7，7，放于两边（第二次称）
a)不平衡，则有问题的苹果是轻的。
将7个苹果分为3，3，1。称两次即可得有问题的苹果。
b)平衡，则有问题的苹果在2组，且是重的。
方法同1)a)。
2)平衡。则坏苹果在3组。


这里讨论3次称量确定12个苹果中的1个未知重量的坏苹果。
先分成3组,每组4个,标号1,2,3,
1)1放天平左,2放天平右
不平。
假设1组是轻的,把1组对半分,每组两个放到天平上称（第二次称）
a)平,则可知坏苹果在2组且重量比正常的重
b)不平，则可知在1组且为轻,第三次就很容易称出来了.
2)平。坏苹果在3组。
把第三组四个苹果编号A,B,C,D,若A与B不平衡（第二次称）,只须A与1组中一个好苹果比（第三次称）,如平,则B坏,不平,则A坏,且知道轻重.
A与B称若平衡（第二次称）,则坏苹果在C,D中,第三次只须把C与1组中的一个好苹果比（第三次称）,如平衡,则D为坏,如不平则C为坏,且知道轻重.

这楼答案有bug
这题用三进制做
我不想改答案了。

22568

4.不说了..熟知的私钥的解释..
5.随便码一个可行解吧..反正还是推圈常见的动规题..
记局面<a,b,c>表示"已知某a个中可能有重的或另外某b个中可能有轻的或另外c个可能有坏的(剩下的(40-a-b-c)个是好的)".显然任何时候的信息可以归结为酱紫的一个局面.
所求为<0,0,40>的策略.
记[a,b,c,d]为取出a个可能重的和b个可能轻的和c个可能坏的和d个已知好的.

1. I.[0,0,13,0]<[0,0,13,0]⇒<13,13,0>
   
2. i.[4,4,0]<[5,5,0]⇒<4,5,0>
   
3.   (I).[1,1,0]<[2,2,0]⇒<1,2,0>
   
4.    (i).[1,1,0]<[0,0,0]⇒<1,0,0>
   
5.    (ii).[1,1,0]>[0,0,0]⇒<0,1,0>
   
6.    (iii).[1,1,0]=[0,0,0]⇒<0,1,0>
   
7.   (II).[1,1,0]=[2,2,0]⇒<1,2,0>,同I.i.(I).
   
8. ii.[4,4,0]=[5,5,0]⇒<4,4,0>,弱于I.i.
   
9. II.[0,0,13,0]=[0,0,13,0]⇒<0,0,14>
   
10. i.[0,0,4]<[0,0,5]⇒<4,5,0>,同I.i.
    
11. i.[0,0,4]=[0,0,5]⇒<0,0,5>
    
12.   (I).[0,0,1]<[0,0,2]⇒<1,2,0>,同I.i.(I).
    
13.   (II).[0,0,1]=[0,0,2]⇒<0,0,2>
    
14.    (i).[0,0,1]<[0,0,0]⇒<1,0,0>
    
15.    (ii).[0,0,1]=[0,0,0]⇒<0,0,1>

复制代码

看不懂的别让我解释.反正也没人会细看.
小福利:懒得完全编程的可以使用

1. lambda (p,q,r),(a,b,c),(d,e,f):{(p-a-d,q-b-e,r-c-f),(a+c,e+f,0),(d+f,b+c,0)}

复制代码

辅助..
看不懂的别让我解释.反正也没人会细看.

21457

既然这么快就有写出来了，那就请大家顺便看下17L的题目里有个反白的附加条件吧