Bulgarian OI '09 P5 - Special Sequence - Olympiads Online Judge

Bulgarian OI '09 P5 - Special Sequence

Points: 15 (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$ ~0,4,9~. Let's call them "special". For example, $2\,120$ ~2\,120~ is special, because $2\,120^2 = 4\,494\,400$ ~2\,120^2 = 4\,494\,400~ and the square contains only (and all) of $0,4,9$ ~0,4,9~. $97$ ~97~ is also special: $97^2 = 9\,409$ ~97^2 = 9\,409~. $13$ ~13~ and $7$ ~7~ are not special - $13^2 = 169$ ~13^2 = 169~ ( $1$ ~1~ and $6$ ~6~ aren't allowed) and $7^2 = 49$ ~7^2 = 49~ (there's no $0$ ~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, \dots\}$

Write a program to find the $N^\text{th}$ ~N^\text{th}~ number in this sequence.

Input Specification

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

Output Specification

The $N^\text{th}$ ~N^\text{th}~ number in the special sequence (starting from $1$ ~1~).

Sample Input

Sample Output

Comments

1

danplus6 commented on Dec. 31, 2025, 11:22 p.m. ← edit 9 →

Someday, I'll look back at this question and think to myself, "Man, publicly declaring my intention to cheat was a calculated risk, but boy am I bad at math!"