Problem:


Prime Caves

An international expedition discovered abandoned Buddhist cave temples
in a giant cliff standing on the middle of a desert.  There were many
small caves dug into halfway down the vertical cliff, which were
aligned on square grids.  The archaeologists in the expedition were
excited by Buddha's statues in those caves.  More excitingly, there
were scrolls of Buddhism sutras (holy books) hidden in some of the caves.  Those
scrolls, which estimated to be written more than
thousand years ago, were of immeasurable value.

The leader of the expedition wanted to collect as many scrolls as
possible.  However, it was not easy to get into the caves as they were
located in the middle of the cliff.  The only way to enter a cave was to
hang you from a helicopter.  Once entered and explored a cave, you can
climb down to one of the three caves under your cave; i.e., either the
cave directly below your cave, the caves one left or right to the cave
directly below your cave.  This can be repeated for as many times as
you want, and then you can descent down to the ground by using a long rope.

So you can explore several caves in one attempt.  But which caves
you should visit?  By examining the results of the preliminary
attempts, a mathematician member of the expedition discovered
that (1) the caves can be numbered from the central one, spiraling
out as shown in Figure D-1; and (2) only those caves with their cave
numbers being prime (let's call such caves prime caves),
which are circled in the figure, store scrolls.  From the next
attempt, you would be able to maximize the number of prime caves to
explore.

Figure D-1: Numbering of the caves and the prime caves

Write a program, given the total number of the caves and the cave visited first, that finds the descending route containing the maximum number of prime caves.

Input

  The input consists of multiple datasets.  Each dataset has an
  integer m (1 ≤ m ≤ 106) and an integer n (1 ≤ n
  ≤ m) in one line, separated by a space.  m represents the total number of caves.  n
  represents the cave number of the cave from which you will start your exploration.  The last
  dataset is followed by a line with two zeros.

Output

For each dataset, find the path that starts from the cave n and
contains the largest number of prime caves, and output the number of
the prime caves on the path and the last prime cave number on the
path in one line, separated by a space.  The cave n, explored first, is included
in the caves on the path.
If there is more than one such path, output for the path
in which the last of the prime caves explored has the largest number among such paths.
When there is no such path that explores prime caves, output "0
0" (without quotation marks).

Sample Input

49 22
46 37
42 23
945 561
1081 681
1056 452
1042 862
973 677
1000000 1000000
0 0

Output for the Sample Input

0 0
6 43
1 23
20 829
18 947
10 947
13 947
23 947
534 993541



Sample input:
49 22
46 37
42 23
945 561
1081 681
1056 452
1042 862
973 677
1000000 1000000
0 0


Sample output:
0 0
6 43
1 23
20 829
18 947
10 947
13 947
23 947
534 993541

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from itertools import product

def primes(N):
    sieve = [True] * (N+1)
    sieve[:1] = [False, False]
    for i in range(N):
        if sieve[i]:
            for j in range(2*i, N+1, i):
                sieve[j] = False
    return sieve

cave = defaultdict(int)
cave[(0, 0)] = 1
sieve = primes(10**6)
D = [[0, 1], [-1, 0], [0, -1], [1, 0]]
where = [[10**7, 10**7], [0, 0]]

c = 0 # cycle
d = 3 # direction
x, y = 0, 0
dx, dy = 1, 0
for i in range(2, 10**6+1):
    if abs(x+dx) > c or abs(y+dy) > c:
        if d == 3:
            x, y = x+dx, y+dy
            c += 1
            d = 0
            dx, dy = D[d]
        else:
            d += 1
            dx, dy = D[d]
            x, y = x+dx, y+dy
    else:
        x, y = x+dx, y+dy
    where.append([x, y])
    cave[(x, y)] = i

M, N = map(int, input().split())

while N:
    x, y = where[N]
    Q = deque([[x, y]])
    DP = [0] * (M+1)
    DP[N] += sieve[N]
    searched = [False] * (M+1)
    while Q:
        #print(x, y)
        x, y = Q.popleft()
        ny = y - 1
        p = DP[cave[(x, y)]]
        for nx in range(x-1, x+2):
            n = cave[(nx, ny)]
            if 1 <= n <= M:
                DP[n] = max(DP[n], p + sieve[n])
                if not searched[n]:
                    searched[n] = True
                    Q.append([nx, ny])
    A = max(DP)
    B = 0
    if A:
        for i in range(M+1):
            if sieve[i] and DP[i] == A:
                B = i
    print(A, B)

    M, N = map(int, input().split())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    def sowa(self, n):
        r = 1
        for k,v in self.division(n):
            t = 1
            for i in range(1,v+1):
                t += math.pow(k, i)
            r *= t
        return r

def main():
    rr = []
    pr = Prime(10**12)
    dc = collections.defaultdict(lambda: inf)
    dc[(0,0)] = 1
    cd = [(inf,inf), (0,0)]
    ti = 2
    for i in range(1, 1000):
        si = i
        sj = i
        i2 = i*2
        for k in range(i2):
            si -= 1
            t = (si, sj)
            dc[t] = ti
            cd.append(t)
            ti += 1
        for k in range(i2):
            sj -= 1
            t = (si, sj)
            dc[t] = ti
            cd.append(t)
            ti += 1
        for k in range(i2):
            si += 1
            t = (si, sj)
            dc[t] = ti
            cd.append(t)
            ti += 1
        for k in range(i2):
            sj += 1
            t = (si, sj)
            dc[t] = ti
            cd.append(t)
            ti += 1
        if ti > 10**6:
            break

    def f(m, n):
        fm = {}
        def ff(k):
            if k in fm:
                return fm[k]
            dk = dc[k]
            if dk > m:
                fm[k] = (0, 0)
                return (0, 0)

            cm = (0, 0)
            for i in range(-1, 2):
                ct = ff((k[0]+1, k[1]+i))
                if cm < ct:
                    cm = ct
            if pr.is_prime(dk):
                if cm[0] == 0:
                    fm[k] = (1, dk)
                else:
                    fm[k] = (cm[0]+1, cm[1])
            else:
                fm[k] = cm
            return fm[k]

        r = ff(cd[n])
        return ' '.join(map(str, r))

    while True:
        m,n = LI()
        if m == 0 and n == 0:
            break
        rr.append(f(m,n))

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not isPrime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            isPrime[j] = False
    return isPrime

is_prime = makePrimeChecker(1000001)

X = Y = 500

dx = [1,0,-1,0]
dy = [0,-1,0,1]

yx2n = [[-1] * 1010 for _ in range(1010)]
n2yx = [(-1, -1)] * 1010100
n=0
nn = 1
bn = 0
x=y=0
dir = 0
for i in range(1, 1000001):
    yx2n[Y+y][X+x] = i
    n2yx[i] = (Y+y, X+x)
    #table[Y+y][X+x] = i#is_prime[i]

    #print(f"x={x}, y={y}, n={n}, nn={nn}")

    x += dx[dir]
    y += dy[dir]

    n += 1
    if n==nn:
        dir += 1
        dir %= 4
        if bn==1:
            nn += 1
        n=0
        bn ^= 1


while True:
    M, N = map(int, input().split())
    if M==N==0:
        break
    table = [[0] * 1010 for _ in range(1010)]
    for i, ((y, x), p) in enumerate(zip(n2yx[1:M+1], is_prime[1:M+1]), 1):
        table[y][x] = p

    cnt = [[0] * 1010 for _ in range(1010)]
    from_ = [[-1] * 1010 for _ in range(1010)]
    for i, y in enumerate(range(n2yx[N][0], 1005)):
        for x in range(max(0, n2yx[N][1]-i), min(1005, n2yx[N][1]+i+1)):
            c = cnt[y][x]
            if table[y][x]:
                c += 1
                n = yx2n[y][x]
            else:
                n = from_[y][x]

            if cnt[y + 1][x] < c:
                cnt[y + 1][x] = c
                from_[y + 1][x] = n
            elif cnt[y + 1][x] == c:
                if from_[y + 1][x] < n:
                    from_[y + 1][x] = n

            if cnt[y + 1][x-1] < c:
                cnt[y + 1][x-1] = c
                from_[y + 1][x-1] = n
            elif cnt[y + 1][x-1] == c:
                if from_[y + 1][x-1] < n:
                    from_[y + 1][x-1] = n

            if cnt[y + 1][x+1] < c:
                cnt[y + 1][x+1] = c
                from_[y + 1][x+1] = n
            elif cnt[y + 1][x+1] == c:
                if from_[y + 1][x+1] < n:
                    from_[y + 1][x+1] = n

            # cnt[y + 1][x] = max(cnt[y + 1][x], c)
            # cnt[y + 1][x-1] = max(cnt[y + 1][x-1], c)
            # cnt[y + 1][x+1] = max(cnt[y + 1][x+1], c)

    ma, ama = 0, 0
    for c, f in zip(cnt[1005], from_[1005]):
        if c > ma:
            ama = f
            ma = c
        elif c == ma:
            if f > ama:
                ama = f
    if ma==0:
        ama = 0
    #a = max(cnt[1005])

    print(ma, ama)

Submission status: Accepted

Solution code:
from math import sqrt
from collections import deque
M = 10**6
prime = [1]*(M+1)
prime[0] = prime[1] = 0
for i in xrange(2, int(sqrt(M))+1):
    if prime[i]:
        for j in xrange(i*i, M+1, i):
            prime[j] = 0
def calc(x):
    k = int(sqrt(x))
    if k % 2:
        p = k/2
        if x <= k**2 + k:
            i = x-k**2
            return (p+1, p-i)
        else:
            i = x-(k**2 + k)
            return (p+1-i, -p-1)
    else:
        p = k/2
        if x <= k**2 + k:
            i = x-k**2
            return (-p, -p+i)
        else:
            i = x-(k**2+k)
            return (-p+i, p)
C = map(calc, xrange(M+1))
dic = {x: i+1 for i, x in enumerate(C)}
while 1:
    m, n = map(int, raw_input().split())
    if m == n == 0:
        break
    used = {}
    deq = deque()
    deq.append(n)
    used[n] = prime[n]
    u = set()
    while deq:
        c = deq.popleft()
        if c in u:
            continue
        u.add(c)
        x, y = C[c-1]
        for dx in [-1, 0, 1]:
            v = dic.get((x+dx, y+1), M+1)
            if v <= m:
                deq.append(v)
                used[v] = max(used[c]+prime[v], used.get(v, 0))
    cnt = 0; num = 0
    for k in used:
        if prime[k]:
            if cnt < used[k]:
                cnt = used[k]
                num = k
            elif cnt == used[k] and num < k:
                num = k
    print cnt, num

Submission status: Accepted

Solution code:
from math import sqrt
from collections import deque
M = 10**6
prime = [1]*(M+1)
prime[0] = prime[1] = 0
for i in xrange(2, int(sqrt(M))+1):
    if prime[i]:
        for j in xrange(i*i, M+1, i):
            prime[j] = 0
P = {(0, 0): 1}; R = [None, (0, 0)]
c = 1; i = 1; p = 1
x = y = 0
while c < M:
    for j in xrange(i):
        x += p; c += 1
        P[x, y] = c; R.append((x, y))
    for j in xrange(i):
        y -= p; c += 1
        P[x, y] = c; R.append((x, y))
    p = -p
    i += 1
deq = deque()
dd = [-1, 0, 1]
while 1:
    m, n = map(int, raw_input().split())
    if m == n == 0:
        break
    deq.append(n)
    cnts = {n: prime[n]}
    used = set()
    while deq:
        v = deq.popleft()
        x, y = R[v]
        for dx in dd:
            t = P.get((x+dx, y+1), M+1)
            if t <= m:
                cnts[t] = max(cnts[v] + prime[t], cnts.get(t, 0))
                if t not in used:
                    deq.append(t)
                    used.add(t)
    vals = sorted((v, k) for k, v in cnts.items() if prime[k])
    print "%d %d" % vals[-1] if vals else "0 0"

Submission status: Accepted

Solution code:
from collections import defaultdict,deque

fact = [1 for i in range(1000001)]
fact[1] = 0
z = 2
while 1:
    j = 2
    while z*j < 1000001:
        fact[z*j] = 0
        j += 1
    for j in range(z+1,1000001):
        if fact[j]:
            z = j
            break
    else:
        break
d = defaultdict(lambda : None)
f = [None for i in range(1000001)]
x,y,di = 0,0,"d"
f[1] = (0,0)
d[(0,0)] = 1
for i in range(2,1000001):
    if di == "d":
        if d[(x+1,y)] == None:
            x += 1
            di = "r"
        else:
            y += 1
    elif di == "r":
        if d[(x,y-1)] == None:
            y -= 1
            di = "u"
        else:
            x += 1
    elif di == "u":
        if d[(x-1,y)] == None:
            x -= 1
            di = "l"
        else:
            y -= 1
    else:
        if d[(x,y+1)] == None:
            y += 1
            di = "d"
        else:
            x -= 1
    d[(x,y)] = i
    f[i] = (x,y)
v = [[] for i in range(1000001)]
for i in range(1,1000001):
    x,y = f[i]
    for j in range(-1,2):
        if d[(x+j,y+1)] != None:
            v[i].append(d[(x+j,y+1)])

while 1:
    m,n = map(int, input().split())
    if m == n == 0:
        break
    ans = [-1 for i in range(m+1)]
    q = deque()
    q.append(n)
    ans[n] = fact[n]
    while q:
        x = q.popleft()
        for y in v[x]:
            if y <= m:
                if ans[y] < 0:
                    ans[y] = ans[x]+fact[y]
                    q.append(y)
                else:
                    if ans[x]+fact[y] > ans[y]:
                        ans[y] = ans[x]+fact[y]
    ma = max(ans)
    if ma == 0:
        print(0,0)
    else:
        for i in range(m+1)[::-1]:
            if fact[i]:
                if ans[i] == ma :
                    k = i
                    break
        print(ma, k)

Submission status: Accepted

Solution code:
def solve():
    M = 10 ** 6
    e = 10 ** 3
    
    # the sieve of Eratosthenes
    primes = [True] * (M + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, e):
        if primes[i]:
            for j in range(i * 2, M + 1, i):
                primes[j] = False
    
    # Create square grid sequence
    sg = [[None] * e for i in range(e)]
    for i, t_el, r1, r2 in zip(range(e // 2), range(e, 1, -2),sg, sg[::-1]):
        s1 = t_el ** 2
        s2 = s1 - 3 * (t_el) + 3
        
        r1[i:i+t_el] = range(s1, s1 - t_el, -1)
        r2[i:i+t_el] = range(s2, s2 + t_el)
    
    for i, t_el in zip(range(e // 2 - 1), range(e - 2, 1, -2)):
        s1 = t_el ** 2 + 1
        s2 = s1 + t_el * 3 + 1
        for c, n1, n2 in zip(sg[i+1:i+1+t_el], range(s1, s1 + t_el),
                             range(s2, s2 - t_el, -1)):
            c[i] = n1
            c[i+t_el+1] = n2
    
    from sys import stdin
    file_input = stdin
    
    while True:
        m, n = map(int, file_input.readline().split())
        if m == 0:
            break
        
        # calculate the position of n
        sn = n ** 0.5
        i_sn = int(sn)
        mid = e // 2
        h_i_sn = i_sn // 2
        if i_sn % 2:
            if sn == i_sn:
                s_r = mid + h_i_sn # start row
                s_c = s_r - 1 # start column
            elif n >= (i_sn ** 2) + i_sn + 1: # on the upper side
                s_r = mid - h_i_sn - 1
                s_c = mid - h_i_sn - 1 + (i_sn + 1) ** 2 - n
            else: # on the right side
                s_r = mid + h_i_sn - n + i_sn ** 2 + 1
                s_c = mid + h_i_sn
        else:
            if sn == i_sn:
                s_r = mid - h_i_sn
                s_c = s_r
            elif n <= (i_sn ** 2) + i_sn: # on the left side
                s_r = mid - h_i_sn + n - i_sn ** 2 - 1
                s_c = mid - h_i_sn - 1
            else: # on the lower side
                s_r = mid + h_i_sn
                s_c = mid + h_i_sn - 1 - (i_sn + 1) ** 2 + n
        
        # calculate the required square grid size
        sm = m ** 0.5
        i_sm = int(sm)
        h_i_sm = i_sm // 2
        if i_sm % 2:
            b = mid + h_i_sm # bottom
            l = mid - h_i_sm - 1 # leftmost
            if sm == i_sm:
                r = mid + h_i_sm - 1 # rightmost
            else:
                r = mid + h_i_sm
        else:
            r = mid + h_i_sm - 1
            if sm == i_sm:
                l = mid - h_i_sm
            else:
                l = mid - h_i_sm - 1
            if m <= i_sm ** 2 + i_sm:
                b = mid + h_i_sm - 1
            else:
                b = mid + h_i_sm
        
        # optimize square grid
        t_sg = [x[l:r+1] for x in sg[s_r:b + 1]]
        
        c1 = s_c - l
        for i, x in zip(range(c1, 0, -1), t_sg):
            x[:i] = [0] * i
        c2 = r - s_c
        for i, x in zip(range(c2, 0, -1), t_sg):
            x[-i:] = [0] * i
            
        if t_sg[-1][0] == 0:
            for i, x in enumerate(t_sg[-1]):
                if x:
                    break
            t_sg = [x[i:] for x in t_sg]
        if t_sg[-1][-1] == 0:
            for i, x in enumerate(t_sg[-1][::-1]):
                if x:
                    break
            t_sg = [x[:-i] for x in t_sg]
        
        if m in t_sg[-1][1:]:
            x = t_sg[-1]
            i = x.index(m)
            x[i+1:] = [0] * (len(x) - i - 1)
        
        for x in t_sg:
            if x[0] > m:
                x[0] = 0
            if x[-1] > m:
                x[-1] = 0
        
        # DP
        rec_size = len(t_sg[0]) + 2
        prev = [0] * rec_size
        ans1 = 0
        ans2 = 0
        for x in t_sg:
            cur = [0] * rec_size
            for i, t in enumerate(zip(prev, prev[1:], prev[2:], x), start=1):
                a, b, c, y = t
                if primes[y]:
                    v = 1 + max(a, b, c)
                    if v == ans1 and y > ans2:
                        ans2 = y
                    elif v > ans1:
                        ans1 = v
                        ans2 = y
                else:
                    v = max(a, b, c)
                cur[i] = v
            prev = cur
        
        print(ans1, ans2)
        

solve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

N = 10**6 + 1
p = list(range(N))
p[1] = 0
for i in range(2, int(N**.5) + 1):
    p[i * 2::i] = [0] * len(p[i * 2::i])

cart2num = {}


def cart2spi(x, y):
    size = max(abs(x), abs(y))
    if x + y > 0:
        num = (2 * size - 1) ** 2
        sx, sy = size, 1 - size
        num += y - sy + sx - x
    else:
        num = (2 * size) ** 2
        sx, sy = -size, size
        num += sy - y + x - sx
    return num


def spi2cart(n):
    root = int(n ** .5)
    diff = n - root ** 2
    if root % 2:
        x, y = root // 2 + 1, -root // 2 + 1
        dx, dy = -1, 1
    else:
        x, y = -root // 2, root // 2
        dx, dy = 1, -1
    x += dx * max(diff - root, 0)
    y += dy * min(diff, root)
    return x, y


def solve(max_p, s):
    prv = {spi2cart(s - 1): [1, s] if p[s] else [0, 0]}
    res = []
    while 1:
        nxt = defaultdict(lambda: [0, 0])
        for x, y in prv:
            ny = y - 1
            for dx in [-1, 0, 1]:
                nx = x + dx
                if (nx, ny) in cart2num:
                    num = cart2num[nx, ny]
                else:
                    num = cart2num[nx, ny] = cart2spi(nx, ny) + 1
                if num > max_p:
                    if dx == 0:
                        res.append(prv[x, y])
                    continue
                nxt_cnt, prv_cnt = nxt[nx, ny][0], prv[x, y][0]
                if p[num]:
                    if nxt_cnt < prv_cnt + 1:
                        nxt[nx, ny] = [prv_cnt + 1, num]
                    elif nxt_cnt == prv_cnt + 1:
                        nxt[nx, ny][1] = max(nxt[nx, ny][1], num)
                else:
                    if nxt_cnt < prv_cnt:
                        nxt[nx, ny] = prv[x, y]
                    elif nxt_cnt == prv_cnt:
                        nxt[nx, ny][1] = max(nxt[nx, ny][1], prv[x, y][1])
        if not nxt:
            break
        prv = nxt
    return max(res)


for e in sys.stdin.readlines()[:-1]:
    m, n = map(int, e.split())
    print(*solve(m, n))

Submission status: Runtime Error

Solution code:
from math import sqrt
from collections import deque
M = 10**6
prime = [1]*(M+1)
prime[0] = prime[1] = 0
for i in xrange(2, int(sqrt(M))+1):
    if prime[i]:
        for j in xrange(i*i, M+1, i):
            prime[j] = 0
P = {(0, 0): 1}; R = [None, (0, 0)]
c = 1; i = 1; p = 1
x = y = 0
while c < M:
    for j in xrange(i):
        x += p; c += 1
        P[x, y] = c; R.append((x, y))
    for j in xrange(i):
        y -= p; c += 1
        P[x, y] = c; R.append((x, y))
    p = -p
    i += 1
deq = deque()
R = [-1, 0, 1]
while 1:
    m, n = map(int, raw_input().split())
    if m == n == 0:
        break
    deq.append(n)
    cnts = {n: prime[n]}
    used = set()
    while deq:
        v = deq.popleft()
        x, y = R[v]
        for dx in R:
            t = P.get((x+dx, y+1), M+1)
            if t <= m:
                cnts[t] = max(cnts[v] + prime[t], cnts.get(t, 0))
                if t not in used:
                    deq.append(t)
                    used.add(t)
    vals = sorted((v, k) for k, v in cnts.items() if prime[k])
    print "%d %d" % vals[-1] if vals else "0 0"