Loading...More solutions (fewer than 10 lines) to some SPOJ classical problems using Python.
Note: SPOJ may prevent Python from being used for solving some problems or set time limits suitable only for compiled languages.
some of these were originally written in Perl and have been rewritten in Python. Many solutions have Perl-like references and influences in them.
SPOJ User-id: beta_projects
Numeral System of the Maya (MAYA)
Time: 0.00
Output: Your program has to output the value of the number in the input file in the nowadays more common decimal system. One number per line.
B = [0, 1, 20, 360, 7200, 144000, 2880000, 57600000]
c = lambda d: d.count('.') + 5*d.count('-')
while True:
n = int(raw_input())
if n==0: break
A = reversed([raw_input() for _ in range(n)])
print sum(c(d) * B[i] for i, d in enumerate(A, 1))
Buying Apples! (ABA12C)
Time: 0.00
Summary: Find the minimum amount of money he has to spend.
for _ in xrange(input()): n, k = map(int, raw_input().split()) P = [(int(x), i) for i,x in enumerate(map(int, raw_input().split()), 1) if x>=0] dp = [0]+[9999]*k for p, i in P: for j in xrange(i, k+1): if dp[j-1] != 9999: dp[j] = min(dp[j], dp[j-i] + p) print dp[k] if dp[k] != 9999 else -1
Sometimes, a penalty is good! (ACPC10E)
Time: 0.00
Summary: Determine the number of games, and the number of teams to add.
from math import log, ceil while True: g, t, a, d = map(int, raw_input().split()) if g < 0: break y = g*a + d x = 2**int(ceil(log(y, 2))) m = x + t*(t-1)/2*g - 1 print '%d*%d/%d+%d=%d+%d' % (g, a, t, d, m, x-y)
The Cats and the Mouse (CATM)
Time: 0.00
Output: You must output k lines with answers for each test case. The answer is YES, if the mouse can escape or NO otherwise.
n, m = map(int, raw_input().split()) for _ in range(int(raw_input())): x1, y1, x2, y2, x3, y3 = map(int, raw_input().split()) xd = min(x2+abs(y1-y2), x3+abs(y1-y3)) xm = max(x2-abs(y1-y2), x3-abs(y1-y3)) yd = min(y2+abs(x1-x2), y3+abs(x1-x3)) print 'YES' if x1 < xd or y1 < yd or x1 > xm else 'NO'
Billiard (BILLIARD)
Time: 0.00
Output: Calculate the measure of the angle A in degrees and the velocity of the ball measured in inches per second.
from math import pi, sqrt, atan while True: a, b, s, m, n = map(float, raw_input().split()) if s==0: break vx = m*a/s vy = n*b/s print '%.2lf %.2lf' % (atan(vy/vx)*180.0/pi, sqrt(vx*vx + vy*vy))
Bytelandian gold coins (COINS)
Time: 0.00
Summary: Find the maximum amount of American dollars you can make.
m = {}
def coins(n):
if n==0: return n
if not n in m:
m[n] = max(n, coins(n/2) + coins(n/3) + coins(n/4))
return m[n]
for _ in xrange(10):
print coins(input())
Nim-B Sum (NY10B)
Time: 0.00
Summary: Calculate the Nim sum in base B of X and Y.
for _ in xrange(input()): csi, b, x, y = map(int,raw_input().split()) i, s = 1, 0 while x+y > 0: s+= (x+y)%b * i x//= b; y//= b; i*= b print csi, s
Making Money (MKMONEY)
Time: 0.00
Summary: Print the value of the investment at the end of a year.
from math import floor for cs in range(1, 100000): P, r, n = map(float, raw_input().split()) if n==0: break print 'Case %d. $%.2f at %.2f%% APR compounded %d times yields' % (cs, P, r, n), for i in range(int(n)): P+= floor((P*r/n))/100 print '$%.2f' % P
GENIE SEQUENCE (KURUK14)
Time: 0.00
Summary: Is it possible to form a genie sequence?
for _ in xrange(int(raw_input())): A = [0]*1001 n = int(raw_input()) for i in map(int, raw_input().split()): if A[i+1]==0: A[i+1] = 1 else: A[n-i] = 1 print 'YES' if n==sum(A) else 'NO'
Manku Word (MAY99_2)
Time: 0.00
Summary: Print the nth manku word.
for _ in xrange(input()): s = '' n = int(raw_input()) while n > 0: n, r = divmod(n, 5) if r==0: n -= 1 s += 'umank'[r] print s[::-1]
Farmer Cream (UCV2013C)
Time: 0.00
Summary: Determine the fate of the farmer.
while True: d, f, b, m = map(int, raw_input().split()) if d<1 or f<1 or b<1 or m<1: break n = (f*f + f + 2) /2 t = d - n*b if t > m: print 'Farmer Cream will have', t, 'Bsf to spend.' else: print 'The firm is trying to bankrupt Farmer Cream by', m-t, 'Bsf.'
Maya Calendar (MAYCA)
Time: 0.00
Summary: Convert Mayan dates from the Haab calendar to the Tzolkin calendar.
haab = {'pop':0, 'no':1, 'zip':2, 'zotz':3, 'tzec':4, 'xul':5, 'yoxkin':6,\
'mol':7, 'chen':8, 'yax':9, 'zac':10, 'ceh':11, 'mac':12, 'kankin':13, \
'muan':14, 'pax':15, 'koyab':16, 'cumhu':17, 'uayet':18}
tzolkin = 'imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, \
chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau'.split(', ')
c = int(raw_input())
print c
for _ in xrange(c):
n, d, y = raw_input().split()
ndays = int(float(n)) + haab[d]*20 + int(y)*365
print ndays%13 + 1, tzolkin[ndays%20], ndays/260
Game of chocolate (NAJGC)
Time: 0.00
Summary: For each test case print the case number and Gwen win probability in a/b format.
from fractions import gcd for cs in xrange(1, int(raw_input())+1): x1, y1, x2, y2 = map(int,raw_input().split()) n = x1*(x2+1) + y1*(y2+1) d = (x1+y1) * (x2+y2+1) if n==0 or d==0: print 'Case %d: 0' % cs else: g = gcd(d,n); print 'Case %d: %d/%d' % (cs, n/g, d/g)
Black and White (BANDW)
Time: 0.00
Output: Find the least possible number of moves such that you can change the chip's position.
while True: S, T = raw_input().split() if S=='*' and T=='*': break c, f = 0, 0 for s,t in zip(S,T): if s!=t and f==0: c +=1 f = (s!=t) print c
Seinfeld (ANARC09A)
Time: 0.00
Summary: Find the minimum number of operations needed to convert the given string into a balanced one.
import sys
for cs, s in enumerate(sys.stdin.readlines(), 1):
if s[0] == '-': break
n, cnt = 0, 0
for c in s:
if c == '{': n+= 1
elif c == '}' and n==0: n+= 1; cnt+= 1
elif c == '}' and n>0: n-= 1
print '%d. %d' % (cs, n/2+cnt)
The Knights of the Round Circle (KNIGHTSR)
Time: 0.00
Summary: Compute the average number of Knights to leave the circle during a competition.
A = [0, 0]
for i in xrange(2, 10001):
A.append(A[-1] + 1.0/i)
while True:
n = int(raw_input())
if n == 0: break
print 'With %d competitors, a Jedi Knight will be replaced approximately %.2f times.' % (n, A[n])
Pyramids (PIR)
Time: 0.00
Summary: Find the volume of a tetrahedron given only the six edge-lengths.
from math import sqrt
for _ in xrange(input()):
A, D, B, E, C, F = map(lambda x: int(x)**2, raw_input().split())
volume = sqrt((-A*B*C - A*D*E - B*D*F - C*E*F + A*C*D + B*C*D + \
A*B*E + B*C*E + B*D*E + C*D*E + A*B*F + A*C*F + \
A*D*F + C*D*F + A*E*F + B*E*F - C*C*D - C*D*D - \
B*B*E - B*E*E - A*A*F - A*F*F)/144.0)
print "%.4f" % volume
Rama and Friends (GSHOP)
Time: 0.00
Summary: Find the maximum possible sum which can be obtained after modifying the array.
for _ in xrange(input()): n, k = map(int, raw_input().split()) A = map(int, raw_input().split()) for i in xrange(min(n, k)): if A[i]>=0: break A[i] *= -1 k-=1 m = min(A) if k&1 else 0 print sum(A)-2*m
Family members (FAMWEALT)
Time: 0.00
Summary: Print the wealth of yth node in a single line.
def fnr(x, w, n=0): if x <= 1: return w q = 4.0 if x%4==3 else 2.0 if n: return fnr((x - x%2)/2, w*q, 1) return fnr((x - x%2)/2, w/q) for _ in xrange(input()): x, y, w = map(int, raw_input().split()) print '%.6f' % (fnr(y, fnr(x, w, 1)))
N DIV PHI_N (NDIVPHI)
Time: 0.00
Summary: Find the smallest m <= N such that m/phi(m) is maximum.
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
79,83,89,97,101]
for _ in xrange(20):
n = int(raw_input())
px = 1
for p in primes:
if px*p > n: break
px*=p
print px
Happy Numbers I (HPYNOS)
Time: 0.00
Output: Find the number of times a process had to be done to determine that N is happy, or -1 if N is not happy.
N = int(raw_input()) a = [] while True: N = sum(int(d)**2 for d in str(N)) if N in a or N==1: break a.append(N) print len(a)+1 if N==1 else -1
Last Non-Zero Digit of Factorials (FCTRL4)
Time: 0.00
Summary: find the last non-zero digit of N!.
import sys def L(n): p = lambda x: [1,2,4,8][x%4] if n<5: return [1,1,2,6,4][n] return p(n/5) * L(n/5) * L(n%5) % 10 for b in sys.stdin.readlines(): print L(int(b))
Traversing Grid (BTCODE_A)
Time: 0.00
Summary: Determine if (xd,yd) is reachable from (xs,ys).
from fractions import gcd for _ in xrange(input()): xs, ys, xd, yd = map(int, raw_input().split()) gd = abs(gcd(xd, yd)) gs = abs(gcd(xs, ys)) while 0 < gs < gd: gs *= 2 print 'YES' if gd==gs else 'NO'
Alice Sieve (ALICESIE)
Time: 0.00
Paraphrased: Add 1 and divide by 2.
for _ in xrange(int(raw_input())):
print (int(raw_input())+1) / 2
AP - Complete The Series v2 (AP3)
Time: 0.00
Summary: Print the series numbers separated by single space.
from math import sqrt for _ in xrange(int(raw_input())): x, y, s = map(int,raw_input().split()) d = 5*y + 7*x + 2*s n = int((d + sqrt(d*d - 48*s*(x + y))) / (2*(x + y))) dx = (y-x)/(n-6) a = x - 2*dx print n, "\n", ' '.join(str(a + dx*i) for i in xrange(n))
Maximal Quadrilateral Area (QUADAREA)
Time: 0.00
Paraphrased: Find the Maximal Quadrilateral Area for a Cyclic Quadrilateral using Brahmagupta's formula.
from math import sqrt
for _ in xrange(int(raw_input())):
a, b, c, d = map(float, raw_input().split())
s = (a+b+c+d)/2
print "%.2f" % sqrt(((s-a)*(s-b)*(s-c)*(s-d)))
PLAY WITH MATH (ENIGMATH)
Time: 0.00
Paraphrased: Calculate the GCD for two numbers.
from fractions import gcd for _ in xrange(input()): A, B = map(int, raw_input().split()) g = gcd(A, B) print B/g, A/g
Anti-Blot System (ABSYS)
time: 0.00
Paraphrased: Recover addition problems damaged by ink blots. SPOJ Python solutions
for _ in xrange(input()):
raw_input(); a, _, b, _, c = raw_input().split()
if 'machula' in a: a = str(int(c) - int(b))
elif 'machula' in b: b = str(int(c) - int(a))
else: c = str(int(a) + int(b))
print a, '+', b, '=', c
Sum of divisors! (ABA12D)
Time: 0.00
Output: Output T lines each containing a single integer ‘c’ which denotes the number of K-numbers which lie in the interval [A,B] inclusive of the end points.
A023194 = [2, 4, 9, 16, 25, 64, 289, 729, 1681, 2401, 3481, 4096, 5041, 7921, 10201, 15625, \ 17161, 27889, 28561, 29929, 65536, 83521, 85849, 146689, 262144, 279841, 458329, \ 491401, 531441, 552049, 579121, 597529, 683929, 703921, 707281, 734449, 829921, 1190281] for _ in range(int(raw_input())): L, H = map(lambda x:max(A023194, key=lambda y:y>=int(x)), raw_input().split()) print A023194.index(H) - A023194.index(L)
Uncle Jack (UJ)
Time: 0.00
Paraphrased: Simple combination calculation.
while True:
N, D = map(int, raw_input().split())
if N==0 and D==0: break
print pow(N, D)
Candy I (CANDY)
Time: 0.00
Summary: Find the smallest number of moves for each block of data.
while True: n = input() if n == -1: break A = [int(raw_input()) for _ in xrange(n)] s = sum(A) print -1 if s%n else sum(abs(s/n-a) for a in A)/2
Bird tree (NWERC11B)
Time: 0.00
Summary: Print the string representation of the location of this fraction in the Bird tree.
for _ in xrange(input()):
a, b = map(int, raw_input().split('/'))
s = ''
while a*b > 1:
s += 'L' if a < b else 'R'
a, b = (b-a, a) if a < b else (b, a-b)
print s
Two Game (TWOGAME)
Time: 0.00
Output: For each test case print a single line with the character Y if it is possible for Alice to reach the given pair or N if it is impossible.
for _ in range(int(raw_input())): a, b = map(int, raw_input().split()) while b: a, b = b, a%b while a%2==0: a>>= 1 print 'Y' if a==1 else 'N'
Load Testing (GCJ101C)
Time: 0.00
Output: For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of load tests you need to run in the worst case before knowing within a factor of C how many people the site can support.
from math import sqrt for cs in xrange(1, int(raw_input())+1): L, P, C = map(int, raw_input().split()) y = 0 while L*C < P: L = sqrt(L*P) y += 1 print 'Case #%i: %s' % (cs, y)
GLJIVE (GLJIVE)
Time: 0.00
Output: Help Super Mario and tell him how many points he will score.
def f(s=0): for _ in range(10): d = int(raw_input()) s += d if s >= 100: return s if s <= 100+d/2 else s-d return s print f()
Vero Dominoes (VERODOOM)
Time: 0.22
Summary: Find the total dots in the domino pieces.
for _ in xrange(int(raw_input())): n = int(raw_input()) print n*(n+1)*(n+2)/2
Increasing Powers of K (INCPOWK)
Time: 0.04
Summary: For each test case print a single line, the Nth term of the sequence Sk.
for _ in xrange(int(raw_input())): k, n = map(int, raw_input().split()) print int(bin(n)[2:], k)
Flowers Flourish from France (MFLAR10)
Time: 0.01
Summary: Determine if a sentence is a tautogram.
while True: w = raw_input().strip().lower().split() if w[0]=='*': break s = sum(1 for c in w if c[0]==w[0][0]) print 'Y' if len(w)==s else 'N'
Coke madness (RPLC)
Time: 0.04
Summary: Calculate the minimum energy required by David to pass the street.
for cs in xrange(1, int(raw_input())+1): raw_input() s, m = 0, 0 for x in raw_input().split(): s += int(x) if s < 0: s, m = 0, m-s print 'Scenario #%d: %d' % (cs, m+1)
Help Tohu (TOHU)
Time: 0.02
Summary: Find the value of a sequence.
for _ in xrange(input()): n = float(raw_input()) print '%.11f' % (2.0/3 + (1.0/6 + 1/(n+2) - 1/(n+1))/2)
Tohu again (TOHU2)
Time: 0.02*
Summary: The 'ol "gray elephant from Denmark" trick.
for _ in xrange(input()): t = [raw_input()[-1] for _ in xrange(99)] print "YES" if t[8:81:9]==[t[8]]*9 else "NO"
CANDY (LQDCANDY)
Time: 0.00
Summary: Find the length of the chocolate bar and the minimum number of times to break the bar.
from math import log, ceil for _ in xrange(input()): n, c = int(raw_input()), 0 e = int(ceil(log(n, 2))) while n%2 == 0: n/=2; c+=1 print 2**e, e-c
Easy Jug (MAY99_3)
Time: 0.03 PYPY
Summary: Output "YES" if manku can drink exactly z litres of water else "NO".
Note: Had to use my own GCD routine to get fastest time. Weird.
def gcd(a, b):
while b != 0:
(a, b) = (b, a % b)
return a
for _ in xrange(int(raw_input())):
x, y, z = map(int, raw_input().split())
print 'NO' if (z>x and z>y) or z%gcd(x,y)!=0 else 'YES'
Real Mangoes for Ranjith (MANGOES)
Time: 0.01
Summary: Find the number of "real" mangoes Ranjith gets.
for _ in xrange(int(raw_input())): N = int(raw_input()) print ((N/2 + 1)**2) % N
Pyramidal Constructions (PIRACON)
Time: 0.01*
Summary: Calculate the total number and "Tringus" number of pieces needed for a pyramid of level K.
for cs in xrange(1, int(raw_input())+1):
K = int(raw_input())
print 'Pyramid E. Nro# %d: %d' % (cs, K*(2*K*K + 6*K - 5)/3)
print 'Tringus:', 2*(K*K - K)
Kusac (KUSAC)
Time: 0.00
Summary: Find the minimum number of cuts.
from fractions import gcd N, M = map(int, raw_input().split()) print M - gcd(M, N)
Match the words (NOVICE62)
Time: 0.02
Summary: Take a 2 column one-to-one relationship and match non correctly.
A = [0, 0, 1] for i in xrange(3, 100000): A.append(((i-1) * (A[-1]+A[-2])) % 1000000007) for _ in xrange(input()): n = int(raw_input()) print 0 if n >= 100000 else A[n]
AP - Complete The Series (Easy) (AP2)
Time: 0.00
Summary: Determine the number of terms in the series and the series numbers.
for _ in xrange(input()): a, b, c = map(int, raw_input().split()) n = (c*2)/(a+b) d = (b-a)/(n-5) m = a-2*d print n, '\n', " ".join(str(m+d*i) for i in range(n))
Enough of analyzing, let’s play (EALP1)
Time: 0.32
Summary: Your task is to find the number of ways Player 1 can start the game so that after his first move, he is in the winning position.
from operator import xor for cs in xrange(1, input()+1): raw_input() A = map(int, raw_input().split()) s = reduce(xor, A, 0) print 'Case %d: %d' % (cs, sum(1 for a in A if s^a < a))
Large subsequence Problem (LARSUBP)
Time: 0.68*
Summary: Find the number of subsequences.
for cs in xrange(1, int(raw_input())+1): br = [0]*10 ar = map(int, list(raw_input())) for a in ar: br[a]+= sum(br[:a]) + 1 print 'Case %d: %d' % (cs, sum(br) % 1000000007)
Biased Standings (BAISED)
Time: 0.28
Summary: For each of the test cases output a single line with a single integer : the badness of the best rank list for the given teams.
for _ in xrange(int(raw_input())): raw_input() n = int(raw_input()) A = sorted([int(raw_input().split()[1]) for _ in xrange(n)]) print sum(abs(A[i]-i-1) for i in xrange(n))
Bye Bye Cakes (BYECAKES)
Time: 0.01
Summary: Output a single line with four non-negative integers separated by single spaces,
representing the amount of each ingredient John needs to buy.
from math import ceil while True: A = map(float, raw_input().split()) if A[0] < 0: break mx = max(ceil(A[i] / A[i+4]) for i in xrange(4)) print ' '.join(str(int(mx*A[i+4] - A[i])) for i in xrange(4))
Operation Bits (OPBIT)
Time: 0.06
Summary: For each test case print the corresponding key.
from math import sqrt for _ in xrange(input()): a, b = map(int, raw_input().split()) x, y = 0xFFFFF, 0 for i in xrange(int(sqrt(a)), int(sqrt(b))): t = (i+1)*(i+1) - i*i x &= t y ^= t print x&y
Encode Integer (SNGINT)
Time: 0.02
Summary: Encode N into another possible smallest integer M (M > 0), such that product of digits of M equals to N.
for _ in xrange(input()): n, s = input(), '' if n == 0: print 10 elif n < 10: print n else: for i in xrange(9, 1, -1): while n%i == 0: s += str(i) n /= i print -1 if n > 1 else s[::-1]
Between the Mountains (ACPC11B)
Time: 0.07*
Summary: Find the minimum altitude difference between two suitable platform points.
for _ in xrange(input()): A = sorted(map(int, raw_input().split())[1:]) B = sorted(map(int, raw_input().split())[1:]) d = abs(A[0]-B[0]) for a in A: for b in B: d = min(d, abs(a-b)) if a < b: break print d
Fast Sum of two to an exponent (FAST2)
Time: 0.00
Summary: Output the sum from 2^0 to 2^n MODULO 12980...
for _ in xrange(input()): n = int(raw_input()) print pow(2, n+1, 1298074214633706835075030044377087) - 1
The Yellow Brick Road (YELBRICK)
Time: 0.03
Summary: Find the minimum number of cubes that can be cut from the given stones.
while True: t, vol, N = 0, 1001, int(raw_input()) if N==0: break for i in xrange(N): a, b, c = map(int, raw_input().split()) t += a*b*c vol = min(a, b, c, vol) print t/vol**3
abs(a-b) I (ABSP1)
Time: 0.26*
Summary: Calculate the summation of the absolute difference of all the distinct pairs.
for _ in xrange(input()): N = input() A = map(int, raw_input().split()) s, x = 0, 0 for i in xrange(1, N): x += (i*(A[i] - A[i-1])) s += x print s
Distinct Subsequences (DSUBSEQ)
Time: 0.14
Summary: Find the number of distinct subsequences.
m = 10**9 + 7 for _ in xrange(int(raw_input())): r, t, s = 2, [0]*100, map(ord, raw_input()) t[s[0]] = 1 for i in s[1:]: tmp = t[i] t[i] = r r = (2*r - tmp) % m print r
Johnny The Gambler (LCPC12F)
Time: 0.08
Summary: The number of valid pairs (j, k).
for cs in xrange(1, int(raw_input())+1): cnt = 0 C = map(int, raw_input().split()) X = C[0]; A = [0]*2001 for c in C[2:]: if X >= c: cnt += A[X-c] A[c] += 1 print '%d. %d' % (cs, cnt)
Consecutive sequence (SEQ6)
Time: 2.00*
Summary: Calculate number of sequences which sum is equal to N.
from math import sqrt while True: n = 2*int(raw_input()) if n==0: break q = int(sqrt(n)) + 1 r = sum((i+n/i)%2 for i in xrange(1, q) if n%i==0) print 2*r+q%2 if q*q == n else 2*r
Self Numbers (MCUR98)
Time: 0.15*
Summary: Calculate the first 1 million self numbers.
v = [0]*1000001 for i in xrange(1, 1000000): if v[i]==0: print i s, n = 0, i while n > 0: s, n = s + n%10, n//10 v[min(s+i, 1000000)] = 1
Valences (UCV2013J)
Time: 0.22*
Summary: For each compound output a single line with the sum of the valences.
while True: V = raw_input().split() n = int(V[0]) if n == 0: break print sum(map(int, V[n/2+1:]))
hai jolly jolly jolly (NITT2)
Time: 0.31 PYPY
Summary: Given a number you have to tell whether the number is divisible by 252 and 525.
def d(s, n, r=0):
for c in s:
r = (10*r + int(c)) % n
return r==0
for _ in xrange(input()):
s = raw_input()
print ('Yes' if d(s,252) else 'No'), ('Yes' if d(s,525) else 'No')
Cylinder (CYLINDER)
Paraphrased: Calculate the biggest possible volume of a cylinder.
from math import pi
while True:
w, h = map(float, raw_input().split())
if w==0 and h==0: break
res = h/2/(pi+1) if h < w*(pi+1) else w/2
res2 = pi * res*res * w
res3 = w*w/4 * (h*pi - w) / pi**2
print '%.3f' % max(res2, res3)
Ohani And The Series (OHANISER)
Time: 0.40
Summary: Find the only number in a row.
t, m = [1], 10**9+7 for _ in xrange(1, 100000): t.append(2*t[-1] % m) for cs in xrange(1, input()+1): n = int(raw_input()) print 'Case %d: %d' % (cs, 1 if n==1 else (n+1)*t[n-2] % m)
With a Pit of Death (DOJO)
Time: 0.02
Summary: Avoid the pit of death.
for _ in xrange(input()): n, m, i ,j = raw_input().split() m = int(m[-1]) * int(n) j = int(j[-1]) + int(i) print 'Possible.' if m%2 and j%2==0 else 'Impossible.'
The return of the Cake (REBOUND)
Time: 0.70
Summary: Find the perfect shot.
from math import sqrt for _ in xrange(int(raw_input())): x, y, z = map(int, raw_input().split()) d = int(sqrt(x*x + y*y + 2*y*z)) a = 2*x*z + 2*z*d b = 2*y + 4*z print 'Not this time.' if a % b else a/b
Rachu (MAY99_4)
Time: 0.06 PYPY
Summary: Calculate the number of ways muffins could be distributed.
from math import factorial as f def C(n, k): return f(n)//f(k)//f(n-k) n, r = map(int, raw_input().split()) print -1 if n < r else C(n-1, r-1) % 10000007
Constructible Regular Polygons (POLCONST)
Time: 0.14
Summary: Print “Yes” if the regular polygon can be constructed with compass and straightedge.
A000215 = [3, 5, 17, 257, 65537] for _ in xrange(int(raw_input())): n = int(raw_input()) while n%2==0: n/=2 for a in A000215: if n%a==0: n/=a print 'Yes' if n==1 else 'No'
Rectangles Perimeter (MMAXPER)
Time: 0.01
Summary: Find the maximum possible length of the upper envelop line.
n = int(raw_input()) A = [map(int, raw_input().split()) for _ in xrange(n)] L1, L2 = A[0][1], A[0][0] for i in xrange(1, n): L1, L2 = max(L1+abs(A[i-1][0]-A[i][0])+A[i][1], L2+abs(A[i-1][1]-A[i][0])+A[i][1]), \ max(L1+abs(A[i-1][0]-A[i][1])+A[i][0], L2+abs(A[i-1][1]-A[i][1])+A[i][0]) print max(L1, L2)
Mario and Mushrooms (MARIO2)
Time: 0.10
Summary: Output the probability that Mario will survive if he receives all the randomly placed mushrooms one by one.
for cs in xrange(1, input()+1): m, k = map(int, raw_input().split()) print 'Case #%d: %.8f' % (cs, 1.0/(k + m*k + 1))
Can You Make It Empty 2 (EMTY2)
Time: 0.06★
Summary: Can you empty a string of binary digits by recursively removing '100's.
for cs in xrange(1, input()+1): s, cnt = raw_input(), 0 for b in s[::-1]: cnt+= 1 if b=='0' else -2 if cnt < 0: break print 'Case %d: %s' % (cs, 'no' if cnt else 'yes')
Imperial Units (IMPUNITS)
Time: 0.03
Summary: For each test case, output a single line with two positive integers C and D representing
that CU1 is equivalent to DUN.
from fractions import gcd while True: n = int(raw_input()) if n == -1: break nx, dx = 1, 1 for i in xrange(n-1): a, b = map(int, raw_input().split()) nx, dx = nx*a, dx*b print nx/gcd(nx, dx), dx/gcd(nx, dx)
Feline Olympics - Mouseball (MBALL)
Time: 0.13
Summary: Specify the number of even numbers and odd numbers respectively.
m = 10**5+10 dp = [1]+[0]*m for i in [2,3,6,7,8]: for j in xrange(i, m): dp[j]+= dp[j-i] for _ in xrange(input()): print dp[int(raw_input())]
Fractions on Tree (NG0FRCTN)
Time: 0.32
Summary: Print the numerator and denominator of the lowest form of the fraction.
m = {1:1}
def f(n):
if not n in m:
m[n] = f(n/2)+f(n/2+1) if n&1 else f(n/2)
return m[n]
while True:
n = int(raw_input())
if n==0: break
print '%d/%d' % (f(n), f(n+1))
GETTING AN AP (APPROB)
Time: 0.62
Summary: Find p/q, where p/q is an irreducible fraction denoting the probability of forming an arithmetic progression from the chits LJ picks.
from fractions import gcd for _ in xrange(input()): n = int(raw_input()) p = (3*n*n + 1)/2 if n%2 else 3*n*n/2 q = 6*n**3 g = gcd(p, q) print '%d/%d' % (p/g, q/g)
0 0 Pairs (M00PAIR)
Time: 0.05
Summary: For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.
import sys A = [0, 1] for _ in xrange(1000): A.append(2*A[-2] + A[-1]) for ns in sys.stdin: print A[int(ns)-1]
Street Trees (STREETR)
Time: 0.64
Summary: Output the minimal number of trees that must be planted.
from fractions import gcd n = int(raw_input()) A = [int(raw_input()) for _ in xrange(n)] d = 0 for i in xrange(1, n): d = gcd(d, A[i]-A[i-1]) print (A[-1]-A[0])/d - n+1
A Needle in the Haystack (NHAY)
Time: 0.27
Summary: Output all positions of the needle's occurences within the haystack.
while True: try: _, n, h = [raw_input() for _ in xrange(3)] p = h.find(n) while p > 0: print p p = h.find(n, p+1) print except: break
Yet Another Permutations Problem (YAPP)
Time: 0.11
Summary: How many permutations of the first N numbers exist such that the maximum element between the indices [i..j] is either present at index i, or at index j?
for _ in xrange(input()): print pow(2, int(raw_input())-1, 1000000007)
Ljutnja (C1LJUTNJ)
Time: 0.44
Summary: Minimize the total anger for the children of the corn. See the movie to get the reference. Also, the mod 2^64 was a nice touch in adding to one's misery.
m, n = map(int, raw_input().split()) W = sorted([int(raw_input()) for _ in xrange(n)]) t = sum(W) - m ta = 0 for i in xrange(n): anger = min(W[i], t/(n-i)) ta += anger * anger t -= anger print ta % 2**64
Army Strength (ARMY)
Time: 0.25
Paraphrased: Go. Go. Godzilla. Find the more powerful 'monster' before the next movie!
for _ in xrange(input()):
raw_input(); raw_input(); #blank & unneeded
Gmax = max(map(int, raw_input().split()))
Mmax = max(map(int, raw_input().split()))
print 'Godzilla' if Gmax >= Mmax else 'MechaGodzilla'
Ambiguous Permutations (PERMUT2)
Time: 0.34
Paraphrased: Determine whether the permutation is ambiguous or not.
while True:
if input()==0: break
p = map(int, raw_input().split())
for j, pj in enumerate(p, 1):
if pj != j and p[pj-1] != j:
print 'not',
break
print 'ambiguous'
Collatz (CLTZ)
Time: 0.28
Paraphrased: Collatz sequence.
import sys
for ns in sys.stdin:
n, c = int(ns), 1
while n != 1:
n = 3*n +1 if n%2 else n>>1
c += 1
print c
Niceness of the string (IITKWPCA)
Time: 0.02
Paraphrased: Find the unique words in a string.
for _ in xrange(input()): print len(set(raw_input().split()))
Playing With Balls (IITKWPCN)
Time: 0.02
Paraphrased: Determine the probability that the color of last ball remaining in the bag is black.
for _ in xrange(int(raw_input())):
B = int(raw_input().split()[1])
print '1.000000' if B%2 else '0.000000'
Number Steps (NSTEPS)
Time: 0.02★
Paraphrased: Find the value at an (x,y) coordinate in a stair-step pattern.
for _ in xrange(int(raw_input())):
x, y = map(int, raw_input().split())
print x+y-x%2 if x==y or (x-y)==2 else 'No Number'
DOTA HEROES (DOTAA)
Time: 0.11
Paraphrased: Find whether a team can survive the trip to an opponent's empire.
for _ in xrange(int(raw_input())):
n, m, D = map(int, raw_input().split())
c = sum((int(raw_input())-1)/D for _ in xrange(n))
print 'YES' if c >= m else 'NO'
Counting Triangles (TRICOUNT)
Time: 0.09
Paraphrased: Count the number of triangles in a triangular grid (triangle tiling).
for _ in xrange(int(raw_input())):
n = int(raw_input())
print n*(n+2)*(2*n+1) / 8
Wine trading in Gergovia (GERGOVIA)
Time: 0.08 PYPY
Paraphrased: Add the net transactions in wine trading.
while True: t, w = 0, 0 if raw_input() == '0': break for a in raw_input().split(): t+= int(a) w+= abs(t) print w
Move To Invert (MINCOUNT)
Time: 0.13
Paraphrased: Calculate the minimum number of moves required to invert the triangle.
for _ in xrange(int(raw_input())): h = int(raw_input()) print h*(h+1) / 6
War (TAP2013G)
Time: 0.82
Paraphrased: When it comes to war, cheaters always prosper. Simple sort and compare to see who wins more battles, and thus, the war.
S = input()
Q = sorted(map(int, raw_input().split()))
N = sorted(map(int, raw_input().split()))
b = 0
for j in range(S):
if Q[b] < N[j]: b+=1
print b
Revenge of the squares (variation) (SQUAREV1)
Time: 0.65
Paraphrased: Given a number N count the number R of different presentations of N in the form A*A+B*B with A and B being positive integers including zero.
from math import sqrt for _ in xrange(50): x = input() print sum(1 for i in xrange(1, int(sqrt(x/2))+1) if sqrt(x - i*i)%1 == 0)
Make them equal ! (MKEQUAL)
Time: 0.10
Paraphrased: Calculate the maximum number of elements which can have the same value.
for _ in xrange(int(raw_input())): n = int(raw_input()) t = sum(map(int, raw_input().split())) print n-1 if t%n else n
Counting Triangles III (TCOUNT3)
Time: 0.02
Paraphrased: Find the number of triangles in the “level N” hexagon.
for _ in xrange(int(raw_input())): N = int(raw_input()) print N + N*N*(10*N + 9)
Party (CFPARTY)
time: 0.06
Paraphrased: Maximum number of people at the end of a party.
for _ in xrange(int(raw_input())): print max(0, int(raw_input())-2)
Adding Reversed Numbers (ADDREV)
Time: 0.02*
Paraphrased: Calculate reversed sum of two reversed numbers.
for _ in xrange(int(raw_input())):
a, b = raw_input().split()
print int(str((int(a[::-1]) + int(b[::-1])))[::-1])
Clones (NCLNE)
Time: 0.86
Paraphrased: Check a sequence for legitimacy according to clone rules of replication.
for _ in xrange(int(raw_input())): raw_input(); b = map(int, raw_input().split()) d = reduce(lambda d,t: 2*(d - t), b[:-1], 1) print 'Yes' if d==b[-1] else 'No'
Gopu and Digits Divisibility (SPCQ)
Time 0.43 PYPY
Paraphrased: Find the smallest "nice" number greater or equal to n.
def sd(n): return sum(int(i) for i in str(n))
for _ in xrange(int(raw_input())):
n = int(raw_input())
while n % sd(n): n+=1
print n
Pebble Solver (PEBBLE)
Time: 0.07*
Paraphrased: Find the minimum number of steps required for your program to solve the game.
import sys
for g, st in enumerate(sys.stdin, 1):
c = 0
for s in st.strip():
c+= (s=='1') ^ (c&1)
print "Game #%d: %d" % (g, c)
Factorial length (LENGFACT)
Time: 0.01
Paraphrased: Use Stirling's formula to calculate the length of a factorial.
from math import log10, pi, e
for _ in xrange(input()):
n = input()
print 1 if n<4 else int(log10(2*pi*n)/2 + n*log10(n/e)) + 1
A Famous ICPC Team (TEAM2)
Time: 0.02
Paraphrased: Find the minimum side length of the large box required to ship 4 square-shaped suitcases.
import sys
for c, ns in enumerate(sys.stdin, 1):
A = sorted(map(int, ns.split()))
print 'Case %d: %d' % (c, A[2] + A[3])
Candy III (CANDY3)
Time: 0.01*
Paraphrased: Determine if candies can be distributed equally.
for _ in xrange(int(raw_input())):
raw_input(); n = int(raw_input())
k = sum(int(raw_input())%n for _ in xrange(n))
print "NO" if k%n else "YES"
Candy Distribution (CADYDIST)
Time: 0.21 PYPY
Paraphrased: Find the least amount of money Alice must spend on candy. (PYPY)
while True:
N = input()
if N==0: break
C = sorted(map(int, raw_input().split()))
P = sorted(map(int, raw_input().split()))
print sum(C[i] * P[N-i-1] for i in xrange(N)) #cost
Factorial (FCTRL)
Time: 0.31 PYPY
Paraphrased: Simply, find the number of trailing zeros in a factorial.
for _ in xrange(input()):
n = input()
c = 0
while n >= 5:
n /= 5
c += n
print c
Musical Chairs (ANARC08H)
Time: 0.78
Paraphrased: Find the winner of the game.
while True:
N, D = map(int, raw_input().split())
if N==0 and D==0: break
print N, D, reduce(lambda a,j:(a+D)%j, xrange(2, N+1), 0) + 1
Traversing Grid (TRGRID)
Time: 0.02
Paraphrased: Find the required direction you will be facing at the end.
for _ in xrange(input()): n, m = map(int, raw_input().split()) if n>m: print 'U' if m%2==0 else 'D' else: print 'L' if n%2==0 else 'R'
Princess Farida (FARIDA)
Time: 0.20
Paraphrased: Simple DP solution.
for cs in xrange(1, input()+1): raw_input() dp = [0, 0] for x in map(int, raw_input().split()): dp.append(max(x+dp[-2], dp[-1])) print 'Case %d: %d' % (cs, dp[-1])
Conga line (CONGA)
Time: 0.34 PYPY
Paraphrased: Find the minimum time it takes to start dancing.
while True: n = input() if n == 0: break a = map(int, raw_input().split()) print sum(a[n-i-1] - a[i] - (n-2*i-1) for i in xrange(0, n/2))
Crucial Equation (CEQU)
Time: 0.96
Paraphrased: Determine if there exists at least one solution to ax + by = c.
from fractions import gcd
for cs in xrange(1, input()+1):
a, b, c = map(int, raw_input().split())
print "Case %d: %s" % (cs, ('No' if c % gcd(a,b) else 'Yes'))
Maggu and Triangles (IITWPC4B)
Time: 0.30
Paraphrased: Calculate the number of triangles you can create from a wire of length n.
for _ in xrange(input()):
n = input()
k = n*n if n%2==0 else (n+3)*(n+3)
print k/48+1 if k%48>24 else k/48
Sums in a Triangle (SUMITR)
Time: 0.38
Paraphrased: Compute the largest sum on the paths starting from the top towards the base of a numerical triangle.
for _ in xrange(input()):
nx = input()
t = [map(int, raw_input().split()) for _ in xrange(nx)]
for r in xrange(nx-1, 0, -1):
for c in xrange(0, r):
t[r-1][c] += max(t[r][c], t[r][c+1])
print t[0][0]
Mohib and series (MOHIB)
Time: 0.02
Paraphrased: Print the largest possible number in the sequence.
for _ in xrange(int(raw_input())): x, avg = map(int, raw_input().split()) print (avg*avg - x*x - 3*x + 3*avg)/2
Christmas Play (AMR10G)
Time: 0.39
Paraphrased: Minimize the height difference between the tallest and shortest in a group.
for _ in xrange(int(raw_input())): N, K = map(int, raw_input().split()) h = sorted(map(int, raw_input().split())) print min(h[K-1+i] - h[i] for i in xrange(N-K+1))
Why this kolaveri di (WTK)
Time: 0.08
Paraphrased: Josephus Problem.
for _ in xrange(int(raw_input())): n = int(raw_input()) print reduce(lambda q,k: (q+n-k)%k+1, xrange(2, n+1), 1)
Loop Expectation (LOOPEXP)
Time: 0.04
Paraphrased: Calculate the expected number of times the 'if' block of the provided pseudo-code executes.
a = [0, 1] for i in xrange(2, 100001): a.append(a[-1] + 1.0/i) for _ in xrange(int(raw_input())): print a[int(raw_input())]
Training Land of Fury (NFURY)
Time: 0.09
Paraphrased: Print the minimum number of pieces that should be bought.
from math import sqrt A = [0] + [999999]*1000 for i in xrange(1, 1001): for j in xrange(1, int(sqrt(i))+1): A[i] = min(A[i], A[i-j*j]+1) for _ in xrange(int(raw_input())): print A[int(raw_input())]
Pigeonhole Tower (PHT)
Time: 0.37
Paraphrased: Find the minimum number of pieces that should be bought.
from math import sqrt for cs in xrange(1, int(raw_input())+1): n = int(raw_input()) print 'Case %d: %d' % (cs, sqrt(n+1)-1)
Atoms in the Lab (ATOMS)
ime: 0.08
Paraphrased: Determine the time at which the reaction will have to be stopped.
from math import log for _ in xrange(int(raw_input())): N, K, M = map(int, raw_input().split()) print 0 if M<=N else int(log(M/N, K))
Boring Factorials (DCEPC11B)
Time: 0.30
Paraphrased: Print N! modulo P.
for _ in xrange(int(raw_input())): n, p = map(int, raw_input().split()) if n < p: q = reduce(lambda a,j:(a*j)%p, xrange(p-1, n, -1), 1) print p - pow(q, p-2, p) if n < p else 0
Break the Chocolate (BC)
Time: 0.08
Paraphrased: Minimum numbers of steps to break a chocolate bar.
from math import log, ceil
for cs in xrange(1, input()+1):
N, M, K = map(int, raw_input().split())
t = ceil(log(N, 2)) + ceil(log(M, 2)) + ceil(log(K, 2))
print "Case #%d: %d %d" % (cs, N*M*K-1, t)
SHAHBAG (SHAHBG)
Time: 0.11
Paraphrased: Print number of groups currently in shahbag.
raw_input() cnt, Px = 0, [False]*20002 for p in map(int, raw_input().split()): Px[p] = True if Px[p-1] == Px[p+1] == True: cnt-= 1 if Px[p-1] == Px[p+1] == False: cnt+= 1 print cnt print 'Justice'
Glass Beads (BEADS)
Time: 0.03
Paraphrased: Find number of the bead which is the first at the worst possible disjoining.
for _ in xrange(int(raw_input())): maxm = s = raw_input() maxf = 0 for f in xrange(len(s)): m = s[f:] + s[:f] maxm, maxf = (m, f) if maxm > m else (maxm, maxf) print maxf + 1
Fashion Shows (FASHION)
Time: 0.08
Paraphrased: Print a single integer denoting the sum of the hotness bonds for all pairs that MMDS has proposed.
for _ in xrange(input()): raw_input() A = sorted(map(int, raw_input().split())) B = sorted(map(int, raw_input().split())) print sum(a*b for a,b in zip(A,B))
Run length encoding (RLE)
Time: 0.16
Paraphrased: Find the run length encoding of the input string.
import sys, re
buff = sys.stdin.readlines()
for s in buff:
sx = ''
for g, c in re.findall(r'((\w)\2{0,})', s):
j = len(g)
sx+= c*j if j <= 3 else str(j)+'!'+c
print sx
KNJIGE (KNJIGE)
Time: 0.80
Paraphrased: Find the number of moves.
n = int(raw_input()) for a in reversed([raw_input() for _ in range(n)]): if a == str(n): n-= 1 print n
Pizza (EGYPIZZA)
Time: 0.01
Paraphrased: Find the the minimal number of pizzas.
import sys, math
buff = map(lambda s:s.strip(), sys.stdin.readlines())
a = buff.count('3/4')
b = buff.count('1/2')
c = buff.count('1/4')
q = a + b/2.0 + 1
print int(math.ceil((q + (c-a - 2*b%2)/4.0) if a < c else q))
Bowling (BOWLING1)
Time: 0.02
Paraphrased: Calculate the bowling score.
for _ in xrange(int(raw_input())): d = map(int,raw_input().split()) s = 0 for _ in xrange(10): s+= sum(d[:2 + (d[0]+d[1] > 9)]) d = d[2 - (d[0] > 9):] print s
Dukkar and Pikka (DUKKAR)
Time: 0.42
Paraphrased: Calculate the number of numbers divisible by P on Nth row of the pascal triangle.
for _ in xrange(int(raw_input())): n, p = map(int, raw_input().split()) nx = n+1 ans = 1 while n>0: n, r = divmod(n, p) ans*= r+1 print nx-ans
SHAKTIMAN AND KILWISH (SHAKTI)
Time: 0.12
Summary: Determine who wins the game.
for _ in range(int(raw_input())): n = int(raw_input()) print 'Sorry Shaktiman' if n%2 else 'Thankyou Shaktiman'
The Blind Passenger (MYQ1)
Time: 0.39
Output: Help the man find his seat by telling him the row number (1,2,...), seat position(window or aisle or middle), and the direction(left or right).
for _ in range(int(raw_input())): n = int(raw_input()) if n==1: print 'poor conductor' else: r = (n+3)/5 print r, 'AWWAAMWWMA'[n%10], 'L' if n%10<4 else 'R'
HOW MANY GAMES (GAMES)
Time: 0.09
Output: For each test case, find the minimum number of matches the player should have played to achieve that average.
for _ in xrange(int(raw_input())):
s = raw_input() + '.'
n = int(s.replace('.', ''))
f = 10 ** len(s[s.index('.')+2:])
print f/gcd(n,f)
Hard Launching (RPLH)
Time: 0.03
Output: Output the string “Scenario #i: “ where i is the test case you are analyzing followed by a single number D, denoting the Degrees necessary to do the launch, if the launching can't be done, output D as -1. the number must have a precision of 2 decimal digits.
from math import pi, asin for cs in range(1, int(raw_input())+1): ta, sp = map(float, raw_input().split()) si = ta*9.806 / sp / sp print 'Scenario #%d: %.2f' % (cs, asin(si)*90/pi if si <= 1 else -1)
BRODOVI (BRODOVI)
Time: 0.46 PYPY
Output: The first and only line of output must contain the required minimum number of ships.
n, c = int(raw_input()), 0 bx = [int(raw_input())-1 for _ in range(n)][1:] for b in bx: for q in bx[c+1:]: if q%b==0: bx.remove(q) c+=1 print c
Filchs Dilemna (BYTESH1)
Time: 0.01
Output: For each test case, output the last four digits of the number of ways of carpeting the 2xN way. If the answer involves fewer than 4 digits, print the entire number.
f = [1,1]; g = [1,0] for i in range(2, 33001): f.append((f[-1] + f[-2] + 2*g[-1]) % 10000) g.append((f[-3] + g[-1])) for _ in range(int(raw_input())): print f[int(raw_input())]
Easy Calculation (TRIGALGE)
Time: 0.02*
Output: T real numbers rounded to 6 digits one in each line.
from math import sin def f(a, b, c, p, r): while (r - p > 1e-6): q = (p + r) / 2.0 r, p = (q, p) if a*q + b*sin(q) > c else (r, q) return r for _ in xrange(int(raw_input())): a, b, c = map(int, raw_input().split()) print '%.6f' % f(a, b, c, 0, c)
Find the Clones (CLONE)
Time: 0.09
Output: For each test case, you have to output n lines, each line containing a single integer. The first line contains the number of different people that were not copied. The second line contains the number of people that were copied only once (i.e., there are two identical copies for each such person.)
from collections import Counter while True: n, m = map(int, raw_input().split()) if n==0 and m==0: break q =[0]*n for z in Counter(raw_input() for _ in range(n)).values(): q[z-1]+= 1 for qx in q: print qx
Road net (ROADNET)
Time: 1.03
Output: For each test case your program should write all the pairs of the neighbouring towns (i.e. their numbers). There should be one pair in each line. Each pair can appear only once. The numbers in each pair should be given in increasing order. Pairs should be ordered so that if the pair (a, b) precedes the pair (c, d) then a < c or (a = c and b < d).
for _ in range(int(raw_input())): n = int(raw_input()) d = [map(int, raw_input().split()) for _ in range(n)] for i in range(n-1): for j in range(i+1, n): for k in range(n): if j!=k and i!=k and d[j][k]+d[k][i]==d[j][i]: break if k==n-1: print i+1, j+1 raw_input()
Roommate Agreement (CRAN02)
Time: 3.64
Output: The number of such sequences whose sum if zero.
from collections import defaultdict
for _ in range(int(raw_input())):
raw_input()
d = defaultdict(lambda: 0, {0:1})
s, ans = 0, 0
for q in map(int, raw_input().split()):
s+= q
ans+= d[s]
d[s]+= 1
print ans
Matches (FERT21_0)
Time: 0.01
Output: Find (1/2)**n with full precision to n<=1000.
for _ in xrange(input()):
n = int(raw_input())
x = 5**(n-1)
print '1' if n==1 else '0.'+str(x).zfill(n-1) # x/10**n
Discussion
No comments yet.