Codeforces ラウンド #274 (ディビジョン 1) A B C_html/css_WEB-ITnose

昨夜一起来都 5 点半了。試験

1 秒

テストごとのメモリ制限

スケジュールによれば、学生は i 番目の科目の試験を番号 ai の日に受けることができます。しかし、ヴァレラさんは各教師と取り決めをし、i 番目の科目の教師は、bi 日 (bi?

サンプル テスト

35 23 14 2

注

最初のサンプルでは、​​ヴァレラは初日にまず 2 番目の科目の試験を受けます (教師はこう書きます)予定日である 3) を押します。翌日、彼は 3 番目の科目の試験を受け (教師は予定日 4 を書き留めます)、次に最初の科目の試験を受けます (教師は日付 5 のマークを書き留めます)。したがって、ヴァレラは 2 日目に最後の試験を受け、日付は 3、4、5 の降順ではありません。

36 15 24 3

B： http://codeforces.com/contest/480/problem/B

テストごとの制限時間

入力

標準出力

Valery は、バーランドの学校の体育教師です。もうすぐ生徒たちは走り幅跳びのテストを受ける予定ですが、ヴァレリーはお気に入りの定規をなくしてしまいました!

However, there is no reason for disappointment, as Valery has found another ruler, its length is l centimeters. The ruler already has nmarks, with which he can make measurements. We assume that the marks are numbered from 1 to n in the order they appear from the beginning of the ruler to its end. The first point coincides with the beginning of the ruler and represents the origin. The last mark coincides with the end of the ruler, at distance l from the origin. This ruler can be repesented by an increasing sequence a1,?a2,?...,?an, where ai denotes the distance of the i-th mark from the origin (a1?=?0, an?=?l).

Valery believes that with a ruler he can measure the distance of d centimeters, if there is a pair of integers i and j (1?≤?i?≤?j?≤?n), such that the distance between the i-th and the j-th mark is exactly equal to d (in other words, aj?-?ai?=?d).

