C++博客-wyiu

poj.org 1423

wyiu — Tue, 05 Oct 2010 09:08:00 GMT

/*
* poj1423.cpp
*
*  Created on: 2010-10-5
*      Author: wyiu
*/

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const double PI = 3.1415926535897932384626433832795;

const double E = 2.71828182845904523536;

int main()
{
    int m, n;
    double t;
    int result;

    scanf("%d", &m);

    while(m--)
    {
        scanf("%d", &n);

        t = 0.5*log10(2.0*PI*n)+n*log10(n/E);
        result = (int)t;
        result++;
        printf("%d\n", result);
        fflush(stdout);
    }
    return 0;
}

wyiu 2010-10-05 17:08 发表评论

hit 1214

wyiu — Tue, 05 Oct 2010 07:13:00 GMT

/*
* hit1214.cpp
*
*  Created on: 2010-10-3
*      Author: wyiu
*/
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;

unsigned f[]={1, 1, 2, 3, 5, 8, 13, 21, 34,
        55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
        6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
        832040, 1346269, 2178309, 3524578, 5702887, 9227465,14930352,24157817,39088169,63245986,
        102334155, 165580141, 267914296, 433494437,701408733, 1134903170, 1836311903, 2971215073
};

bool check(string s)
{
    for(int i=0; i<s.length()-1; i++)
        if(s[i]=='1' && s[i+1]=='1')
            return false;
    return true;
}
int main()
{
    int n;
    unsigned val;
    int len;
    string s;
    int i;

    scanf("%d", &n);

    while(n--)
    {
        cin>>s;

        val = 0;
        len = s.length();
        for(i=len-1; i>=0; --i)
        {
            if(s[i] == '1')
            val += f[len-i];
        }
        printf("%u in decimal, ", val);
        fflush(stdout);

        if(check(s))
        {
            printf("already in standard form\n");
            fflush(stdout);
            continue;
        }

        for(i=0; i<len && s[i]=='0'; i++);
        string stds(s.substr(i, len-i));

        bool changed;
        while(!check(stds))
        {
            for(i=0, changed=false; i<stds.length()-1; i++)
            {
                if(stds[i]=='1' && stds[i+1]=='1')
                {
                    stds[i]='0';
                    stds[i+1]='0';
                    if(i==0)
                        stds = string("1")+stds;
                    else stds[i-1]='1';
                    changed = true;
                }
                if(changed)
                    break;
            }
        }

        cout<<"whose standard form is "<<stds<<endl;

    }
    return 0;
}

wyiu 2010-10-05 15:13 发表评论

5.9 Strategy

wyiu — Mon, 04 Oct 2010 04:27:00 GMT

/*
* 5_9_Strategy.cpp
*
*  Created on: 2010-9-25
*      Author: wyiu
*/

class Compositor
{
public:
    virtual int compose(Coord natural[], Coord stretch[], Coord shrink[],
                    int componentCount, int lineWidth, int breaks) = 0;

protected:
    Compositor();

};

//------------------------------------------------------------------------
class Composition
{
public:
    Composition(Compositor *);
    void repair();

private:
    Compositor *_compositor;
    Component *_components;
    int _componentCount;
    int _lineWidth;
    int *_lineBreaks;
    int _lineCount;
};

void Composition::repair()
{
    Coord *natural;
    Coord *stretchability;
    Coord *shrinkability;
    int componentCount;
    int *breaks;

    //prepare the arrays with the desired component sizes
    //

    //determine where the breaks are:
    int breakCount;
    breakCount = _compositor->compose(natural, stretchability, shrinkability,
                                        componentCount, _lineWidth, breaks);

    //lay out components according to breaks
    //
}

//--------------------------------------------------------------------
//subclass of Compositor
class SimpleCompositor : public Compositor
{
public:
    SimpleCompositor();

    virtual int compose(Coord natural[], Coord stretch[], Coord shrink[],
                    int componentCount, int lineWidth, int breaks);

    //
};

class TeXCompositor : public Compositor
{
public:
    TeXCompositor();

    virtual int compose(Coord natural[], Coord stretch[], Coord shrink[],
                    int componentCount, int lineWidth, int breaks);

    //
};

class ArrayCompositor : public Compositor
{
public:
    ArrayCompositor();

    virtual int compose(Coord natural[], Coord stretch[], Coord shrink[],
                    int componentCount, int lineWidth, int breaks);

    //
};

//-----------------------------------------
//using example
int main()
{
    //

    Composition *quick = new Composition(new SimpleCompositor);
    Composition *slick = new Composition(new TeXCompositor);
    Composition *iconic = new Composition(new ArrayCompositor);

    //.

    return 0;
}

