All submissions for this problem are available.
Read problems statements in Russian here
The Head Chef is studying the motivation and satisfaction level of his chefs . The motivation and satisfaction of a Chef can be represented as an integer . The Head Chef wants to know the N th smallest sum of one satisfaction value and one motivation value for various values of N . The satisfaction and motivation values may correspond to the same chef or different chefs . Given two arrays, the first array denoting the motivation value and the second array denoting the satisfaction value of the chefs . We can get a set of sums(add one element from the first array and one from the second). For each query ( denoted by an integer qi ( i = 1 to Q ) , Q denotes number of queries ) , find the qi th element in the set of sums ( in non-decreasing order ) .
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a two space seperated integers K and Q denoting the number of chefs and the number of queries .
- The second line of each test case contains K space-separated integers A1, A2, ..., AK denoting the motivation of Chefs.
- The third line of each test case contains K space-separated integers B1, B2, ..., BK denoting the satisfaction of Chefs.
- The next Q lines contain a single integer qi ( for i = 1 to Q ) , find the qi th element in the set of sums .
- For each query of each test case, output a single line containing the answer to the query of the testcase
Should contain all the constraints on the input data that you may have. Format it like:
- 1 ≤ T ≤ 5
- 1 ≤ K ≤ 20000
- 1 ≤ Q ≤ 500
- 1 ≤ qi ( for i = 1 to Q ) ≤ 10000
- 1 ≤ Ai ≤ 10^18 ( for i = 1 to K )
- 1 ≤ Bi ≤ 10^18 ( for i = 1 to K )
Input: 1 3 1 1 2 3 4 5 6 4 Output: 7
Example case 1. There are 9 elements in the set of sums :
1 + 4 = 5
2 + 4 = 6
1 + 5 = 6
1 + 6 = 7
2 + 5 = 7
3 + 4 = 7
2 + 6 = 8
3 + 5 = 8
3 + 6 = 9
The fourth smallest element is 7.
|Tags||binary-search, cook40, easy, priority, sorting, vineetpaliwal|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.