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))

SPOJ: 1030. Triple Fat Ladies

Pattern Matchers have been designed for various sorts of patterns. Mr. HKP likes to observe patterns in numbers. After completing his extensive research on the squares of numbers, he has moved on to cubes. Now he wants to know all numbers whose cube ends in 888.

Given a number k, help Mr. HKP find the kth number (indexed from 1) whose cube ends in 888.

Problem: Sphere Online Judge (SPOJ) – Problem EIGHTS

Solution: Yeah, an other number problem! And again I just looked for patterns.

for i in xrange(0, 4444):
     if str(i**3)[-3:] == "888":
         print i, i**3

Which gets us:

192 7077888
442 86350888
692 331373888
942 835896888
1192 1693669888
1442 2998442888
1692 4843965888
1942 7323988888
2192 10532261888
2442 14562534888
2692 19508557888
2942 25464080888
3192 32522853888
3442 40778626888
3692 50325149888
3942 61256172888
4192 73665445888
4442 87646718888

EDIT: Thanks to the anonymous person who found a simple connection between the numbers but can’t properly communicate. You can find the k-th number with this simple formula: $192 + 250(k-1)$

You should see that each number ends in 2. If you look closer you see that the last two digits are 42 if i is even, and 92 if i is odd. Let’s look at the other digits. We get:

If you do some basic arithmetics you see that:

1
4  =  1 + 3
6  =  4 + 2
9  =  6 + 3
11 =  9 + 2
14 = 11 + 3
16 = 14 + 2

You can calculate your first digits either recursively or search for a function. This takes probably some time, so I looked this sequence up. OEIS gives us the formular: a(n) = floor((5n-2)/2) for n > 2

from math import floor

def kthnumber(k):
    if k > 2:
        num = "%i" % int((floor( (5 * (k - 1) + 3) / 2.0 )))
    else:
        if k == 1:
            num = "1"
        elif k == 2:
            num = "4"

    if k % 2 == 0:
        num += "42"
    else:
        num += "92"

    return num



t = int(raw_input())
for c in xrange(0, t):
    print kthnumber(int(raw_input()))