KSMALL - K-th smallest number
Given an array of (pseudo) random numbers generated by the C++ function below, your task is to find the K-th smallest number of all the numbers.
unsigned array[5000000]; void randomize(unsigned a,unsigned b,unsigned mod) { for( int i=0 ; i<5000000 ; i++ ) { a = 31014 * (a & 65535) + (a >> 16); b = 17508 * (b & 65535) + (b >> 16); array[i] = ((a << 16) + b) % mod; } }
Note that the computation might overflow, but we only care about the last 32 bit of each result so it doesn't matter.
Input
One line with 4 numbers (a, b, mod, K) separated by space.
0 < a, b < 65535
2 < mod < 232-1
1 < K < 5x106
Output
K-th smallest number of all the generated numbers.
Example
Input: 2 3 100000007 23 Output: 434
hide comments
Jason S:
2014-08-24 04:42:56
Is it supposed to be sorted(array)[k-1] or the kth unique value? I have some thousands of testcases based on the former (which the example implies) that pass but am getting WA. |
|
anurag garg:
2014-03-25 13:41:50
@author can you have a look at my submission:11324082
|
Added by: | Andy |
Date: | 2014-03-10 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |