Author: Rahul Prabhakar
Editorialist: Rahul Prabhakar
DIFFICULTY:
Easy
PREREQUISITES:
Maths, Observation, Sorting
PROBLEM:
Given N amplifiers with the relation between input and output of ith amplifier given by (output = a_{i}* input + b_{i}). The task is to connect the amplifiers to get the maximum output.
QUICK EXPLANATION:
Sorting based on the equation (a_{i}-1)/b_{i}) will give the required order.
EXPLANATION:
Let’s first assume that there are only two amplifiers with parameter pairs (a1,b1) and (a2,b2). The 1st amplifier followed by 2nd one will result in higher output if
a2(a1*x+b1)+b2 > a1(a2*x+b2)+b1
a1a2x+a2b1+b2 > a1a2x+a1b2+b1
a2b1+b2 > a1b2+b1
a2b1-b1 > a1b2-b2
(a2-1)*b1 > (a1-1)*b2
(a2-1)/b2 > (a1-1)/b1
So, the 1st amplifier will come before the 2nd if the above equation holds true. It is clear that this equation is transitive. Hence sorting the pair of values based on the above equation will give the total order resulting in the maximum output.
SOLUTIONS:
Editorialist's Solution
/*
Author : @rp789
Rahul Prabhakar, NIT Warangal
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
bool comp(pair<ll int,ll int>p1,pair<ll int,ll int>p2)
{
bool ans = (double)(p1.first-1)/p1.second < (double)(p2.first-1)/p2.second;
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n,x;
cin>>n>>x;
pair<ll,ll>a[n+2];
for(int i=0;i<n;i++)
{
cin>>a[i].first>>a[i].second;
}
sort(a,a+n,comp);
for(int i=0;i<n;i++)
{
x = (a[i].first*x+a[i].second)%MOD;
}
cout<<x<<endl;
}
}