Problem G. Wpremig的称球问题

题目描述 

作为一个常规的面试题:用天平(只能比较,不能称重)从一堆共有x个的小球中找出其中唯一一个质量和其他不一样的,最少需要使用多少次天平。

Wpremig毕竟也是要准备实习的人了,所以他最近在研究这类经典面试题。

现在他想知道如果给你x个小球,其中(x-1)个小球的质量相等,称为标准球,有1个小球与标准球质量不同并且不知道是比其他的球轻还是重,和一个天平,最多称y次,能否找出那个质量不同的小球,并且告诉Wpremig这个小球的质量比标准球重还是轻?

对于天平 : 只能比较,不能称重,即每次可以在天平两边放任意个球,天平会平衡,或者向一边倾斜,平衡则表示两边质量相等,向一边倾斜则向下的一边质量较重。

输入描述:

多组数据,不超过100组。
每组数据包含两个正整数x,y(2<=x,y<=1000000)

输出描述:

对于每组数据,如果可以在最多称y次的情况下找出x个小球中那个质量不同的小球并且求出它的质量是比其他的小球重还是轻,则输出"Yes",否则输出"No"

示例1

输入

6 3

输出

Yes

首先给出结论:若称 y 次需要找出质量不同的球并且知道轻重,最多能称的球数量是 n=(3^k-3)/2

证明思路如下,依次证明引理:
引理一:
如果有 m 个球或者是标准或者比标准重,以及 n 个球或者是标准或者比标准轻以及至少 1 个标准球,则 k 次称量能够确定是哪个球的充要条件是:m+n≤3^k
引理二:
如果有 n 个球不知道是标准重量还是更轻还是更重,以及至少 1 个标准球,则 k 次称量能够确定是哪个球的充要条件是:n≤1/2(3^k+1)
引理三:
如果有 n 个球不知道是标准重量还是更轻还是更重,以及至少 1 个标准球,则 k 次称量能够确定是哪个球,以及这个球是更轻还是更重的充要条件是:n≤1/2(3^k−1)
引理一的充分性证明思路是:
令m=3i+j, n=3k+r。每边放 i 个可能重的,k 个可能轻的,然后 j,r=0,1,2 总共 9 种可能,
分类讨论一下可以递归解决。
必要性是显然的。
引理二的充分性证明思路是:
(3^k+1)/2个球,第一次(3^(k-1)+1)/2个球放左边,(3^(k-1)-1)/2个球加上标准球放右边,还余下(3^(k-1)+1)/2个第一次称量结束,要么平衡可以用递归证明,要么不平衡用引理证明。
引理三的充分性证明思路同理,区别在于余下(3^(k-1)-1)/2个球。
引理三的必要性证明思路与上面那个问题二相同
引理二的比较性证明就麻烦一些,不过思路还是类似。如果第一次称量不平衡要利用引理一,平衡的话递归。
最终两个问题的证明都需要单独讨论第一次称量,因为没有标准球可以借,并且数目比引理中少一,然后就可以利用引理的结论,通过类似的思路证明。

AC code

#include <bits/stdc++.h>
using namespace std;
int main(){
int x,y;
while (~scanf("%d%d",&x,&y)){
if (x <= 2){
puts("No");
continue;
}
long long now = 3;
int k;
for (k = 2 ; k < 15 ; ++k){
now *= 3;
if ((now-3)/2 >= x) break;
}
if (k <= y) puts("Yes");
else puts("No");
}
return 0;
} 

发表评论,支持MarkDown语法