L1-7拼接梯子

NC205456. L1-7拼接梯子

描述

这一天，StarrySky 的梯子断裂，不能像以往一样在天际自由翱翔了，为此，他十分苦恼，甚至失去了对宝可梦的热爱。

幸运的是，kcxz 为他拼凑出了一把更加牢固的梯子，但为了回报，StarrySky 必须回答 kcxz 提出的关于梯子的一个问题，否则，kcxz 将狠心离去。

问题如下：

已知 kcxz 只拥有 k 段构造梯子的材料，长度分别为 $2^1, 2^2, ..., 2^k$ ，且为了构造出的梯子效果更好，这 k 段材料不能裁剪，同时，在拼接过程中，材料之间不能覆盖，即：如果选择长度为 $2^1, 2^2$ 的两端拼接，则拼接出来的长度只能是 6.

同时又已知 StarrySky 想要一把长度为 L 的梯子。

kcxz 希望 StarrySky 在 $1\ s$ 内回答出，这 k 段材料是否能够拼接成长度为 L 的梯子，如果可以，还想要 StarrySky 同时回答选择的最长的材料长度为多少。

输入描述

两个用空格隔开的正整数 k, L，表示 kcxz 拥有的材料数量以及 StarrySky 想要的梯子长度。

输出描述

如果能用这 k 段材料拼接出长度为 L 的梯子，则输出 "Yes"（不含引号），并在第二行输出一个正整数，表示选择的最长材料的长度，否则输出 "No"（不含引号）。

示例1

输入:

3 10

输出:

Yes
8

说明:

选择 $2^1, 2^3$ 这两段材料即可拼接出长度为 10 的梯子，其中最长的材料长度为 $2^3 = 8$ .

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 380K, 提交时间: 2020-09-25 19:53:29

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll n,l;
	cin>>n>>l;
	if(l&1)
	{
		cout<<"No";
		return 0;
	}
	int x=0;
	while(l)
	{
		l/=2;
		x++;
	}
	if(n+1<x)
		cout<<"No";
	else
	cout<<"Yes"<<endl<<(ll)pow((ll)2,x-1);
}

C++(clang++11) 解法, 执行用时: 12ms, 内存消耗: 480K, 提交时间: 2021-05-06 12:56:09

#include <bits/stdc++.h>
int main()
{
	long long k,l,i,one=1;
	scanf("%lld%lld",&k,&l);
	for(i=60;i>=0;i--) if((one<<i)&l) break;
	if(i>k||l&1) printf("No\n");
	else printf("Yes\n%lld",one<<i);
}

Python3(3.5.2) 解法, 执行用时: 26ms, 内存消耗: 3536K, 提交时间: 2020-05-03 15:50:18

import math

k,l=map(int,input().split(' '))

if l<=2**(k+1)-2 and l%2==0:
    print("Yes")
    print(2**int(math.log(l,2)))
else:
    print("No")