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

< 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++)
cout<<"go for it ";
1.partial_sort and priority_queue gives tle

Last edit: 2018-10-13 17:41:28
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
still it shows time limit exceeded.
I don't understand what to do next

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. :(
Is the time limit too strict??

: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.

Andy: most people who solve this don't even reach half the time limit, so I think it's reasonable.

Last edit: 2015-01-30 14:46:00

Added by:Andy
Date:2014-03-10
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All