Codeforces Round #341 (Div. 2) [Codeforces621]A. Wet Shark and Odd and Even （模拟）B. Wet Shark and Bishops （數學）E. Wet Shark and Blocks （DP&&矩陣快速幂）

此處有目錄↑

Codeforces Round #341 (Div. 2)：http://codeforces.com/contest/621

A. Wet Shark and Odd and Even （模拟）

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Today, Wet Shark is given n integers. Using any of these integers no more than once, Wet Shark wants to get maximum possible even (divisible by 2) sum. Please, calculate this value for Wet Shark.

Note, that if Wet Shark uses no integers from the n integers, the sum is an even integer 0.

Input

The first line of the input contains one integer, n (1 ≤ n ≤ 100 000). The next line contains n space separated integers given to Wet Shark. Each of these integers is in range from 1 to 109, inclusive.

Output

Print the maximum possible even sum that can be obtained if we use some of the given integers.

Sample test(s) input

3
1 2 3
      

output

6      

input

5
999999999 999999999 999999999 999999999 999999999
      

output

3999999996      

Note

In the first sample, we can simply take all three integers for a total sum of 6.

In the second sample Wet Shark should take any four out of five integers 999 999 999.

題目大意：有n個數，每個數隻能加1次，求最大的是偶數的和

大緻思路：如果目前數是偶數，則直接加在答案上；如果目前數是奇數，則存入數組，最後排序，從最大開始，每兩個奇數一組加在答案上

#include <cstdio>
#include <algorithm>

using namespace std;

int n,a,num[100005],cnt;
long long ans;

int main() {
    scanf("%d",&n);
    ans=cnt=0;
    while(n--) {
        scanf("%d",&a);
        if(a&1)
            num[cnt++]=a;
        else
            ans+=a;
    }
    sort(num,num+cnt);
    while(cnt>1) {
        ans+=num[--cnt];
        ans+=num[--cnt];
    }
    printf("%I64d\n",ans);
    return 0;
}
           

B. Wet Shark and Bishops （數學）

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Today, Wet Shark is given n bishops on a 1000 by 1000 grid. Both rows and columns of the grid are numbered from 1 to 1000. Rows are numbered from top to bottom, while columns are numbered from left to right.

Wet Shark thinks that two bishops attack each other if they share the same diagonal. Note, that this is the only criteria, so two bishops may attack each other (according to Wet Shark) even if there is another bishop located between them. Now Wet Shark wants to count the number of pairs of bishops that attack each other.

Input

The first line of the input contains n (1 ≤ n ≤ 200 000) — the number of bishops.

Each of next n lines contains two space separated integers xi and yi (1 ≤ xi, yi ≤ 1000) — the number of row and the number of column where i-th bishop is positioned. It's guaranteed that no two bishops share the same position.

Output

Output one integer — the number of pairs of bishops which attack each other.

Sample test(s) input

5
1 1
1 5
3 3
5 1
5 5
      

output

6
      

input

3
1 1
2 3
3 5
      

output

Note

In the first sample following pairs of bishops attack each other: (1, 3), (1, 5), (2, 3), (2, 4), (3, 4) and (3, 5). Pairs (1, 2), (1, 4), (2, 5)and (4, 5) do not attack each other because they do not share the same diagonal.

題目大意：在1000*1000的棋盤上，有n個棋子-象，象在斜線上能互相攻擊，即使他們中間還有别的象

大緻思路：統計某條斜線上的象的數目為num，則最終答案加上C(n,2)=num*(num)/2;

                  右斜線橫坐标減縱坐标為定值，但可能為負，是以應加一個常數防止越界；左斜線橫坐标加縱坐标為定值。是以可以開兩個數組統計在同一斜線上的象數目

#include <cstdio>
#include <algorithm>

using namespace std;

int n,i,j;
int l[2015]={0},r[2015]={0};
long long ans;
const int MID=1005;

int main() {
    scanf("%d",&n);
    ans=0;
    while(n--) {
        scanf("%d%d",&i,&j);
        ++l[i+j];
        ++r[i-j+MID];
    }
    for(i=0;i<2015;++i) {
        if(l[i]>1)
            ans+=l[i]*(l[i]-1)/2;
        if(r[i]>1)
            ans+=r[i]*(r[i]-1)/2;
    }
    printf("%I64d\n",ans);
    return 0;
}
           

E. Wet Shark and Blocks （DP&&矩陣快速幂）

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

There are b blocks of digits. Each one consisting of the same n digits, which are given to you in the input. Wet Shark must chooseexactly one digit from each block and concatenate all of those digits together to form one large integer. For example, if he chooses digit1 from the first block and digit 2 from the second block, he gets the integer 12.

Wet Shark then takes this number modulo x. Please, tell him how many ways he can choose one digit from each block so that he gets exactly k as the final result. As this number may be too large, print it modulo 109 + 7.

Note, that the number of ways to choose some digit in the block is equal to the number of it's occurrences. For example, there are 3ways to choose digit 5 from block 3 5 6 7 8 9 5 1 1 1 1 5.

Input

The first line of the input contains four space-separated integers, n, b, k and x (2 ≤ n ≤ 50 000, 1 ≤ b ≤ 109, 0 ≤ k < x ≤ 100, x ≥ 2) — the number of digits in one block, the number of blocks, interesting remainder modulo x and modulo x itself.

The next line contains n space separated integers ai (1 ≤ ai ≤ 9), that give the digits contained in each block.

Output

Print the number of ways to pick exactly one digit from each blocks, such that the resulting integer equals k modulo x.

Sample test(s) input

12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5
      

output

3
      

input

3 2 1 2
6 2 2
      

output

input

3 2 1 2
3 1 2
      

output

6
      

Note

In the second sample possible integers are 22, 26, 62 and 66. None of them gives the remainder 1 modulo 2.

In the third sample integers 11, 13, 21, 23, 31 and 33 have remainder 1 modulo 2. There is exactly one way to obtain each of these integers, so the total answer is 6.

題目大意：總共有b位數字，每一位數字都可以從n個數字（1~9）中選，求最終結果模x後等于k的方案數

終于有機會能做出3題了，調了好久

大緻思路：看到答案很大，就知道是dp，但是由于b很大，肯定需要矩陣快速幂優化，可以算出dp的轉移方程，進而求得系數矩陣

方法一：O(log(b)*x^3)

設dp[i][j]表示前i個數字組成的數字模x為j時的方案數，num[a]表示可選數字中a出現的次數

則狀态轉移方程為：dp[i][j]=∑(num[a]*dp[i-1][d])，（1<=a<=9，0<=d<x，且j=(10*d+a)%x）

則最終答案是dp[b][k]，由于b很大，是以需要矩陣快速幂優化

設系數矩陣為P.m[MAX][MAX]，則dp[b]=dp[b-1]*P.m=…=dp[0]*(P.m)^b

對于1<=a<=9，0<=d<x，dp[0][d]對dp[1][(10*d+a)%x]有貢獻，是以系數矩陣P.m[d][(10*d+a)%x]+=num[a]

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX=105;
const long long MOD=1000000007;

int num[10]={0},x;

struct Matrix{
    long long  m[MAX][MAX];
}dp,P,I;

Matrix matrixmul(const Matrix& a,const Matrix& b) {//矩陣乘法
    int i,j,k;
    Matrix c;
    for (i = 0 ; i < x; i++)
        for (j = 0; j < x;j++) {
            c.m[i][j] = 0;
            for (k = 0; k < x; k++)
                c.m[i][j] += (a.m[i][k] * b.m[k][j])%MOD;
            c.m[i][j] %= MOD;
        }
    return c;
}

Matrix quickpow(long long n) {
    Matrix m = P, b = I;
    while (n >= 1) {
        if (n & 1)
            b = matrixmul(b,m);
        n = n >> 1;
        m = matrixmul(m,m);
    }
    return b;
}

int main() {
    int n,b,k,a,i,j;
    scanf("%d%d%d%d",&n,&b,&k,&x);
    while(n--) {
        scanf("%d",&a);
        ++num[a];
    }
    memset(I.m,0,sizeof(I.m));
    memset(P.m,0,sizeof(P.m));
    memset(dp.m,0,sizeof(dp.m));
    for(i=0;i<x;++i) {
        I.m[i][i]=1;
        for(j=1;j<=9;++j) {
            P.m[i][(10*i+j)%x]+=num[j];
        }
    }
    dp.m[0][0]=1;
    dp=matrixmul(dp,quickpow(b));
    printf("%I64d\n",dp.m[0][k]);
    return 0;
}
           

方法二：O(log(b)*x^2)

賽後看到有人用O(log(b)*x^2)的方法

設dp[i][j]表示前i個數字組成的數字模x為j時的方案數，num[a]表示可選數字中a出現的次數

則通過dp[1]可以利用快速幂的方法求得dp[b]，由于dp[i]是一維，是以O(x^2)便可通過dp[i]算得dp[2*i]和dp[2*i+1]

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX=105;
const long long MOD=1000000007;

int num[10]={0},x;

struct Matrix{
    long long  dp[MAX];
    Matrix() {
        memset(dp,0,sizeof(dp));
    }
}ans;

Matrix matrixmul(const Matrix& a,const Matrix& b,int pow) {
    int i,j,k;
    Matrix c;
    for (i = 0 ; i < x; i++) {
        for (j = 0; j < x;j++) {
            k=(i*pow+j)%x;
            c.dp[k]=(c.dp[k]+a.dp[i]*b.dp[j])%MOD;
        }
    }
    return c;
}

void quickpow(long long n) {
    int pow=10%x;
    Matrix b=ans;
    while (n >= 1) {
        if (n & 1)
            ans = matrixmul(ans,b,pow);
        n = n >> 1;
        b = matrixmul(b,b,pow);
        pow=(pow*pow)%x;//pow等于10^前面的數字位數
    }
}

int main() {
    int n,b,k,a,i;
    scanf("%d%d%d%d",&n,&b,&k,&x);
    while(n--) {
        scanf("%d",&a);
        ++num[a];
    }
    for(i=1;i<=9;++i)
        ans.dp[i%x]+=num[i];//更新b==1時的答案
    quickpow(b-1);//由于此時ans已經是第一次的結果了，是以需要減一
    printf("%I64d\n",ans.dp[k]);
    return 0;
}
           

——————————————————————補題分割線——————————————————————

C. Wet Shark and Flowers （數學）

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

There are n sharks who grow flowers for Wet Shark. They are all sitting around the table, such that sharks i and i + 1 are neighbours for all i from 1 to n - 1. Sharks n and 1 are neighbours too.

Each shark will grow some number of flowers si. For i-th shark value si is random integer equiprobably chosen in range from li to ri. Wet Shark has it's favourite prime number p, and he really likes it! If for any pair of neighbouring sharks i and j the product si·sj is divisible by p, then Wet Shark becomes happy and gives 1000 dollars to each of these sharks.

At the end of the day sharks sum all the money Wet Shark granted to them. Find the expectation of this value.

Input

The first line of the input contains two space-separated integers n and p (3 ≤ n ≤ 100 000, 2 ≤ p ≤ 109) — the number of sharks and Wet Shark's favourite prime number. It is guaranteed that p is prime.

The i-th of the following n lines contains information about i-th shark — two space-separated integers li and ri (1 ≤ li ≤ ri ≤ 109), the range of flowers shark i can produce. Remember that si is chosen equiprobably among all integers from li to ri, inclusive.

Output

Print a single real number — the expected number of dollars that the sharks receive in total. You answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if 

.

Sample test(s) input

3 2
1 2
420 421
420420 420421
      

output

4500.0
      

input

3 5
1 4
2 3
11 14
      

