102 SPOJ programming problem solutions using Python (average of 4 lines) to some of the easier SPOJ classical problems using Python which run in minimum time (0.00 sec.). Most of these solution are older and were converted from perl, C++ or crafted using Python directly.

The sole purpose of this collection is to aid a research project in comparative machine/human language where source code is considered a subconscious form of recorded thought.

Note: These solutions don’t have much point value, if any, when competing for rank.
SPOJ User-id: beta_projects

102 Easier Classical SPOJ Solutions using Python

ACMT	ACPC10A	ACT	ADV04J	AE00	AMR12D	AMZRCK	ANARC09B
BEENUMS	BINSTIRL	BISHOPS	BOMARBLE	BROUL	CANTON	CHOTU	CIRCLE_E
CODCHESS	CODEIT03	COINTOSS	COLONY	CPRMT	CRAZYSK	CRDS	CUBARTWK
CUTCAKE	DANGER	DIG	DOUGHNUT	EBOXES	EC_CONB	EIGHTS	FACEFRND
FAKETSP	FAVDICE	FENCE1	FTHEELF	FUNPROB	GARDENAR	GEOPROB	GIRLSNBS
GNY07H	GOODB	GUANGGUN	HANGOVER	HC	HEADSHOT	HEPNUM	HLP_RAMS
HUBULLU	IITKWPCB	IWGBS	JOKER1	JULKA	LASTDIG	LCPC12E	M3TILE
MAIN113	MAXGRITH	MAXLN	MBEEWALK	MCIRGAME	MISERMAN	MKLABELS	MUL
MZVRK	NEG2	NGM	NITK06	NOVICE43	OAE	OFFSIDE	PALACE
PARKET1	PB	POSAO	PRISMSA	PRLGAME2	QCJ2	QCJ3	RANJAN02
ROOTCIPH	RROOT	SCPC11B	SCPC11D	SILVER	SNGPG	SNOOKER	SOLDIERS
SPEED	SYNC13C	TAP2014B	TCOUNT2	TOANDFRO	TRENER	TSHOW1	UCV2013A
UCV2013I	VHELSING	VPL2_AA	WILLITST	WORDCNT	YUMMY

Tower Of Hanoi – Revisited (RANJAN02)

Time: 0.00
Output: Classic towers of Hanoi game.

for _ in xrange(input()): print 3**input() - 1

Naya Shatranj (New Chess) (CODCHESS)

Time: 0.00
Output: For each ni×ni board print on a single line “0” if A wins considering both players play optimally well. Otherwise, print “1”.

for _ in xrange(int(raw_input())): print 1 - int(raw_input())%2

REAL ROOTS (RROOT)

Time: 0.00
Output: Probability that the given quadratic equation has real roots. 1-sqrt(2)/3/sqrt(S)

for _ in xrange(input()): print '%.6f' % (1 - (2**0.5/3)/(input()**0.5))

A Game with Numbers (NGM)

Time: 0.00
Output: Determine who wins at a game which is way more complicated that this solution.

N = int(raw_input()) % 10
print "1\n%d" % N  if N!=0 else  2

A Famous Game (PRLGAME2)

Time: 0.00
Output: Calculate the probability of the next ball Mr. M picks out is red.

import sys
for cs, ns in enumerate(sys.stdin, 1):
	N, P, Q = map(float, ns.split())
	print 'Case %d: %.4f' % (cs, (Q+1)/(P+2))

Van Helsings gun (VHELSING)

Time: 0.00
Output: Steinmetz Solid. 8*(2-sqrt(2)*R**3

for _ in xrange(input()): print '%.4f' % ((16 - 8*2**0.5) * input()**3)

TRIANGULAR PRISM (PRISMSA)

Time: 0.00
Output: Minimize surface area of triangular prism when the volume is V.

for i in xrange(int(raw_input())):
    V = int(raw_input())
    print '%.10f' % (6.75**0.5 * (16.0*V*V)**(1/3.))

Maximum Girth (MAXGRITH)

Time: 0.00
Output: Find the maximum girth of a graph

for _ in xrange(input()):
	n = int(raw_input())
	print (n+1)*2//3 % 1000000007

Decipher (ROOTCIPH)

Time: 0.00
Output: Find the square of the distance to the enemy aircraft.

for _ in xrange(int(raw_input())):
    a, b, c = map(int, raw_input().split())
    print a*a - 2*b

Julka (JULKA)

Time: 0.00
Output: SPOJ Python solutions.

for _ in range(10):
    t = int(raw_input()); k = int(raw_input())
    print (t+k)/2, '\n', (t-k)/2 

Point Connection Game in a Circle (MCIRGAME)

Time: 0.00
Output: Catalan numbers.

from math import factorial as f
while True:
    n = int(raw_input())
    if n == -1: break
    print f(2*n) / f(n) / f(n+1))

