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
David:
2021-03-02 09:45:11
Given that there are no Java solutions, it seems that Java programs should be given more time. |
|
wjli:
2020-08-04 22:51:17
Nice problem for SQRT decomposition. |
|
priyanshul:
2018-11-21 13:07:06
its showing segmentation fault, what should I do? (i am using quicksort to sort the array and then reading the (k-1)th element of the array. |
|
jmr99:
2018-10-13 17:18:18
if(heard about ""nth_element"" stl in c++)
|
|
akki:
2017-04-14 13:36:15
Hint: Learn 3-way partitioning (quicksort). |
|
aakash_s:
2016-09-23 08:29:41
I have tried O(n) approach with optimizations
|
|
sivakumarar:
2016-09-22 19:07:43
How to find which of the 20 test case failed. Is there are way to get the test input files to test and debug it locally , before uploading the solution. |
|
Sarot Busala:
2015-07-01 09:33:25
I have tried 3 different ways, one of this is O(N) approach and got only TLE. :(
|
|
:D:
2015-03-10 22:10:15
Re Jason S: It's the sorted(array)[k-1] version. That way for every K in the specified input range there is always a valid solution. |
|
Rahul Lingala:
2015-01-23 21:58:07
Time limit is too strict. I know the perfect algorithm, but still my solution is not getting accepted even after optimising it to the maximum extent.
|
Added by: | Andy |
Date: | 2014-03-10 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |