NC200311. H-绵羊的银币
描述
f[0] = 0 f[1] = 1 f[n] = f[n/2] + f[n/4] (n>=2)
输入描述
第一行一个整数T ( 1 <= T <= 250000 ) ，表示T次询问。
下面T行，每行一个整数n ( 0 <= n <= 1018 ) ，表示当前需要购买多少只绵羊
由于输入输出过多，请使用scanf和printf，否则容易超时
n极大，log2(n)精度不够，请不要使用<math.h>的任何log函数，否则容易Wrong Answer
输出描述
对于每个询问,输出需要支付的银币数量
示例1
输入:
4 1 2 3 4
输出:
1 1 1 2
C(clang11) 解法, 执行用时: 102ms, 内存消耗: 3540K, 提交时间: 2020-12-05 18:08:12
#include<stdio.h>
int main()
{
long long i,j=0,k=0,t,n,l,a[10000];
a[0]=1,a[1]=2;
scanf("%lld",&t);
for(l=0;l<t;l++,k=0){
scanf("%lld",&n);
if(n==0){
printf("0\n");
continue;}
for(i=4;i-1<n;i=i*2)
k++;
for(i=2;i<=k;i++)
{
a[i]=a[i-1]+a[i-2];
}
printf("%lld\n",a[k]);
}}
C++11(clang++ 3.9) 解法, 执行用时: 565ms, 内存消耗: 3688K, 提交时间: 2019-12-07 21:15:32
#include<iostream>
#include<cstring>
using namespace std;
long long t,n,i,f[200];
int main()
{
f[1]=f[2]=1;
for(int i=3;i<=100;i++)f[i]=f[i-1]+f[i-2];
cin>>t;
while(t--)
{
cin>>n;
for(i=0;(1ll<<i)-1<n;i++);
cout<<f[i]<<endl;
}
}
C++14(g++5.4) 解法, 执行用时: 604ms, 内存消耗: 3576K, 提交时间: 2019-12-07 21:36:58
#include<bits/stdc++.h>
using namespace std;
long long t,n,i,f[200],sum=1;
int main()
{
f[1]=f[2]=1;
for(int i=3;i<=100;i++)f[i]=f[i-1]+f[i-2];
cin>>t;
while(t--)
{
cin>>n;
for(i=0;(sum<<i)-1<n;i++);
cout<<f[i]<<endl;
}
}
Python3(3.5.2) 解法, 执行用时: 3661ms, 内存消耗: 6604K, 提交时间: 2019-12-15 16:47:54
d=[0,1,1] for i in range(3,61): d.append(d[i-2]+d[i-1]) for i in range(int(input())): n = int(input()) j=0 while((1<<j)-1<n):j+=1 print(d[j])
pypy3 解法, 执行用时: 1131ms, 内存消耗: 34416K, 提交时间: 2021-09-14 22:06:01
d=[0,1]
for i in range(2,61):d.append(d[i-2]+d[i-1])
for i in range(int(input())):
n=int(input())
print(d[len(bin(n))-2]if n else 0)