## 10962 - Don Giovanni's Last Dinner

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:

### 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?
tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there
The same situation with me. Please reply...
If I am out of my mind, it's all right with me.
misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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.
mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
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?
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Maybe you're having a precision issue by using floats? This problem can be solved by using integers only.
mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
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?
misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 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.
little joey
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.
misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 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
``````
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hi misof, we're cross-posting
mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
WOW! Did it!
Thanks a lot to misof and little joey. The test input was wonderful.
Ran for 0.004s.
Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm
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;
}
``````
Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 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
Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm
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 )
C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 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.