欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1273. 袁绍的刁难

程序员文章站 2024-03-17 13:13:04
...

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

Hint

样例说明:
郭嘉能够拿到的总武力值从小到大为1、3、4、9、10、12、13……所以第7大的总武力值是13。
对于50%的输入文件,有k≤5000。
对于100%的输入文件,有k≤2^31-1。


Solution

根据找规律发现,从第二个数开始,当前这个数比前一个数了:1,2,1,5,1,2,1,14,1,2,1,5,1,2,1,41,1,2,1,5,1,2,1,14......

可以发现:

  • 去掉所有的1:2,5,2,14,2,5,2,41,2,5,2,14,2,5,2......
  • 再去掉所有的2:5,14,5,41,5,14,5......
  • 再去掉所有的5:14,41,14.....

所以,规律就是,我们每次去掉的数即为上次去掉的数*3-1。然后计算出每次我们去掉的数出现的次数,加上即可。

 

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int n=11,a[10000];
int m(int x,int y){
	if(y==0) return 1;
	int sum=1;
	for(int i=1;i<=y;i++) sum*=3;
	return sum;
}
void dg(int k,int s){
	if(k>n){
		if(s) a[++a[0]]=s;
		return;
	}
	dg(k+1,s);
	dg(k+1,s+m(3,k-1));
}
int main(){
	freopen("recruitment.in","r",stdin);
	freopen("recruitment.out","w",stdout);
	scanf("%d",&n);
	dg(1,0);
	sort(a+1,a+1+a[0]);
	for(int i=1;i<=a[0];i++) printf("%d\n",a[i]);
	return 0;
}


作者:zsjzliziyang 
QQ:1634151125 
转载及修改请注明 
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/86670475