Facebook Hacker Cup 2019 Qualification Round

1_leapfrog_ch1.py

# coding: utf-8

"""
https://www.facebook.com/hackercup/problem/656203948152907/

βカエルの数をbとする。
b=N-1のとき、葉Nが空いていないので不可。
bを小さくすることを考えると、1個おきに並ぶのが最善で、2*b=N-1。
"""

T = input()
for i in range(T):
  L = raw_input()
  N = len(L)
  b = L.count("B")
  ans = "Y" if b*2>=N-1 and b<N-1 else "N"
  print "Case #%s: %s" % (i+1, ans)

2_leapfrog_ch2.py

# coding: utf-8

"""
https://www.facebook.com/hackercup/problem/2426282194266338/

βカエルの数をbとする。
b=N-1のとき、葉Nが空いていないので不可。
b=0のとき、ジャンプすることができないので不可。
b=1のとき、N=3ならば可能で、それ以外は不可。
それ以外の場合はCh. 1と異なり、以下のようにして移動できるので可能。
  ABB........
  AB.B.......
  .B.BA......
  ..BBA......
  .ABB.......
"""

T = input()
for i in range(T):
  L = raw_input()
  N = len(L)
  b = L.count("B")
  if b>=N-1:
    ans = "N"
  elif b==0:
    ans = "N"
  elif b==1 and N==3:
    ans = "Y"
  elif b==1:
    ans = "N"
  else:
    ans = "Y"
  print "Case #%s: %s" % (i+1, ans)

3_mr_x.py

# coding: utf-8

"""
https://www.facebook.com/hackercup/problem/589264531559040/

式が、変数もしくは定数1文字ならば、1文字を定数に書き換えれば条件を満たせる。
式が演算子を含む場合も、最後に計算する演算子1文字を書き換えれば条件を満たせる。
最後に計算する演算子の右辺と左辺を考え、両方が変数ならば演算子を^に、
少なくとも一方が0ならば&に、少なくとも一方が1ならば|にする。
(x^x), (x|1), (x&0)はいずれも条件を満たす。
与えられた式が条件を満たすかを判定して、答えが0か1かを決める。
"""

T = input()
for i in range(T):
  E = raw_input()
  if (eval(E.replace("x", "0").replace("X", "1"))==
      eval(E.replace("x", "1").replace("X", "0"))):
    ans = 0
  else:
    ans = 1
  print "Case #%s: %s" % (i+1, ans)

4_trees_as_a_service.py

# coding: utf-8

"""
https://www.facebook.com/hackercup/problem/330920680938986/

不正解

葉から根に向かって木を構築していく。
以下の手順を繰り返す。
1. Zi≠vか、Zi=vならばXiもYiもすでに使用済みの頂点vを探す。
   そのようなvが存在しないならば、ループが存在するということで不可。
2. Zi=vとなるiについて、XiとYiを含む部分木の根に辺を張る。
   このとき、XiとYiが同じ部分木に含まれているならば、Ziが最小共通祖先にならないので不可。
この手順で木が構築できるならば、その木は制約を満たす。
手順1で候補となるvは独立しているので、選ぶ順序で結果が変わることはなく、
この手順で構築できないならば制約は満たせない。
"""

def solve(N, M, X, Y, Z):
  for i in range(M):
    X[i] -= 1
    Y[i] -= 1
    Z[i] -= 1

  U = [False]*N
  C = [[v] for v in range(N)]
  P = [-1]*N

  for _ in range(N):
    for v in range(N):
      if not U[v]:
        ok = True
        for i in range(M):
          if Z[i]==v and (X[i]!=Z[i] and not U[X[i]] or Y[i]!=Z[i] and not U[Y[i]]):
            ok = False
        if ok:
          break
    else:
      return "Impossible"
    for i in range(M):
      if Z[i]==v and X[i]!=Z[i] and Y[i]!=Z[i]:
        for t in range(N):
          if X[i] in C[t] and Y[i] in C[t]:
            return "Impossible"
    for i in range(M):
      if Z[i]==v:
        for xy in [X[i], Y[i]]:
          if xy!=Z[i]:
            for t in range(N):
              if t!=v and xy in C[t]:
                P[t] = v
                C[v] += C[t]
                C[t] = []
    U[v] = True
  root = -1
  for i in range(N):
    if P[i]==-1:
      if root==-1:
        root = i
      else:
        P[i] = root
  return " ".join(str(p+1) for p in P)

T = input()
for t in range(T):
  N, M = map(int, raw_input().split())
  X = [0]*M
  Y = [0]*M
  Z = [0]*M
  for i in range(M):
    X[i], Y[i], Z[i] = map(int, raw_input().split())
  ans = solve(N, M, X, Y, Z)
  print "Case #%s: %s" % (t+1, ans)