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

还算短

Posted by sxyz007 at 2008-05-03 22:02:32 on Problem 1965
#include<iostream>
using namespace std;
#define maxn 1000
struct Bignum {
    int l,d[maxn];
    bool Readin() {
        char str[maxn];
        if (scanf("%s",str)==EOF) return false;
        memset(d,0,sizeof(d)),l=30;
        for (int i=0; i<strlen(str); i++)
            d[l++]=str[strlen(str)-1-i]-'0';
        while (!d[l-1] && l>1) l--;
        return true;
    }
    void Plus(Bignum a) {
        l>?=a.l;
        for (int i=0; i<l; i++) {
            d[i]+=a.d[i];
            if (d[i]>9) {
                d[i]-=10;
                d[i+1]++;
            }
        }
        if (d[l]) l++;
    }
    void Multiply(Bignum a) {
        int td[maxn];
        memset(td,0,sizeof(td));
        for (int i=0; i<l; i++)
            for (int j=0; j<a.l; j++)
                td[i+j]+=d[i]*a.d[j];
        l=l+a.l-1;
        for (int i=0; i<l-1; i++)
            if (td[i]>9) {
                td[i+1]+=td[i]/10;
                td[i]%=10;
            }
        while (td[l-1]>9) {
            td[l]=td[l-1]/10;
            td[l-1]%=10;
            l++;
        }
        memcpy(d,td,sizeof(td));
    }
    void Divide(int num) {
        for (int i=l-1; i>0; i--) {
            d[i-1]+=d[i]%num*10;
            d[i]/=num;
        }
        d[0]/=num;
        while (!d[l-1] && l>1) l--;
    }
    int Compare(Bignum a) {
        if (l<a.l) return -1;
        if (l>a.l) return 1;
        for (int i=l-1; i>=0; i--)
            if (d[i]<a.d[i]) return -1;
            else if (d[i]>a.d[i]) return 1;
        return 0;
    }
    void Print() {
        int sum=0;
        for (int i=0; i<l; i++) sum+=d[i];
        printf("%d ",sum%10);
        for (int i=l-1; i>=10; i--) printf("%d",d[i]);
        printf(".");
        for (int i=9; i>=0; i--) printf("%d",d[i]);
        printf("\n");
    }
} a,e,high,low,mid;

bool Judge() {
    Bignum tmp=low;
    tmp.Plus(e);
    if (tmp.Compare(high)<0) return true;
    return false;
}

int main() {
    Bignum cube,tmp;
    memset(e.d,0,sizeof(e.d));
    e.d[0]=e.l=1;
    while (a.Readin()) {
        low=e;
        high=a,high.Plus(e);
        while (Judge()) {
            tmp=low,tmp.Plus(high);
            tmp.Divide(2);
            cube=tmp;
            cube.Multiply(tmp);
            cube.Multiply(tmp);
            if (cube.Compare(a)>0) high=tmp;
            else low=tmp;
        }
        low.Print();
    }
    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