wyiu 2010-10-04 12:27 发表评论

The first 50 Fibonacci numbers Fn for n = 0, 1, 2, ... ,49 are:

wyiu — Sun, 03 Oct 2010 10:13:00 GMT

F₀=	0	F₁=	1	F₂=	1	F₃=	2	F₄=	3
F₅=	5	F₆=	8	F₇=	13	F₈=	21	F₉=	34
F₁₀=	55	F₁₁=	89	F₁₂=	144	F₁₃=	233	F₁₄=	377
F₁₅=	610	F₁₆=	987	F₁₇=	1,597	F₁₈=	2,584	F₁₉=	4,181
F₂₀=	6,765	F₂₁=	10,946	F₂₂=	17,711	F₂₃=	28,657	F₂₄=	46,368
F₂₅=	75,025	F₂₆=	121,393	F₂₇=	196,418	F₂₈=	317,811	F₂₉=	514,229
F₃₀=	832,040	F₃₁=	1,346,269	F₃₂=	2,178,309	F₃₃=	3,524,578	F₃₄=	5,702,887
F₃₅=	9,227,465	F₃₆=	14,930,352	F₃₇=	24,157,817	F₃₈=	39,088,169	F₃₉=	63,245,986
F₄₀=	102,334,155	F₄₁=	165,580,141	F₄₂=	267,914,296	F₄₃=	433,494,437	F₄₄=	701,408,733
F₄₅=	1,134,903,170	F₄₆=	1,836,311,903	F₄₇=	2,971,215,073	F₄₈=	4,807,526,976	F₄₉=	7,778,742,049

int f[47]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34,
        55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
        6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
        832040, 1346269, 2178309, 3524578, 5702887, 9227465,14930352,24157817,39088169,63245986,
        102334155, 165580141, 267914296, 433494437,701408733, 1134903170, 1836311903
};

wyiu 2010-10-03 18:13 发表评论

hdu 1250

wyiu — Sun, 03 Oct 2010 09:40:00 GMT

/*
* 1250.cpp
*
*  Created on: 2010-10-3
*      Author: wyiu
*/

#include <cstdio>
#include <cstring>
using namespace std;

int n;
int f[5][2100];

void init()
{
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    f[1][0] = 1;
    f[2][0] = 1;
    f[3][0] = 1;
    n--;
}

int fib()
{
    if(n < 4) return 1;

    int i, j, r, t, m;
    for(i=4, m=1; i<=n; i++)
    {
        for(j=0, r=0; j<m; j++)
        {
            t = f[(i-1)%5][j]+f[(i-2)%5][j]+f[(i-3)%5][j]+f[(i-4)%5][j] + r;
            f[i%5][j] = t % 10;
            r = t / 10;
        }
        if(r > 0)
        {
            f[i%5][j] = r;
            m++;
        }
    }
    return m;
}

void display(int m)
{
    int j;
    for(j=m-1; j>=0; j--)
    {
        printf("%d", f[n%5][j]);
    }
    printf("\n");
    fflush(stdout);
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        init();
        int m = fib();
        display(m);
    }
    return 0;
}

wyiu 2010-10-03 17:40 发表评论

hdu 1568

wyiu — Sun, 03 Oct 2010 08:42:00 GMT

/*
* 1568.cpp
*
*  Created on: 2010-10-2
*      Author: wyiu
*/
#include <cstdio>
#include <cmath>
using namespace std;

int main()
{

    int f[30];
    f[0]=0;
    f[1]=1;
    for(int i=2; i<=20; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    int n;
    while(scanf("%d", &n) != EOF)
    {
        if(n <= 20)
        {
            printf("%d\n", f[n]);
            fflush(stdout);
            continue;
        }
        double a = -0.5*log10(5) + n*(log10(0.5*(1+sqrt(5.0))));
        double r = a - int(a);
        double b = pow(10, r);
        while(b < 1000)
        {
            b*=10;
        }
        printf("%d\n", int(b));
        fflush(stdout);
    }
    return 0;
}

wyiu 2010-10-03 16:42 发表评论

poj.org 3070

wyiu — Sun, 03 Oct 2010 08:41:00 GMT

/*
* 3070.cpp
*
*  Created on: 2010-10-2
*      Author: wyiu
*/
#include <cstdio>
using namespace std;
struct Matrix
{
    int a11, a12;
    int a21, a22;
};

Matrix mutilMatrix(Matrix a, Matrix b)
{
    Matrix c;
    c.a11 = (a.a11*b.a11+a.a12*b.a21 ) % 10000;
    c.a12 = (a.a11*b.a12+a.a12*b.a22 ) % 10000;
    c.a21 = (a.a21*b.a11+a.a22*b.a21 ) % 10000;
    c.a22 = (a.a21*b.a12+a.a22*b.a22 ) % 10000;
    return c;

}

Matrix powerMatrix(int n)
{
    if(n == 0)
    {
        Matrix m0 ;
        m0.a11=1;
        m0.a12=0;
        m0.a21=0;
        m0.a22=1;
        return  m0;
    }
    else
    {
        Matrix a, b;
        a = powerMatrix(n/2);
        b = mutilMatrix(a, a);
        if(n%2 != 0)
        {
            Matrix m1 ;
            m1.a11=1;
            m1.a12=1;
            m1.a21=1;
            m1.a22=0;

            b = mutilMatrix(b, m1);
        }
        return b;
    }

}

int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        if(n == -1)
            break;

        Matrix r = powerMatrix(n);

        printf("%d\n", r.a12);
        fflush(stdout);
    }
    return 0;
}