output

0.0
      

Note

A prime number is a positive integer number that is divisible only by 1 and itself. 1 is not considered to be prime.

Consider the first sample. First shark grows some number of flowers from 1 to 2, second sharks grows from 420 to 421 flowers and third from 420420 to 420421. There are eight cases for the quantities of flowers (s0, s1, s2) each shark grows:

1. (1, 420, 420420): note that s0·s1 = 420, s1·s2 = 176576400, and s2·s0 = 420420. For each pair, 1000 dollars will be awarded to each shark. Therefore, each shark will be awarded 2000 dollars, for a total of 6000 dollars.
2. (1, 420, 420421): now, the product s2·s0 is not divisible by 2. Therefore, sharks s0 and s2 will receive 1000 dollars, while shark s1will receive 2000. The total is 4000.
3. (1, 421, 420420): total is 4000
4. (1, 421, 420421): total is 0.
5. (2, 420, 420420): total is 6000.
6. (2, 420, 420421): total is 6000.
7. (2, 421, 420420): total is 6000.
8. (2, 421, 420421): total is 4000.

The expected value is 

.

In the second sample, no combination of quantities will garner the sharks any money.

題目大意：n個人圍着一個桌子坐，每個人可以随機種s[i]朵花，其中l[i]<=s[i]<=r[i]，如果相鄰兩個人種花數的乘積能被一個質數p整除，則這兩個人會分别得到1000元，求所有人得錢總數的期望

一看到數學題直接就放棄了，一看題解，原來還是比較簡單的

官方題解：

Let f(x) be the probability that the product of the number of flowers of sharks x and 

 is divisible by p.

We want the expected value of the number of pairs of neighbouring sharks whose flower numbers are divisible by p. From linearity of expectation, this is equal to the probabilities that each pair multiplies to a number divisible by p, or f(0) + f(1) + ... + f(n). (Don't forget about the wrap-around at n)

Now, for each pair of neighbouring sharks, we need to figure out the probability that their product is divisible by p. Consider an interval[li, ri]. How many numbers in this interval are divisible by p? Well, it is easier if we break the interval [li, ri] up into [1, ri] - [1, li - 1]. Since 1, 2, ..., x contains 

 numbers divisible by p, the interval [li, ri] contains 

 numbers divisible by p.

Now, consider two numbers 

 and 

, with 

. Let ai be the number of integers divisible by pin the interval [li, ri], and define aj similarly. Now what's the probability that fi·fj is divisible by p? We can count the opposite: the probability that fi·fj is not divisible by p. Since p is a prime, this means neither fi nor fj is divisible by p. The number of integers in [li, ri]not divisible by p is ri - li + 1 - ai. Similar for j. Therefore, the probability fi·fj is not divisible by p is given by 

. Therefore, the probability it is can be given by 

. Now, just sum over this for all i.

大意是先計算i和i+1個人[l,r]中不能被p整除的機率x[i],x[i+1]，則兩人種花數乘積能被p整除的機率為1-x[i]*x[i+1]，則兩人共收錢2000*( 1-x[i]*x[i+1])

運用正難則反的方法，先計算[1,l-1]和[1,r]中能被p整除的數的個數為[(i-1)/p]，[r/p]，則[l,r]中不能被p整除的數為r-l+1-[r/p]+[(i-1)/p]

#include <cstdio>

using namespace std;

int n,p,fl,fr,l[2],r[2],i,cur;
double ans=0;

inline double f(int x) {
    return 1.0-(0.0+r[x]/p-(l[x]-1)/p)/(r[x]-l[x]+1);
}

int main() {
    scanf("%d%d%d%d",&n,&p,&fl,&fr);
    l[0]=fl;
    r[0]=fr;
    cur=1;
    for(i=1;i<n;++i) {
        scanf("%d%d",l+cur,r+cur);
        ans+=1.0-f(0)*f(1);
        cur^=1;
    }
    l[cur]=fl;
    r[cur]=fr;
    printf("%.6lf\n",2000.0*(ans+1.0-f(0)*f(1)));
    return 0;
}
           

D. Rat Kwesh and Cheese （模拟||數學分析）

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Wet Shark asked Rat Kwesh to generate three positive real numbers x, y and z, from 0.1 to 200.0, inclusive. Wet Krash wants to impress Wet Shark, so all generated numbers will have exactly one digit after the decimal point.

Wet Shark knows Rat Kwesh will want a lot of cheese. So he will give the Rat an opportunity to earn a lot of cheese. He will hand the three numbers x, y and z to Rat Kwesh, and Rat Kwesh will pick one of the these twelve options:

1. a1 = xyz;
2. a2 = xzy;
3. a3 = (xy)z;
4. a4 = (xz)y;
5. a5 = yxz;
6. a6 = yzx;
7. a7 = (yx)z;
8. a8 = (yz)x;
9. a9 = zxy;
10. a10 = zyx;
11. a11 = (zx)y;
12. a12 = (zy)x.

Let m be the maximum of all the ai, and c be the smallest index (from 1 to 12) such that ac = m. Rat's goal is to find that c, and he asks you to help him. Rat Kwesh wants to see how much cheese he gets, so he you will have to print the expression corresponding to that ac.

Input

The only line of the input contains three space-separated real numbers x, y and z (0.1 ≤ x, y, z ≤ 200.0). Each of x, y and z is given with exactly one digit after the decimal point.

Output

Find the maximum value of expression among xyz, xzy, (xy)z, (xz)y, yxz, yzx, (yx)z, (yz)x, zxy, zyx, (zx)y, (zy)x and print the corresponding expression. If there are many maximums, print the one that comes first in the list.

xyz should be outputted as x^y^z (without brackets), and (xy)z should be outputted as (x^y)^z (quotes for clarity).

Sample test(s) input

1.1 3.4 2.5
      

output

z^y^x
      

input

2.0 2.0 2.0
      

output

x^y^z
      

input

1.9 1.8 1.7
      

output

(x^y)^z      

題目大意：給定0.1~200.0的三個一位小數，輸出十二種表達式中結果最大的

已經想到用log了，但是200.0^200.0還是太大，用double不能表示，但是long double能夠表示，沒想到long double還是做題不夠

200.0^200.0            ≈         1.60694e+460

double                                -1.7*10^-308~1.7*10^308

long double                       -1.2*10^-4932~1.2*10^4932

方法一：long double模拟

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int num=0,index=1;
long double res;
char ans[11][11]={"x^y^z",
                  "x^z^y",
                  "(x^y)^z",
                  "y^x^z",
                  "y^z^x",
                  "(y^x)^z",
                  "z^x^y",
                  "z^y^x",
                  "(z^x)^y",
                 };

inline void MyMax(long double a) {
    if(res+0.0000000001<a) {
        res=a;
        index=num;
    }
}

inline long double pow_pow(long double x,long double y,long double z) {//x^y^z
    ++num;
    return pow(y,z)*log(x);
}

inline long double pow_multi(long double x,long double y,long double z) {//(x^y)^z
    ++num;
    return y*z*log(x);
}

int main() {
    double x,y,z;
    scanf("%lf%lf%lf",&x,&y,&z);
    res=pow_pow(x,y,z);
    MyMax(pow_pow(x,z,y));
    MyMax(pow_multi(x,y,z));//由于(x^y)^z=x^(y*z)=(x^z)^y，則所有的第四個均不會輸出

    MyMax(pow_pow(y,x,z));
    MyMax(pow_pow(y,z,x));
    MyMax(pow_multi(y,x,z));

    MyMax(pow_pow(z,x,y));
    MyMax(pow_pow(z,y,x));
    MyMax(pow_multi(z,x,y));
    printf("%s\n",ans[index-1]);
    return 0;
}
           

方法二：數學分析

比賽時也通過分析的手段解答，但是隻靠分析無法得出答案 官方正解：

The tricky Rat Kwesh has finally made an appearance; it is time to prepare for some tricks. But truly, we didn't expect it to be so hard for competitors though. Especially the part about taking log of a negative number.

We need a way to deal with xyz and xyz. We cannot directly compare them, 200200200 is way too big. So what we do? Take log! 

 is an increasing function on positive numbers (we can see this by taking 

, then 

, which is positive when we are dealing with positive numbers). So if 

, then x ≥ y.

When we take log, 

 But yz can still be 200200, which is still far too big. So now what can we do? Another log! But is it legal? When x = 0.1 for example, 

, so we cannot take another log. When can we take another log, however? We need

 to be a positive number. yz will always be positive, so all we need is for 

 to be positive. This happens when x > 1. So ifx, y, z > 1, everything will be ok.

There is another good observation to make. If one of x, y, z is greater than 1, then we can always achieve some expression (out of those 12) whose value is greater than 1. But if x < 1, then xa will never be greater than 1. So if at least one of x, y, z is greater than 1, then we can discard those bases that are less than or equal to 1. In this case, 

. Remember that 

, so 

. Similarly, 

.

The last case is when x ≤ 1, y ≤ 1, z ≤ 1. Then, notice that for example, 

. But the denominator of this fraction is something we recognize, because 10 / 3 > 1. So if all x, y, z < 1, then it is the same as the original problem, except we are looking for the minimum this time.

大概意思是分類讨論： ①如果x,y,z均大于1，則可以取兩次對數，進而降低次數，取最大值 ②如果x,y,z均小于1，則将底數去倒數後，取兩次對數，取最小值 ③剩餘的情況，隻能用大于等于1的數當底數，取兩次對數，取最大值

讨論太麻煩，代碼就不寫了...

方法三：complex<double>模拟

又看到有人說可以用複數解決log(x)為負的問題

log( - x) = log( - 1 * x) = log( - 1) + logx =log(x)+π*i 

#include <cstdio>
#include <cmath>
#include <complex>
#include <algorithm>

using namespace std;

int num=0,index=1;
complex<double> res;
char ans[11][11]={"x^y^z",
                  "x^z^y",
                  "(x^y)^z",
                  "y^x^z",
                  "y^z^x",
                  "(y^x)^z",
                  "z^x^y",
                  "z^y^x",
                  "(z^x)^y",
                 };

inline void MyMax(complex<double> a) {
    if(abs(a.imag())<1e-6) {//如果a沒有虛部
        if(abs(res.imag())<1e-6) {
            if(res.real()<a.real()) {
                res=a;
                index=num;
            }
        }
        else {//如果res有虛部
            res=a;
            index=num;
        }
    }
    else {//如果a有虛部
        if(abs(res.imag())>1e-6) {//如果res有虛部
            if(res.real()>a.real()) {
                res=a;
                index=num;
            }
        }
    }
}

inline complex<double> pow_pow(complex<double> x,complex<double> y,complex<double> z) {//x^y^z
    ++num;
    return z*log(y)+log(log(x));
}

inline complex<double> pow_multi(complex<double> x,complex<double> y,complex<double> z) {//(x^y)^z
    ++num;
    return log(y*z)+log(log(x));
}

int main() {
    double xx,yy,zz;
    scanf("%lf%lf%lf",&xx,&yy,&zz);
    complex<double> x(xx),y(yy),z(zz);
    res=pow_pow(x,y,z);
    MyMax(pow_pow(x,z,y));
    MyMax(pow_multi(x,y,z));//由于(x^y)^z=x^(y*z)=(x^z)^y，則所有的第四個均不會輸出

    MyMax(pow_pow(y,x,z));
    MyMax(pow_pow(y,z,x));
    MyMax(pow_multi(y,x,z));

    MyMax(pow_pow(z,x,y));
    MyMax(pow_pow(z,y,x));
    MyMax(pow_multi(z,x,y));
    printf("%s\n",ans[index-1]);
    return 0;
}