Google Code Jam 2019 Qualification
Google Code JamとはGoogleが主催するプログラミングコンテストです。先日、予選が開催されました。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705
Question1 Foregone Solution
問題文
整数Nが与えられます。A+B=Nを満たす整数A,Bのうち、4を含まないものの1例を示してください。
解答例
nを2で割る。nが奇数ならリストに格納した後のaに+1する。
割った値a,bを1桁ずつに分解し、4が含まれていたらその桁の値をaは+1,bは-1とする。
t = int(input())
n = []
a = []
b = []
for i in range(t):
n.append(int(input()))
for i in range(t):
if n[i]%2 == 0: #If n is even number
d = 0
x = int(n[i]/2)
y = x
num = []
while x != 0: #nを各桁に分割し、リストに格納する
num.append(int(x%10))
x /= 10
for j in range(len(num)): #もし桁が4であればその桁を+1する
if 4 == num[j]:
d += 10**j
a.append(y+d)
b.append(y-d)
else: #If n is odd number add 1 to 'a' last
d = 0
x = int(n[i]/2)
y = x
num = []
while x != 0:
num.append(int(x%10))
x /= 10
for j in range(len(num)):
if 4 == num[j]:
d += 10**j
a.append(y+d+1)
b.append(y-d)
for i in range(t):
print('Case #{0}: {1} {2}'.format(i+1, a[i], b[i]))
input:
4
2345
4444
888
9876
output:
Case # 1 : 1173 1172
Case # 2 : 2222 2222
Case # 3 : 555 333
Case # 4 : 5938 3938
Question2 You Can Go Your Own Way
Nが与えられます。N*Nマス上を移動するYouとLydiaがいます。Lydiaが進む方向(SまたはE)が与えられます。Lydiaと同じマスからマスへの移動をすることなしに、Youがスタートの北西からゴールの南東のブロックまで進む1例を示してください。
解答例
・YouとLydiaが同じマスにいたらLydiaが進まない方角に進む。(LydiaがEならYouはSに進む)
・YouとLydiaが異なるマスにいたらYouはゴールの南東へ近づく方向へ進む。SとEのうち、現在いる位置からゴールまで遠い方の方角へ進む。
分かりづらいので具体例↓
n=5のとき S=4, E=4となればよい。
異なるマスにいるときにS=1, E=3であるときSに進む。
t = int(input())
n = []
p = []
q = []
ans = [[] for i in range(t)]
for i in range(t):
n.append(int(input()))
p.append(input())
for i in range(t):
q.append(list(p[i]))
ans = [[] for i in range(t)]
for i in range(t):
ms = 0 #Youの座標を(ms, me) Lydiaの座標を(os, oe)であらわす
me = 0
os = 0
oe = 0
for j in range(n[i]+n[i]-2): #(ms, me) = (n*2-2, n*2-2)を満たすまで繰り返す
if ms == os and me == ms:
if q[i][j] == 'S':
ans[i].append('E')
me += 1
else:
ans[i].append('S')
ms += 1
else:
if ms > me:
ans[i].append('E')
me += 1
else:
ans[i].append('S')
ms += 1
if q[i][j] == 'S':
os += 1
else:
oe += 1
anss = []
for i in range(t):
s = ''
for j in range(len(ans[i])):
s += ans[i][j]
anss.append(s)
for i in range(t):
print('Case #{0}: {1}'.format(i+1, anss[i]))
input:
4
2
SE
5
EESSSESE
8
SESESESESESESE
10
EEESSSESESESSESEES
output:
Case # 0 : ES
Case # 1 : SESEESES
Case # 2 : ESESESESESESES
Case # 3 : SESESESESESEESESSE
Question3,4は解答していません。問題文の解釈がおおまかなので、間違っていたらコメント欄にて報告してください。