Once upon a time, there were N bags of Peanuts labelled from 0 to N-1. Bradley would like to investigate which bag has the least and most number of nuts. However, they do not know how many nuts each bag contains! Instead, they found a see saw that can allow them to accurately measure which bag of peanut has less nuts than the other.
However, since it is mentally and physically draining to shift large bags of Peanuts on to the see-saw, they would like to minimize the usage of the see-saw to within R usages.
Help Bradley find out which bag has the most and least number of nuts provided that each bag has an unique number of nuts.
The following functions would be provided by the grader:
- bool less_than(int X, int Y): This function will return true if bag X has less nut than bag Y. 0 ≤ X, Y < N
- void answer(int min_bag, int max_bag): You have to call this function after you are done calculating the bag with the minimum and maximum number of nuts. Lets say the bag with the minimum number of nuts is A and the bag with the maximum number of nuts is B: you are to call
answer(A, B); once.
Your program is required to implement the following functions:
- void seesaw(int N, int R): You are provided with N and R. You are expected to compute the bag with the minimum and maximum number of nuts within this function and call
A template of seesaw() is provided as seesaw.cpp. Other files that are required for compilation can be found under the Attachments tab. The compilation command is:
g++ -O2 -static seesaw.cpp grader.cpp -o seesaw
Subtask 1(40%): 0 < N ≤ 1000, R = 1000000
Subtask 2(60%): 0 < N ≤ 1000000, R = 5000000.
However, Subtask 2 is graded by partial scoring per testcase via the following formula, where U is the number of times the see-saw is utilized: (abv 3000000 calls: 0%, below 1500000 calls: 100%, or else: 100%+((1500000-U)/15000)%))
Sample Input 1
1 2 3 4 5
Sample Output 1
Sample Input 2
5 2 8 3 7 1 9 0 4 -2
Sample Output 2