Another Box Problem (QCJ2)

Time: 0.00
Output: Catalan numbers. Again!

from math import factorial as f
while True:
	n = int(raw_input())
	if n==0: break
	print f(2*n) / f(n) / f(n+1) % 761238923

Binary Stirling Numbers (BINSTIRL)

Time: 0.00
Output: Calculate the Stirling number of the second kind, S(n,m).

for _ in xrange(int(raw_input())):
    n, m = map(int, raw_input().split())
    print int(not((n-m) & ((m-1)/2)))

Hubulullu (HUBULLU)

Time: 0.00
Output: Print the person who moves first. BS Problem.

for _ in xrange(input()):
    p = int(raw_input().split()[1])
    print "Airborne wins."  if p==0 else  "Pagfloyd wins." 

Bishops (BISHOPS)

Time: 0.00
Output: Maximum number of bishops that can be placed on nxn chessboard without threatening each other. Also a good example for handling EOF on input.

import sys
for ns in sys.stdin: print max(1, 2*(int(ns)-1))

Happy Coins (HC)

Time: 0.00
Output: Print the name of whom the final coin belongs to.

for _ in xrange(input()):
	S = sum(raw_input()=='lxh' for _ in xrange(input()))
	print 'lxh'  if S % 2 else  'hhb'

WHAT A CO-ACCIDENT (SYNC13C)

Time: 0.00
Output: Simple combination calculation.

for _ in xrange(int(raw_input())):
    c1, c2 = map(int, raw_input().split())
    print 'Ramesh'  if c1%2 and c2%2 else  'Suresh'

Hangover (HANGOVER)

Time: 0.00
Output: Calculate 1/2 + 1/3 + … 1/(n+1)

while True:
	c, n = float(raw_input()), 2
	if c == 0: break
	while c > 0:
		c-= 1.0/n
		n+= 1
	print n-2, 'card(s)'

Cut the Silver Bar (SILVER)

Time: 0.00
Output: Calculate log(n)/log(2)

from math import log
while True:
    n = int(raw_input())
    if n == 0: break
    print int(log(n,2))

Counting Ids (UCV2013A)

Time: 0.00
Output: Find the number of possible IDs modulo 10^9+7.

m = 10**9 + 7
while(True):
    N, L = map(int, raw_input().split())
    if N==0 and L==0: break
    print ((pow(N, L+1, m)-1)*pow(N-1, m-2, m) - 1) % m

Alpha Centauri Tennis (ACT)

Time: 0.00
Output: (Really?) Print the last character of a string. Another BS Problem.

for _ in xrange(input()):
    N, S = raw_input().split()
    print S[-1]

One Geometry Problem (GEOPROB)

Time: 0.00
Output: Calculate the length of a missing geometrical segment.

for _ in xrange(int(raw_input())):
    b, c, d = map(int, raw_input().split())
    print (c-b)+(c-d) 

Triple Fat Ladies (EIGHTS)

Time: 0.00
Output: find the kth number (indexed from 1) whose cube ends in 888.

for _ in range(int(raw_input())):
    k = int(raw_input())
    print 250*(k-1) + 192  

Will it ever stop (WILLITST)

Time: 0.00
Paraphrase: Output ‘TAK’ if n is a power of 2 else output ‘NIE’

n = int(raw_input())
print "TAK"  if n == -n&n else  "NIE"

Girls and Boys (GIRLSNBS)

Time: 0.00
Output: Minimize the Gender Regularity in a linear arrangement of boys and girls

