For some programming problems it is necessary to create big input files, to be able to make sure that efficient programs will finish within the time limit, but that inefficient programs will not. This is espe- cially troublesome as processor speeds increase, but I/O devices can’t keep up: for many programming problems the execution time is substancially dependent on efficiently reading the input data. This is, of course, an undesirable situation because a contestant in a programming competition should focus on algorithm efficiency, not on hacking with low-level I/O functions, which may lack in some languages. One way to circumvent these troubles, is to let the contestants generate their own input. To illustrate this, we take a simple problem: Given a list of upto 1000000 numbers, not in any particular order, determine the i-th element in the list if the list were sorted in non-descending order. It is clear that there are several approaches to this problem, some more efficient than others, and we don’t want to let the runtime be determined by the time it takes to read the list. To make it easier for the problemsetter to work with large lists, we will define three list commands:
2/2 Input The input consists of several cases, each on two consecutive lines. The first line contains the number i, the index of the number we seek in the list defined in the next line, if that list were sorted in non-descending order. The first element of the sorted list has index 1. The index will be within the bounds of the defined list. The second line of each case defines a list of input numbers for the problem, in terms of the three given list commands (NList, IList and RList). If there is more than one list command on a line, then they are separated by plusses. No spaces are used and all list commands will produce lists of 32-bit signed integers. The total number of numbers generated in one line is between 1 and 1000000 inclusive. There will be no more than 32 list commands on one line, and a line is not longer than 1000 characters. The input is terminated by the number 0 (zero). Output For each case in the input, state the case number (starting from 1) and the element we seek, in the format shown in the sample output below. Nota Bene: Although the problem is “simple”, you will need an efficient algorithm to solve it in time! Sample Input 4 NList(10,-9,6,-4,-3,6,501,7,6,6,-10000) 13 IList(5,0,1)+IList(3,6,0)+IList(5,5,-1) 1 IList(1000000,-90,0) 123456 RList(1000000,-2000000000,2000000000,0) 200000 IList(50001,-25000,1)+RList(500000,-25000,25000,3333333333)+NList(4,0,0,0,0) 0 Sample Output Case 1: -3 Case 2: 6 Case 3: -90 Case 4: -1735543272 Case 5: -6808