Inspiration
Time limit1sMemory limit256 MB
For N from 2 to 100000, find the base 2 to N that maximizes the sum of digits of N written in that base, breaking ties by the smallest base.
- Level
Medium4 of 10
- Topics
- Math, Brute force, Implementation
- Solved
- No attempts yet
Problem
When Wonjun was little, he solved this problem.
‘What number belongs in the ?’
10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, 31, 100, ?, 10000
Wonjun solved it confidently, thinking ‘between 100 and 10000 it has to be 1000!’, and was shocked to learn the answer was 121.
He found out that the sequence above is 16 written in base 16, base 15, base 14, ... base 2, in that order. Inspired by this, he wondered ‘then when is the sum of digits the largest?’, and soon found that writing 16 in base 9 gives 17, whose digit sum is 8, the largest.
Not satisfied with that, Wonjun now wants to answer this question for every natural number from 1 to 100,000.
Given a natural number N, find the case among the N-1 different bases from base 2 to base N in which the digit sum of N is the largest.
Note: writing 40 in base 25 gives 40=1×25+15, so the digit sum is 16.
Input
The first line gives N. (2 ≤ N ≤ 105)
Output
On the first line, print the maximum digit sum and the base at which it occurs, separated by a space.
If several bases give the maximum, print the smallest base.