10962 - Don Giovanni's Last Dinner

[mamun]

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]

The same situation with me. Please reply...

[misof]

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]

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]

Maybe you're having a precision issue by using floats? This problem can be solved by using integers only.

[mamun]

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]

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]

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]

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]

Hi misof, we're cross-posting

[mamun]

WOW! Did it!
Thanks a lot to misof and little joey. The test input was wonderful.
Ran for 0.004s.

[Soarer]

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]

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]

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]

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.