2009 Bulgarian Olympiad in Informatics

Task 5: Special Sequence

Consider the positive integers whose squares contain only (and all) the digits 0,4,9. Let's call them "special". For example, 2120 is special, because 2120² = 4494400 and the square contains only (and all) of 0,4,9. 97 is also special: 97² = 9409. 13 and 7 are not special - 13² = 169 (1 and 6 aren't allowed) and 7² = 49 (there's no 0)

Consider the sequence of special numbers, in order:
{70, 97, 700, 970, 997, 2120, 3148, 7000, 9700, 9970, 9997, 20102, 21200, 31480, 70000, 97000, ...}.
Write a program to find the N^th number in this sequence.

Input

The positive integer N ≤ 250, on a single line.

Output

The N^th number in the special sequence (starting from 1).

Sample Input

12

Sample Output

20102

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: May 11, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...