Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

230K O(n)

Posted by 2011301200288 at 2016-08-06 00:25:20 on Problem 1001
#include <iostream>
using namespace std;

int GET_R(char R[],int r[])
{
	int i,j=0,p=0;
	for(i=5;i>=0;i--)
	{
		if(R[i]=='.')
			p=5-i;//记录小数点位置
		else
			r[j++]=(int)R[i]-48;//char transfer to int
	}							//经转换 r为整数 且R*10^p=r
	return p;
}

int compute(int sss[6][125],int r[6])
{
	int i,j;
	for(i=1;i<=5;i++)
		for(j=1;j<=124;j++)
		{
			if(j-i>=0)
				sss[i][j]=sss[0][j-i];//错位装填,第一行为r,第二行为10r.....
			else
				sss[i][j]=0;
		}
	for(i=0;i<=5;i++)
		for(j=0;j<=124;j++)
			sss[i][j]*=r[i];		//矩阵每一行乘以对应位 每位最大为81
	for(j=0;j<=124;j++)
		for(i=1;i<=5;i++)
			sss[0][j]+=sss[i][j];	//矩阵列求和装入第一行,得到带权重的结果,每位最大为81*6
	for(j=0;j<=123;j++)				//每位保留对10求余,进位加到下一位
	{
		sss[0][j+1]+=(sss[0][j]-sss[0][j]%10)/10;//进位给下一位
		sss[0][j]=sss[0][j]%10;					//对10求余是本位得数
	}											//R^n=sss*10^(-point*n)
	return 0;
}

int show_result(int sss[6][125],int p)
{
	int i=124,j=0;
	while(sss[0][j]==0)
		j++;
	while(sss[0][i]==0&&i>p)
		i--;
	if(sss[0][i]==0)
	{
		cout<<'.';
		i=p-1;
		while(i>=j)
		{
			cout<<sss[0][i--];
		}
	}
	else
	{
		while(i>=p)
			cout<<sss[0][i--];
		if(p>0&&i>=j)
			cout<<'.';
		while(i>=j)
			cout<<sss[0][i--];
	}
	cout<<endl;
	return 0;
}

int main()
{
	char s[6];
	int point,n,i;
	while(cin>>s>>n)
	{
		if(n==0)
			cout<<1<<endl;
		else
		{
			int r[6]={0};
			int sss[6][125]={0};
			point=GET_R(s,r);
			point*=n;//point*n是结果中小数的位数
			for(i=0;i<=5;i++)
			{
				sss[0][i]=r[i];
			}//r装入矩阵sss  左低右高
			while(--n>0)
				compute(sss,r);//sss*=r
			show_result(sss,point);
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator