Glass Measurement

Problem code: GLASS

All submissions for this problem are available.

Statement

Chef has n glasses each with a capacity of xi.
There are Q+1 people playing a game including the Chef himself. Everyone at his/her turn gives a positive integer Mi and asks the Chef if volume M of water can be transferred using the n glasses with Chef. Chef at his own turn wants to give M as the highest integer volume which cannot be constructed using these n glasses.
So, you need to help chef with this game.
Assume that to construct a volume M, we have a reserve with infinite volume of liquid. If Chef uses ith glass, he has to transfer a volume equal to xi in one turn. He can use a glass multiple times. However, transfer of liquid between glasses is not permitted. For example, you cannot obtain volume of 2 by tranferring liquid from glass of volume 5 to glass of volume 3.
It is always possible to construct volume 0.

Input

First line contains t ( ? 20 ) which is the number of test cases. For each test case, the first line contains n ( the number of glasses ) . The next line contains n space separated integers denoting the capacity of each glass. The next line contains a single integer Q - the number of players excluding the Chef. Then follows a line containing 3 space separated integers a,b,c. Calculate Mi for the ith person as (a*i+b)%c ( i ? 1 ).

Output

For each test case, the first line of output should contain the highest value M desired by Chef [ If there is no positive M, then output -1 ]. Then follows a line containing 2 integers A and B where A denotes the number of Mi which cannot be constructed using the given glasses and B denotes the number of Mi which can be constructed.

Sample Input 

1
2
3 5
2
8 1 10

Sample Output 

7
1 1

Constraints

1 < n ? 10
1 ? xi ? 107
MIN(xi) ? 100000
1 ? Q ? 1000000
1 ? a,c ? 1012
0 ? b ? 1012


Sample Test Case Explanation

There are 2 glasses of size 3 and 5. Volumes 1, 2, 4, 7 cannot be created by the combinations of glass suggested in the problem. Hence, the highest volume is 7.
The 2 queries are for 9 and 7. 9 can be created using the glasses and 7 cannot.

Author: anshuman_singh
Date Added: 2-09-2010
Time Limit: 7 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions