2015年NEUACM一月月赛题解

A Money , money

时间限制: 1 Sec  内存限制: 128 MB 提交: 15  解决: 14

题目描述

Small K seen recently stock market really too violent, so he want to choose some ways to earn money.

At every month, he can use three ways to manage his money . For example , if he has 1000 dollars , At first month,

he can use 500 for A way , 300 for B way, and 200 just do nothing.  After first month , he will get X1 / 100 * 500 + y1 / 100 * 300 money.

Then he can use this money to invest in later months.

So the question is :

The total money he can earn after investing.  (Earn money not the early money + earn money)

输入

The first number n means that there are n cases.

next n cases' format will be that

the first line has 12 real number , means X way's profit x1% in every month

the second line has 12 real number ,means Y way's profit y1% in every month

the third line has 12 real number , means Z way's profit z1% in every month

输出

Every case ,you output a real number , means the profit Small K can get. (returned three decimal places)

样例输入

1
3.1 3.2 3.2 3.1 3.4 3.0 2.9 3.8 3.5 3.0 3.2 4.0
10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.7 10.9 11.0 11.1 11.2
15.0 -3.0 -10.0 30.0 20.0 10.0 0.0 -12.0 -9.0 20.0 30.0 -23.0
10000

样例输出

46857.904

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f

double s;
double xx[],yy[],zz[];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=;i<=;i++) scanf("%lf",&xx[i]);
        for(int i=;i<=;i++) scanf("%lf",&yy[i]);
        for(int i=;i<=;i++) scanf("%lf",&zz[i]);
        scanf("%lf",&s);
        double t=s;
        for(int i=;i<=;i++)
        {
            double m=max(max(xx[i],yy[i]),zz[i]);
            if(m>) s=s+s*m/;
        }
        printf("%.3f\n",s-t);
    }
    return ;
}

B a Simple Problem

时间限制: 1 Sec  内存限制: 128 MB 提交: 8  解决: 7

题目描述

Many people think hh is a diaosi, but hh is a very rich

man whose nickname is wenzhoutuhao,and he made a lot of

money by buying the stock of neusoft. He bought n

diamonds.One day he found that his warehouse is too small

to accommodate these diamonds. so he decide to transfer

c of the diamonds to another warehouse.

He made the n diamonds into a row, with a number written

on their positions, the number is the value of the diamond,

the unit is billion(oh no so rich man),then,hh tells you

to choose c diamonds,which will be sent to other

warehouse,he also imposed two conditions.They are:

　 1.the chosen c diamonds must be formed a contiguous

segment

　 2.any of the chosen diamond’s value should not be greater

than t,because he thought you may be would steal them.

Find the number of ways you can choose the c diamonds.

输入

50 group tests,the first line of input will contain three space separated integer n(1<=n<=10^5),t(0<=t<=10^9) and c(1<=c<=n)

the next line will contain n space separated integer,the ith integer is the value of ith diamond,the value will be non-negative and will not be exceed 10^9

输出

print a single integer——the number of ways you can choose the c diamonds

样例输入

4 3 3
2  3  1  1
1 1 1
2

样例输出

2
0

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010

int main()
{
    int n,t,c;
    int a[N];
    while(scanf("%d%d%d",&n,&t,&c)!=EOF)
    {
        for(int i=;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int ans=,tmp=,l=;
        for(int i=;i<=n;i++)
        {
            if(a[i]<=t)
            {
                tmp+=a[i];
                l++;
                if(l==c)
                {
                    ans++;
                    tmp-=a[i-c+];
                    l--;
                }
            }
            else
            {
                tmp=;
                l=;
            }
        }
        printf("%d\n",ans);
    }
    return ;
}

C Sum?Sum!

时间限制: 1 Sec  内存限制: 128 MB 提交: 26  解决: 13

题目描述

Kid want to learn math better.Now Kid know how to calculate the sum of 1 to n in a short time.But this time,he is given a much more difficult question——to calculate the sum of 1 to 10^n.Kid think for a long time——10^10 ms and then he solve the question successfully.

Do you know how to solve it ?

输入

The first line is a integer t(1<=t<=10),indicate the number of case.

For each t,there is a integer n(the meaning of n is in the above),1<=n<=10^4.

输出

For each case,just print the answer of the sum.

样例输入

1
1

样例输出

55

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define N 100010

int main()
{
    int n;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        if(n==)
        {
            printf("1\n");
            continue;
        }
        printf("");
        for(int i=;i<=n;i++) printf("");
        printf("");
        for(int i=;i<=n;i++) printf("");
        printf("\n");
    }
    return ;
}