from math import ceil
while(True):
    G, B = map(float, raw_input().split())
    if G==-1 and B==-1: break
    print int(ceil(max(G,B)/(1+min(G,B))))

Playing with Marbles (BOMARBLE)

Time: 0.00
Output: Given the information of how many pentagons will be created, write a program to calculate the number of marbles needed.

while True:
	n = int(raw_input())
	if n==0: break
	print (3*(n+1)**2 - n)/2

Harry and big doughnuts (DOUGHNUT)

Time: 0.00
Output: Determine if doughnuts would cause Harry’s spine to crack.

for _ in xrange(int(raw_input())):
	c, k, w, = map(int,raw_input().split())
	print 'yes'  if k>=c*w else  'no'

Cards (CRDS)

Time: 0.00
Output: Find the second pentagonal number modulo 1,000,007.

for _ in xrange(int(raw_input())):
    n = int(raw_input())
    print (n*(3*n+1)/2) % 1000007 

THE MAX LINES (MAXLN)

Time: 0.00
Output: Always a right triangle, use Thales’ theorem to solve.

for cs in xrange(1, int(raw_input())+1):
    r = int(raw_input())
    print "Case %d: %.2f" % (cs, 4*r*r + 0.25)

What’s Next (ACPC10A)

Time: 0.00
Output: Check for a common difference or common ratio. Calculate next in series.

while (True):
    a1, a2, a3 = map(int,raw_input().split())
    if a1==0 and a2==0 and a3==0: break
    print '%s %d' % (('AP', a3+a2-a1)  if a2-a1 == a3-a2 else  ('GP', a3*a2/a1))

Yanu in Movie theatre (FUNPROB)

Time: 0.00
Output: Calculate the probability for replenishing supply in simple queue based on cost of x and supply of x and 2x.

while (True):
    N, M = map(float, raw_input().split())
    if N==0 and M==0: break
    print '%.6f' % ((M-N+1)/(M+1)  if M >= N else  0)

In Danger (DANGER)

Time: 0.00
Output: Find the position of the person who survives.

from math import log
while True:
    n = float(raw_input())
    if n == 0: break
    print '%d' % (2*(n - 2**int(log(n,2))) + 1)

Luis Quest (VPL2_AA)

Time: 0.00
Output: Determine for a certain number of creatures p, the exact time Luis has to be in the room to see that amount.

from math import log
for cs in xrange(1, int(raw_input())+1):
	p0, p1, t, p = map(float, raw_input().split())
	print 'Scenario #%d: %.2f' % (cs, ((log(p)-log(p0))*t / (log(p1)-log(p0))))

Invisible point (ADV04J)

Time: 0.00
Output: Determine for a certain number of creatures p, the exact time Luis has to be in the room to see that amount.

from math import log, ceil
for _ in range(int(raw_input())):
	n = float(raw_input())
	print int(ceil(log(n, 2))) + 1

SOLDIERS (SOLDIERS)

Time: 0.00
Output: Find the maximum number of soldiers that can be placed in a separate line.

for _ in xrange(int(raw_input())):
	m, n = map(int,raw_input().split())
	print max(m*(n/2+n%2), n*(m/2+m%2))

Traveling Salesman (FAKETSP)

Time: 0.00
Output: For each segment of the trip, output the total distance traveled up to that point.

import sys
A = [ map(float, ns[ns.find('(')+1:-3].split(','))  for ns in sys.stdin ]
d = 0
for i in xrange(len(A)-1):
	d += ((A[i][0]-A[i+1][0])**2 + (A[i][1]-A[i+1][1])**2)**0.5
	print "The salesman has traveled a total of %.3f kilometers." % d

Accomodate the palace (PALACE)

Time: 0.00
Output: Find the total number of ways people can be accommodated.

for _ in xrange(int(raw_input())):
	n = int(raw_input())-1
	print pow(2, n*n % 204, 98777)

Count on Cantor (CANTON)

Time: 0.00
Output: Find the corresponding term in Cantor’s enumeration.

from math import sqrt, ceil
for _ in xrange(int(raw_input())):
	x = int(raw_input())   
	n = ceil((sqrt(8*x+1)-1)/2) 
	t = x - n*(n-1)/2   
	print 'TERM %d IS %d/%d' % ((x, n-t+1, t)  if n%2 else  (x, t, n-t+1)) 

Play with Dates (CODEIT03)

Time: 0.00
Output: Print the day of the week for the date given.

from datetime import datetime
for _ in xrange(int(raw_input())):
	d, m, y = map(int, raw_input().split())
	print datetime(y, m, d).strftime('%A')

Empty Boxes (EBOXES)

Time: 0.00
Output: Calculate the number of nested boxes

for _ in range(int(raw_input())):
    N, K, T, F = map(int, raw_input().split())
    print F + (F-N)/(K-1)

The last digit (LASTDIG)

Time: 0.00
Output: Find the last digit of an exponentiation
Note: Same program solves: LASTDIG2 – The last digit re-visited

for _ in xrange(int(raw_input())):
	a, b = map(int, raw_input().split())
	print pow(a, b, 10)

Feanor The Elf (FTHEELF)

Time: 0.00
Output: Given a height and velocity, calculate the maximum distance that an arrow can reach when it hits the ground.

from math import sqrt
while(True):
    V, H = map(int, raw_input().split())
    if V==-1 and H==-1: break
    print "%.6f" % (V/9.8 * sqrt(H*19.6 + V*V))

Even Numbers (EC_CONB)

Time: 0.00
Output: Marina is very bored, so she attempts a mindless task that, you guessed it, only causes more boredom. I just can’t make this stuff up.

for _ in xrange(int(raw_input())):
    a = int(raw_input())
    print a  if a%2 else  int(bin(a)[:1:-1], 2)	

Rectangles (AE00)

Time: 0.00
Output: Calculate how many rectanges can be formed from a set of squares.

from math import sqrt
N = int(raw_input())
print sum(N/i-i+1 for i in xrange(1, int(sqrt(N)+1)))

Counting Triangles II (TCOUNT2)

Time: 0.00
Output: Find the number of triangles in the “level N” hexagon. (Doesn’t allow Python) SPOJ solutions using Python

for _ in xrange(int(raw_input())):
	N = float(raw_input())
	print int(N*(7*N*N + 4.5*N + 1)/2)

The Mirror of Galadriel (AMR12D)

Time: 0.00
Output: Determine if the string is a palindrome. SPOJ solutions using Python

def is_palindromic(s): return s==s[::-1]
for _ in xrange(int(raw_input())):
    print 'YES' if is_palindromic(raw_input()) else 'NO'

He is offside! (OFFSIDE)

Time: 0.00
Output: Compare minimum in one list to the second minimum in another and determine offside condition.

while True:
    A, D = map(int, raw_input().split())
    if A==0 and D==0: break
    b = min(map(int, raw_input().split()))
    C = sorted(map(int, raw_input().split()))
    print 'Y'  if b < C[1] else  'N'

Circular Track (SPEED)

Time: 0.00
Output: Calculate the number of distinct point two countercyclical runners will meet. SPOJ solutions using Python

from fractions import gcd
for _ in xrange(int(raw_input())):
    S1, S2 = map(int, raw_input().split())
    print abs((S1-S2) / gcd(S1, S2))

Good Predictions (GOODB)

Time: 0.00
Output: Compute the number of valid ordered combinations of submission results.

from math import factorial as f
n, w, t, r = map(int, raw_input().split())
print f(n) / (f(w)*f(t)*f(r)) % 1000000007

The Game (QCJ3)

Time: 0.00
Output: Determine who wins the game.

from operator import xor
for _ in xrange(int(raw_input())):
	raw_input()
	C = map(int, raw_input().split())
	a = reduce(xor, (i for i, c in enumerate(C, 1) if c%2), 0)
	print 'Hanks Wins'  if a==0 else  'Tom Wins'

Favorite Dice (FAVDICE)

Time: 0.00
Output: Determine whether the permutation is ambiguous or not.

A=[0, 1]
for i in xrange(2, 1001):
	A.append(A[-1] + 1.0/i)
for _ in xrange(int(raw_input())):
	sides = int(raw_input())
	print '%.2f' % sides*A[sides]

Bee Walk (MBEEWALK)

Time: 0.00
Output: OEIS 002898 - Number of n-step closed paths on hexagonal lattice; n<15.

