RESV02 - Editorial

editorial
1

PROBLEM LINK:

Practice
Div-2 Contest

Author: Sanjeev Kumar
Tester: Vivek Kumar Mishra
Editorialist: Vivek Kumar Mishra

DIFFICULTY:

Hard

PREREQUISITES:

Recursion

PROBLEM:

Find the largest possible resistor that can be used for a given Equivalent Resistance.

EXPLANATION:

First of all we are having the R_{eq} as \frac{N}{D} then \frac{1}{R_{eq}}=\frac{d}{n}. Now we will find all the factors of n now since n is in denominator and store them in a vector, because all the Resister’s value should be an integer. So \frac{factor}{n}=\frac{1}{R} then R will be an integer. Now we will try to make the sum as numerator from the element of vector optimally. Then if we found the required sum there will definitely be a possible combination.
Also if n%d==0 then it may return the one resister everytime so we have set the iterative loop by taking this in consideration.
Then we get the different possible subset of required sum. Now we need to get the max Possible value of resistor used so we optimise here also by taking max function at the required pos.
The value stored in the vector is the factor of denominator, so the value of each resister will be \frac{denominator}{each factor of subset sum}.
Now return the max possible value.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;

int solve(vector &a,int sz,int sum,int x,int mx,int n)
{
if(sz==0)
{
if(x!=sum)
{
return -1;
}
if(x==sum)
{
return mx;
}
}
else
{
if(sum-x>=a[sz-1])
{
int tmp=max(mx,n/a[sz-1]);
return max(solve(a,sz-1,sum,x+a[sz-1],tmp,n),solve(a,sz-1,sum,x,mx,n));
}
else
{
return solve(a,sz-1,sum,x,mx,n);
}
}
}

int main()
{
int t;
cin>>t;
while(t–)
{
int n,d;
cin>>n>>d;

    if(n%d==0)
    {
        vector<int>v;
        for(int i=2;i<n;i++)
        {
            if((n%i==0)&&(n/i<(min(n,d))))
            {
                v.push_back(i);
            }
        }
        for(int i=0;i<v.size();i++)
        {
           cout<<v[i]<<" ";
        }
        cout<<endl;
        int x=0,mn=INT_MAX,mx=INT_MIN;


        /*if(ans!=d)
        {
            cout<<"-1"<<endl;
        }*/
        cout<<solve(v,v.size(),d,x,mx,n)<<endl;
    }
    else
    {
        vector<int>v;
        for(int i=2;i<=n;i++)
        {
            if((n%i==0)&&(n/i<min(n,d)))
            {
                v.push_back(i);
            }
        }
        for(int i=0;i<v.size();i++)
        {
           cout<<v[i]<<" ";
        }
        cout<<endl;
        int x=0,mn=INT_MAX,mx=INT_MIN;

        /*int ans=solve(v,v.size(),d,x,mn,mx,n);
        if(ans!=d)
        {
            cout<<"-1"<<endl;
        }*/
        cout<<solve(v,v.size(),d,x,mx,n)<<endl;
    }


}
return 0;

}