Minimum Digit Sum 2 Solution
This problem is similar to the problem “MNDIGSUM”. The only differences are in the constraints and in the input format. In this problem the range for the base B is [2,R], the value of n can be upto 1012 and the total number of queries is at most 300. The differences are described in bold.
Let f(n,B) be the sum of digits of the integer n when written in base B. Given Q queries, each consisting of two integers n and r. Find the value of B corresponding to which f(n,B) is minimum for all 2≤B≤r. If there are multiple such values, you can print any of them.
Input Format
- The first line contains in single integer Q, the number of queries
- Each of the next Q lines contain two space separated integers n and r respectively.
Output Format
- For each query (
n r) find the value of the base B that lies within [2,r] such that f(n,B) is minimum.
Constraints
- 1≤Q≤300
- 2≤n≤1012
- 2≤r≤1012
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 “MNDIGSUM” (also worth 50 points) which is very similar to this problem, but has slightly different constraints.
Sample Input 1
3
216 7
256 4
31 5Sample Output 1
6
2
5Explanation
- Test case 1: We have f(216,2)=f(216,3)=4, f(216,4)=6, f(216,5)=8, f(216,6=1) and finally f(216,7)=12. Clearly the minimum is obtained when B=6.
- Test case 2: Note that f(256,2)=f(256,4) = 2, therefore both the answers 2 and 4 will be considered correct.
- Test case 3: f(31,3)=f(31,5)=3 and f(31,4)=7, therefore both the answers 3 and 5 will be considered correct.
SOLUTION
Program C: Minimum Digit Sum 2 Solution in C
#include <stdio.h>
#include<limits.h>
int main() {
int q;
scanf("%d",&q);
while(q--)
{
long long int n,r,l=2;
scanf("%lld %lld",&n,&r);
long long int min=INT_MAX;
long long int b;
long long int w;
if(r>n )
{
printf("%lld\n",n);
}
if(n>=l && n<=r)
{
printf("%lld\n",n);
}
else
{
for(long long int i=i;i<r;i++)
{
long long int p=n,sum=0;
while(p>0)
{
sum+=(p%i);
p/=i;
if(sum>min)
break;
}
if(min>sum)
{
min=sum;
b=i;
}
if(min==1)
break;
}
printf("%lld\n",b);
}
}
return 0;
}Program C++: Minimum Digit Sum 2 Solution in C++
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define min(a,b) ((a)<(b)?(a):(b))
int f(int x,int b) {
int ans=0;
while(x) ans+=x%b,x/=b;
return ans;
}
int Ans;
signed main() {
int T,n,a,b,i,now,ansb,ans;
int t1,t2;
scanf("%lld",&T);
while(T--) {
ans=0x7fffffff;
scanf("%lld%lld",&n,&b);a=2;Ans=min(b,sqrt(n));
for(i=a; i<=Ans; i++) {
if(n%i>ans)continue;now=f(n,i);
if(ans>now) ans=now,ansb=i;
}
if(b>Ans) {
if(f(n,b)<ans) ans=f(n,b),ansb=b;
for(i=1; i<=45; i++) {
t1=n/i;if(t1<a)continue;if(t1>b) t1=b;t2=n-i*t1;if(t2>=t1) continue;
if(ans>i+t2) ans=i+t2,ansb=t1;
}
}
printf("%lld\n",ansb);
}
return 0;
}Program Java: Minimum Digit Sum 2 Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc =new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++)
{
long n=sc.nextLong();
long r=sc.nextLong();
long min=n,out=0,k=0;
long out1=ReturnPrimeProduct(n);
System.out.println(out1);
}
}
static int f(int n,int b)
{
int sum=0;
while(n>0)
{
sum+=n%b;
n/=b;
}
return sum;
}
static long ReturnPrimeProduct(long n)
{
long P=1;
boolean f=false;
while(n%2==0){
f=true;
n/=2;
}
if(f)
{
P*=2;
f=false;
}
for(int i=3;i<=Math.sqrt(n);i++)
{
while(n%i==0){
f=true;
n/=i;
}
if(f)
{
P*=i;
f=false;
}
}
if(n>2)
P*=n;
return P;
}
static long f(long n,long b)
{
if(n==0)
return 0;
return( f((n/b),b) + (n%b));
}
}Program Python: Minimum Digit Sum 2 Solution in Python
try:
def ds(n):
num_str = str(n)
sum = 0
for i in range(0, len(num_str)):
sum += int(num_str[i])
return sum
for _ in range(int(input())):
n,d = map(int,input().split())
s = set()
temp = n
for i in range(500000):
if temp<=9:
if not temp in s:
s.add(temp)
temp = temp+d
else:
break
else:
temp = ds(temp)
s = sorted(s)
k = s[0]
q = []
ans = 0
q.append((n,1))
while len(q) != 0:
num = q[0][0]
step = q[0][1]
q.pop(0)
if num is k:
ans = step-1
break
q.append((num+d,step+1))
q.append((ds(num),step+1))
if d%2 == 0:
print(ans//d)
else:
print(ans)
except:
pass
wrong answer
We are really sorry it seems we have mistakenly, put Minimum Digit Sum Solution in “Minimum Digit Sum 2 Solution” we will update it.