for _ in xrange(int(raw_input())):
    n = int(raw_input()) - 1
    print [0, 6, 12, 90, 360, 2040, 10080, 54810, 290640, 1588356, 8676360, \
           47977776, 266378112, 1488801600][n]

Tambourine (UCV2013I)

Time: 0.00
Output: Find the radius of the big circle to build the tambourine.

from math import pi, sin
while(True):
    r, N = map(int, raw_input().split())
    if r==0 and N==0: break
    print '%.2f' % (r / sin(pi/2/N))

Check the coprimeness (IITKWPCB)

Time: 0.00
Output: Find largest non-negative number less than or equal to floor (N/2) which is coprime to N.

for _ in xrange(int(raw_input())):
	n = int(raw_input())
	k = n/2
	print (k  if n==2 or n%2 else  (k-2  if k%2 else  k-1)) 

LATGACH3 (M3TILE)

Time: 0.00
Output: See A001835 a(n) = 4*a(n-1) – a(n-2), with a(0)=1, a(1)=1.

def T(n): 
	if n==0 or n==1: return 1
	return 4*T(n-1) - T(n-2)
while True:
	n = int(raw_input())
	if n==-1: break
	print '0' if n%2 else T(n/2+1)

Build a Fence (FENCE1)

Time: 0.00
Output: Calculate the area of a semi-circle. (0.1591549 is 1/(2*pi)).

while True:
    L = int(raw_input())
    if L == 0: break
    print '%.2f' % (0.1591549*L*L)

Three Circle Problem (EASY) (CIRCLE_E)

Time: 0.00
Output: Kissing circles. Given three mutually tangent circles, what radius can a fourth tangent circle have?

from math import sqrt
for _ in xrange(int(raw_input())):
    R1, R2, R3 = map(lambda x:1/float(x), raw_input().split())
    Rs = R1 + R2 + R3 + 2*sqrt(R1*R2 + R2*R3 + R3*R1)
    print '%.6f' % (1/Rs)

111…1 Squared (GUANGGUN)

Time: 0.00
Output: Find the sum of digits of the square of a repunit or Demlo numbers.

import sys
for ns in sys.stdin:
	n = int(ns)
	print 81*(n/9) + (n%9)**2

MODIFY SEQUENCE (NITK06)

Time: 0.00
Output: Can a sequence be modified to all zeros with several operations?

for _ in xrange(int(raw_input())):
    d = 0; raw_input()
    for a in map(int, raw_input().split()):
        d = a - d
    print "YES"  if d==0 else  "NO"

Parking Bay (PB)

Time: 0.00
Output: How many sequences are there such that every rebel can dock his star ship?

for _ in xrange(int(raw_input())):
	n = int(raw_input())
	print pow(n+1, n-1, 10007)

Faridi and Yadav (CHOTU)

Time: 0.00
Output: Complicated and obtuse instructions – you’re gonna have to read this one yourself.

from math import sqrt
for _ in xrange(int(raw_input())):
	X, Y = map(int, raw_input().split())
	print '%.3f' % (2*sqrt(X*X - Y*Y))

Snooker (SNOOKER)

Time: 0.00
Output: Find the number of ways in which the ball can be hit so that it eventually reaches one of the four holes.

from fractions import gcd
while True:
	M, N = map(int, raw_input().split())
	if M==0: break
	g = gcd(M, N)
	print 4*(M/g + N/g - 2)

Cubist Artwork (CUBARTWK)

Time: 0.00
Output: Find the minimum number of cubes.

while True:
	w, d = map(int, raw_input().split())
	if w==0 and d==0: break
	wx = map(float, raw_input().split())
	dx = map(float, raw_input().split())
	print sum(i * max(wx.count(i), dx.count(i)) for i in xrange(1, 21))

Whirligig number (MZVRK)

Time: 0.00
Output: Calculate the sum of the whirligig of all numbers between two given numbers A and B (inclusive).

def fnr(n):
	if n<2: return n
	return 2*fnr(n/2) + n/2 + n%2
a, b = map(int, raw_input().split())
print fnr(b) - fnr(a-1)	

To and Fro (TOANDFRO)

Time: 0.00
Output: Find the original plain-text message. SPOJ solutions using Python

