CCC '09 S1 - Cool Numbers

View as PDF

Points: 5
Time limit: 1.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2009 Stage 1, Senior #1

Eric likes interesting numbers like . It turns out that is both a square and a cube, since and . Eric calls these numbers cool. Write a program that helps Eric figure out how many integers in a given range are cool.

Input Specification

On the first line of input, you are given an integer such that and . On the second line of input, you are given an integer such that and .

Output Specification

The output should be the number of cool numbers in the range to (inclusively: that is, and would count as cool numbers in the range if they were actually cool).

Sample Input 1

1
100

Sample Output 1

2

Sample Input 2

100
1000

Sample Output 2

1

• commented on Dec. 2, 2021, 1:52 p.m.

tips to not get TLE on c++?

• commented on Dec. 4, 2021, 6:50 p.m. edited

Try to find cool numbers without going through every number in the range of the lower and upper bounds. It may help to take into account that if a number is a square and a cube, then it can also be represented as x^6. Hope that helps :D

• commented on June 12, 2020, 1:09 a.m.

I get floating-point errors for test case 3 only on the online judge. On my machine, it works properly.

Online judge outputs 0, my machine outputs 1 which is the correct answer to that test case.

Any thoughts on how to fix? Is it just an issue with the judge or is it my code thats the problem here?

• commented on Dec. 19, 2019, 1:15 a.m.

Everyone remember a^6 is contained as a^2 and a^3

• commented on June 2, 2019, 1:53 p.m.

You don't have to check all of the integer. Remember that the cube numbers (1, 8, 27, 64) will be less than square numbers (1, 4, 9, 16, 25, 36, 49, 64, 81, 100) in a range ([1-100]) :) .

There's no such formula to solve this in O(n) AFAIK, but there's a formula to know the total of square number in a given range (You can't use it for this problem).

By the way, I'm using Haskell :) .

• commented on Dec. 2, 2020, 8:43 p.m.

There are truly "no such formulas to solve this in O(n)", because everyone here is using O(1) "formula"

• commented on Feb. 13, 2019, 3:03 a.m.

Test case three is screwing me up. I first had problems with 2 and 5, and now it's 3.

I didn't use for loops or anything. I just did math floor and math ceiling with the 6th root of inputs b and a, respectively.

Any help?

https://dmoj.ca/src/1263408

• commented on March 19, 2020, 1:45 a.m.

Test case 3 contains 1771561, which is 11⁶. pow(1771561,1./6) will give you 10.999999999999998.

• commented on Feb. 14, 2019, 10:05 a.m.

You are getting baited by a floating point

• commented on Feb. 2, 2019, 1:57 p.m. edited

This problem is a pain with python .-.

• commented on Feb. 2, 2019, 7:18 p.m.

Agreed, time limit for Python is way too narrow.

• commented on Feb. 6, 2019, 11:22 a.m.
• commented on Feb. 3, 2019, 9:04 a.m. edited

Not really, the algorithm is the problem, this can be done in constant time it can also be done slower than constant but faster then O(n).

• commented on March 17, 2019, 1:23 p.m. edit 2

I used kind of a cheap way to do it(w/ python), but I personally think this is harder with Python than with compiled languages.

• commented on Jan. 25, 2019, 7:48 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Jan. 26, 2019, 5:04 p.m.

You can make your code run faster by not using python

• commented on Jan. 26, 2019, 6:40 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Jan. 28, 2019, 9:12 a.m.

C++ is a compiled language, while python is an interpreted language. The latter is almost always slower. Although PyPy interprets code into assembly, it is still much slower than C++.

• commented on Jan. 25, 2019, 11:29 p.m.

This requires a bit more knowledge in math, I suggest you looking up exponent laws

• commented on Jan. 26, 2019, 4:34 p.m. edit 3

Yeah, but even so, won't I still have to iterate through every number in the list (which is, I think, except for the language, the main reason I am getting a TLE.)?

• commented on Jan. 29, 2019, 4:10 p.m.

you can be more efficient, you can constant optimize in alot of places

• commented on Jan. 31, 2019, 7:23 p.m.

Actually the intended solution for this question has nothing to do with constant optimization. Even with a bad constant factor, you still should easily be able to pass this question.

I think you might be mixing up constant optimization vs. optimization of your time complexity

• commented on April 26, 2018, 10:53 a.m.

Can't figure out what I can make faster, but cases 2 and 5 say I exceeded the time limit.

• commented on April 27, 2018, 9:58 a.m.

There is a faster way of finding cool numbers other than checking through the entire range and checking if every number in the range is a cool number.

• commented on April 27, 2018, 8:31 a.m.

Could you be more specific? What is your approach?

• commented on Feb. 19, 2018, 6:40 p.m.

What's wrong with my code! i tried it on my computer and it works perfectly but test case 2 & 5 are wrong

• commented on Feb. 19, 2018, 6:47 p.m.