SPOJ: 8132. Street Trees

A group of trees is planted along a straight line.

KOI is planning to plant more trees so that the distance between two adjacent trees is equal for all trees.

For simplicity, each tree can only be planted on an integer coordinate.

Problem: Sphere Online Judge (SPOJ) – Problem STREETR

Solution:
To illustrate this problem I drew this small graphic:

The large trees are given and we have to find the small ones. You can see pretty fast that the maximum difference between trees is the minimum difference between already planted trees. But we’re not only looking for one arbitrary solution (which would be zero difference), we’re looking for the greatest difference or more generally the Greatest common divisor.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def gcdList(lst):
    myGcd = gcd(lst[0], lst[1])
    for c in lst[1:]:
        myGcd = gcd(myGcd, c)

    return myGcd

N = int(raw_input())
diff = []
lastTree = int(raw_input())
for i in xrange(1, N):
    newTree = int(raw_input())
    diff.append(newTree - lastTree)
    lastTree = newTree

myGcd = gcdList(diff)

trees = map(lambda x: (x / myGcd) - 1, diff)
print sum(trees)

SPOJ: 1728. Common Permutation

Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

Problem: Sphere Online Judge (SPOJ) – Problem CPRMT

Solution: That’s short and nice problem. You have to find all letters which are in both strings. I’d actually like to see some other implementations of this. I bet there are some languages which handle this in a smart way.

def intersection(lst1, lst2):
    same = []
    if len(lst1) > len(lst2):
        for k in lst1:
            try: # checks if element k is in lst2
                lst2.remove(k)
                same.append(k)
            except:
                pass
    else:
        for k in lst2:
            try:
                lst1.remove(k)
                same.append(k)
            except:
                pass
    same.sort()
    return same


while True:
    try:
        inp1 = raw_input()
        inp2 = raw_input()

        common = intersection(list(inp1), list(inp2))
        print "".join(common)
    except:
        break

SPOJ: 3374. Scavenger Hunt

He does a poor job, though, and wants to learn from Bill’s routes. Unfortunately Bill has left only a few notes for his successor. Bill never wrote his routes completely, he only left lots of little sheets on which he had written two consecutive steps of the routes. […]
This made much sense, since one step always required something from the previous step. George however would like to have a route written down as one long sequence of all the steps in the correct order.

Problem: Sphere Online Judge (SPOJ) – Problem SCAVHUNT

Solution:

scenarios = int(raw_input())

for i in xrange(0, scenarios):
    S = int(raw_input())

    myDict = dict()
    myRevDict = dict()

    for j in xrange(0, S - 1):
        fromLocation, toLocation = raw_input().split()
        myDict[fromLocation] = toLocation
        myRevDict[toLocation] = fromLocation
    

    # find start
    start = ""
    for key in myDict.keys():
        if key not in myRevDict:
            start = key
            break
    
    # print message
    print "Scenario #%i:" % (i + 1)

    # print path
    currentKey = start
    for l in xrange(0, S - 1):
        print currentKey
        currentKey = myDict[currentKey]

    print currentKey
    print ""

SPOJ: 1268. CN Tower (Easy)

On the way, she stops in Toronto to do some sightseeing. The unfortunate thing about travelling is that everyone back home expects her to bring back pictures of everything. […] 351 m up the tower is the “360” rotating restaurant, which rotates a full 360 degrees every 72 minutes. From there, Christy can see the whole city, and take close-up pictures of all the landmarks using her fancy new 100x optical zoom camera. Since the restaurant itself rotates, she only needs to stand in one place to take pictures in all directions. […] Since the restaurant staff only realize she is a tourist once she starts taking pictures, we begin measuring the time required once she takes her first picture.

Problem: Sphere Online Judge (SPOJ) – Problem CNEASY

Solution: Afterwards this problem is really easy, however I first made it too hard. The trick is pretty easy we are looking for the biggest distance between each consecutive degree. To check the difference between the highest and the lowest I appended (lowest + 360) to the list of degrees. The + 360 helps to calculate the distance more easily. Afterwards just select the biggest difference and calculate the minimum time.

from math import ceil

for i in xrange(0, int(raw_input())):
    n = int(raw_input())
    degrees = []
    for i in xrange(0, n):
        degrees.append(float(raw_input().split()[1]))

    degrees.sort()
    degrees.append(degrees[0] + 360)
    maxDegrees = max([(degrees[i] - degrees[i-1]) for i in xrange(1, n + 1)])

    print "%i" % (ceil ((360 - maxDegrees) * 12))