首页 > ACM题库 > HDU-杭电 > HDU 2763-HOJ-The Two Note Rag-动态规划-[解题报告]C++
2014
02-14

HDU 2763-HOJ-The Two Note Rag-动态规划-[解题报告]C++

The Two Note Rag

问题描述 :

Since most computers are binary machines, both powers of two and problems that involve only two values are important to computer scientists. The following problem has to do with powers of two and the digits 1 and 2.Some powers of two as decimal values, such as 29 = 512 and 289 = 618,970,019,642,690,137,449,562,112 end in a string of digits consisting only of 1′s and 2′s (12 for 29 and 2112 for 289 ). In fact, it can be proved that:

For every integer R, there exists a power of 2 such that 2K uses only the digits 1 and 2 in its last R digits.

This is shown a bit more clearly in the following table:

Your job is to write a program that will determine, for given R, the smallest K such that 2K ends in a string of R digits containing only 1′s and 2′s.

输入:

The first line of the input contains a single decimal integer, N, 1 ≤ N ≤ 50, the number of problem data sets to follow. Each data set consists of a single integer R, 1 ≤ R ≤ 20, for which we want a power of 2 ending in a string of R 1′s and 2′s.

输出:

The first line of the input contains a single decimal integer, N, 1 ≤ N ≤ 50, the number of problem data sets to follow. Each data set consists of a single integer R, 1 ≤ R ≤ 20, for which we want a power of 2 ending in a string of R 1′s and 2′s.

样例输入:

6 
1 
2 
4 
5 
7 
15

样例输出:

1 1 1 
2 2 9 
3 4 89 
4 5 589 
5 7 3089 
6 15 11687815589

题解:

#include<iostream>
#include<cstring>
using namespace std;
int d[55];
__int64 i,len,j;
__int64 f(int r){
	memset(d,0,sizeof(d));
	len=1;
	d[0]=1;
	for(i=1;;i++){
	  for(j=0;j<len;j++)d[j]*=2;
	    for(j=0;j<len;j++)
	    {
		  if(d[j]>9)d[j+1]+=d[j]/10;
		  d[j]=d[j]%10;
	    }
	    if(d[len])len++;
	    if(len>50)len=51; 
	  for(j=0;j<len;j++)
	    if(d[j]==1||d[j]==2) continue;
	    else break;
	  if(j>=r)return i;
	  else continue;
	}
}
int main(){
	int n,r,le=1;
    cin>>n;
	while(n--){
		cin>>r;
		cout<<le++<<' '<<r<<' '<<f(r)<<endl;
	}
	return 0;
}

参考:http://blog.csdn.net/lindonglian/article/details/23597429


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!