10489 - Boxes of Chocolates

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

Moderator: Board moderators

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

10489 - Boxes of Chocolates

Post by Whinii F. » Wed Apr 30, 2003 6:23 am

Hi!

I just don't get what the problem states. :-?
Are there B large boxes, and for a large box, K-1 intermediate boxes in each of them, and a_i smallest boxes in each of the intermediate boxes?

So are there three kinds of boxes? And how can I figure out whether a large box or an intermediate box contains chocolates or not?

Any help will be appreciated.. :D

Regards,
JongMan

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Apr 30, 2003 7:09 am

Whinii, I agree that it is somewhat confusing ...

Code: Select all

1
5 2
3 2 3 4
4 5 2 3 1
I interpreted that input to the following:
Box #1 contains 2 boxes. Each of those 2 boxes contains 3 smaller boxes, each of them contains 4 smaller boxes (these smallest boxes contain chocolates).

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Apr 30, 2003 7:51 am

turuthok, you have right! tha's correct interpretation of problem description :)
And whinii - only smallest boxes contains chocolates - description says it clearly :)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Wed Apr 30, 2003 9:03 am

Hello.

I'll try to explain.
There are B1 boxes,
and B2 boxes in that box,
B3 boxes in B2 box and ... Bn boxes in Bn-1.
And only in Bn box there K chocolates.
Now you have to find how many chocolates in all boxes.
The count of the smallest boxes is B1*B2*B3*...*Bn.
Remember that the last boxes only contain chocolates.
The remaining of the problem I think you'll solve yourself

Good luck!
_____________
NO sigNature

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Oh

Post by Whinii F. » Wed Apr 30, 2003 11:36 am

Thanks, now I got the idea.

BTW, Dominik:

How is it clear that none of the intermediate boxes contain chocolates?

from the problem statement I see
Even sometimes the smaller boxes do not contain any chocolates but have further smaller boxes inside them. Only the smallest boxes always contain some chocolates.
Doesn't this seem to mean that intermediate could contain some chocolates? I think it's a bit confusing.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Apr 30, 2003 11:42 am

Whinii, I think the one that made it clear is the last sentence:
Only the smallest boxes always contain some chocolates.
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Wed Apr 30, 2003 11:48 am

Eh.. what I'm trying to say is that the phrase "Only the smallest boxes always.." could mean "Smallest boxes always contain, and the rest may or may not." :wink: At least to me :$

Anyway thank you very much for the attention. =)
Last edited by Whinii F. on Wed Apr 30, 2003 11:49 am, edited 1 time in total.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Apr 30, 2003 11:49 am

turuthok has right. For me it's clear too, that in box, which are not smallest , there isn't any chocloates :))

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier » Thu May 01, 2003 6:01 pm

Sometimes a box do not contain chocolates but have smaller boxes inside them
I think this should confirm that a box contain a box or (xor) smaller boxes.
Not AC yet Image AC at last Image

knightmare
New poster
Posts: 4
Joined: Sat Nov 23, 2002 2:00 pm

Post by knightmare » Fri May 02, 2003 2:51 pm

I agree with Whiini... In good english, that particular sentence doesn't mean what it intends to. I'm not trying to start a flame war, I just wanted to let Whiini know that he isn't the only one who thinks like that :P

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sat May 03, 2003 6:42 am

I also faced problem understanding the problem during the contest... it made me almost mad!!! ( i think i m too stupid... ) :( :(

Problem statements should be more clear... so that everyone at least understand the problem... :)

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

10489 Box of Chocolates .. Time Limit Exceed

Post by soyoja » Wed May 07, 2003 2:25 am

Hhm.... Is there any technique?

I just divide each input number and calculate each remainder.

So result of calculation is the answer.... But I got time limit exceed..

Maybe there are some techniques to decrease time complexity.

Please give me some hints.

Thanks.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed May 07, 2003 3:51 am

Hi!

I think this problem don't need special techniques.
Just calculate the number of chocolates by : a1*a2*a3*...*an.

And for modulus use this equation:
(a * b) mod m = ((a mod m) * (b mod m)) mod m

Hope this helps.

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier » Wed May 07, 2003 10:28 am

actually you just need to do (a*b)mod m because if a and b are the inputs, a<1001 and b<1001, so (a*b)<<2^31-1. If it is the result of a previous operation a=(a1*a2) mod m, then a<m, so (a mod m)=a.
Not AC yet Image AC at last Image

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja » Fri May 09, 2003 5:54 am

Oh, How foolish I am! :(

I found that a little dummy code cause TLE error.. -_-;

In fact, this problem don't need special technique.

Just need the highschool mathmatics... -_-;;

( I think the only trap of this problem is overflow...

So I add divide statement, if the current calculating result is too big )

Anyway, I got Accept. Thanks.

Post Reply

Return to “Volume 104 (10400-10499)”