## 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?

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

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?

- little joey
- 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 wordsmamun 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.

*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.

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

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