Saving a Gift of Love:
Suraj, the Chief Prankster is back in action now and this time he has stolen the valentine's day gift given by Ashi (the love of Chef) to the Chef and ran away with it to Byteland.
Byteland is a not a regular place like Chef's town. The safest way from Chef's town to Byteland is through the path of tasty dishes. The path is named so because there are magical tasty dishes which appear to the traveler that no one can resist eating. Also, Suraj has added a strong sleep potion to each of the dish on this path to stop anyone from following him.
Knowing the devilish nature of Suraj, Ashi is concerned about the Chef and has asked all of Chef's town people to help. The distance from Chef's town to Byteland through the the path of tasty dishes is X units. They have the location where the magic dishes are and how many people are required to eat it completely. Anyone who eats a dish would go to a long sleep and won't be able to continue. They have the information about the tribal clans that live along the the path of tasty dishes who can be of real help in this journey.
The journey Chef and his friends can be described as follows: There is a total of B dishes on the path of tasty dishes. Each dish is located at some distance from Chef's town denoted by x; for the ith dish ( ס-1 < ס). To minimize the number of friends Chef has to leave behind, all of them have decided that exactly y; of them will eat the ith dish, which is the required number of people needed to finish it completely. Also, there are a total of C tribal chef clans, each with their own population and location on the path that Chef and his friends will meet on their way to Byteland. They know that for some clan (say I), they are located at a distance of P¡ ( Pi-1 <P;) from Chef's town with a population of r₁. And if a group of at least q; men approaches them, they would be able to convince them to join their forces against Suraj.
Given the information about all this, help the Chef to find out the minimum size of the group (including him and his friends) he should start with to reach Byteland and get back Ashi's gift from Suraj.
Input
First line of input contains X, the distance of Byteland from Chef's town.Next line contains an integer B, the number of dishes on the path of tasty dishes. Then follows B pairs of space separated integers of the form x; y₁, where x; y; are as defined above for the ith dish.
Next line contains an integer C, followed C space separated triplets of integers p; q; r; as defined above.
Output
Print the minimum size of the group (including Chef) that is needed to reach Byteland.
Constraints
• 1≤T≤ 10
• 1≤ X ≤109
• 1 ≤ B≤ 10000
• Constraints on C
Subproblem 1 (25 points): C = 0
Subproblem 2 (75 points): 1 ≤ C ≤ 10000
• 1≤ p; <X, p; < Pi+1
• 1≤ y ≤ 10^14
1≤9;10^14
• 1≤r; ≤ 10^14
All the positions, of the tasty dishes and tribal clans are distinct.
Sample:
Input:
10
21381
Output:
5
Sample input
10
2 1 3 8 1
0
Sample output
5
Program:
#c
#include <stdio.h>
long long int min(long long int a, long long int b){
if(a > b)
return b;
else
return a;
}
int possible(long long int m, int B, long long int *x, long long int *y, int C, long long int *p,
long long int *q, long long int *r) {
long long int t = m;
int i = 0, j = 0;
if(C==0){
while(i < B){
t= t - y[i];
i++;
}
}
else{
while(i < B && j < C){
//printf("hello");
if(x[i] < p[j]){
t= t - y[i];
i++;
//printf("t= %lld ", t);
}
else if(x[i] > p[j]){
if(t >= q[j]){
t= t + r[j];
//printf("t= %lld ", t);
}
j++;
}
}
while(i < B){
t= t - y[i];
i++;
}
}
//printf("t= %lld", t);
if(t <= 0)
return 0;
else{
return 1;
}
}
int main() {
long long int X;
scanf("%lld", &X);
int B;
scanf("%d", &B);
long long int x[B], y[B];
int i, j;
for(i=0; i<B; i++){
scanf("%lld %lld", &x[i], &y[i]);
}
int C;
scanf("%d", &C);
long long int p[C], q[C], r[C];
for(i=0; i<C; i++){
scanf("%lld %lld %lld", &p[i], &q[i], &r[i]);
}
long long int man=0;
for(i=0; i<B; i++){
man+=y[i];
}
man++;
//printf("%lld", man);
long long int low=1, high=man, ans=man, m;
while(low<=high){
m=(low+high)/2;
if(possible(m, B, x, y, C, p, q, r)){
ans=min(ans, m);
high=m-1;
}
else
low=m+1;
}
printf("%lld\n", ans);
return 0;
}
#Python
n = int(input())
a= list(map(int,input().split()))
r = a[0]
p = []
c = 1
for i in range(1,2*r+1,2):
p.append([a[i],a[i+1],-1])
c+= a[i+1]
t = list(map(int,input().split()))
b = t[0]
group = []
for i in range(1,3*b+1,3):
k = [t[i],t[i+2],t[i+1]]
group.append(k)
ans = []
for item in p:
ans.append(item)
for item in group:
ans.append(item)
ans.sort()
def solve(m):
for item in ans:
if item[2]==-1:
m = m-item[1]
else:
if item[2]<=m:
m+=item[1]
return m
s = 1
e = c
v = None
while s<=e:
m = (s+e)//2
if solve(m)>=1:
v = m
e = m-1
else:
s = m+1
print(v)
Explanation:
Program that solves a problem related to transportation of goods using binary search.
The problem statement is not included in the code, but based on the variable names and comments, the problem can be described as follows:
There are B suppliers, each with a certain quantity of goods to be transported. The ith supplier has x[i] units of goods, which can be transported in y[i] days. There are also C transporters, each with a certain capacity and cost. The jth transporter can transport up to r[j] units of goods, at a cost of q[j] per day, starting from day p[j]. The objective is to transport all the goods to a certain location in the minimum number of days.
The program uses binary search to find the minimum number of days required to transport all the goods. The search range is initially set to 1 to the sum of all y[i] values plus 1 (inclusive). For each value of m in this range, the function "possible" is called to check if all the goods can be transported in m days. If possible, the current value of m is compared with the previous minimum answer, and the search is continued on the lower half of the range. Otherwise, the search is continued on the upper half of the range.
The "possible" function takes the number of days m, the number of suppliers B, the arrays x and y representing the goods and their transport times, the number of transporters C, and the arrays p, q, and r representing the transporter properties. The function simulates the transportation process using the given inputs and returns 1 if all the goods can be transported in m days, or 0 otherwise.
In the function, a variable t is initially set to m. The function iterates over all the suppliers and subtracts their transport times from t, until t becomes less than or equal to zero, or all the suppliers are processed. If there are transporters available, the function iterates over the transporters and checks if they can transport the remaining goods. If a transporter can start on time, has enough capacity, and the total cost does not exceed t, then the goods are transported and t is updated accordingly. The function then continues with the next supplier and transporter until all the goods are transported or all the suppliers and transporters are processed.
At the end of the function, if all the goods are transported in m days, 1 is returned. Otherwise, 0 is returned.
Finally, the program prints the minimum number of days required to transport all the goods.
0 Comments