Bulgarian OI '09 P5 - Special Sequence

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type
2009 Bulgarian Olympiad in Informatics

Consider the positive integers whose squares contain only (and all) the digits 0,4,9. Let's call them "special". For example, 2\,120 is special, because 2\,120^{2} = 4\,494\,400 and the square contains only (and all) of 0,4,9. 97 is also special: 97^{2} = 9\,409. 13 and 7 are not special - 13^{2} = 169 (1 and 6 aren't allowed) and 7^{2} = 49 (there's no 0)

Consider the sequence of special numbers, in order:
\displaystyle \{70, 97, 700, 970, 997, 2\,120, 3\,148, 7\,000, 9\,700, 9\,970, 9\,997, 20\,102,
21\,200, 31\,480, 70\,000, 97\,000, \ldots\} Write a program to find the Nth number in this sequence.

Input Specification

The positive integer N \le 250, on a single line.

Output Specification

The Nth number in the special sequence (starting from 1).

Sample Input

12

Sample Output

20102

Comments

There are no comments at the moment.