Submit | All submissions | Best solutions | Back to list |
WPBB - B Nobel (professional) |
A scientist, aspiring to the Nobel Prize, made a series of n measurements and received all possible results from the set {1,2,3, ...,n-1,n}. The scientist knows that if he could only obtain s/k as a result, the Nobel Prize would be his. He decided to disregard all but k measurements, such that the average of the remaining ones is s/k. Help him with this task. The stakes are high as the scientist has offered to share the award.
Multiple test cases
The first line of the input contains Z ≤ 8000 - the number of test cases. Z descriptions of single test cases follow.
Single test case
The input contains one line with three space-separated integers n, s and k.
Bounds
Common: 1 ≤ k ≤ n ≤ 40000, 0 ≤ s ≤ 109.
Output
Basic: If there exist k different elements of the set {1,2,...,n} whose average is s/k, the only line of the output should contain the word YES. Otherwise, output NO.
Professional: The first row should be as in the basic version. Additionally, if the answer is YES, output a second line containing a binary string of length n (containing ones and zeroes, not separated by spaces). A 1 on position i in the string means that the measurement i should be retained by the scientist, 0 - that it should be disregarded.
Sample input
3 3 6 2 5 7 3 1 1 1
Sample output for the professional version
NIE TAK 11010 TAK 1
Added by: | gawry |
Date: | 2011-10-07 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |