(9 votes, average: 4.67 out of 5)

## Medium Level SPOJ Problems

More solutions (fewer than 15 lines) to some SPOJ classical problems using Python that will cause one to pause and think. Then optimize for a first-place time spot.

Most of these were written in Perl or C++ and I have been converting them to Python. Many solutions have Perl-like references and influences in them.

SPOJ User-id: beta_projects

### PRIMITIVEROOTS (PROBLEM4)

Time: 0.00
Summary: Find the product of all primitive roots of n.

```from math import sqrt; from itertools import count, islice
def isPrime(n):
if n < 2: return False
return all(n%i for i in islice(count(2), int(sqrt(n)-1)))
for cs in range(int(raw_input())):
n = int(raw_input())
if n == 3: print '%d:%d' % (cs+1, 2)
elif isPrime(n): print '%d:%d' % (cs+1, 1)
else: print '%d:%s' % (cs+1, 'NOTPRIME')
```

### Wood, Axe and Grass (WAGE)

Time: 0.00
Summary: For each test case, print the grid as it appears at the end of the nth day.

```def next_to(z):
if (x+1<r and Cx[x+1][y]==z) or (x-1>=0 and Cx[x-1][y]==z) or (y-1>=0 and Cx[x][y-1]==z) or \
(y+1<c and Cx[x][y+1]==z): return True  #with edge detection
return False

for _ in xrange(input()):
r, c, n = map(int, raw_input().split())
C = [list(raw_input().strip()) for _ in xrange(r)]
for _ in xrange(n):
Cx = [_[:] for _ in C]  #copy array by value
for x in xrange(r):
for y in xrange(c):
if C[x][y]=='W' and next_to('G'): C[x][y]='G'
elif C[x][y]=='A' and next_to('W'): C[x][y]='W'
elif C[x][y]=='G' and next_to('A'): C[x][y]='A'
for _ in C:
print ''.join(_)
```

### Sphere in a tetrahedron (TETRA)

Time: 0.00
Summary: Find the product of all primitive roots of n.

```from math import sqrt
def area(a, b, c):
s = (a + b + c) / 2.0
return sqrt(s*(s-a)*(s-b)*(s-c))
for _ in range(int(raw_input())):
WX, WY, WZ, XY, XZ, YZ = map(int, raw_input().split())
u = WY*WY + WZ*WZ - YZ*YZ
v = WZ*WZ + WX*WX - XZ*XZ
w = WX*WX + WY*WY - XY*XY
vol = sqrt(4*WX*WX*WY*WY*WZ*WZ - WX*WX*u*u - WY*WY*v*v - WZ*WZ*w*w+u*v*w) / 12.0
s = area(YZ,XZ,XY) + area(WX, WY, XY) + area(YZ, WY, WZ) + area(WX, XZ, WZ)
print '%.4f' % ((3*vol) / s)
```

### Poker (POKER)

Time: 0.00
Summary: or each test case output one line describing the type of a hand, exactly like in the list above.

```from collections import Counter
rank = [ 0, 0, 0, 'four of a kind', 0, 'full house', 'two pairs', 'three of a kind', \
'pair', 'flush', 'high card', 'straight flush', 'straight', 'royal flush']
straights = [[v-4, v-3, v-2, v-1, v] for v in range(6, 15)] + [[2, 3, 4, 5, 14]]
vx ={'2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9, 'T':10, 'J':11, 'Q':12, 'K':13, 'A':14}
for _ in range(input()):
h = raw_input()
v = sorted([vx[h[i]] for i in range(0,14,3)])
c = Counter(v)
flush = int(h.count(h[1]) == 5)
score = len(c)*2 - int(4 in c.values()) + int(3 in c.values()) - flush + int(v in straights)*2 + int(min(c)==10)*2
print rank[score]
```

### Basically Speaking (BASE)

Time: 0.00
Summary: Convert from one base to another.

```import sys
def base(dec, base):
list, res = '0123456789ABCDEF', ''
while dec != 0:
res, dec = res+list[dec % base], dec//base
return res[::-1]
s, bx, by = b.split()
t = base(int(s, int(bx)), int(by))
print "  ERROR"  if len(t) > 7 else  t.rjust(7, ' ')
```

