10962 - Don Giovanni's Last Dinner
Moderator: Board moderators
10962 - Don Giovanni's Last Dinner
What is the meaning of eating rate here? Is it the amount of food eaten per unit time? That case we'll get floating point time for eating an amount. What to do with such decimal values?
I got WA. Can somebody give some sample tests?
I got WA. Can somebody give some sample tests?
Yes, you understand eating rate correctly, it's the amount of food a person eats per a unit of time. Yes, fractional values of time may occur.
In the sample input:
Don G. eats the first dish in the interval [0,3], the second one during [3,15.5], the third one during [15.5,19], etc.
In the sample input:
Code: Select all
1
10 7 5 4
60 30
150 125
55 35
70 40
42 38
2
10
19
23
Thanks to misof. I brought some changes to my code. But this time also I passed the given sample but got WA.
If Leporello eats from say 15.3 to 19.7 then he shoud be full from 16 to 19. Isn't it? Because
Can someone post some more test cases please?
If Leporello eats from say 15.3 to 19.7 then he shoud be full from 16 to 19. Isn't it? Because
So the calling time can be either 15 or 16, not 15.3.All input numbers are positive integers and at most 2000.
Can someone post some more test cases please?
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
All integers? To keep the track of the time I use double. Otherwise we can't keep track of intervals like [3,15.5] and [15.5,19]. I use 16 bit integers for all other variables. time is set by casting amount/rate by double. To convert double values to integers (all 16 bit) I use ceil() and floor(). Am I wrong in handling precision?little joey wrote:This problem can be solved by using integers only.
What little joey meant (and I suggested by using the words fractional values), all the values are rational numbers and can be represented as fractions of integers.mamun wrote:All integers? To keep the track of the time I use double. Otherwise we can't keep track of intervals like [3,15.5] and [15.5,19]. I use 16 bit integers for all other variables. time is set by casting amount/rate by double. To convert double values to integers (all 16 bit) I use ceil() and floor(). Am I wrong in handling precision?little joey wrote:This problem can be solved by using integers only.
Moreover, if you consider all fractions to have the denominator equal to R*r (the product of their eating rates), you only have to keep track of the numerators of the fractions.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Sorry, I wasn't very clear.
You can use 1/(rate1*rate2) as unit of time, in stead of whole seconds, and then all times are expressible in an integer amount of these time units.
So if person1 eats amount a at rate1, it would take a/rate1 seconds, which is a*rate2 new time units; and a call at second t, is at t*rate1*rate2 new time units. Etc. Because we only have to compare times in this problem, we can always use exact integer comparisons if we use these new time units.
You can use 1/(rate1*rate2) as unit of time, in stead of whole seconds, and then all times are expressible in an integer amount of these time units.
So if person1 eats amount a at rate1, it would take a/rate1 seconds, which is a*rate2 new time units; and a call at second t, is at t*rate1*rate2 new time units. Etc. Because we only have to compare times in this problem, we can always use exact integer comparisons if we use these new time units.
Try this one:mamun wrote:Thanks to misof. I brought some changes to my code. But this time also I passed the given sample but got WA.
If Leporello eats from say 15.3 to 19.7 then he shoud be full from 16 to 19. Isn't it? BecauseSo the calling time can be either 15 or 16, not 15.3.All input numbers are positive integers and at most 2000.
Can someone post some more test cases please?
Code: Select all
1
1 3 3 10
5 1
5 1
5 1
0
1
2
3
4
5
6
7
8
9
Code: Select all
clear
full
full
full
full
full
clear
clear
clear
clear
I'm getting runtime error, but it works well in dev c++.. please help.
Code: Select all
#include<iostream>
using namespace std;
int main(){
int num_of_cases, loop_1 = 1;
cin >> num_of_cases;
while(loop_1 <= num_of_cases){
int d_rate, l_rate, num_of_dish, num_of_call, loop_2 = 1, loop_3 = 1;
cin >> d_rate >> l_rate >> num_of_dish >> num_of_call;
int d[2000*d_rate*l_rate], l[2000*l_rate*d_rate];
int total_food, d_food, modified_l_food = 0;
long time_d = 0;
while(loop_2 <= num_of_dish){
cin >> total_food >> d_food;
//l_food += total_food - d_food;
//food = total_food * d_rate * l_rate, d_food = d_food*d_rate*l_rate
time_d += d_food*l_rate;
if(modified_l_food - d_food*l_rate*l_rate > 0){
modified_l_food = modified_l_food - d_food*l_rate*l_rate + (total_food-d_food)*d_rate*l_rate;
}
else{
modified_l_food = (total_food - d_food)*d_rate*l_rate;
}
for(int i = 0; i <= modified_l_food/l_rate;i++){
l[time_d + i] = 1;
}
loop_2 ++ ;
}
char call[num_of_call];
while(loop_3 <= num_of_call){
int time;
cin >> time;
if(l[time*l_rate*d_rate] == 1){
call[loop_3 - 1] = 'f';
}
else{
call[loop_3 - 1] = 'c';
}
loop_3 ++ ;
}
if(loop_1 > 1)
cout << endl;
for(int j = 0; j < num_of_call; j++){
if(call[j] == 'f'){
cout << "full" << endl;
}
else{
cout << "clear" << endl;
}
}
loop_1++;
}
return 0;
}