1273. 袁绍的刁难(recruitment.pas/cpp)
(File IO): input:recruitment.in output:recruitment.out
Time Limits: 1000 ms Memory Limits: 131072 KB
Description
黄巾之乱后，郭嘉到了袁绍的统辖地区，结果袁绍想给我们的郭嘉大大一个下马威，且正值他招募将领的时候，于是乎，袁绍就让郭嘉大大去替他招募将领。
这时候有很多很多的将领到袁绍处报到（别人家底厚，四世三公哪~~），每个将领的编号依次为1、2、3……N，第i个将领的武力值为3^(i-1)。
袁绍需要我们的郭嘉大大招纳任意个将领，而郭嘉选中的将领有一个“总武力值”为各个将领的武力值之和。例如：郭嘉这一次招募了第一个将领和第三个将领，那么“总武力值”为1+9=10。
袁绍想知道，他可以获得的第k大的“总武力值”是多少，请你帮助我们的郭嘉大大告诉袁绍这个第k大的“总武力值”。
从文件中读入k，输出郭嘉能够获得的，第k大的“总武力值”。
Input
数据包含n+1行，第一行读入n(n≤100)。以下n行每行包含一个k。
Output
输出包含n行，每行输出一个对应的结果。
Sample Input
1
7
Sample Output
13
Data Constraint
Hint
样例说明：
郭嘉能够拿到的总武力值从小到大为1、3、4、9、10、12、13……所以第7大的总武力值是13。
对于50%的输入文件，有k≤5000。
对于100%的输入文件，有k≤2^31-1。
这道题其实将k转成二进制，然后每一位乘3^(i-1)就是答案了（对不起各位，我"吸"了氧原子（O1）、氧气（O2）和臭氧（O3）以及Ofast，和快读、快写，不过这也可以不用）
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
using namespace std;
long long int a[33],n,k,b[33],tou,xc,ans;
inline long long read()
{
register long long int zzj=0,zyf=1;
register char fqy=getchar();
while(fqy<'0'||fqy>'9'){if(fqy=='-')zyf=-1;fqy=getchar();}
while(fqy>='0'&&fqy<='9'){zzj=zzj*10+fqy-'0';fqy=getchar();}
return zzj*zyf;
}
inline void write(register long long int fqy)
{
if(fqy<0)putchar('-');
if(fqy>9)write(fqy/10);
putchar(fqy%10+'0');
}
int main()
{
// freopen("recruitment.in","r",stdin);
// freopen("recruitment.out","w",stdout);
a[0]=1;
for(long long int i=1;i<=32;i++)
{
a[i]=a[i-1]*2;a[i-1]--;
}
b[1]=1;
for(long long int i=2;i<=32;i++)
{
b[i]=b[i-1]*3;
}
n=read();
for(long long int w=1;w<=n;w++)
{
k=read();
tou=32;xc=k;ans=0;
while(xc>0)
{
for(long long int i=1;i<=tou;i++)
{
if(a[i-1]<xc&&xc<=a[i])
{
tou=i;break;
}
}
ans+=b[tou];
xc-=a[tou-1]+1;
}
write(ans);
printf("\n");
}
return 0;
}