2015
05-24

# D-mail

To control the world, which is the ambition of Ryntarou Okabe, a mad scientist, is a problem that both of technology and wisdom are needed to handle it. After long time of experiment, Okabe eventually invented a strange machine, Telephone Oven, which can be used to send mails to the past! The mail is called D-mail in short. D-mail can be used to change the future of the world, but it cannot change it as what Okabe thinks exactly. According to the theory of time travel, the future of the world can be described by a real number, which is called Divergence. Now, Okabe has already calculated the Divergence that represents the world in which Okabe takes the control of the whole world. He calls it Steins Gate. There are kinds of D-mails with different content. And he has got the influence each kind of D-mail has to the Divergence. Now he wants to change the Divergence to a number as close to the Steins Gate as possible by selecting several kinds of D-mail, while each kind of D-mail cannot be used more than once. (He can choose 0 D-mail.)

But if he changes the divergence too greatly that it becomes bigger than 2 or equals 2 during the process he send D-mail, then will he be trapped in the infinity maze of time and be "corrected" by the world itself, so he should choose the best order to send the D-mail so as to keep alive before he achieves his goal. Can you help him calculate the best result he can get? The original Divergence is 0.

The first line contains an integer T, which represents the number of test cases.
For each test, the first line contains a real number D (-1<D<2), Stains Gate and an integer N(0<N<=200 ),represents the number of the kinds of D-mails. For the next N lines, each line contains a real number (which is no lesser than -0.1 and no bigger than 2)showing the influence of this D-mail to the Divergence. (all real number in the input file are written with exactly four digits after a decimal point.)

The first line contains an integer T, which represents the number of test cases.
For each test, the first line contains a real number D (-1<D<2), Stains Gate and an integer N(0<N<=200 ),represents the number of the kinds of D-mails. For the next N lines, each line contains a real number (which is no lesser than -0.1 and no bigger than 2)showing the influence of this D-mail to the Divergence. (all real number in the input file are written with exactly four digits after a decimal point.)

2
0.1234 2
0.1211
0.0023
-0.1234 2
0.1211
0.0023

0.1234
0.0000

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 2e5 + 2e4;

const int shift = 2e5;

bool reach[N];

int w[205];

double x;
scanf("%lf",&x);
if(x > 0)
return x * 10000 + 1e-8;
else
return x * 10000 - 1e-8;
}

int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
memset(reach,false,sizeof(reach));
int goal = read();
scanf("%d",&n);
for(int i=0;i<n;i++)
sort(w,w+n);
reach[ 0 + shift ] = true;
for(int i=0;i<n;i++)
{
bool f = w[i] > 0;
if(f)
{
for(int j=N-1-w[i];j>=0;j--)
if(reach[j])
reach[ j + w[i] ] = true;
}
else
{
for(int j=-w[i];j<N;j++)
if(reach[j])
reach[ j + w[i] ] = true;
}
}
int i = goal + shift , j = 0;
int ans = -1;
while(1)
{
if(i-j >= 0 && reach[i-j])
{
ans = i - j;
break;
}
if(i+j < N && reach[i+j])
{
ans = i + j;
break;
}
++j;
}
printf("%.4f\n",(ans-shift)/10000.0);
}
return 0;
}