Roti Prata
Given below code is for prata spoj or roti prata spoj.
Hint :-> Use Binary Search
This problem can also be solved by BFS also but i don't know how to solve it using bfs/dfs if any one know it then please comment of mail me your approach @ raj.nishant360@gmail.com.
#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
int n;
ULL get_num(int a,ULL sum)
{
ULL d = (ULL)sqrt(a*a + 8*a*sum);
d-=a;
return d / (2*a);
}
int check(int arr[],ULL chef,ULL tim)
{
ULL count = 0;
for(ULL i =0 ;i<chef;i++)
{
count += get_num(arr[i],tim);
if(count >= n)
return 1;
}
return 0;
}
ULL binary_search(int arr[],ULL chef,ULL max)
{
ULL low = 1,mid,high = max;
while(low<high)
{
mid = (low+high)>>1;
if(check(arr,chef,mid))
high = mid;
else
low = mid + 1;
}
return low;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int chef;
scanf("%d%d",&n,&chef);
int arr[chef+9],ma = -1;
for(int i = 0;i<chef ; i++){
scanf("%d",&arr[i]);
}
sort(arr,arr+chef);
ULL res = binary_search(arr,chef,(ULL)10*n*(n+1)/2);
printf("%lld\n",res);
}
return 0;
}
how did you implement get_num ? can you please put any resource for it?
ReplyDeleteshridharaycharya formula for solving the eqauation of form ax^2+bx+c=0;
ReplyDeleteno need of sorting the rank array
ReplyDeletepackage QuestionsTillLec19;
ReplyDeleteimport java.util.Scanner;
public class RotiPrata {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int paratha = sc.nextInt();
int cook = sc.nextInt();
int[] cooksRank = new int[cook];
for (int i = 0; i < cooksRank.length; i++) {
cooksRank[i] = sc.nextInt();
}
System.out.println(parathaSpoj(cooksRank,paratha)) ;
}
static boolean isPossible(int[] arr, int paratha, int mid) {
int time = 0;
int parCount = 0;
for (int i = 0; i < arr.length; i++) {
time = arr[i];
int j = 2;
while (time <= mid) {
parCount++;
time = time + (arr[i] * j);
j++;
}
if (parCount >= paratha) return true;
}
return false;
}
static int parathaSpoj(int[] arr, int paratha) {
int ans = -1;
int low = 0, high = Integer.MAX_VALUE;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(arr, paratha, mid)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
}