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: 8060. Cookies Piles

The kids in my son’s kindergarten made Christmas cookies with their teacher, and piled them up in columns. They then arranged the columns so that the tops of the columns, going from shortest to tallest, were in a nice straight ramp. The cookies were all of uniform size. Given that there were A cookies in the shortest pile, that the difference in height between any two adjacent piles was D cookies, and that there were N piles, can you write a program to figure out how many cookies there were in total?

Problem: Sphere Online Judge (SPOJ) – Problem AMR10F

Solution: This is quite a nice and simple problem. The easiest solution is just to write a loop to calculate the amount of cookies. If you think one step further you can write a general formula for calculating this.
Let’s imagine three piles of cookies.

At the rightmost there are A cookies. The middle one got A + D cookies and the leftmost got A + 2D cookies. If we generalize this we get: $\text{allCookies} = (A + 2 * D) + (A + 1 * D) + (A + 0 * D)$ which can be written as $\sum_{i=0}^{N-1} (A + iD)$ .
And thus can be simplified:

$\sum_{i=0}^{N-1} A + D \sum_{i=0}^{N-1} i = NA + D\frac{(N-1)N}{2}.$

T = int(raw_input())

for i in xrange(0, T):
    N, A, D = raw_input().split()
    
    N = int(N)
    A = int(A)
    D = int(D)

    print (N * A) + D * ( (N - 1) * N ) / 2

SPOJ: 4301. Tables

Byteman works as a carpenter. He has just received an order for s pine-wood tables. Although he has plenty of pine-wood boards in his workshop, he has just run out of screws. Therefore he needs to walk to the warehouse and bring back some boxes with screws. What is the minimum number of boxes that he needs to bring in order to have enough screws to make the tables?

Problem: Sphere Online Judge (SPOJ) – Problem AE1B

Solution: That’s a nice application for an greedy algorithm, i.e. you grab the largest values successively. This yields the optimal solution in this case because we don’t need to find exactly X screws. It’s sufficient to find at least X screws.

inp1 = raw_input()
inp2 = raw_input()


numBoxes, screwsPerTable, tables = inp1.split()

boxes = inp2.split()

numBoxes = int(numBoxes)
screwsPerTable = int(screwsPerTable)
tables = int(tables)
boxes = map(int, boxes)

boxes.sort()
boxes.reverse()

needed = tables * screwsPerTable

i = 0
while needed > 0:
    needed -= boxes[i]
    i += 1

print i

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