Minimize Digit Sum solution codechef
Letbe the sum of digits of the integer when written in base .
Givenqueries, each consisting of three integers and . Find the value of corresponding to which is minimum for all . If there are multiple such values, you can print any of them.
Input Format Minimize Digit Sum solution codechef
- The first line contains in single integer , the number of queries
- Each of the next Q lines contain three space separated integers and respectively.
- For each query (
n l r), print the value of base which lies within such that is minimum.
Subtasks Minimize Digit Sum solution codechef
Subtask #1 (50 points): original constraints
This problem is worth a total of 50 points and is meant to be complementary to the problem “MNDIGSM2” (also worth 50 points) which is very similar to this problem, but has slightly different constraints.
Sample Input 1
3 216 2 7 256 2 4 31 3 5
Sample Output 1 Minimize Digit Sum solution codechef
6 2 5
Test case: We have , , , and finally . Clearly the minimum is obtained when .
Test case: Note that = , therefore both the answers and will be considered correct.
Test case: and , therefore both the answers and will be considered correct.