首页 > 其他 > 详细

codeforces A. TL 题解

时间:2014-05-03 16:53:30      阅读:570      评论:0      收藏:0      [点我收藏+]

Valera wanted to prepare a Codesecrof round. He‘s already got one problem and he wants to set a time limit (TL) on it.

Valera has written n correct solutions. For each correct solution, he knows its running time (in seconds). Valera has also wrote m wrong solutions and for each wrong solution he knows its running time (in seconds).

Let‘s suppose that Valera will set v seconds TL in the problem. Then we can say that a solution passes the system testing if its running time is at most v seconds. We can also say that a solution passes the system testing with some "extra" time if for its running time, a seconds, an inequality 2a?≤?v holds.

As a result, Valera decided to set v seconds TL, that the following conditions are met:

  1. v is a positive integer;
  2. all correct solutions pass the system testing;
  3. at least one correct solution passes the system testing with some "extra" time;
  4. all wrong solutions do not pass the system testing;
  5. value v is minimum among all TLs, for which points 1234 hold.

Help Valera and find the most suitable TL or else state that such TL doesn‘t exist.

Input

The first line contains two integers nm (1?≤?n,?m?≤?100). The second line contains n space-separated positive integers a1,?a2,?...,?an (1?≤?ai?≤?100) — the running time of each of the n correct solutions in seconds. The third line contains m space-separated positive integers b1,?b2,?...,?bm (1?≤?bi?≤?100) — the running time of each of mwrong solutions in seconds.

Output

If there is a valid TL value, print it. Otherwise, print -1.

Sample test(s)
input
3 6
4 5 2
8 9 6 10 7 11
output
5

这句话难读懂:

We can also say that a solution passes the system testing with some "extra" time if for its running time, a seconds, an inequality 2a?≤?v holds.

就是说:如果一个AC的解决方案的运行时间是a,满足2*a <= v,那么就说这个运行时间通过而且有"extra"时间(a)


void TLjudge()
{
	int n, m, minVal = 1<<30, maxVal = 1<<31, a = 0;
	cin>>n>>m;
	while (n--)
	{
		cin>>a;
		if (a < minVal) minVal = a;
		if (a > maxVal) maxVal = a;
	}
	int ans = max(minVal*2, maxVal);
	bool ok = true;
	while (m--)
	{
		cin>>a;
		if (a <= ans)
		{
			ok = false;
			break;
		}
	}
	if (ok) cout<<ans;
	else cout<<-1;
};



codeforces A. TL 题解,布布扣,bubuko.com

codeforces A. TL 题解

原文:http://blog.csdn.net/kenden23/article/details/24873129

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!