wyiu 2010-10-03 16:41 发表评论

hdu 1021

wyiu — Sat, 02 Oct 2010 08:48:00 GMT

/*
* 1021.cpp
*
*  Created on: 2010-10-2
*      Author: wyiu
*/

#include <cstdio>
#include <cstring>
using namespace std;

int f[1000001];

int main()
{
    f[0]=7%3;
    f[1]=11%3;
    for(int i=2; i<=1000000; i++)
    {
        f[i] = (f[i-1] + f[i-2]) % 3;
    }

    int x;
    while(scanf("%d", &x) != EOF)
    {
        if(f[x] == 0)
            printf("yes\n");
        else printf("no\n");
        fflush(stdout);
    }
    return 0;
}

wyiu 2010-10-02 16:48 发表评论

poj 1061 线性同余

wyiu — Wed, 31 Mar 2010 14:54:00 GMT

//推出同余式后直接上算法导论结论

#include <iostream>
using namespace std;
__int64 extgcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
    if(b==0)
    {
        x=1,y=0;return a;
    }
    __int64 r=extgcd(b,a%b,x,y);
    __int64 t=x; x=y; y=t-a/b*y;
    return r;
}
int main()
{
    __int64 x,y,m,n,l,k,t;
    __int64 a,b,c,d;
    while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&n,&m,&l)!=EOF)
    {

        a=m-n;
        b=x-y;
        if(m-n<0)
        {
            a=-a;
            b=(-b+l)%l;
        }
        else b=(b+l)%l;
        d=extgcd(a,l,k,t);
        if(b%d) { printf("Impossible\n"); continue;}
        k=(k*(b/d)%l+l)%(l/d);

        printf("%I64d\n", k);
    }
    return 0;
}

wyiu 2010-03-31 22:54 发表评论

poj 2115 线性同余

wyiu — Wed, 31 Mar 2010 14:48:00 GMT

A+C*X=B(%2^K)
C*X=B-A(%2^K)
令a=c,b=B-A,n=2^K;
利用以下结论（具体证明见《算法导论）：
推论1：方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a,n) | b。
推论2：方程ax=b(mod n)或者对模n有d个不同的解，其中d=gcd(a,n)，或者无解。
定理1：设d=gcd(a,n)，假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b，则方程ax=b(mod n)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e mod (n/d)，最大整数解x2=x1+(d-1)*(n/d)。
定理2：假设方程ax=b(mod n)有解，且x0是方程的任意一个解，则该方程对模n恰有d个不同的解(d=gcd(a,n))，分别为：xi=x0+i*(n/d) mod n 。

a*x=b(%n) => a*x+n*y=b
d=ext_gcd(a,n,x0,y0)
最小整数解x1=(x0*(b/d)%n+n)%(n/d);

#include <iostream>
using namespace std;
__int64 exgcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
    if(b==0)
    {
        x=1;y=0;return a;
    }
    __int64 r=exgcd(b, a%b, x, y);
    __int64 t=x;x=y;y=t-a/b*y;
    return r;
}
int main()
{
    __int64 A,B,C,K;
    __int64 a,b,n,d,x,y,e;
    while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&K)!=EOF)
    {
        if(A==0 && B==0 && C==0 && K==0) break;
        a=C;
        n=((__int64)1<<K); //小心溢出
        b=B-A;
        d=exgcd(a, n, x, y);
        if(b%d) {printf("FOREVER\n"); continue;}
        e=x*(b/d)%n+n;
        printf("%I64d\n",e%(n/d));
    }
    return 0;
};

wyiu 2010-03-31 22:48 发表评论