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

waytoo 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