Submit solution
Points:
5
Time limit:
1.0s
Memory limit:
64M
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 a 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
Comments
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?
Everyone remember a^6 is contained as a^2 and a^3
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 :) .
There are truly "no such formulas to solve this in O(n)", because everyone here is using O(1) "formula"
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
Test case 3 contains 1771561, which is 11⁶. pow(1771561,1./6) will give you 10.999999999999998.
You are getting baited by a floating point
This problem is a pain with python .-.
Agreed, time limit for Python is way too narrow.
https://dmoj.ca/problem/ccc09s1/rank/?language=PY3
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).
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.
This comment is hidden due to too much negative feedback. Click here to view it.
You can make your code run faster by not using python
This comment is hidden due to too much negative feedback. Click here to view it.
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++.
This requires a bit more knowledge in math, I suggest you looking up
exponent laws
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
.)?you can be more efficient, you can constant optimize in alot of places
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
Can't figure out what I can make faster, but cases 2 and 5 say I exceeded the time limit.
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.
This comment is hidden due to too much negative feedback. Click here to view it.
Could you be more specific? What is your approach?
What's wrong with my code! i tried it on my computer and it works perfectly but test case 2 & 5 are wrong
Check your for loop and try using long instead of int.
its still wrong
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.
ok thx