while True:
	c = int(raw_input())
	if c==0: break
	codex = raw_input()
	print ''.join(codex[j*c + (c-i-1  if j%2 else  i)]
		for i in xrange(c)
			for j in xrange(len(codex)/c))

Special String (MAIN113)

Time: 0.00
Output: Print total number of strings which have a length N and are not special.

A = [0, 3, 9]
for _ in xrange(3, 31):
	A.append(2*A[-1] + A[-2])
for _ in xrange(int(raw_input())):
	print A[int(raw_input())]

Tiles of Tetris, Not! (ANARC09B)

Time: 0.00
Output: An angry boss, an incompetent employee and some erroneous tiles with an easy solution.

while True:
	W, H = map(int, raw_input().split())
	if W==0 or H==0: break
	print (W/H  if  W%H==0 else  (H/W  if H%W==0 else  H*W))

Amusing numbers (TSHOW1)

Time: 0.00
Output: Print total number of strings which have a length N and are not special.

for _ in xrange(int(raw_input())):
	n, s = int(raw_input()), ''
	while n:
		n,r = divmod(n, 2)
		n -= 1-r
		s = '65'[r] + s
	print s

0110SS (IWGBS)

Time: 0.00
Output: Fib(N+2) just like AMZRCK - Amz Rock.

F = [0, 1]
for i in xrange(2, 3300):
	F.append(F[-1] + F[-2])
print F[int(raw_input()) + 2]

Area of a Garden (GARDENAR)

Time: 0.00
Output: Calculate the area of the garden.

from math import sqrt
for _ in xrange(int(raw_input())):
	a, b, c = map(float, raw_input().split())
	area = (sqrt(3) * (a*a + b*b + c*c))/8
	s = (a + b + c)/2
	area += (1.5 * sqrt(s*(s-a)*(s-b)*(s-c)))
	print '%.2f' % area

Word Counting (WORDCNT)

Time: 0.00
Summary: For each data test, write in one line the number P Nguyen wants to find.

from itertools import groupby
for i in xrange(int(raw_input())):
	Q = map(len, raw_input().split())
	print max(len(list(L)) for n, L in groupby(Q))

Alaska (SCPC11B)

Time: 0.00
Output: Output a line containing POSSIBLE if Brenda can make the trip.

while True:
	n = int(raw_input())
	if n==0: break
	A = sorted([int(raw_input()) for _ in xrange(n)])
	if sum(1 for i in xrange(n-1)  if A[i+1]-A[i]>200) > 0 or \
		1422-A[-1] > 100: print 'IMPOSSIBLE'
	else: print 'POSSIBLE'

Trener (TRENER)

Time: 0.00
Output: Select a basketball team.

y = ''.join(raw_input()[0] for _ in xrange(int(raw_input())))
s = ''.join(chr(c) for c in xrange(97, 123) if y.count(chr(c)) >= 5)
print s  if s else  'PREDAJA'

Balanced base-3 (TAP2014B)

Time: 0.00
Output: Print a single line containing a string composed solely of the characters '0', '+' and '-' and not beginning with '0', representing the digits of the number N in balanced base-3.

for _ in xrange(int(raw_input())):
	n, s = int(raw_input()), ''
	while n:
		s += '0+-'[n%3]
		if n%3 == 2: n+=1
		n /= 3
	print s[::-1]

Wise And Miser (MISERMAN)

Time: 0.00
Output: Find the minimum amount of fare that Jack has to give.

m, n = map(int, raw_input().split())
a = [[999]+map(int, raw_input().split())+[999] for _ in xrange(m)]
for i in xrange(m-1):
	for j in xrange(1, n+1):
		a[i+1][j] += min(a[i][j], a[i][j-1], a[i][j+1])
print min(a[m-1])

Friends of Friends (FACEFRND)

Time: 0.00
Output: A single integer denoting Bob's number of friends of friends.

a=set(); b=set()
for _ in xrange(int(raw_input())):
	A = raw_input().split()
	a.add(A[0])
	b.update(A[2:])
print len(a ^ (a|b))

Linearian Colony (COLONY)

Time: 0.00
Output: Find the color of the Linearian, either red or blue..

