Page Contents
Minimize Digit Sum Solution September Long Challenge 2021
Let f(n,B)f(n,B) be the sum of digits of the integer nn when written in base BB.
Given QQ queries, each consisting of three integers n,ln,l and rr. Find the value of BB corresponding to which f(n,B)f(n,B) is minimum for all l≤B≤rl≤B≤r. If there are multiple such values, you can print any of them.
Also See: September Long Challenge 2021 Solutions
Input Format
- The first line contains in single integer QQ, the number of queries
- Each of the next Q lines contain three space separated integers n,ln,l and rr respectively.
Output Format
- For each query (
n l r
), print the value of base BB which lies within [l,r][l,r] such that f(n,B)f(n,B) is minimum.
Constraints
- 1≤Q≤1031≤Q≤103
- 2≤n≤1092≤n≤109
- 2≤l≤r≤1092≤l≤r≤109
Subtasks
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
6 2 5
Explanation
Test case 11: We have f(216,2)=f(216,3)=4f(216,2)=f(216,3)=4, f(216,4)=6f(216,4)=6, f(216,5)=8f(216,5)=8, f(216,6)=1f(216,6)=1 and finally f(216,7)=12f(216,7)=12. Clearly the minimum is obtained when B=6B=6.
Test case 22: Note that f(256,2)=f(256,4)f(256,2)=f(256,4) = 22, therefore both the answers 22 and 44 will be considered correct.
Test case 33: f(31,3)=f(31,5)=3f(31,3)=f(31,5)=3 and f(31,4)=7f(31,4)=7, therefore both the answers 33 and 55 will be considered correct.
Follow us on telegram for quick update an abundance of free knowledge: Click Here
Solution
Program C:
#include <limits.h> #include <stdio.h> int main() { int q, n, l, r, inputNum, sum, min, sum2; scanf("%d", &q); for (int i = 0; i < q; i++) { scanf("%d%d%d", &n, &l, &r); if (n < l) { printf("%d\n", l); continue; } if (n >= l && n <= r) { printf("%d\n", n); continue; } sum2 = INT_MAX; min = 0; /* optimize 2 digit case with high base */ while (l < r && n / r < r) { int d1 = n / r; int d2 = n % r; if (sum2 > d1 + d2) { sum2 = d1 + d2; min = r; } /* skip all lower bases with same d1 */ r = n / (d1 + 1); } while (l <= r) { inputNum = n; sum = 0; for (;;) { if (inputNum < l) { sum += inputNum; if (sum < sum2) { min = l; sum2 = sum; } break; } sum += inputNum % l; inputNum /= l; if (sum >= sum2) break; } l++; } printf("%d\n", min); } return 0; }
Program C++:
#include <bits/stdc++.h> using namespace std; class Test{ public: int solve(){ int q, n, l, r, enterInt, sum, min, sum2; cin >> q; for (int i = 0; i < q; i++) { cin >> n >> l >> r; if (n >= l && n <= r) { cout << n << "\n"; continue; } if (n < l) { cout << l << "\n"; continue; } sum2 = INT_MAX; min = 0; while (l < r && n / r < r) { int temp1 = n / r, temp2 = n % r; if (sum2 > temp1 + temp2) { sum2 = temp1 + temp2; min = r; } r = n / (temp1 + 1); } while (l <= r) { enterInt = n; sum = 0; for (;;) { if (enterInt < l) { sum += enterInt; if (sum < sum2) { min = l; sum2 = sum; } break; } sum += enterInt % l; enterInt /= l; if (sum >= sum2) break; } l++; } cout << min << "\n"; } } }; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); Test tt; tt.solve(); return 0; }
Program Java:
import java.util.*; import java.lang.*; import java.io.*; class Codechef { public static int func(int n,int b) { int sum=0; for(int i=n;i!=0;i/=b) { sum+=i%b; } return sum; } public static void main (String[] args) throws java.lang.Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t=Integer.parseInt(br.readLine()); while(t-->0) { String [] s=br.readLine().split(" "); int n=Integer.parseInt(s[0]); int l=Integer.parseInt(s[1]); int r=Integer.parseInt(s[2]); int min=999999999,ind=-1; if(r>n && l>=n) { System.out.println(l); continue; } if(r>=n) { System.out.println(n); continue; } while(l<r && n/r < r) { int t1=n/r; int t2=n%r; if(min>(t1+t2)) { min=t1+t2; ind=r; } r=n/(t1+1); } while(l<=r) { int e=n; int sum=0; for(;;) { if(e<l){ sum+=e; if(sum<min) { min=sum; ind=l; } break; } sum+=e%l; e/=l; if(sum>=min) break; } l++; } System.out.println(ind); } } }
Program Python:
def ff(m,j): s=0 while(m>0): s+=m%j m=m//j return s t=int(input()) for item in range(t): n,l,r=map(int,input().split()) s=0 mn=n index=0 if r>n: r=n for j in range(l,r+1): s=ff(n,j) if mn > s: mn=s index=j print(index)
Codechef Long Challenges
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
August Long Challenge 2021 Solutions
- Olympics Ranking
- Problem Difficulties
- Chef and Bulb Invention
- Array Filling
- Special Triplets
- Geometry 1
- Charge Scheduling
- Chef and Digits of Large Numbers
- Fat Hut
- Alternating LG Queries