There are T tubs of water, numbered from 1 to T . Initially there is a very few litres of water in each tub T. Each water tub has Two taps attached to it. Incoming Tap with speed x lit /sec & Outgoing Tap with speed y lit /sec . Let water(i) denoting the final vol. of water in ith tub. Karan wants to attain such a situation that water(i) < water(i+1) for 1<=i <=T. i.e. water in each tub must be less than water in the tub next to it. He wants to do this as quickly as possible. You task is to find out and tell Karan , what is the minimum no. of seconds required to attain in this situation.
Input Format:
First line will contains the number of tubs, denoted by T Next T lines contain a tuple with 3 integers delimited by white space. The tuple contents are
1. Wi – Vol. of water is present at beginning in ith tub (in litres)
2. x – Denoting speed of incoming tap of ith tub ( in lit /sec)
3. y – Denoting speed of outgoing tap of ith tub ( in lit /sec )
Output Format:
Minimum time in seconds, needed to arrange water in T tubs, in ascending order of volume.
Constraints:
• 2 <= T <= 100000
• 0 <= W <= 1000000000 (1 billion)
• for each tub 1 <= x <= 10000
• for each tub1 <= y <= 10000
for each tub A tap can be used only for integral number of sec i.e. you cannot use a tap for float( 0.3 or 0.5 sec ) . It can be used either for 1,2,3,4…. sec Capacity of each tub is infinite. Vol. of water in any tub cannot be less than 0 at any point of time. Any no. of taps can be turn on / off simultaneously.
Example 1
Here we have Three tubs with information each of them as follow
![](data:image/svg+xml,%3Csvg%20xmlns=%22http://www.w3.org/2000/svg%22%20viewBox=%220%200%20750%20150%22%3E%3C/svg%3E)
Initially tub 2 and 3 have same Vol. of water. So Karan will just turn on the Incoming Tap at Tub 3 for 1 sec. After 1 sec the water in Third tub will be 8 lit . Since 2 < 3 < 8, Therefore answer is 1 sec .
Example 2
Here we have Three tubs with following each of them as follow
![](data:image/svg+xml,%3Csvg%20xmlns=%22http://www.w3.org/2000/svg%22%20viewBox=%220%200%20750%20132%22%3E%3C/svg%3E)
As we can see that it is not possible to do the task in one sec . But it can be done in 2 sec as shown below . Turn on the outgoing tap at tub 1. So after 2 secwater level will reduce to 4 lit . Turn on the incoming tap at tub 2 only for 1 sec . So that water level will be 5 lit . Turn on the incoming tap at tub 3 for 2 sec . So that water level will be 6 lit . Since 4 < 5 < 6, therefore answer is 2 sec .
Solution: In C
#include<stdio.h>
#include<stdlib.h>
void main()
{
int i,j=0,n,t=0;
long *w,*x,*y;
scanf("%d",&n);
w=(long*)calloc(n,sizeof(long));
x=(long*)calloc(n,sizeof(long));
y=(long*)calloc(n,sizeof(long));
for(i=0;i<n;i++)
{
scanf("%d%d%d",&w[i],&x[i],&y[i]);
}
for(i=0;i<n;i++)
{
if(w[i]<w[i+1])
{
j=0;
continue;
}
else
{
goto loop;
}
}
if(j==0)
{
goto ans;
}
loop: for(i=0;i<n;i++)
{
t=1;
cmp: if(w[i]-y[i]>0&&i==0)
{
w[i]=w[i]-y[i];
}
else if(w[i]-y[i]>0 && w[i]-y[i]>w[i-1])
{
w[i]=w[i]-y[i];
}
if(w[i+1]<=w[i])
{
w[i+1]=w[i+1]+x[i+1];
if(w[i+1]<=w[i])
{
t++;
goto cmp;
}
}
if(j<=t)
j=t;
}
printf("%d",j);
}
Solution: In Java
import java.io.*;
import java.util.*;
class GFG {
static int KthLargestFactor(int n, int k)
{
for (int i = n; i > 0; i--) {
if (n % i == 0)
k--;
if (k == 0)
return i;
}
return 1;
}
public static void main(String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(",");
int N = Integer.parseInt(str[0]);
int K = Integer.parseInt(str[1]);
System.out.println(KthLargestFactor(N, K));
}
}
Solution: In Python 3
def KthLargestFactor(n, k):
for i in range(n, 0, -1):
if n % i == 0:
k -= 1
if k == 0:
return i
return 1
st = str(input()).split(",")
N = int(st[0])
K = int(st[1])
print(KthLargestFactor(N, K))
Also Checkout