### The Bytelandian Cryptographer (Act I) (CRYPTO1)

Time: 0.00
Summary: Decode the attack date.

```import time
p = 4000000007
def decrypt(a, p):
k = lambda n: ((p-1)/2 - 1) / 2 + 1
return p - pow(a, k(p), p)
ts = decrypt(int(raw_input()), p)
print time.ctime(ts)
```

### Transform the Expression (ONP)

Time: 0.01
Summary:translate the expressions to RPN form.

```def rpn(s):
vs, ss = [], []
for c in s:
if 'a' <= c <= 'z':
vs.append(c)
elif c in '^*/+-':
ss.append(c)
elif c == ')':
vs.append(vs.pop(-2) + vs.pop() + ss.pop())
return vs[0]
for _ in range(input()):
print rpn(raw_input())
```

### Setnja (SETNJA)

Time: 0.12
Summary: Calculate the value of the given set of walks.

```s = raw_input()
ct, w = 1, 1
for c in s:
left = 2*w
if c=='R':
w = left + ct
elif c=='L':
w = left
elif c=='*':
w += (left + left + ct)
ct *= 3
print w
```

### XOR Game (QN01)

Time: 0.35
Summary: Find the contiguous subsequence with the maximum XOR value.

```n = int(raw_input())
a = map(int, raw_input().split()) + [0]
for x in xrange(1, n):
a[x] ^= a[x - 1]
m = 0
for x in xrange(-1, n + 1):
for y in xrange(x + 1, n + 1):
if a[x] ^ a[y] > m:
m = a[x] ^ a[y]
lo, hi = x + 2, y + 1
print m, '\n', lo, hi
```

### Halloween treats (HALLOW)

Time: 0.96
Summary: For each test case output one line with the indices of the neighbours the children should select (here, index i corresponds to neighbour i who gives a total number of ai sweets).

```while True:
c, n = map(int, raw_input().split())
if c==0 and n==0: break
A = map(int, raw_input().split())
mx = [-1] + [-2]*n
s = 0
for i in range(n):
s = (s+A[i])%c
if mx[s] != -2: break
mx[s] = i
print ' '.join(str(j) for j in range(mx[s]+2, i+2))
```

### Defend The Rohan (ROHAAN)

Time: 0.24
Summary: Find the total distance armies must travel during relocation.

```for cs in range(1, input()+1):
ans, n = 0, input()
A = [map(int, raw_input().split()) for _ in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
A[i][j] = min(A[i][j], A[i][k] + A[k][j])
for _ in range(input()):
x, y = map(int, raw_input().split())
q += A[x-1][y-1]
print 'Case #%d: %d' % (cs, q)
```

### Matrix Game (MATGAME)

Time: 0.19
Summary: Find the total distance armies must travel during relocation.

```c = int(raw_input())
for k in range(c):
N, M = map(int, raw_input().split())
x = 0
for i in range(N):
A = map(int, raw_input().split())[::-1]
a0 = 0
for a in A:
a0 = a - (a<=a0)
x ^= a0
print "FIRST" if x else "SECOND"
if k+1 < c: raw_input()
```

### Monotonous numbers (MONONUM)

Time: 0.11
Summary: Calculate the ratio of the decreasing n-digit integers to the increasing n-digit integers.

```def nCr(n, k):
nt = 1
for t in range(min(k, n-k)):
nt = nt * (n-t) // (t+1)
return nt
for _ in xrange(int(raw_input())):
n = int(raw_input())
print '%.6f' % ((nCr(n + 9, n) - 1)/float(nCr(n + 8, n)))
```

### Recaman’s Sequence (MRECAMAN)

Time: 0.37
Summary: Find the term in Recaman’s Sequence.

```p, a = {0:1}, [0]*500001
for i in range(1, 500001):
t = a[i-1]-i
if t>0 and t not in p:
p[t] = a[i] = t
else:
a[i] = a[i-1]+i
p[a[i]] = 1
while True:
k = int(raw_input())
if k == -1: break
print a[k]
```

### SHAPE GAME (SGAME)

Time: 0.04
Paraphrased: Is it possible to construct figure satisfying the specification.

