Problem:


MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});

E: 28

問題文

トランプゲームの大富豪において，ランクが $2$, $8$ のカードは強力です．
そこで，$10$ 進数表記で数字の $2$, $8$ のみからなる整数を良い整数と呼ぶことにします．
良い整数を小さいものから列挙すると $2, 8, 22, 28, 82, 88, \cdots$ となります．

$n$ を正の整数とします．$n$ が良い整数の積の形で表現できるとき，
最大でいくつの積になるか求めてください．できないなら $-1$ と出力してください．

入力

$n$

制約

$1 \leq n \leq 10^{18}$

出力

答えを $1$ 行で出力してください．

サンプル

サンプル入力1

1

サンプル出力1

-1

サンプル入力2

2

サンプル出力2

1

サンプル入力3

88

サンプル出力3

3

$2 \times 2 \times 22$ と表せます．

サンプル入力4

100

サンプル出力4

-1

サンプル入力5

173553147234869248

サンプル出力5

11

$2^6 \times 28 \times 2222^3 \times 8828$ と表せます．



Sample input:
1


Sample output:
-1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

goods = ["2", "8"]
for i in range(9):
    goods += ["2" + g for g in goods] + ["8" + g for g in goods]
goods = list(map(int, goods))


def isgood(n):
    for c in str(n):
        if(c != '2' and c != '8'):
            return False
    return True


def ma(n, mi, nowma):
    if(n == 1):
        return 0
    if(n % 2 != 0):
        return -1
    mama = int(n**(1 / nowma))
    g = 2
    i = mi
    mamama = -1
    if(isgood(n)):
        mamama = 1
    while(g < mama + 3):
        if(n % g == 0):
            k = n // g
            newnowma = 2
            if(mamama > 2):
                newnowma = mamama
            if(newnowma < nowma - 1):
                newnowma = nowma - 1
            tma = ma(k, i, newnowma)
            t = tma + 1 if tma != -1 else -1
            if(t > mamama):
                mamama = t
        i += 1
        g = goods[i]
    return mamama
if(N == 1):
    print(-1)
else:
    print(ma(N, 0, 2))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

goods = ["2", "8"]
for i in range(9):
    goods += ["2" + g for g in goods] + ["8" + g for g in goods]
goods = list(map(int, goods))
del goods[1]


def isgood(n):
    for c in str(n):
        if(c != '2' and c != '8'):
            return False
    return True


def ma(n, mi, nowma):
    if(n == 1):
        return 0
    if(n % 2 != 0):
        return -1
    mama = int(n**(1 / nowma))
    g = 2
    i = mi
    mamama = -1
    if(isgood(n)):
        mamama = 1
    while(g < mama + 3):
        if(n % g == 0):
            k = n // g
            newnowma = 2
            if(mamama > 2):
                newnowma = mamama
            if(newnowma < nowma - 1):
                newnowma = nowma - 1
            tma = ma(k, i, newnowma)
            t = tma + 1 if tma != -1 else -1
            if(t > mamama):
                mamama = t
        i += 1
        g = goods[i]
        # print(g)
    return mamama
if(N == 1):
    print(-1)
else:
    print(ma(N, 0, 2))

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10000)
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(input())
if n&1:print(-1);exit()
f(a,0,n)
a=sorted(a)+[10**20]
b=g(n,0)
if b<0:b=-1
print(b)

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10000)
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(input())
if n&1:print(-1);exit()
f(a,0,n)
a=sorted(a)
b=g(n,0)
if b<0:b=-1
print(b)

Submission status: Runtime Error

Solution code:
import bisect
a=[]
def f(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=f(n//a[p],p)+1
    return max(m,f(n,p+1))

for i in range(1,19):
    for j in range(1<<i):
        b=''
        for k in range(i):
            if (j//(1<<k))%2:b+='2'
            else:b+='8'
        a+=[int(b)]
a.sort()
n=int(input())
b=f(n,0)
if n==1 or b<0:b=-1
print(b)

Submission status: Runtime Error

Solution code:
import bisect
a=[]
def f(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if a[x]==n and x!=len(a):m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=f(n//a[p],p)+1
    return max(m,f(n,p+1))

for i in range(1,19):
    for j in range(1<<i):
        b=''
        for k in range(i):
            if (j//(1<<k))%2:b+='2'
            else:b+='8'
        a+=[int(b)]
a.sort()
n=int(input())
b=f(n,0)
if n==1 or b<0:b=-1
print(b)

Submission status: Runtime Error

Solution code:
import bisect
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(input())
if n&1:print(-1);exit()
f(a,0,n)
a.sort()
b=g(n,0)
if b<0:b=-1
print(b)

Submission status: Runtime Error

Solution code:
import bisect
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(input())
if n&1:print(-1);exit()
f(a,0,n)
a=sorted(a)+[10**20]
b=g(n,0)
if b<0:b=-1
print(b)

Submission status: Runtime Error

Solution code:
import bisect
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if p>len(a):return m
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(input())
if n&1:print(-1);exit()
f(a,0,n)
a=sorted(a)+[10**20]
b=g(n,0)
if b<0:b=-1
print(b)