D Segment Balls

时间限制: 1 Sec  内存限制: 128 MB 提交: 18  解决: 9

题目描述

Small K has recently earn money in stock market , so he want to make balls to celebrate it.

Now he buys so many balls , and he want to put it into the boxes , he will have two operators to do it.

There are n boxes , which number is in range of (1 , n)

operator 1: PUT B C   he can put C balls to boxes whose number is multiple of B

operator 2: QUERY D E  he want to know the total number of balls in boxes number D to boxes number E.

We guarantee that 1 <= B ,C <= 10 1 <= D <= E <= 1e6

输入

The first number CASE is the case number.Then will be CASE cases.

At every case , the first number is n ,means that we have n boxes.

the second number is q , which means the q operators will be give.

And then will be q lines ,which means q operators.

(1 <= q <= 100000)

输出

Every case ,  print the total balls for every question . A question a line.

样例输入

1
4
8
PUT 1 3
QUERY 2 4
PUT 2 3
QUERY 1 4
QEURY 1 1
QEURY 2 2
QUERY 3 3
QUERY 4 4

样例输出

9
18
3
6
3
6

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define N 10010

ll n,m;
ll sum[];

ll solve(ll pos)
{
    ll res=;
    for(ll i=;i<;i++) res+=pos/i*sum[i];
    return res;
}
int main()
{
    ll T;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        memset(sum,,sizeof(sum));
        while(m--)
        {
            ll x,y;
            char op[];
            scanf("%s%lld%lld",op,&x,&y);
            if(op[]=='P') sum[x]+=y;
            else printf("%lld\n",solve(y)-solve(x-));
        }
    }
    return ;
}

E Caoshen like math

时间限制: 1 Sec  内存限制: 128 MB 提交: 7  解决: 7

题目描述

Worfzyq likes Permutation problems.Caoshen and Mengjuju are expert at these problems . They have n cards,and all of the numbers vi on these cards are different . Because Caoshen doesn't

like disordered permutations,he wants to change the permutation into non-descending

permutation.He defines the operations:every time you can choose two digits casually,and

exchange the positions of them.Caoshen is lazy,he wants to know at least how many operations he

needs to change the permutation into non-descending one?

输入

There are multiple test cases. Each case contains a positive integer n,incicate the number of cards(n<=1000000) . Followed by n positive numbers integers v1,v2,...,vn (1≤vi≤n)

---the value of each card.

输出

Print the minmum operations in a signal line for each test case.

样例输入

5
1 3 2 5 4

样例输出

2

提示

first simple you need change (v2,v3) (v4,v5) and the permutation change to 1 2 3 4 5 . so the  minnum step is 2

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define N 1000010

int a[N];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=;i<=n;i++) scanf("%d",&a[i]);
        int ans=;
        for(int i=;i<=n;i++)
        {
            while(a[i]!=i)
            {
                swap(a[i],a[a[i]]);
                ans++;
            }
        }
        printf("%d\n",ans);
    }
 

F Worfzyq like crossfire

时间限制: 1 Sec  内存限制: 128 MB 提交: 11  解决: 0

题目描述

Worfzyq likes playing crossfire. he is most good at using AK47 Gun.What's more, he has did

much research on the track of bullet and found that the impact point of AK47 would raise after fire

7 times continuously,while the bullet muzzle of next 23 bullets would be kept on the highest point

Worfzyq want to be a master of head-shooting. Hence, he is considering a question.Now, there are n targets front of him, the height of i-th target is hi (cm),Worfzyq has m bullets. He found

that the position of first k shots will be raised at a speed of 1(cm/s),and the position of following

(m-k) shots will be kept on the highest point. Ignoring AK47's moving time, Worfzyq hope the m

bullets can shot as most targets as it can.

输入

There are multiple test cases. Each case contains three positive integer n,m,k

