Sereja and Vectors
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.Sereja have N vectors v, v, ..., v[N]. Every vector is given by K numbers (x, x, ..., x[K]). Sereja want to choose few vectors, such that sum of those vectors will be smaller than or equal to vector A. In other word you should find such numbers: i < i < ...< i[m], such that v[i]+v[i]+...+v[i[m]] <= A. Vector Q <= vector W when Q.x <= W.x, Q.x <= W.x, ..., Q.x[K] <= W.x[K]. Help Sereja, find best subset of vectors in such way that all conditions will hold.
InputFirst line contain integer T - number of testcases. First line of each testcase contain integer N - number of vectors and K - number of integers that contain every vector. Next N lines contain K numbers - next vector coordinates (x, x, ..., x[K]). Last line of input contain vector A, that also given by K numbers.
OutputFor each testcase in first line should contain number q - number of vectors in your subset. Next line should contain q numbers - coordiates of vector: 1 <= i < i < ... < i[q] <= N . If q equal to 0, you shouldn't output second string.
Constraints1 <= T <= 10 1 <= N*K <= 100000 all corrdiantes are positive integers, that are not exceeded 1000000000.
Input: 3 3 2 1 2 2 1 1 1 3 3 5 3 10 20 30 30 20 10 10 30 10 10 30 40 40 10 20 80 60 40 1 1 10 20 Output: 2 1 2 3 2 3 5 0
ScoringLets Sum will be next value: (A.x - v[i].x - v[i].x - ... - v[i[q]].x) + (A.x - v[i].x - v[i].x - ... - v[i[q]].x) + ... + (A.x[k] - v[i].x[k] - v[i].x[k] - ... - v[i[q]].x[k])
Lets S will be the sum of values q/(Sum + 1) per each testcase. You should maximize S. The score will be counted as S/B, where S is your sum, and B will be the best sum.
We have 10 official test files. You must correctly solve all test files to receive OK. During the contest, your overall score is the sum of the scores on the first 2 test files. After the contest, all solutions will be rescored by the sum of the scores on the rest 8 test files.
Testcase generationThere are tests with different N. Most of the tests are random, and some are made in special way.
|Time Limit:||0.619672 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.