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
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
I am getting TLE after 20th case
is there any chance to get AC with this approach
thanks

Ans: The judge will run all 20 test cases even if you fail at some point. It is possible to get accepted with any O(n) approach, although some optimization might be required.

Last edit: 2014-03-25 21:04:16

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