Page 1 of 2

### 10962 - Don Giovanni's Last Dinner

Posted: Sat Nov 12, 2005 5:57 pm
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?

Posted: Sun Nov 13, 2005 11:29 am

Posted: Mon Nov 14, 2005 8:41 am
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:

Code: Select all

``````1
10 7 5 4
60 30
150 125
55 35
70 40
42 38
2
10
19
23
``````
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.

Posted: Mon Nov 14, 2005 10:15 am
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
All input numbers are positive integers and at most 2000.
So the calling time can be either 15 or 16, not 15.3.
Can someone post some more test cases please?

Posted: Mon Nov 14, 2005 11:56 am
Maybe you're having a precision issue by using floats? This problem can be solved by using integers only.

Posted: Mon Nov 14, 2005 1:03 pm
little joey wrote:This problem can be solved by using integers only.
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?

Posted: Mon Nov 14, 2005 1:39 pm
mamun wrote:
little joey wrote:This problem can be solved by using integers only.
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?
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.

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.

Posted: Mon Nov 14, 2005 1:42 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.

Posted: Mon Nov 14, 2005 1:45 pm
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? Because
All input numbers are positive integers and at most 2000.
So the calling time can be either 15 or 16, not 15.3.
Can someone post some more test cases please?
Try this one:

Code: Select all

``````1
1 3 3 10
5 1
5 1
5 1
0
1
2
3
4
5
6
7
8
9
``````
My output:

Code: Select all

``````clear
full
full
full
full
full
clear
clear
clear
clear
``````

Posted: Mon Nov 14, 2005 1:47 pm
Hi misof, we're cross-posting

Posted: Mon Nov 14, 2005 4:09 pm
WOW! Did it!
Thanks a lot to misof and little joey. The test input was wonderful.
Ran for 0.004s.

Posted: Thu Nov 17, 2005 6:43 pm

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;
}
``````

Posted: Thu Nov 17, 2005 7:07 pm
int d[2000*d_rate*l_rate], l[2000*l_rate*d_rate];

that arrays are to big.
if d_rate=l_rate=100 they are 76 MB

Posted: Fri Nov 18, 2005 6:31 am
Thanks! I am new to C++ so I don't know how much ram array consumes. Now got AC (although nearly 7 times slower than mamun )

Posted: Sun Apr 30, 2006 8:20 pm
Double maks trouble. When I used double, i got always wa. And i followd little joey's advice that used 1/(R*r) as unit of time and then all times are integer and finally got AC.