AtCoder Beginner Contest 052 ABCD题

A - Two Rectangles

Time limit : 2sec / Memory limit : 256MB

Score : 100 points

Problem Statement

There are two rectangles. The lengths of the vertical sides of the first rectangle are A, and the lengths of the horizontal sides of the first rectangle are B. The lengths of the vertical sides of the second rectangle are C, and the lengths of the horizontal sides of the second rectangle are D.

Print the area of the rectangle with the larger area. If the two rectangles have equal areas, print that area.

Constraintsfewfew

All input values are integers.
1≤A≤104
1≤B≤104
1≤C≤104
1≤D≤104

Input

The input is given from Standard Input in the following format:

A B C D

Output

Print the area of the rectangle with the larger area. If the two rectangles have equal areas, print that area.

Sample Input 1

Copy

3 5 2 7

Sample Output 1

Copy

The first rectangle has an area of 3×5=15, and the second rectangle has an area of 2×7=14. Thus, the output should be 15, the larger area.

Sample Input 2

Copy

100 600 200 300

Sample Output 2

Copy

60000
题意：求哪个的面积最大
解法：比较大小

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 int main()
 5 {
 6     ll a,b,c,d;
 7     cin>>a>>b>>c>>d;
 8     cout<<max(a*b,c*d);
 9     return 0;
10 }

B - Increment Decrement

Time limit : 2sec / Memory limit : 256MB

Score : 200 points

Problem Statement

You have an integer variable x. Initially, x=0.

Some person gave you a string S of length N, and using the string you performed the following operation N times. In the i-th operation, you incremented the value of x by 1 if Si=I, and decremented the value of x by 1 if Si=D.

Find the maximum value taken by x during the operations (including before the first operation, and after the last operation).

Constraints

1≤N≤100
|S|=N
No characters except I and D occur in S.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the maximum value taken by x during the operations.

Sample Input 1

Copy

5
IIDID

Sample Output 1

Copy

After each operation, the value of x becomes 1, 2, 2, 1 and 2, respectively. Thus, the output should be 2, the maximum value.

Sample Input 2

Copy

7
DDIDDII

Sample Output 2

Copy

The initial value x=0 is the maximum value taken by x, thus the output should be 0.

题意：I是增长，D是下降，现在求变化中的最大值

解法：模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 int main()
 5 {
 6     ll a,b,c,d;
 7     cin>>a;
 8     string s;
 9     cin>>s;
10     ll sum=0;
11     ll max1=0;
12     for(int i=0;i<a;i++)
13     {
14         if(s[i]=='I')
15         {
16             sum++;
17         }
18         else
19         {
20             sum--;
21         }
22         max1=max(sum,max1);
23     }
24     cout<<max1<<endl;
25     return 0;
26 }

C - Factors of Factorial

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

You are given an integer N. Find the number of the positive divisors of N!, modulo 109+7.

Constraints

1≤N≤103

Input

The input is given from Standard Input in the following format:

Output

Print the number of the positive divisors of N!, modulo 109+7.

Sample Input 1

Copy

Sample Output 1

Copy

There are four divisors of 3! =6: 1, 2, 3 and 6. Thus, the output should be 4.

Sample Input 2

Copy

Sample Output 2

Copy

Sample Input 3

Copy

Sample Output 3

Copy

972926972

题意：求N！能被多少个数整除

解法: 额。。。http://oeis.org/A027423

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 typedef long long LL;
 5 LL fun(LL x,LL n)
 6 {
 7     LL res=1;
 8     while(n>0)
 9     {
10         if(n & 1)
11             res=(res*x);
12         x=(x*x);
13         n >>= 1;
14     }
15     return res;
16 }
17 ll a[200]={0,2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61 ,67 ,71 ,73 ,79 ,83 ,89 ,97 ,101 ,103 ,107 ,109 ,113 ,127 ,131 ,137 ,139 ,149 ,151 ,157 ,163 ,167 ,173 ,179 ,181 ,191 ,193 ,197 ,199 ,211 ,223 ,227 ,229 ,233 ,239 ,241 ,251 ,257 ,263 ,269 ,271 ,277 ,281 ,283 ,293 ,307 ,311 ,313 ,317 ,331 ,337 ,347 ,349 ,353 ,359 ,367 ,373 ,379 ,383 ,389 ,397 ,401 ,409 ,419 ,421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,467 ,479 ,487 ,491 ,499 ,503 ,509 ,521 ,523 ,541 ,547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607 ,613 ,617 ,619 ,631 ,641 ,643 ,647 ,653 ,659 ,661 ,673 ,677 ,683 ,691 ,701 ,709 ,719 ,727 ,733 ,739 ,743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809 ,811 ,821 ,823 ,827 ,829 ,839 ,853 ,857 ,859 ,863 ,877 ,881 ,883 ,887 ,907 ,911 ,919 ,929 ,937 ,941 ,947 ,953 ,967 ,971 ,977 ,983 ,991 ,997 ,1001};
18 int main()
19 {
20     ll n;
21     ll mod=1e9+7;
22     ll ans=1;
23     cin>>n;
24     ll b[1010];
25     int pos=0;
26     while(1)
27     {
28         if(a[pos]<=n)
29         {
30            pos++;
31         }
32         else
33         {
34             break;
35         }
36     }
37     //cout<<<<endl;
38     for(int i=1; i<=pos-1; i++)
39     {
40         ll sum=0;
41         for(int j=1; j<=n; j++)
42         {
43             if(fun(a[i],j)<=n)
44             {
45                 sum+=(n/fun(a[i],j));
46             }
47             else
48             {
49                 break;
50             }
51         }
52         ans=ans*(sum+1);
53         ans%=mod;
54     }
55     cout<<ans<<endl;
56     return 0;
57 }

