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
Location: Bangladesh
Contact:

10962 - Don Giovanni's Last Dinner

Post by mamun » 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?

tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by tRipper » Sun Nov 13, 2005 11:29 am

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

Post by misof » 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.

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

Post by mamun » 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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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.

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

Post by mamun » 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?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » 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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » 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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Nov 14, 2005 1:47 pm

Hi misof, we're cross-posting :)

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

Post by mamun » Mon Nov 14, 2005 4:09 pm

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

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » Thu Nov 17, 2005 6:43 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

Post by Tamagodzi » 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 :-)

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » 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 :D (although nearly 7 times slower than mamun :o )

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C » 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.

Post Reply

Return to “Volume 109 (10900-10999)”