Under the rules, the girls should be able to jump at least x centimeters, and the boys should be able to jump at least y (x?

Your task is to determine what is the minimum number of additional marks you need to add on the ruler so that they can be used to measure the distances x and y. Valery can add the marks at any integer non-negative distance from the origin not exceeding the length of the ruler.

Input

The first line contains four positive space-separated integers n, l, x, y (2?≤?n?≤?105, 2?≤?l?≤?109, 1?≤?x?

The second line contains a sequence of n integers a1,?a2,?...,?an (0?=?a1?

Output

In the first line print a single non-negative integer v ? the minimum number of marks that you need to add on the ruler.

In the second line print v space-separated integers p1,?p2,?...,?pv (0?≤?pi?≤?l). Number pi means that the i-th mark should be at the distance of pi centimeters from the origin. Print the marks in any order. If there are multiple solutions, print any of them.

Sample test(s)

input

3 250 185 2300 185 250

output

1230

input

4 250 185 2300 20 185 250

output

input

2 300 185 2300 300

output

2185 230

Note

In the first sample it is impossible to initially measure the distance of 230 centimeters. For that it is enough to add a 20 centimeter mark or a 230 centimeter mark.

In the second sample you already can use the ruler to measure the distances of 185 and 230 centimeters, so you don't have to add new marks.

In the third sample the ruler only contains the initial and the final marks. We will need to add two marks to be able to test the children's skills.

有意思的题。

题意：有一个长为L的尺子，n个刻度，为了测出x和y的长度，问最少要添加几个刻度。

可以用一个set或者二分查找每一个刻度+x，+y是否存在。如果都不存在，那么判断两个刻度之间有没有x+y,y-x的长度，如果有那么只需添加一个就行。代码有点丑233.。

/** * @author neko01 *///#pragma comment(linker, "/STACK:102400000,102400000")#include <cstdio>#include <cstring>#include <string.h>#include <iostream>#include <algorithm>#include <queue>#include <vector>#include <cmath>#include <set>#include <map>using namespace std;typedef long long LL;#define min3(a,b,c) min(a,min(b,c))#define max3(a,b,c) max(a,max(b,c))#define pb push_back#define mp(a,b) make_pair(a,b)#define clr(a) memset(a,0,sizeof a)#define clr1(a) memset(a,-1,sizeof a)#define dbg(a) printf("%d\n",a)typedef pair<int,int> pp;const double eps=1e-9;const double pi=acos(-1.0);const int INF=0x3f3f3f3f;const LL inf=(((LL)1)<<61)+5;const int N=100005;LL a[N];int main(){    int n;    LL l,x,y;    scanf("%d%lld%lld%lld",&n,&l,&x,&y);    for(int i=0;i<n;i++)        scanf("%d",&a[i]);    int ans=0,flag1=0,flag2=0;    for(int i=0;i<n;i++)    {        if(a[i]+x<=l&&binary_search(a+i,a+n,a[i]+x))        {            flag1=1;            break;        }    }    for(int i=0;i<n;i++)    {        if(a[i]+y<=l&&binary_search(a+i,a+n,a[i]+y))        {            flag2=1;            break;        }    }    ans=2-flag1-flag2;    if(ans!=0)    {        if(ans==1)        {            printf("1\n");            if(flag1==0)                printf("%d\n",x);            if(flag2==0)                printf("%d\n",y);            return 0;        }        for(int i=0;i<n;i++)        {            if(a[i]+x+y<=l&&binary_search(a+i,a+n,a[i]+x+y))            {                printf("1\n%d\n",a[i]+x);                return 0;            }            if(a[i]-y>=0&&binary_search(a,a+i,a[i]+x-y))            {                printf("1\n%d\n",a[i]-y);                return 0;            }            if(a[i]+y<=l&&binary_search(a+i,a+n,a[i]+y-x))            {                printf("1\n%d\n",a[i]+y);                return 0;            }        }        printf("2\n%I64d %I64d\n",x,y);    }    else printf("0\n");    return 0;}

C. Riding in a Lift

time limit per test

memory limit per test

input

output

Imagine that you are in a building that has exactly n floors. You can move between the floors in a lift. Let's number the floors from bottom to top with integers from 1 to n. Now you're on the floor number a. You are very bored, so you want to take the lift. Floor number b has a secret lab, the entry is forbidden. However, you already are in the mood and decide to make k consecutive trips in the lift.

Let us suppose that at the moment you are on the floor number x (initially, you were on floor a). For another trip between floors you choose some floor with number y (y?≠?x) and the lift travels to this floor. As you cannot visit floor b with the secret lab, you decided that the distance from the current floor x to the chosen y must be strictly less than the distance from the current floor x to floor b with the secret lab. Formally, it means that the following inequation must fulfill: |x?-?y|?

Your task is to find the number of distinct number sequences that you could have written in the notebook as the result of k trips in the lift. As the sought number of trips can be rather large, find the remainder after dividing the number by 1000000007 (109?+?7).

Input

The first line of the input contains four space-separated integers n, a, b, k (2?≤?n?≤?5000, 1?≤?k?≤?5000, 1?≤?a,?b?≤?n, a?≠?b).

Output

Print a single integer ? the remainder after dividing the sought number of sequences by 1000000007 (109?+?7).

Sample test(s)

input

5 2 4 1

output

input

5 2 4 2

output

input

5 3 4 1

output

Note

Two sequences p1,?p2,?...,?pk and q1,?q2,?...,?qk are distinct, if there is such integer j (1?≤?j?≤?k), that pj?≠?qj.

Notes to the samples:

1. In the first sample after the first trip you are either on floor 1, or on floor 3, because |1?-?2|?
2. In the second sample there are two possible sequences: (1,?2); (1,?3). You cannot choose floor 3 for the first trip because in this case no floor can be the floor for the second trip.
3. In the third sample there are no sought sequences, because you cannot choose the floor for the first trip.

题意：一个人在电梯里面初始位置a层，只能上下|a-b|的位置，也不能停在该楼层，问这样走k次后不同的方案有多少种。

分析：dp方程很好写,dp[i][j]表示第走i次时在第j层有多少种方案，但是直接转移O(k*n*n)的复杂度肯定超时。

注意转移时比如第i次到第j层(设j

/** * @author neko01 *///#pragma comment(linker, "/STACK:102400000,102400000")#include #include #include #include #include #include #include #include #include #include