def q(n, k):
	if n==0 and k==0: return 'red'
	p = k/2
	ans = q(n-1, p)
	if k == 2*p: return 'blue'  if ans == 'red' else  'red'
	return ans
print q(int(raw_input()),int(raw_input())) 

Common Permutation (CPRMT)

Time: 0.00
Output: Find the common permutation. SPOJ solutions using Python

import sys
import collections
for ns in sys.stdin:
	h1=collections.Counter(ns.strip())
	h2=collections.Counter(sys.stdin.next().strip())
	s = ''.join(c * min(h2[c], h1[c]) for c in 'abcdefghijklmnopqrstuvwxyz')
	print s

Headshot (HEADSHOT)

Time: 0.00
Output: Maximize the chances of survival from Russian Roulette.

import sys
for ns in (sys.stdin):
	s, l, e = ns.strip(), 0, 0
	for i in xrange(len(s)):
		if s[i]=='0' and s[i-1]=='0': l += 1
		if s[i]=='0' and s[i-1]=='1': e += 1
	print 'EQUAL'  if l == len(s) or l == e else  ('SHOOT'  if l > e else  'ROTATE')

Johnny's Empire (LCPC12E)

Time: 0.00
Output: Estimate the length of a way between two kingdoms.

from math import sqrt
for cs in xrange(1, int(raw_input())+1):
	x1,y1, x2,y2, ac, l = map(float,raw_input().split())
	ab = sqrt((x1-x2)**2 + (y1-y2)**2)
	cosa = (ab*ab + ac*ac - (l/sqrt(2))**2) / (2*ab*ac)
	if cosa <= 1: print "%d. %.3f" % (cs, 2*ac*sqrt(1-cosa*cosa))
	else: print "%d. No problem" % cs

Knifes Are Fun (JOKER1)

Time: 0.00
Output: Print the number of ways Joker can assign numbers to his knifes.

from operator import mul
for _ in xrange(int(raw_input())):
	n = int(raw_input())
	k = sorted(map(int, raw_input().split()))
	print 0  if k[n-1] < n else  reduce(mul, (k[i]-i for i in xrange(n)))%1000000007
print "KILL BATMAN"

DIAGONAL (DIG)

Time: 0.00
Output: Find the number of intersections of diagonals.

for _ in xrange(int(raw_input())):
	n = int(raw_input())
	print n*(n-1)*(n-2)*(n-3)/24 % 1000000007

Egypt (SCPC11D)

Time: 0.00
Output: Determine if a triangle is right (or wrong).

while True:
 a, b, c = map(lambda x:int(x)*int(x), raw_input().split())
 if a==0 and b==0 and c==0: break
 print 'right'  if a+b==c or a+c==b or b+c==a else  'wrong'

Making Labels (MKLABELS)

Time: 0.00
Output: Calculate the number of different ways a tree with N vertices may be labeled.

for cs in xrange(1, 1000):
	n = int(raw_input())
	if n==0: break
	print 'Case %d, N = %d, # of different labelings = %d' % (cs, n, pow(n, n-2))

Beehive Numbers (BEENUMS)

Time: 0.00
Output: Output a single line containing an uppercase “Y” if N is a beehive number, or an uppercase “N” otherwise.

from math import sqrt
while True:
	n = int(raw_input())
	if n==-1: break
	print 'N'  if sqrt(12*n-3)%1 else  'Y'

Problem 3 (NOVICE43)

Time: 0.00
Output: Bell or exponential numbers: number of ways to partition a set of n labeled elements.

A000110 = [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570]
for _ in xrange(int(raw_input())):
	print A000110[int(raw_input())]

Fast Multiplication (MUL)

Time: 0.00
Output: Multiply two numbers.

for _ in xrange(int(raw_input())):
	a, b = map(int, raw_input().split())
	print a * b

Prime Generator The Easiest Question Ever (SNGPG)

Time: 0.00
Output: Count total number of such primes p in the xrange [a ≥ 0, b > 0] so that (p2 + 1) or/and (p2 + 2) is/are prime(s).

for _ in xrange(int(raw_input())):
	a, b = map(int, raw_input().split())
	print min(3,b)-a+1  if a < 4 else  0

Acm Teams (ACMT)

Time: 0.00
Output: Find the maximum number of teams that can be formed. SPOJ solutions using Python

