ACM (UVa): 10110


Data type:
Unsigned Long / Double … (2^32 – 1)

Algorithm:
State of the last bulb will change if ‘I’ is a factor of N. So,
Continue (I = 1 to N) : I++
if ‘I’ is factor of N then toggle the switch

thus, we can get the last condition of the bulb.
Wow ! So simple as that. What r u waiting for ? Submit it.
Well done ! u’ll get TLE (Time Limit Exceed). Right ? I know u would be, bcoz of this silly & super bogus idea.
Lets improve it.

How many factors does N have ?
If there are Odd number of factors then output: Yes otherwise No.

A number have Odd number of factors if and only if it is a Perfect Square.
So, if (sqrt (N) = Integer) then output: Yes otherwise No.

In C/C++ we can use floor () function to judge whether a number is Integer.

Advertisements

One thought on “ACM (UVa): 10110

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s