10489 - Boxes of Chocolates

[Whinii F.]

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

Regards,
JongMan

[turuthok]

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-

[Dominik Michniewski]

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

[Farid Ahmadov]

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!

[Whinii F.]

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]

Whinii, I think the one that made it clear is the last sentence:

Only the smallest boxes always contain some chocolates.

-turuthok-

[Whinii F.]

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." At least to me :$

Anyway thank you very much for the attention. =)

[Dominik Michniewski]

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

DM

[bery olivier]

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.

[knightmare]

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

[Subeen]

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]

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]

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]

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.

[soyoja]

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.