// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (9 votes, average: 4.67 out of 5)
Loading...

Classical Problems

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]
for b in sys.stdin.readlines():
	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)
 

Discussion

No comments yet.

Post a comment