in SPOJ

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)

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.