D - Walk and Teleport

Time limit : 2sec / Memory limit : 256MB

Score : 500 points

Problem Statement

There are N towns on a line running east-west. The towns are numbered 1 through N, in order from west to east. Each point on the line has a one-dimensional coordinate, and a point that is farther east has a greater coordinate value. The coordinate of town i is Xi.

You are now at town 1, and you want to visit all the other towns. You have two ways to travel:

Walk on the line. Your fatigue level increases by A each time you travel a distance of 1, regardless of direction.
Teleport to any location of your choice. Your fatigue level increases by B, regardless of the distance covered.

Find the minimum possible total increase of your fatigue level when you visit all the towns in these two ways.

Constraints

All input values are integers.
2≤N≤105
1≤Xi≤109
For all i(1≤i≤N−1), Xi<Xi+1.
1≤A≤109
1≤B≤109

Input

The input is given from Standard Input in the following format:

N A B
X1 X2 … XN

Output

Print the minimum possible total increase of your fatigue level when you visit all the towns.

Sample Input 1

Copy

4 2 5
1 2 5 7

Sample Output 1

Copy

From town 1, walk a distance of 1 to town 2, then teleport to town 3, then walk a distance of 2 to town 4. The total increase of your fatigue level in this case is 2×1+5+2×2=11, which is the minimum possible value.

Sample Input 2

Copy

7 1 100
40 43 45 105 108 115 124

Sample Output 2

Copy

From town 1, walk all the way to town 7. The total increase of your fatigue level in this case is 84, which is the minimum possible value.

Sample Input 3

Copy

7 1 2
24 35 40 68 72 99 103

Sample Output 3

Copy

Visit all the towns in any order by teleporting six times. The total increase of your fatigue level in this case is 12, which is the minimum possible value.

题意：看样列知题意

解法：每一步都取最小值

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef long long LL;
LL fun(LL x,LL n)
{
    LL res=1;
    while(n>0)
    {
        if(n & 1)
            res=(res*x);
        x=(x*x);
        n >>= 1;
    }
    return res;
}
ll a[]={0,2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61 ,67 ,71 ,73 ,79 ,83 ,89 ,97 ,101 ,103 ,107 ,109 ,113 ,127 ,131 ,137 ,139 ,149 ,151 ,157 ,163 ,167 ,173 ,179 ,181 ,191 ,193 ,197 ,199 ,211 ,223 ,227 ,229 ,233 ,239 ,241 ,251 ,257 ,263 ,269 ,271 ,277 ,281 ,283 ,293 ,307 ,311 ,313 ,317 ,331 ,337 ,347 ,349 ,353 ,359 ,367 ,373 ,379 ,383 ,389 ,397 ,401 ,409 ,419 ,421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,467 ,479 ,487 ,491 ,499 ,503 ,509 ,521 ,523 ,541 ,547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607 ,613 ,617 ,619 ,631 ,641 ,643 ,647 ,653 ,659 ,661 ,673 ,677 ,683 ,691 ,701 ,709 ,719 ,727 ,733 ,739 ,743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809 ,811 ,821 ,823 ,827 ,829 ,839 ,853 ,857 ,859 ,863 ,877 ,881 ,883 ,887 ,907 ,911 ,919 ,929 ,937 ,941 ,947 ,953 ,967 ,971 ,977 ,983 ,991 ,997 ,};
int main()
{
    ll dp[110000];
    ll a[110000];
    ll n,x,b;
    cin>>n>>x>>b;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[1]=0;
    a[0]=0;
    for(int i=2;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+(a[i]-a[i-1])*x,dp[i-1]+b);
    }
    cout<<dp[n]<<endl;
    return 0;
}