【プログラミング問題】テンセント2017秋募集技術類試験問題

4つのプログラミング問題、120 min、python実現、
第一題
1つの符号化の符号化範囲がa~yの25文字であり、1ビットから4ビットの符号化であると仮定し、この符号化を辞書順に並べ替えると、a,aaa,aaaaa,aaab,aaac,...,b,ba,baa,baaaa,baab,baac,...,yyyyw,yyyyx,yyyyyのうちaのIndexは0,aaaのIndexは1,aaaのIndexは2となる配列が形成される.関数を記述する、入力は任意の符号化であり、この符号化に対応するIndexを出力する.
説明を入力:

 , 100.

出力の説明:

 index

入力例1:

baca

出力例1:

16331

d = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8, 'i':9, 'j':10, 'k':11, 'l':12, 'm':13, 'n':14, 'o':15, 'p':16, 'q':17, 'r':18, 's':19, 't':20, 'u':21, 'v':22, 'w':23, 'x':24, 'y':25}

s = raw_input()
res = 0
nums = [1] + [0] * 3
for i in range(1, 4):
	nums[i] = nums[i-1] * 25 + 1
# print(nums)
for i in range(len(s)):
	res += nums[4-i-1] * (d[s[i]] - 1) + 1
print(res - 1)

第二題
ゲームには様々なタスクがあり、そのうち1つのタスクプレイヤーは1回しかできない.これらのタスクは全部で1024個あり、タスクID範囲[1024].32個のunsigned intタイプで1024個のタスクが完了したかどうかを記録してください.初期状態はすべて未完了です.2つのパラメータを入力し、いずれもタスクIDであり、最初のIDを設定する必要があるタスクはすでに完了している.2番目のIDのタスクが完了しているかどうかを確認します.2番目のIDのタスクが出力1を完了した場合、出力0が完了していない場合、パラメータを出力します.第1または第2のIDが［1024］の範囲外である場合、出力−1.
説明を入力:

 , ID.

出力の説明:

入力例1:

1024 1024

出力例1:

1

id1, id2 = map(int, raw_input().split())
if id1 < 1 or id1 > 1024:
    print(-1)
elif id2 < 1 or id2 > 1024:
    print(-1)
else:
    todo = [0] * 32
    if id1%32 == 0:
        a, b = id1/32 - 1, 31
    else:
        a, b = id1/32, id1%32 - 1
    todo[a] = 2**31
    while b:
        todo[a] = todo[a] >> 1
        b -= 1
    if id2%32 == 0:
        c, d = id2/32 - 1, 31
    else:
        c, d = id2/32, id2%32 - 1
    while d:
        todo[c] = todo[c] << 1
        d -= 1
    if todo[c] == 2**31:
        print(1)
    else:
        print(0)

第三題
正の整数を与え、記述プログラムは、入力された正の整数に等しい質量数の和を計算し、結果を出力する.入力値は1000未満です.例えば、入力が10の場合、プログラムは結果を2に出力すべきである.(合計2対の質量数の和は10であり,それぞれ(5,5),(3,7)である)
説明を入力:

 n,(3 ≤ n < 1000)

出力の説明:

入力例1:

10

出力例1:

2

def iszs(n):
	for i in range(2, int(n**0.5)+2):
		if n%i == 0:
			return False
	return True
 
n = input()
zs = []
for i in range(1, n):
	if i in zs:
		continue
	if iszs(i):
		zs.extend([i])
i, j = 0, len(zs) - 1
res = 0
while i <= j:
	tmp = zs[i] + zs[j]
	if tmp == n:
		res += 1
		i += 1
		j -= 1
	elif tmp < n:
		i += 1
	else:
		j -= 1
print(res)

第四題
geohash符号化:geohashは2次元の緯度を文字列に変換するのによく用いられ、2つのステップに分けられる:第1のステップは緯度のバイナリ符号化であり、第2のステップはbase 32トランスコードである.この問題は緯度のバイナリ符号化を考察する:アルゴリズムは緯度[-90,90]に対して二分法によって無限に近似する(所望の精度に依存して、本題の精度は6である).なお,本題では二分法近似の過程で下向きに整列するだけで二分を行い,二分中間値に対して右区間に属する.アルゴリズムの例は以下の通りである:緯度80に対してバイナリ符号化過程を行う:1)区間[-90,90]は[-90,0),[0,90]に二分され、左右区間となり、80が右区間と決定され、1と表記される.2)前ステップの右区間[0,90]に対して[0,45],[45,90]に二分し,[45,90]を行い,80が右区間であることを決定し,1と表記する.3)[45,90]に対して[45,67],[67,90]の2分割を行い、80を右区間とし、1としてマークすることができる.4)[67,90]に対して[67,78],[78,90]の2分割を行い、80を右区間とし、1としてマークすることができる.5)[78,90]に対して二分[78,84),[84,90]を行い、80を左区間とし、0と表記することができる.6)[78,84)に対して二分[78,81],[81,84)を行い、80を左区間とし、0と表記することができる.
説明を入力:

 n,(-90 ≤ n ≤ 90)

出力の説明:

入力例1:

80

出力例1:

111100

n = input()
ef = [i for i in range(-90, 91)]
i, j = 0, len(ef) - 1
res = ''
while i < j - 1 and len(res) < 6:
	mid = (i + j) / 2
	if ef[mid] <= n:
		res += '1'
		i = mid
	else:
		res += '0'
		j = mid
print(res)

第四題は90%しか過ぎていないので、少し夢中になって、心身ともに苦労して、鉢鉢鶏を食べに行ってリラックスして、ふん!