NC21849. 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
pypy3(pypy3.6.1) 解法, 执行用时: 41ms, 内存消耗: 18780K, 提交时间: 2021-04-15 20:37:24
import sys for line in sys.stdin: a =line.split() b,d = map(int,a) m = 3 if(b <=2): print('No') continue for i in range(2,16): m*=3 if b <= (m-3)/2: break if i <=d: print('Yes') else: print('No')
C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 228K, 提交时间: 2018-12-29 20:22:10
#include <stdio.h> #include <math.h> int main(){ int x,y; while(scanf("%d",&x)!=EOF){ scanf("%d",&y); if(x<=2) printf("No\n"); else if((pow(3,y)-3)/2>=x) printf("Yes\n"); else printf("No\n"); } }
Python3(3.5.2) 解法, 执行用时: 28ms, 内存消耗: 3424K, 提交时间: 2019-02-04 02:44:27
while True: try: n,m=map(int,input().split()) if n==2 or (pow(3,m)-3<2*n): print('No') else: print('Yes') except: break;
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2020-03-13 11:39:23
#include<bits/stdc++.h> using namespace std; int main() { int n,m; while(cin>>n>>m) printf("%s\n",n==2||ceil(log(2*n)/log(3.0))>m?"No":"Yes"); return 0; }