バイトジャンプ2020秋招アルゴリズム岡筆記試験(python)
全部で4つのプログラミング問題で、制限時間は120 minです.3つ作りました.
第一題.
明ちゃんは朝学校に行って目覚まし時計をN個注文しました.目覚まし時計が鳴った後、起きるか、次の目覚まし時計が鳴るのを待つかを選びました.授業時間と道中に時間がかかることが知られています.明ちゃんが一番遅くどの目覚まし時計の時間に起きますか.
入力: N個の目覚まし時計 時間(分) 授業時間何時何分 N行、各行が目覚まし時計の時 出力:一番遅い目覚まし時計の時
例:
入力:5 59 06 59 04 00 05 00 06 00 07 00 08 00
出力:06 00
考え方:
まず、授業時間-時間をかけて一番遅く起きる時間を得る.そして、すべての目覚まし時計を並べ替えた後、一番遅い目覚まし時計を二分で見つけます.
第二題
明ちゃんと紅ちゃんは暗号化方法を発明した.長さNの"0/1"文字列S(明文)に対してK回暗号化する.i回目の暗号化はi-1回右に移動します.その後、このK文字列に対して異を求めたり、最終的な密文を得たりします.例えば、S="1001010",K=4である.以下の1001010 ;1001010 \; \; 1001010 \; \; \; 1001010暗号文P="1110100110"は暗号文を書く復号アルゴリズムを要求し,明文を得る.
入力:1.2つの数.明文長N、暗号化回数K 2.密文
出力:明文[しゅつりょく:めいぶん]
例:
入力:7 4 1110100110出力:1001010
構想
まず異種の性質を理解する.A⨁B=C Abigoplus B=C A⨁B=Cの場合、B=A⨁C B=Abigoplus C B=A⨁Cとなる.3つの数に相当して2つの数が既知であれば、3番目の数を異ならせるか、求めることができます.2.任意の数が0と異なるか、それ自体を得る.暗号文Pの長さはN−K+1であることが知られている.そして、密文から分析を始める.例えば、上記の例では、明文は1001010、密文は1110100110である.では、密文の最後の1人は明文の最後の1人と3人の0異から得られた.では、密文の最後の一人である明文の最後の一人は、明文の最後の一人の後ろを得ることになります.次に密文の最下位2位は2つの0と明文の最下位2位と明文の最下位1位で得られた.すなわち0⨁0⨁S(N−2)⨁S(N−1)＝P(N＋K−3)0bigoplus 0bigoplus S(N−2)bigoplus S(N−1)＝P(N＋K−3)0⨁0⨁S(N−2)⨁S(N−1)＝P(N−1)＝P(N＋K−3)＝P(N＋K−3)は性質2から,S(N−2)S(N−1)＝P(N(N＋K−1)＝P(N＋K−−−1)＝P(N＋K−−−1)＝P(N＋K−−1)＝P(N＋K−3)S(N−2)bigoplus S(N−1)＝P(N＋K−3)S(N−2)⨁S(N−1)＝P(N＋K−3)は性質1から,S(N−2)＝P(N＋K−3)ÅS(N−1)S(N−1)S(N−2)＝P(N＋K−3)／bigoplus S(N−1)S(N−1)S(N−2)＝P(N＋K−3)ÅS(N−1)は同理であり,S(N−3)＝P(N＋K−4)＝P(N＋K−4)ÅS(N−1)ÅS(N−1)S(N−2)S(N−3)＝P(N＋K−4)／bigoplus S(N−1)(N−1)／bigoplus S(N−1)(N−1)／N(N−1)／N−1)／bigopluBigoplus S(N−2)S(N−3)＝P(N＋K−4)⨁S(N−1)⨁S(N−2)
後ろから見ると、つまり明文の数は、その後ろの明文異または後、さらに異または上の対応位置の密文に等しい.しかし、この数以降の桁数はK-1位を超えないことが多い.例えば、上述の例S(N−5)＝P(N＋K−6)−S(N−2)−S(N−3)−S(N−3)−S(N−4))S(N−5)＝P(N＋K−6)bigoplus S(N−2)bigoplus S(N−3)bigoplus S(N−3)bigoplus S(N−4)S(N−5)＝P(N＋K−6)S(N−2)−S(N−3)S(N−3)／bigoplus S(N−3)S(N−5)＝P(N−5)＝P(N−5)＝P(N−K−6)−S(N−2)−S(N−3)N−4))ここではS(N−1)S(N−1)S(N−1)S(N−1)を切り捨てた.
このような方法によれば、平均1文字ずつ復号するにはK回の異文化または操作が必要であり、合計N文字が復号される.従って時間的複雑度はO(KN)O(KN)O(KN)である.しかし、これは50%のcaseしか通過しなかった.時間が複雑すぎてタイムアウトになった.
S(N−5)＝P(N＋K−6)ÅS(N−2)ÅS(N−5)＝P(N＋K−6)ÅS(N−2)ÅS(N−3)ÅS(N−3)ÅS(N−4)S(N−5)＝P(N＋K−6)bigoplus S(N−2)bigoplus S(N−3)bigoplus S(N−4)S(N−5)＝P(N＋K−6)ÅS(N−2)ÅS(N−3)ÅS(N−S(N−3)ÅS(N−S(N−−−3)ÅS(N−−−−−−N−−3)ÅS(N−−−4)S(N−6)＝P(N＋K−7)ÅS(N−3)ÅS(N−4)ÅS(N−5)S(N−6)＝P(N＋K−7)／bigoplus S(N−3)bigoplus S(N−4)bigoplus S(N−5)S(N−6)=P(N+K−7)−S(N−3)−S(N−4)−S(N−4)−S(N−5)等式の右側をA,Bの2つの部分に分け,Aは対応する位置の密文であり,もう1つの部分Bは前K−1の明文の異和である.毎回B部分はK-1回計算する必要はなく,前回のB部分で明文異または明文を1つ削除してから新異または明文を1つ削除すればよいことが分かった.しかしどのように1つの異種を取り除くかというと,性質1が見られ,S(N−6)の式の前回のB部分B′に対してB′=S(N−2)⨁S(N−3)⨁S(N−4)B′=S(N−2)bigoplus S(N−3)bigoplus S(N−4)B′=S(N−2)⨁S(N−3)⨁S(N−4)であり,一方,今回のB部B=B′⨁S(N−2)⨁S(N−5)B=B′bigoplus S(N−2)bigoplus S(N−5)B=B′⨁S(N−2)⨁S(N−5)である.毎回2回だけ異或をしてB部分を得たのに相当し、再びA部分を異或して今回の結果を得た.すなわち,復号化には最大3回まで異種または異種が必要である.逆数K−1ビット前の暗号文については,B’の一部を削除する必要はない.
第三題
社長は従業員に年末ボーナスを出して、従業員は一列に座っています.条件:1.従業員1人当たり少なくとも100元の年末ボーナス.2.隣接する従業員は互いに相手の年末ボーナスを知ることができて、会社の年が大きいのは会社の年より少なくとも100元多くて、従業員は意見がありません.質問:ボスはどのように年末ボーナスを出して以上の条件を満たして、しかも総和が最も少ないですか.
入力:1.N人の従業員2.各従業員の来社年.出力:従業員1人あたりの年末ボーナス
例1
入力:5 7 3 9 6 2出力:200 100 100 300 200 100
例2
入力:4 1 1 1 1出力:100 100 100 100 100
構想
従業員一人一人に対して、彼の左右が彼より小さい従業員の数を連続して見なければならない.次に、左右の最大値をとります.では、年末ボーナスはこの値*100に等しい.
第一題.
明ちゃんは朝学校に行って目覚まし時計をN個注文しました.目覚まし時計が鳴った後、起きるか、次の目覚まし時計が鳴るのを待つかを選びました.授業時間と道中に時間がかかることが知られています.明ちゃんが一番遅くどの目覚まし時計の時間に起きますか.
入力:
例:
入力:5 59 06 59 04 00 05 00 06 00 07 00 08 00
出力:06 00
考え方:
まず、授業時間-時間をかけて一番遅く起きる時間を得る.そして、すべての目覚まし時計を並べ替えた後、一番遅い目覚まし時計を二分で見つけます.
n = int(input().strip()) #
clocks = []
for i in range(n):
clock = [int(x) for x in input().strip().split(" ")]
clocks.append(clock)
time = int(input().strip()) #
deadline = [int(x) for x in input().strip().split(" ")] #
# - =
h = deadline[0]
m = deadline[1] - time
while m < 0:
h -= 1
m += 60
deadline = [h, m]
clocks.sort(key=lambda x: (x[0], x[1]))
def less(a, b):
if a[0] == b[0]:
return a[1] < b[1]
else:
return a[0] < b[0]
def greater(a, b):
if a[0] == b[0]:
return a[1] > b[1]
else:
return a[0] > b[0]
def print_res(num):
print(str(num[0]) + " " + str(num[1]))
#
low, high = 0, n
while low <= high:
mid = (low + high) // 2
if less(clocks[mid], deadline): # deadline
if mid < n - 1: #
if greater(clocks[mid + 1], deadline): # deadline
print_res(clocks[mid])
break
else:
low = mid + 1
else: #
print_res(clocks[mid])
break
elif greater(clocks[mid], deadline): # deadline
high = mid - 1
if high <= 0:
print_res(clocks[0])
break
else: # deadline，
print_res(clocks[mid])
break
第二題
明ちゃんと紅ちゃんは暗号化方法を発明した.長さNの"0/1"文字列S(明文)に対してK回暗号化する.i回目の暗号化はi-1回右に移動します.その後、このK文字列に対して異を求めたり、最終的な密文を得たりします.例えば、S="1001010",K=4である.以下の1001010 ;1001010 \; \; 1001010 \; \; \; 1001010暗号文P="1110100110"は暗号文を書く復号アルゴリズムを要求し,明文を得る.
入力:1.2つの数.明文長N、暗号化回数K 2.密文
出力:明文[しゅつりょく:めいぶん]
例:
入力:7 4 1110100110出力:1001010
構想
まず異種の性質を理解する.A⨁B=C Abigoplus B=C A⨁B=Cの場合、B=A⨁C B=Abigoplus C B=A⨁Cとなる.3つの数に相当して2つの数が既知であれば、3番目の数を異ならせるか、求めることができます.2.任意の数が0と異なるか、それ自体を得る.暗号文Pの長さはN−K+1であることが知られている.そして、密文から分析を始める.例えば、上記の例では、明文は1001010、密文は1110100110である.では、密文の最後の1人は明文の最後の1人と3人の0異から得られた.では、密文の最後の一人である明文の最後の一人は、明文の最後の一人の後ろを得ることになります.次に密文の最下位2位は2つの0と明文の最下位2位と明文の最下位1位で得られた.すなわち0⨁0⨁S(N−2)⨁S(N−1)＝P(N＋K−3)0bigoplus 0bigoplus S(N−2)bigoplus S(N−1)＝P(N＋K−3)0⨁0⨁S(N−2)⨁S(N−1)＝P(N−1)＝P(N＋K−3)＝P(N＋K−3)は性質2から,S(N−2)S(N−1)＝P(N(N＋K−1)＝P(N＋K−−−1)＝P(N＋K−−−1)＝P(N＋K−−1)＝P(N＋K−3)S(N−2)bigoplus S(N−1)＝P(N＋K−3)S(N−2)⨁S(N−1)＝P(N＋K−3)は性質1から,S(N−2)＝P(N＋K−3)ÅS(N−1)S(N−1)S(N−2)＝P(N＋K−3)／bigoplus S(N−1)S(N−1)S(N−2)＝P(N＋K−3)ÅS(N−1)は同理であり,S(N−3)＝P(N＋K−4)＝P(N＋K−4)ÅS(N−1)ÅS(N−1)S(N−2)S(N−3)＝P(N＋K−4)／bigoplus S(N−1)(N−1)／bigoplus S(N−1)(N−1)／N(N−1)／N−1)／bigopluBigoplus S(N−2)S(N−3)＝P(N＋K−4)⨁S(N−1)⨁S(N−2)
後ろから見ると、つまり明文の数は、その後ろの明文異または後、さらに異または上の対応位置の密文に等しい.しかし、この数以降の桁数はK-1位を超えないことが多い.例えば、上述の例S(N−5)＝P(N＋K−6)−S(N−2)−S(N−3)−S(N−3)−S(N−4))S(N−5)＝P(N＋K−6)bigoplus S(N−2)bigoplus S(N−3)bigoplus S(N−3)bigoplus S(N−4)S(N−5)＝P(N＋K−6)S(N−2)−S(N−3)S(N−3)／bigoplus S(N−3)S(N−5)＝P(N−5)＝P(N−5)＝P(N−K−6)−S(N−2)−S(N−3)N−4))ここではS(N−1)S(N−1)S(N−1)S(N−1)を切り捨てた.
このような方法によれば、平均1文字ずつ復号するにはK回の異文化または操作が必要であり、合計N文字が復号される.従って時間的複雑度はO(KN)O(KN)O(KN)である.しかし、これは50%のcaseしか通過しなかった.時間が複雑すぎてタイムアウトになった.
S(N−5)＝P(N＋K−6)ÅS(N−2)ÅS(N−5)＝P(N＋K−6)ÅS(N−2)ÅS(N−3)ÅS(N−3)ÅS(N−4)S(N−5)＝P(N＋K−6)bigoplus S(N−2)bigoplus S(N−3)bigoplus S(N−4)S(N−5)＝P(N＋K−6)ÅS(N−2)ÅS(N−3)ÅS(N−S(N−3)ÅS(N−S(N−−−3)ÅS(N−−−−−−N−−3)ÅS(N−−−4)S(N−6)＝P(N＋K−7)ÅS(N−3)ÅS(N−4)ÅS(N−5)S(N−6)＝P(N＋K−7)／bigoplus S(N−3)bigoplus S(N−4)bigoplus S(N−5)S(N−6)=P(N+K−7)−S(N−3)−S(N−4)−S(N−4)−S(N−5)等式の右側をA,Bの2つの部分に分け,Aは対応する位置の密文であり,もう1つの部分Bは前K−1の明文の異和である.毎回B部分はK-1回計算する必要はなく,前回のB部分で明文異または明文を1つ削除してから新異または明文を1つ削除すればよいことが分かった.しかしどのように1つの異種を取り除くかというと,性質1が見られ,S(N−6)の式の前回のB部分B′に対してB′=S(N−2)⨁S(N−3)⨁S(N−4)B′=S(N−2)bigoplus S(N−3)bigoplus S(N−4)B′=S(N−2)⨁S(N−3)⨁S(N−4)であり,一方,今回のB部B=B′⨁S(N−2)⨁S(N−5)B=B′bigoplus S(N−2)bigoplus S(N−5)B=B′⨁S(N−2)⨁S(N−5)である.毎回2回だけ異或をしてB部分を得たのに相当し、再びA部分を異或して今回の結果を得た.すなわち,復号化には最大3回まで異種または異種が必要である.逆数K−1ビット前の暗号文については,B’の一部を削除する必要はない.
def xor(a, b):
if a == b:
return "0"
else:
return "1"
N, K = [int(x) for x in input().strip().split(" ")]
P = input().strip()
S = ""
last_B = "0"
for i in range(K-1, N+K-1)[::-1]:
num = xor(last_B, P[i])
S = num + S
if len(S) >= K:
last_B = xor(last_B, S[K - 1])
last_B = xor(last_B, num)
print(S)
第三題
社長は従業員に年末ボーナスを出して、従業員は一列に座っています.条件:1.従業員1人当たり少なくとも100元の年末ボーナス.2.隣接する従業員は互いに相手の年末ボーナスを知ることができて、会社の年が大きいのは会社の年より少なくとも100元多くて、従業員は意見がありません.質問:ボスはどのように年末ボーナスを出して以上の条件を満たして、しかも総和が最も少ないですか.
入力:1.N人の従業員2.各従業員の来社年.出力:従業員1人あたりの年末ボーナス
例1
入力:5 7 3 9 6 2出力:200 100 100 300 200 100
例2
入力:4 1 1 1 1出力:100 100 100 100 100
構想
従業員一人一人に対して、彼の左右が彼より小さい従業員の数を連続して見なければならない.次に、左右の最大値をとります.では、年末ボーナスはこの値*100に等しい.
N = int(input())
years = [int(x) for x in input().strip().split(" ")]
left = [1] * N #
right = [1] * N #
for i in range(1, N):
if years[i] > years[i - 1]:
left[i] += left[i-1]
for i in range(N-1)[::-1]:
if years[i] > years[i + 1]:
right[i] += right[i+1]
for i in range(N):
years[i] = str(max(left[i], right[i]) * 100)
print(" ".join(years))