Kth Smallest

View as PDF

Submit solution

All submissions

Best submissions

Points: 100 (partial)

Time limit: 3.0s

Memory limit: 256M

Author:

glipR

Problem type

This problem is interactive, which means you need to communicate with the grader using standard input and output. There are some gotchas to watch out for with interactive problems (flush your I/O!), see this post for more information.

You have a series of $q$ ~q~ non-decreasing sequences of positive integers, each of length $k$ ~k~. You'd like to find the $k^{th}$ ~k^{th}~ smallest value of all of these sequences collectively.

For example, suppose $q = 4$ ~q = 4~ and $k = 5$ ~k = 5~, with the following sequences:

[19, 32, 51, 239, 258]
[31, 349, 380, 6736, 6767]
[24, 24, 709, 18506, 18530]
[2, 27, 29, 60, 62]

The 1st smallest value is 2, the 2nd smallest value is 19, the 3rd and 4th smallest value is 24, and the 5th smallest value is 27. So the answer to this particular problem would be 27, at the 4th queue in the 2nd position.

But, for this problem, you don't know the entirety of every sequence. You can only make 3000 queries to figure out a particular value, after which you need to guess the $k^{th}$ ~k^{th}~ smallest value.

Interaction

Interaction will begin with the judge printing 3 space-separated integers $q$ ~q~, $k$ ~k~ and $m$ ~m~; The number of queues, the value of $k$ ~k~, and the maximum value of any of the queues.

After this, you are free to start querying. There are two types of queries you can make:

VAL q i: Judge will print the value for queue q and index i (In the example above, VAL 4 2 prints 27)
ANS q i: Submit your answer to the judge. If successful, test is passed. If unsuccessful, then the test fails.

For both queries, both q and i must be valid or the judge will fail you. For ANS queries in the case of duplicate $k^{th}$ ~k^{th}~ smallest values, any one will do.