479D - Long Jumps, 480B - Long Jumps
It is easy to see that the answer is always , or . If we can already measure both x and y, output . Then try to measure both x and y by adding one more mark. If it was not successful, print two marks: one at x, other at y. So, how to check if the answer is ? Consider all existing marks. Let some mark be at r. Try to add the new mark in each of the following positions: r - x, r + x, r - y, r + y. If it become possible to measure both x and y, you have found the answer. It is easy to check this: if, for example, we are trying to add the mark at r + x, we just check if there is a mark at r + x + y or r + x - y (by a binary search, since the marks are sorted). Make sure that the adde marks are in [, L].
好久没写解题报告了。
这是一道模拟题，其实是看了Tutorial 才确定下的算法思路。
题目意思还是很简单的，在[0, L]范围内增加一个标记处，使得能测量出X，Y的值。
易得，增加标记出只有三种情况，0，1，2
0的话就是已有的标记出就可以测量出X,Y的值。
2的话就是 就算增加一个标记出也无法测量出X，Y的值。
在1这种情况下是可以分类的。
1.r -c
2.r + c
3.r - y
4.r + y
有四种可能标记处。
ex. 如果我们在（r + c）处做标记（保证合法），则判断原有序列中是否存在(r + c) - y 或者是(r + c) + y
如果存在，则得证增加这么一个(r + c)可以测量出X,Y的值。
如果还不动，画一条先端模拟一下就会懂了～
Tips: 有一点不能忘记，就是一开始算已有的标记出是否能测出X，Y的时候
不能用O(n^2)的遍历。
只需要O（n）的遍历，当然，同一数字可能同时满足测量X，Y的情况。
（查找一个值的时候，在有序序列中可用STL中的binary_search）
好久没贴代码了= =
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
using namespace std;
const int INF = 0x3f3f3f3f; int a[];
int n, l; bool Ok(int num){
if(num > && num <= l) return true;
return false;
} int main(){
int i, j, k, t, x, y;
while(EOF != scanf("%d%d%d%d",&n,&l,&x,&y)){
for(i = ; i <= n; ++i) scanf("%d",&a[i]);
bool xx = false;
bool yy = false;
for(i = ; i <= n; ++i){
if(binary_search(a, a + n + , a[i] + x)){
xx = true;
}
if(binary_search(a, a + n + , a[i] + y)){
yy = true;
}
}
if(xx && yy){
printf("0\n");
continue;
}
bool status = false;
for(i = ; i <= n; ++i){
if(Ok(a[i] - x)){
if(yy){
printf("1\n%d\n",a[i] - x);
status = true;
break;
}
if(binary_search(a, a + n + , a[i] - x - y) || binary_search(a, a + n + , a[i] - x + y)){
printf("1\n%d\n",a[i] - x);
status = true;
break;
}
}
if(Ok(a[i] + x)){
if(yy){
printf("1\n%d\n",a[i] + x);
status = true;
break;
}
if(binary_search(a, a + n + , a[i] + x - y) || binary_search(a, a + n + , a[i] + x + y)){
printf("1\n%d\n",a[i] + x);
status = true;
break;
}
}
if(Ok(a[i] - y)){
if(xx){
printf("1\n%d\n",a[i] - y);
status = true;
break;
}
if(binary_search(a, a + n + , a[i] - y - x) || binary_search(a, a + n + , a[i] - y - x)){
printf("1\n%d\n",a[i] - y);
status = true;
break;
}
}
if(Ok(a[i] + y)){
if(xx){
printf("1\n%d\n",a[i] + y);
status = true;
break;
}
if(binary_search(a, a + n + , a[i] + y - x) || binary_search(a, a + n + , a[i] + y + x)){
printf("1\n%d\n",a[i] + y);
status = true;
break;
}
}
}
if(!status){
printf("2\n%d %d\n",x,y);
}
}
return ;
}