[PYTHON] Graduate School of Information Science and Technology, The University of Tokyo, Department of Creative Informatics, Winter 2015 Programming Exam

This is an example of the answer to the 2015 winter hospital exam.

• The content of the description is personally solved by the author and does not guarantee the correct answer, and is not related to the University of Tokyo or the organization involved in providing the content of this examination.

Question theme

--Memoization recursion

Problem statement

• If the University of Tokyo points out, the problem statement will be deleted.

Functions, classes

def func1(n):
    Max = 10000    
    memo = [0 for _ in range(Max)]
    memo[0] = 1
    mod = 1<<24
    for i in range(1, Max):
        memo[i] = (161 * memo[i-1]+2457) % mod
    return memo[n]

def func1_v2(n):
    Max = 1000000+7
    memo = [0 for _ in range(Max)]
    memo[0] = 1
    mod = 1<<24
    for i in range(1, Max):
        memo[i] = (161 * memo[i-1]+2457) % mod
    return memo[n]

def make_func2_memo(memo_size=10000):
    memo = [0 for _ in range(memo_size)]
    memo[0] = 1
    mod = 1<<26
    for i in range(1, len(memo)):
        memo[i] = (1103515245 * memo[i-1]+12345) % mod
    return memo

def get_min_k(memo_size=1000007):
    memo = make_func2_memo(memo_size)
    for k in range(1, memo_size):
        if memo[0] == memo[k]:
            return k
    return -1

(1)

def solve1():
    n = 100
    print(func1(n))

(2)

def solve2():
    Max = 100
    memo = [0 for _ in range(Max)]
    memo[0] = 1
    mod = 1<<24
    # f(0) =Odd at 1
    cnt = 0
    for i in range(1, Max):
        memo[i] = (161 * memo[i-1]+2457) % mod
        if memo[i] % 2 == 0:
            cnt += 1
    print(cnt)

(3)

def solve3():
    Max = 100
    memo = [0 for _ in range(Max)]
    memo[0] = 1
    mod = 1<<24
    # f(0) = 1, i: even
    cnt = 0
    for i in range(1, Max):
        memo[i] = (161 * memo[i-1]+2457) % mod
        if i % 2 == 1 and memo[i] % 2 == 0:
            cnt += 1
    print(cnt)

(4)

def solve4():
    n = 1000000
    print(func1_v2(n))

(5)

def solve5():
    memo = make_func2_memo()
    print('g(2): ', memo[2])
    print('g(3): ', memo[3]) 

(6)

def solve6():
    n = 1
    mod = 1<<26
    cur = 1
    k = 1
    while True:                
        cur = (1103515245 * cur+12345) % mod
        if cur == 1:
            break
        k += 1
        if k > 100000000:
            k = -1
            break
    return k 

(7) When g (n) = g (n + k) and any n holds h(n) = g(n) mod 2^10 h(n+k) = g(n+k) mod 2^10 Therefore, h (n) = h (n + k) holds for any n. Therefore, the search range of k is k obtained in (6), and if this is g_k, it is narrowed down to the range of k <= g_k. Also, when h (m) = h (m + k) holds for a certain m (non-negative integer), if h (m) = a, then h (m + 1) = (1103515245 * a + 12345) mod 2 ^ 26 Since mod 2 ^ 10 and h (m + k) = a, h (m + k + 1) = h (m + 1). That is, when h (m) = h (m + k) holds for a certain non-negative integer m, h (M) = h (M + k) holds for any non-negative integer M> = m. In other words, to satisfy the subject, we need to search for k such that h (0) = h (k), which is h (n) = h (n + k) for any nonnegative integer n.

def solve7():
    max_k = 67108864
    g_mod = 1<<26
    h_mod = 1<<10
    g_cur = 1
    h_cur = 1
    for k in range(1, max_k+1):
        g_cur = (1103515245 * g_cur+12345) % g_mod
        h_cur = g_cur % h_mod
#         print(g_cur, h_cur)
        if h_cur == 1:
            return k        
    return -1

Impressions

――Hmm, if I misunderstood the problem, I think this year is too easy ... -I thought it would be bad if I couldn't make it in time for the linear search in (6), but since the search was completed properly in 10 ^ 8 or less, there was no particular ingenuity, and all the questions were solved in about 45 minutes. ――The part that is easy to make mistakes is the pigeonhole principle! You might think that the search in (6) can be suppressed by k <= 2 ^ 26 ... (Since it is an arbitrary non-negative integer, the search is necessary until g (k) = 1).