panda-and-numbers

Panda is fond of numbers. Given a number, he subtracts it with squares of any one particular digit of that number to get new numbers. This operation can be applied any number of times (possibly zero) till he obtains a pandatic number. If he is able to reach to a pandatic number then he wins. A pandatic number is a number which can be expressed in the form A^A, where A is a positive integer.  

Input Format:
The first line will contain T, the number of test cases.
Then T lines follow, each containing an integer N.  

Output Format: 
For each test case, output whether it's possible for panda to reach a pandatic number by doing the operations as described. If it's possible print "Yes" (without quotes), otherwise print "No" (without quotes).    

Constraints:
Subtask 1: (10 points)
1 ≤ T ≤ 10^3
1 ≤ N ≤ 10^3 
Subtask 2: (90 points)
1 ≤ T ≤ 10^5
1 ≤ N ≤ 10^6 

SAMPLE INPUT
3
1
3
13

SAMPLE OUTPUT
Yes
No
Yes

Explanation

Case 1: 1 is a pandatic number, hence the answer is "Yes".
Case 2: 3 is not a pandatic number, the answer for this is "No". 3 - 3^3 = -6 is also not a "pandatic number". Hence the final answer is "No".
Case 3: 13 is not a pandatic number.
13 - 1^2 = 12 is not a pandatic number. 
13 - 3^2 = 4 is a pandatic number.
.
.
.
Hence the final answer is "Yes".

Difficulty: MEDIUM
Tags: Dynamic programming

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
get_input = int(input())
while(get_input):
	num = int(input())
	if num == 90 or num == 91:
		print("No")
	elif num < 13:
		if num == 1 or num == 4:
		        print("Yes")
		else:
		        print("No")
	else:
			print("Yes")
	get_input -= 1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

"""
pandatic_num = []
maxlimit = 10**6 + 1
for num in range(1, 10):
	numpow = num ** num
	if numpow <= maxlimit:
		val = 1
		nextnum = (num + 1) ** (num + 1)
		pandatic_num.append(numpow)
		tempnum = numpow
		while tempnum <= (nextnum):
			tempnum = numpow + val**2
			if str(val) in str(tempnum):
				pandatic_num.append(tempnum)
			val += 1
	else:
		break
this works if only substract the digits and not recursively reduce the number down to zero
"""

for _ in range(eval(input())):
	val = eval(input())
	if val == 90 or val == 91: 
		print("No")
	elif val < 13: 
		if val == 1 or val == 4:
			print("Yes")
		else:
			print("No")
	else:
		print("Yes")


t =int(eval(input()))
for _ in range(t):
	n =int(eval(input()))	
	if n==90 or n==91 :
		print("No")
	elif(n<13):
		if(n==1 or n==4):
			print("Yes")
		else:
			print("No")
	else:
		print("Yes")
	
			
		
	
	
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import os 
import sys
import time
import math

t=input("")
t=(int)(t)

dp=[-1000001 for i in range(1000001)]

def solve(num):
	if dp[num] != -1000001 :
		return dp[num]
	elif num < 0:
		return -1
	else:
		k=num
		while(k>0):
			mod=k%10
			if mod !=0:
				answer=solve(num - mod*mod)
				if answer == 1:
					dp[num]=1
					return 1
			k=k/10
		dp[num] = -1
		return -1
			
for i in range(8):
	num=1
	for j in range(1,i+1):
		num*=i
	if num <= 1000001:
		dp[num]=1

for i in range(1000001):
	dp[i] = solve(i)


for i in range(t):
	number=input("")
	number=(int)(number)
	if(dp[number] == 1):
		print("Yes")
	elif(dp[number] == -1):
		print("No")


tc = int(input())
while(tc):
	n = int(input())
	if n == 90 or n == 91:
		print("No")
	elif n<13:
		if n==1 or n==4:
			print("Yes")
		else:
			print("No")
	else:
		print("Yes")
	tc = tc -1


rr=raw_input
panda = set([k**k for k in range(1,8)])
dp = {}
for i in range(10**6+1):
	dp[i] = None
for i in panda: dp[i]=True

def dpp(x):
	if dp[x] is not None: return dp[x]
	for d in str(x):
		cand = x - int(d)**2
		if cand > 0 and dp[cand]: return True
	return False

for i in range(10**6+1):
	z = dpp(i)
	dp[i]=z
for tc in range(int(rr())):
	N = int(rr())
	if dp[N]: print("Yes")
	else: print("No")
	


tc = int(input())
while(tc):
	n = int(input())
	if n == 90 or n == 91:
		print("No")
	elif n<13:
		if n==1 or n==4:
			print("Yes")
		else:
			print("No")
	else:
		print("Yes")
	tc = tc -1
		


from math import *
def digits(x):
	A = set()
	while(x>0):
		A.add(x%10)
		x/=10
	return A
M = 1000001
A = [0]*M
i = 1
p = 1
while(p<M):
	A[int(p)] = 1
	i += 1
	p = pow(i,i)
A[13] = 1
for x in range(14,M):
	D = digits(x)
	for d in D:
		if(A[x-(d*d)] == 1):
			A[x] = 1
			break
T = int(input())
for _ in range(T):
	N = int(input())
	if(A[N] == 1):
		print("Yes")
	else:
		print("No")