for _ in xrange(int(raw_input())):
	e, n = map(int, raw_input().split())
	mx, mn = (e,n)  if e>n else  (n,e)
	print (e+n)/3  if mn > mx/2 else  mn

Yummy Triangular Pizza (YUMMY)

Time: 0.00
Output: Find the number of possible different shapes of the pizza.

A006534 = [1, 1, 1, 4, 6, 19, 43, 120, 307, 866, 2336, 6588, 18373, 52119, 147700, 422016]
for cs in xrange(1, int(raw_input())+1):
	n = int(raw_input()) - 1
	print 'Case #%d: %d' % (cs, A006534[n])

PARKET (PARKET1)

Time: 0.00
Output: What is the dimensions of the room, L and W, respectively.

from math import sqrt
r, b = map(int, raw_input().split())
q = r/2 + 2
d = int(sqrt(q*q - 4*(r+b)))
print (q + d)/2, (q - d)/2

Topper Rama Rao (HLP_RAMS)

Time: 0.00
Output: Specify the number of even numbers and odd numbers respectively.

for _ in xrange(int(raw_input())):
	n = int(raw_input())
	odds = pow(2, bin(n).count('1'))
	print n-odds+1, odds

The Moronic Cowmpouter (NEG2)

Time: 0.00
Output: The cows may be on to something.

print bin(int(raw_input()) + 2863311530 ^ 2863311530)[2:]

OAE (OAE)

Time: 0.00
Output: A single line for each test case, containing the answer modulo 314159.

for _ in xrange(int(raw_input())):
	n = int(raw_input())-1
	print (4*pow(8, n, 314159) + 5*pow(10, n, 314159)) % 314159

Jobs (POSAO)

Time: 0.00
Output: Print least possible time in which all jobs can be done.

n, k = map(int, raw_input().split())
print 2*n - 1  if k > n else  k + n*n/k - (n%k==0)

Amz Rock (AMZRCK)

Time: 0.00
Output: Calculate the number of good playlists.

p = 5**0.5
for _ in xrange(int(raw_input())):
	n = int(raw_input()) + 2
	print int(((1+p)**n-(1-p)**n)/(2**n*p))

Crazy Shopkeeper (CRAZYSK)

Time: 0.00
Output: Print the total number of items the customer will have after exchanging maximum no of cards for getting extra items.

for i in xrange(int(raw_input())):
	x, n = map(int, raw_input().split())
	x+= x/(n-1)
	print x  if x%n else  x-1

Coin Tosses (COINTOSS)

Time: 0.00
Output: What is the expected number of tosses needed till you get N consecutive heads?

for _ in xrange(int(raw_input())):
	n, m = map(int, raw_input().split())
	print '%d.00' % (pow(2, n+1) - pow(2, m+1))

Eat all the brownies ! (CUTCAKE)

Time: 0.00
Output: Number of cuts. SPOJ solutions using Python

from math import sqrt
for _ in xrange(int(raw_input())):
	n = int(raw_input()) - 1
	print int((sqrt(8*n + 1) + 1)/2 - 1)

Heptadecimal Numbers (HEPNUM)

Time: 0.00
Output: print <, =, or > for the appropriate relationship between two Heptadecimal Numbers.

while True:
	a, b = raw_input().split()
	if a=='*' and b=='*': break
	a, b = a.zfill(len(b)), b.zfill(len(a))
	print '=' if a==b else ('>' if a > b else '<')           

Babylonian Roulette (BROUL)

Time: 0.00
Output: Estimate the number of people that played in a day.

from math import ceil 
while True:
	p, b, f = map(int, raw_input().split())
	if b == 0: break
	print 'No accounting tablet'  if (p-f)%b else  int(ceil(abs(p-f)/b/3.0))

Tiling a Grid With Dominoes (GNY07H)

Time: 0.00
Output: A005178(n) = a(n-1)+5*a(n-2)+a(n-3)-a(n-4).

A005178 = [0, 1, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 
	1174500, 3335651, 9475901, 26915305, 76455961, 217172736, 616891945, 1752296281]
for cs in xrange(1, int(raw_input())+1):
    W = int(raw_input()) + 1
    print cs, A005178[W]