(1<=n,m,k<=2000000) , Followed by n positive numbers integers H1,H2.....Hn(1<=Hi<=2000000) ，indicate the height of target.

输出

Output most of targets to be shot for each test case.

样例输入

9 9 6
1 2 3 4 5 6 6 6 6

样例输出

9

提示

first sample Worfzyq has 9 bullets, first 6 bullents he will kill the target 1,2,3,4,5,6 , next 3

bullets the impact point would be kept on 6(cm) . So next 3 bullents worfzyq will kill the target

7,8,9. Finally,he will kill at most 9 target .

/* 不会 */

G a interesting game

时间限制: 1 Sec  内存限制: 128 MB 提交: 17  解决: 5

题目描述

One day,Kid is in class.But Kid think what the teacher teaching is so boring,so he decide to play a

game with himself.He will give himself a matrix with n rows and m columns.Then for each

position,Kid will write 0 or 1 on it.Kid want to find that there are how many schemes that for each

row and each column the number of 1 is odd.

输入

The first line is a integer t,the number of case.

Then for each case,there are two numbers,n and m,implies the rows and the columns.

输出

For each case,output only one integer,the number of schemes.

样例输入

1
2 2

样例输出

2

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define M 9999
#define N 10010
#define DLEN 4

class BigNum
{
private:
    int len;
    int a[N];
public:
    BigNum(){len=;memset(a,,sizeof(a));}
    BigNum(const int&);
    BigNum(const BigNum &);

    friend ostream& operator << (ostream&,BigNum&);

    BigNum operator + (const BigNum &)const;
    BigNum operator * (const BigNum &)const;
    BigNum operator ^ (const int &)const;
    BigNum &operator= (const BigNum &);
};
BigNum::BigNum(const int &b)
{
    int c,d=b;
    len=;
    memset(a,,sizeof(a));
    while(d>M)
    {
        c=d-(d/(M+))*(M+);
        d=d/(M+);
        a[len++]=c;
    }
    a[len++]=d;
}
BigNum::BigNum(const BigNum &T)
{
    len=T.len;
    memset(a,,sizeof(a));
    for(int i=;i<len;i++) a[i]=T.a[i];
}
BigNum & BigNum::operator = (const BigNum &n)
{
    len=n.len;
    memset(a,,sizeof(a));
    for(int i=;i<len;i++) a[i]=n.a[i];
    return *this;
}
ostream& operator << (ostream& cout,BigNum& b)
{
    cout<<b.a[b.len-];
    for(int i=b.len-;i>=;i--) printf("%04d",b.a[i]);
    return cout;
}
BigNum BigNum::operator + (const BigNum &T)const
{
    BigNum t(*this);
    int big=T.len>len?T.len:len;
    for(int i=;i<big;i++)
    {
        t.a[i]+=T.a[i];
        if(t.a[i]>M)
        {
            t.a[i+]++;
            t.a[i]-=M+;
        }
    }
    t.len=t.a[big]?big+:big;
    return t;
}
BigNum BigNum::operator * (const BigNum &T)const
{
    BigNum ret;
    int i,j;
    int tmp1,tmp2;
    for(i=;i<len;i++)
    {
        int up=;
        for(j=;j<T.len;j++)
        {
            tmp1=a[i]*T.a[j]+ret.a[i+j]+up;
            if(tmp1>M)
            {
                tmp2=tmp1-tmp1/(M+)*(M+);
                up=tmp1/(M+);
                ret.a[i+j]=tmp2;
            }
            else
            {
                up=;
                ret.a[i+j]=tmp1;
            }
        }
        if(up) ret.a[i+j]=up;
    }
    ret.len=i+j;
    while(!ret.a[ret.len-] && ret.len>) ret.len--;
    return ret;
}
BigNum BigNum::operator ^ (const int &n)const
{
    int i;
    BigNum t,ret();
    if(n==) return ;
    if(n==) return *this;
    int m=n;
    while(m>)
    {
        t=*this;
        for(i=;(i<<)<=m;i<<=) t=t*t;
        m-=i;
        ret=ret*t;
        if(m==) ret=ret*(*this);
    }
    return ret;
}
int main()
{
    int T;
    ll n,m,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        //buteforce();
        if((n%+m%)%)
        {
            cout<<<<endl;
            continue;
        }
        k=(n-)*(m-);
        BigNum ans();
        while(k--)
        {
            ans=ans*;
        }
        cout<<ans<<endl;
    }
    return ;
}

