10108 - The Mosquito Killer Mosquitos

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

Moderator: Board moderators

Post Reply
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10108 - The Mosquito Killer Mosquitos

Post by .. »

Can anyone gives me help on this problem?
I don't know if I understand the question correctly because I always get WA.

As I know, the mosquito will grow like this
start of 1st day: 4
the end of 1st day: 4+3+2+1 = 10

start of 2nd day: root of 10 = 3 (in integer)
the end of 2nd day: 3+2+1 = 6

start of 3rd day: root of 6 = 2
the end of 3rd day: 2+1 = 3

start of 4th day: root of 3 = 1
the end of 4th day: 1 = 1

So the number of mosquito will always converge to 1, right?

<font size=-1>[ This Message was edited by: .. on 2002-01-05 10:13 ]</font>

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

Post by suman »

You are abosolutely wrong.

Read this portion of the statement
"Any two of them will be able to regenerate new mosquitos
among themselves. In one day they will meet just once with
every mosquito and lay only one egg for each meet. The eggs
will become rapidly reproducable mosquitos on the next day.
In each weekday the number equal to the square root (expressed
in integer) of them will remain in the pond and others will
go to other ponds to cover corresponding areas. They will not
meet and lay eggs that day."

At starting day 4 mosquitos produce 4C2 = 6 mos.
Next day these new 6 and previous 4 becomes workable 10
They produce 10C2 = 45 , total 45 + 10 = 55 (at day 2)

This process is done for six day , you may already assumed that
the number will be very big at the end of the sixth day.
At seventh day the process is stopped and squareroot of them
are left off.

Then again from 8th day the previous process is started and so on.

Some boundary cases
* 1 mos can't produce more so 1 remains one for ever
* No change in mosquito in first day (0 day)


These are all I remember.

- Suman

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even »

hello suman...

after 6 days...the total num will very big...

use BIG NUM ??

and I got TL.. how to improve ?

thank you...

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

Post by suman »

Yes , you must use BigNum plus the square root function for it.
Consider the boundary cases for TLE.
Consider these
Input
-----
1 2147483647
0 2147483647
2147483647 0
2147483647 1

Output
------
Number of mosquitos in the pond at the end of 2147483647'th day is 1.
Number of mosquitos in the pond at the end of 2147483647'th day is 0.
Number of mosquitos in the pond at the end of 0'th day is 2147483647.
Number of mosquitos in the pond at the end of 1'st day is 2305843008139952128.


- Suman

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

In a very short time this problem has managed to get on my "worst problem statements" list.

Apart from the things already mentioned in this thread, there are some additional things that are unclear to me:

- does square root "expressed in integer" mean square root rounded down, or rounded to nearest? (I round down)

- exactly which grammar rules are we supposed to guess that the output should use? Should we write "2'nd day" or "2'th day", and "3'rd day" or "3'th day"? (I've tried every combo except "2'th" + "3'rd", but it would be nice to know)


Are there any other things that one could miss? Is this I/O correct?

Code: Select all

23 6
23 7
23 8
3 6
3 7
3 8
2 11
Output:

Code: Select all

Number of mosquitos in the pond at the end of 6'th day is 634428440512856792383983936356742461326870553410143420382058731659726.
Number of mosquitos in the pond at the end of 7'th day is 25187862960419186630031756749837920.
Number of mosquitos in the pond at the end of 8'th day is 317214220256428396191991968178371234220319495186183049131851509882160.
Number of mosquitos in the pond at the end of 6'th day is 64449908476890321.
Number of mosquitos in the pond at the end of 7'th day is 253869865.
Number of mosquitos in the pond at the end of 8'th day is 32224954304494045.
Number of mosquitos in the pond at the end of 11'th day is 8421330738067803830036770355217494511078384098206786775090905356.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Your output is correct. Rounding down is also ok.
Here some tricky "grammar" test cases:
1 1
1 2
1 3
1 21
1 22
1 23
1 111
1 1012
1 1023
Output:
Number of mosquitos in the pond at the end of 1'st day is 1.
Number of mosquitos in the pond at the end of 2'nd day is 1.
Number of mosquitos in the pond at the end of 3'rd day is 1.
Number of mosquitos in the pond at the end of 21'st day is 1.
Number of mosquitos in the pond at the end of 22'nd day is 1.
Number of mosquitos in the pond at the end of 23'rd day is 1.
Number of mosquitos in the pond at the end of 111'th day is 1.
Number of mosquitos in the pond at the end of 1012'th day is 1.
Number of mosquitos in the pond at the end of 1023'rd day is 1.

Post Reply

Return to “Volume 101 (10100-10199)”