```def ck(A): return sum(1 for x in A if x%2)
for _ in range(input()):
A = [0]*301
raw_input()
while True:
a, b = map(int, raw_input().split())
if a == -1 and b == -1: break
A[a] += 1; A[b] += 1
print 'NO' if ck(A) else 'YES'
```

### Working in Beijing (WORKB)

Time: 1.10
Output: For each test case, output a single integer indicating the minimum cost for this year.

```for cs in range(1, int(raw_input())+1):
n, a, b = map(int, raw_input().split())
t = map(int, raw_input().split())
c = 2*a + n*b
fc = 2*a
for i in range(1, n):
inx = (t[i]-t[i-1]-1) * b
c+= inx if inx < fc else fc
print 'Case #%d: %d' % (cs, c)
```

### Alphacode (ACODE)

Time: 0.04
Paraphrased: Find the number of possible decodings for the input string.

```while True:
s = raw_input()
if s[0]=='0': break
dp = [1] + [0]*(len(s)-1) + [1]
for i in range(1, len(s)):
if s[i]>'0':
dp[i] = dp[i-1]
if 9 < int(s[i-1]+s[i]) <= 26:
dp[i]+= dp[i-2]
print dp[-2]
```

### Prime or Not (PON)

Time: 0.01
Paraphrased: For each test case output string "YES" if given number is prime and "NO" otherwise.

```import random
def miller_rabin(n):
d = n - 1
s = 0
while d % 2 == 0:
d >>= 1
s += 1
for repeat in range(1):
a = 0
while a == 0:
a = random.randrange(n)
if not miller_rabin_pass(a, s, d, n):
return False
return True

def miller_rabin_pass(a, s, d, n):
a_to_power = pow(a, d, n)
if a_to_power == 1:
return True
for i in range(s-1):
if a_to_power == n - 1:
return True
a_to_power = (a_to_power * a_to_power) % n
return a_to_power == n - 1
def f():
for _ in range(input()):
n=int(raw_input())
print "YES" if miller_rabin(n) else "NO"
f()
```

### Just Next !!! (JNEXT)

Time: 0.40
Paraphrased: Find the next lexicographical permutation.

```# Project Nayuki
# Computes the next lexicographical permutation of the specified list in place,
# returning whether a next permutation existed. (Returns False when the argument
# is already the last possible permutation.)
#
def next_permutation(arr):
# Find non-increasing suffix
i = len(arr) - 1
while i > 0 and arr[i - 1] >= arr[i]:
i -= 1
if i <= 0:
return False

# Find successor to pivot
j = len(arr) - 1
while arr[j] <= arr[i - 1]:
j -= 1
arr[i - 1], arr[j] = arr[j], arr[i - 1]

# Reverse suffix
arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
return True

for _ in xrange(int(raw_input())):
n = int(raw_input())
A = raw_input().split()
print ''.join(A)  if next_permutation(A) else  -1
```

### Joseph’s Problem (NAGAY)

Time: 0.10
Output: Output the sum requested.

```
n, k = map(int, raw_input().split())
i, a = 1, 0
while i <= n:
j, r  = divmod(k, i)
if j == 0: break
s = min(r/j, n-i)
a+= (r+r - s*j) * (s+1) / 2
i+= s+1
print  a + r*(n-i+1)
```

### Khairy and Gold Alloys (WAL3A)

Time: 0.13
Output: For each test case output one line contains how many Gold Alloys are destroyed by Khairy.

```
for _ in range(int(raw_input())):
n = int(raw_input())
A = map(int, raw_input().split())
for i in range(1, n):
A[i-1] = min(A[i-1], A[i])
c =2*A[0]
for i in range(1, n-1):
c+=2*A[i]- min(A[i-1], A[i])
print c if n!=1 else 0
```

### Guess the Number (GUESSTHE)

Time: 0.11
Output: For each test case output a single line with the minimum positive integer that satisfies all the
clues, or −1 if there is no such a number.

```
from fractions import gcd
def f(s):
lcm = lambda a, b: a*b/gcd(a,b)
ans = reduce(lcm, (n for n, c in enumerate(s, 1) if c == 'Y'), 1)
for n, c in enumerate(s, 1):
if c == 'N' and ans%n == 0: return -1
return ans
while True:
s = raw_input()
if s == "*": break
print f(s)
```