H Planar map

时间限制: 1 Sec  内存限制: 128 MB 提交: 7  解决: 6

题目描述

Tigher has work for a long time in a famous company.One day she is given a planar map(look at

the following) and a point.The planar map can be regarded as a polygon.The planar map has n

positions,which are the n vertexes in the polygon.

Actually the point replace the position of a supermarket.The supermarket has a range of its

effect,which show as a circle.The company wants to know the maximum radius of the

circle.Unfortunately,Tigher decides to see movie with her BF this evening.So she give the project

to the ipqhjjybj(so poor!).However,ipqhjjybj want to have dinner with his new friends(do you

输入

An interger CASE ,which means the total case num.

For every case, the first line is an interger means n.(1<=n<=6)

Then will be n lines (x , y) which indicates the n points' position.

The n+2 line will be the coordinate of the supermarket,and we promise that this point must be in the internal of the planar map.

And this n points will form n lines , which is (n1, n2) (n2 , n3) (n3 ,n4) (n4, n5)...(nn,n1)

输出

It will give just an real number . (Preserve 3 decimal places)

样例输入

4
4
0 0
2 0
2 2
0 2
1 1
1
1 1
1 1
6
0 0
2 0
3 1
2 2
1 1
0 2
1 0.5
3
0 0
0 1
1 0
0.5 0.5

样例输出

1.000
0.000
0.500
0.000

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define N 1000010

#define PI acos(-1.0)
#define EPS 1e-8
#define N 1010

int dcmp(double x)
{
    if(fabs(x)<EPS) return ;
    return x<?-:;
}
struct Point
{
    double x,y;
    Point (){}
    Point (double x,double y):x(x),y(y){}
    Point operator + (Point p){
        return Point(x+p.x,y+p.y);
    }
    Point operator - (Point p){
        return Point(x-p.x,y-p.y);
    }
    Point operator *(double d){
        return Point(x*d,y*d);
    }
    double operator * (Point p){
        return x*p.x+y*p.y;
    }
    double operator ^ (Point p){
        return x*p.y-y*p.x;
    }
};

struct Line
{
    Point s,e;
    Line (){}
    Line (Point s,Point e):s(s),e(e){}
};
double PointToPoint(Point a,Point b)
{
    return sqrt((a-b)*(a-b));
}
Point PointToSeg(Line l,Point p)
{
    Point res;
    double t=((p-l.s)*(l.e-l.s))/((l.e-l.s)*(l.e-l.s));
    if(t>= && t<=)
    {
        res.x=l.s.x+(l.e.x-l.s.x)*t;
        res.y=l.s.y+(l.e.y-l.s.y)*t;
    }
    else
    {
        if(PointToPoint(p,l.s)<PointToPoint(p,l.e)) res=l.s;
        else res=l.e;
    }
    return res;
}

int n;
Point p[N],q;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
        scanf("%lf%lf",&q.x,&q.y);
        double ans=INF;

        for(int i=;i<n;i++)
        {
            Line l=Line(p[i],p[(i+)%n]);
            ans=min(ans,PointToPoint(q,PointToSeg(l,q)));
        }
        printf("%.3f\n",ans);
    }
    return ;
}

I 题都没看到

/* 无题 */

J Eliminate zero AC

时间限制: 1 Sec  内存限制: 128 MB

题目描述

Last night,Kid submitted a problem for many times but he got many WA,so he is sad.Out of

sympathy, his coach gave him a very simple problem so that Kid can solve it quickly. The problem

is to select as many numbers as possible range 1 to n so that among these selected number there

are no number can be divided exactly by other number. Can you solve it as quick as Kid?

输入

There are multiple cases.

For each case, there is a integer n(1<=n<=10^9)

输出

For each case,just output the answer.(the most numbers you can select)

样例输入

5

样例输出

3

提示

You can select {2,3,5} or {3,4,5}... but you can’t select {2,3,4,5} because 2|4.

So the answer is 3.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define N 100010

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int ans=n/;
        if(n%) ans++;
        printf("%d\n",ans);
    }
    return ;
}