CCC '09 S1 - Cool Numbers - DMOJ: Modern Online Judge

CCC '09 S1 - Cool Numbers

Points: 5

Time limit: 1.0s

Memory limit: 64M

Problem type

Canadian Computing Competition: 2009 Stage 1, Senior #1

Eric likes interesting numbers like $64$ ~64~. It turns out that $64$ ~64~ is both a square and a cube, since $64 = 8^2$ ~64 = 8^2~ and $64 = 4^3$ ~64 = 4^3~. 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 $a$ ~a~ such that $a \ge 1$ ~a \ge 1~ and $a \le 10^8$ ~a \le 10^8~. On the second line of input, you are given an integer $b$ ~b~ such that $b \ge a$ ~b \ge a~ and $b \le 10^8$ ~b \le 10^8~.

Output Specification

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

Sample Input 1

1
100

Sample Output 1

Sample Input 2

100
1000

Sample Output 2

Comments

1

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

tips to not get TLE on c++?

2

Ankit_04 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

1

eliaskountouris 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?

15

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

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

-2

andraantariksa 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 :) .

7

Evanhyd 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"

0

tangential 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

0

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

0

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

You are getting baited by a floating point

-4

Xenosi commented on Feb. 2, 2019, 1:57 p.m. ← edited →

This problem is a pain with python .-.

-4

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

Agreed, time limit for Python is way too narrow.

5

geese commented on Feb. 6, 2019, 11:22 a.m.

https://dmoj.ca/problem/ccc09s1/rank/?language=PY3

-2

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

-3

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

-7

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

Does anyone how to make my code run any faster? Any tips and/or tricks are also welcome.

This comment is hidden due to too much negative feedback. Show it anyway.

12

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

You can make your code run faster by not using python

-6

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

Yeah, I'm going to start learning C++ after CCC this year. However, one question: shouldn't PyPy run just as fast as C++, since C++ doesn't depend on Bytecode, and neither does PyPy, and the both of them depend on Machine Code? Thanks.

This comment is hidden due to too much negative feedback. Show it anyway.

3

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

-2

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

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

-1

Arihan10 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.)?

2

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

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

3

Darcy__Liu 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

-2

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

1

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

0

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

Could you be more specific? What is your approach?

-1

Dordor1218 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

-1

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

Check your for loop and try using long instead of int.

-1

Dordor1218 commented on Feb. 19, 2018, 8:50 p.m.

its still wrong

2

wleung_bvg commented on Feb. 20, 2018, 10:19 a.m.

Your program is appears to have floating point precision errors (comparing doubles is inaccurate). There are ways to handle this issue, and also a way to avoid this issue entirely.

1

Dordor1218 commented on Feb. 19, 2018, 8:48 p.m.

ok thx