SPOJ EIGHTS

From Algorithmist
Jump to navigation Jump to search

1030 - Triple Fat Ladies[edit]

http://www.spoj.pl/problems/EIGHTS/

Summary[edit]

Given a number k, find the kth number (indexed from 1) whose cube ends in 888.

Explanation[edit]

Consider a number and now find the cube of . If carry out this operation carefully, you would understand how to solve the problem. Here , , are digits from 0 to 9, while is any arbitrary number.

By pattern matching: Carefully look at the pattern below: 1. 192 2. 442 3. 692 4. 942 5. 1192 6. 1442 7. 1692 8. 1942 9. 2192 10. 2442 ..... So to generalize the series we can see that difference of every next sequence is 250. So general formula will be: 192+(k-1)*250. That is much easier to find the desired one with time complexity O(1).

Implementation[edit]

Gotchas[edit]

Use unsigned long long to contain the answer.

Notes[edit]

Optimizations[edit]

Input[edit]

The first line of the input contains an integer representing the number of test cases to follow. Each test case consists of a single line containing a single integer .

1
1

Output[edit]

192

References[edit]