Chaotic Sequence

Computer Science Level 4

10 students are standing in a row. From left to right, they are labeled as 1 to 10. When the teacher left for the bathroom, they start to switch positions. When the teacher come back on the k th k^\text{th} minute, the queue becomes the k th k^\text{th} lexicography order.

The teacher needs your help to answer 2 types of queries:

  • K L N : On the k th k^\text{th} minute, what is the label of the n th n^\text{th} person from the left?
  • K P N : On the k th k^\text{th} minute, what is the position of the person labeled n n ?

This file contains 1000 queries. What is the sum of all output?

Sample Input 

1
2
3
4
5
6
7
8
 
1 L 1
1 L 2
1 L 10
2 L 10
1 P 1
1 P 2
1 P 10
2 P 9

Sample Output 

1
2
3
4
5
6
7
8
 
1
2
10
9
1
2
10
10

For this example, the answer is 45.


The answer is 5582.

View wiki
Christopher Boo by Christopher Boo , 24, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Christopher Boo
Jul 17, 2016

The hardest part is to get the k th k^{\text{th}} lexicographic order. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
def perm(k):
    L = [1,2,3,4,5,6,7,8,9,10]
    P = []
    for j in range(10):
        t = 0
        while k > factorial(9-j):
            t += 1
            k -= factorial(9-j)
        P.append(L[t])
        del L[t]
    return P

Why and how does this work? The first person will remain at the first position for 9 ! 9! permutations, the second will remain for 8 ! 8! permutations and so on. Using this logic, we can determine the position one by one. After that you just have to find the label of the n n -th person or the position of the person labeled n n .

2 Helpful 0 Interesting 0 Brilliant 0 Confused

For the sake of completeness, here is the full code: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
import urllib2

factorial = lambda n: reduce(lambda x, y: x*y, range(1,n+1),1)
def perm(k):
    L = [1,2,3,4,5,6,7,8,9,10]
    P = []
    for j in range(10):
        t = 0
        while k > factorial(9-j):
            t += 1
            k -= factorial(9-j)
        P.append(L[t])
        del L[t]
    return P

data = urllib2.urlopen("http://pastebin.com/raw/JrBL9Rau").read().split("\n")

ans = []
for line in data:
    line = line.split()
    command = line[1]
    K = int(line[0])
    N = int(line[2])
    order = perm(K)
    if command == 'L':
        ans.append(order[N-1])
    elif command == 'P':
        ans.append(order.index(N)+1)

print sum(ans)

Agnishom Chattopadhyay - 4 years, 11 months ago
You Kad
Jul 29, 2016 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
from urllib.request import urlopen
from re import search

Permutations = []
def next_permutation(n):
    p = list(range(1,n+1))
    yield p
    test = True
    while test:
        i = n-1
        while i > 0 and p[i] <= p[i-1]:
            i-=1
        if i == 0:
            test = False
        else:
            j = n-1
            while j > i-1 and p[j] <= p[i-1]:
                j -= 1
            p[j], p[i-1] = p[i-1], p[j]
            p[i:] = p[-1:i-1:-1]
            yield p
Sum = 0
Gen = next_permutation(10)


with urlopen('http://pastebin.com/raw/JrBL9Rau') as f:
    for line in f:
        parameters = search("(\d+) (L|P) (\d+)", str(line))
        K, letter, N = int(parameters.group(1)), parameters.group(2), int(parameters.group(3))
        n = len(Permutations)
        if K > n:
            for _ in range(n, K):
                Permutations.append(list(next(Gen)))
        p = Permutations[K-1]
        if letter == 'L':
            Sum += p[N-1]
        elif letter == 'P':
            Sum += p.index(N)+1
    print(Sum)

0 Helpful 0 Interesting 0 Brilliant 1 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...