Problem:


難儀な人たちが座る椅子

 4つの国の中心にある中立都市アイズシティには、大陸横断列車バンダイ号のホームがあります。 ホームには、バンダイ号を待つ乗客用の椅子が一列に用意されており、ホームに入ってきた人は自由に椅子を利用することができます。

  このバンダイ号、安いし早いし快適ということで、周囲の4つの国からの利用者が絶えません。今日は開通記念日ということで、ホームに座っている人たちに特別なことをしてあげようと思っています。そのためには、改札を通った人たちがどこに座っているか把握しなければなりません。4つの国の人たちの難儀な性格を考慮して、椅子がどのように埋まっているかをシミュレートするプログラムを作成してください。改札を通った人たちは、次々に一列に並んだ椅子に座っていきます。4つの国の人たちは、国ごとに決まった性格と座り方があります。それぞれの座り方は以下の通りです。

A国人の性格
   A 国人は座れればいい。左端から見ていき空いている椅子に座る。

B国人の性格
 B 国人は A 国人が苦手。 A 国人の隣以外で、右端から空いている椅子に座る。ただし、 A国人の隣しか空いていない場合、我慢して左端から空いている椅子に座る。

    

C国人の性格
 
   C 国人は人の隣に座りたい。左側から順に座っている人を見ていき、一番左側に座っている人  の右隣に座ろうとするが、そこが埋まっているならその人の左隣に座ろうとする。そこも埋まっ  ているなら次の人の隣に同条件で座ろうとする。どの椅子にも人が座っていなければ真ん中(椅子の数 n が奇数の場合 (n+1)/2 、偶数の場合 n/2+1 )の椅子に座る。

    

D国人の性格

   D 国人は人の隣に座りたくない。一番近い人との距離が、一番大きくなる椅子に座ろうとする。同条件の椅子が複数ある場合や、どうしても誰かの隣に座らなければならない場合、その中で一番左側にある椅子に座る。誰も座っていない場合は左端の椅子に座る。
   

    

バンダイ号に乗ろうとしている乗客の情報を入力とし、 椅子にどのように座っているかを出力するプログラムを作成してください。左から順番に座っている人の国籍を出力します。ただし、空席の場合は # (半角シャープ)を出力してください。

Input

複数のデータセットの並びが入力として与えられます。        入力の終わりはゼロふたつの行で示されます。
各データセットは以下の形式で与えられます。

n m
a1
a2
:
am

1 行目に椅子の数 n (1 ≤ n ≤ 100) と乗客の数 m (m ≤ n) が与えられます。続く m 行に i 人目の情報 ai が与えられます。ai は１つの文字で、'A' ならば A 国人、'B' ならば B 国人、'C' ならば C 国人、'D' ならば D 国人を表します。

データセットの数は 100 を超えません。

Output

データセットごとに、最終的な椅子の状態を１行に出力します。

Sample Input

5 4
A
B
C
D
5 4
D
C
B
A
0 0

Output for the Sample Input

ACD#B
DCA#B



Sample input:
5 4
A
B
C
D
5 4
D
C
B
A
0 0


Sample output:
ACD#B
DCA#B

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20

while True:
  n, m = map(int, input().split())
  if not n:
    break

  chairs = list("#" * n)

  def sit(s):
    if s == "A":
      chairs[chairs.index("#")] = "A"
    elif s == "B":
      for i in range(n - 1, -1, -1):
        if chairs[i] == "#" and (i == 0 or chairs[i - 1] != "A") and (i == n - 1 or chairs[i + 1] != "A"):
          chairs[i] = "B"
          break
      else:
        chairs[chairs.index("#")] = "B"

    elif s == "C":
      for i in range(1, n):
        if chairs[i] == "#" and chairs[i - 1] != "#":
          chairs[i] = "C"
          break

    else:
      score = [INF for _ in range(n)]
      dist = INF
      for i in range(n):
        if chairs[i] == "#":
          dist += 1
        else:
          dist = 0
        score[i] = dist

      dist = INF
      for i in range(n - 1, -1, -1):
        if chairs[i] == "#":
          dist += 1
        else:
          dist = 0
        score[i] = min(score[i], dist)
      high_score = max(score)
      chairs[score.index(high_score)] = "D"
  
  first = input()
  if first in ["A", "D"]:
    chairs[0] = first
  elif first == "B":
    chairs[-1] = "B"
  else:
    chairs[n // 2] = "C"
  for _ in range(m - 1):
    sit(input())

  print("".join(chairs))

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20

while True:
  n, m = map(int, input().split())
  if not n:
    break

  chairs = list("#" * n)

  def sit(s):
    if s == "A":
      chairs[chairs.index("#")] = "A"
    
    elif s == "B":
      for i in range(n - 1, -1, -1):
        if chairs[i] == "#" and (i == 0 or chairs[i - 1] != "A") and (i == n - 1 or chairs[i + 1] != "A"):
          chairs[i] = "B"
          break
      else:
        chairs[chairs.index("#")] = "B"

    elif s == "C":
      for i in range(0, n):
        if chairs[i] != "#":
          if i - 1  >= 0 and chairs[i - 1] == "#":
            chairs[i - 1] = "C"
            break
          elif i + 1 <= n - 1 and chairs[i + 1] == "#":
            chairs[i + 1] = "C"
            break

    else:
      score = [INF for _ in range(n)]
      dist = INF
      for i in range(n):
        if chairs[i] == "#":
          dist += 1
        else:
          dist = 0
        score[i] = dist

      dist = INF
      for i in range(n - 1, -1, -1):
        if chairs[i] == "#":
          dist += 1
        else:
          dist = 0
        score[i] = min(score[i], dist)
      high_score = max(score)
      chairs[score.index(high_score)] = "D"
  
  first = input()
  if first in ["A", "D"]:
    chairs[0] = first
  elif first == "B":
    chairs[-1] = "B"
  else:
    chairs[n // 2] = "C"
  for _ in range(m - 1):
    sit(input())

  print("".join(chairs))

Submission status: Wrong Answer

Solution code:
def downA(chair):
    for i in range(len(chair)):
        if chair[i]=="#":
            chair[i]="A"
            break

def downB(chair):
    for i in range(len(chair)-1,0,-1):
        if chair[i]=="#" and chair[i-1]!="A":
            chair[i]="B"
            break
    else:
        chair[chair.index("#")]="B"

def downC(chair):
    if set(chair)==set(['#']):
        if len(chair)%2==0:
            chair[n/2+1]="C"
        else:
            chair[(n+1)/2]="C"
        return
    for i in range(len(chair)-1):
        if chair[i]!="#" and chair[i+1]=="#":
            chair[i+1]="C"
            break

def downD(chair):
    if set(chair)==set(["#"]):
        chair[0]="D"
        return
    t=[0]*len(chair)
    cnt=0
    for i in range(len(chair)):
        if chair[i]!="#":
            cnt=0
        else:
            cnt+=1
            t[i]=cnt
    cnt=0
    for i in range(len(chair)-1,-1,-1):
        if chair[i]!="#":
            cnt=0
        else:
            cnt+=1
            t[i]=min(cnt,t[i])
    maxInt=max(t)
    chair[t.index(maxInt)]="D"

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    chair=["#"]*n
    for i in range(m):
        p=raw_input()
        if p=="A":
            downA(chair)
        elif p=="B":
            downB(chair)
        elif p=="C":
            downC(chair)
        elif p=="D":
            downD(chair)
    print "".join(chair)

Submission status: Wrong Answer

Solution code:
def downA(chair):
    for i in range(n):
        if chair[i]=="#":
            chair[i]="A"
            break

def downB(chair):
    for i in range(n-1,0,-1):
        if chair[i]=="#" and chair[i-1]!="A" and chair[i+1]!="A":
            chair[i]="B"
            break
    else:
        chair[chair.index("#")]="B"

def downC(chair):
    if set(chair[:-1])==set(['#']):
        if n%2==0:
            chair[n/2+1]="C"
        else:
            chair[(n+1)/2]="C"
        return
    for i in range(n-1):
        if chair[i]!="#":
            if chair[i+1]=="#":
                chair[i+1]="C"
                break
            elif i-1>=0 and chair[i-1]=="#":
                chair[i-1]="C"
                break


def downD(chair):
    if set(chair[:-1])==set(["#"]):
        chair[0]="D"
        return
    t=[0]*n
    cnt=0
    for i in range(n):
        if chair[i]!="#":
            cnt=0
        else:
            cnt+=1
            t[i]=cnt
    cnt=0
    for i in range(n-1,-1,-1):
        if chair[i]!="#":
            cnt=0
        else:
            cnt+=1
            t[i]=min(cnt,t[i])
    maxInt=max(t)
    chair[t.index(maxInt)]="D"

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    chair=["#"]*n+[""]
    for i in range(m):
        p=raw_input()
        if p=="A":
            downA(chair)
        elif p=="B":
            downB(chair)
        elif p=="C":
            downC(chair)
        elif p=="D":
            downD(chair)
    print "".join(chair)

Submission status: Wrong Answer

Solution code:
def downA(chair):
    for i in range(1,n+1):
        if chair[i]=="#":
            chair[i]="A"
            return

def downB(chair):
    for i in range(n,0,-1):
        if chair[i]=="#" and chair[i-1]!="A" and chair[i+1]!="A":
            chair[i]="B"
            return
    else:
        chair[chair.index("#")]="B"

def downC(chair):
    if set(chair[1:-1])==set(['#']):
        if n%2==0:
            chair[n/2+2]="C"
        else:
            chair[(n+1)/2+1]="C"
        return
    for i in range(1,n+1):
        if chair[i]!="#":
            if chair[i+1]=="#":
                chair[i+1]="C"
                return
            elif i-1>=1 and chair[i-1]=="#":
                chair[i-1]="C"
                return

def downD(chair):
    if set(chair[1:-1])==set(["#"]):
        chair[1]="D"
        return
    t=[0]*(n+2)
    cnt=0
    for i in range(1,n+1):
        if chair[i]!="#":
            cnt=0
        else:
            cnt+=1
            t[i]=cnt
    cnt=0
    for i in range(n,0,-1):
        if chair[i]!="#":
            cnt=0
        else:
            cnt+=1
            t[i]=min(cnt,t[i])
    maxInt=max(t)
    chair[t.index(maxInt)]="D"

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    chair=["X"]+["#"]*n+["X"]
    for i in range(m):
        p=raw_input()
        if p=="A":
            downA(chair)
        elif p=="B":
            downB(chair)
        elif p=="C":
            downC(chair)
        elif p=="D":
            downD(chair)
    print "".join(chair[1:-1])

Submission status: Wrong Answer

Solution code:
#Chairs Where Demanding People Sit:
def A():
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "A"
            return

def B():
    for i in xrange(n - 1, -1, -1):
        if ch[i] == "#" and ch[i - 1] != "A":
            ch[i] = "B"
            return
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "A"
            return

def C():
    if ch[0] != "#" and ch[1] == "#":
        ch[1] = "C"
        return
    for i in xrange(1, n - 1):
        if ch[i] != "#":
            if ch[i - 1] == "#":
                ch[i - 1] = "C"
                return
            if ch[i + 1] == "#":
                ch[i + 1] = "C"
                return
    if ch[n - 2] != "#" and ch[n - 1] == "#":
        ch[n - 1] = "C"
        return
    ch[n / 2 + 1 if n % 2 == 0 else (n + 1) / 2] = "C"

def D():
    if all(map(lambda s: s == "#", ch)):
        ch[0] = "D"
        return
    dist = [1 << 30] * n
    d, flag = 0, False
    for i in xrange(n):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = d
        d += 1
    d, flag = 0, False
    for i in xrange(n - 1, -1, -1):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = min(dist[i], d)
        d += 1
    ch[max(xrange(n), key = lambda i: dist[i])] = "D"

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    ch = ["#"] * n
    f = {"A":A, "B": B, "C": C, "D": D}
    for _ in xrange(m):
        f[raw_input()]()
    print "".join(ch)

Submission status: Wrong Answer

Solution code:
#Chairs Where Demanding People Sit:
def A():
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "A"
            return

def B():
    for i in xrange(n - 1, 0, -1):
        if ch[i] == "#" and ch[i - 1] != "A":
            ch[i] = "B"
            return
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "B"
            return

def C():
    if ch[0] != "#" and ch[1] == "#":
        ch[1] = "C"
        return
    for i in xrange(1, n - 1):
        if ch[i] == "#" and (ch[i - 1] != "#" or ch[i + 1] != "#"):
            ch[i] = "C"
            return
    if ch[n - 2] != "#" and ch[n - 1] == "#":
        ch[n - 1] = "C"
        return
    ch[(n / 2) + 1 if n % 2 == 0 else (n + 1) / 2] = "C"

def D():
    if all(map(lambda s: s == "#", ch)):
        ch[0] = "D"
        return
    dist = [1 << 30] * n
    d, flag = 0, False
    for i in xrange(n):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = d
        d += 1
    d, flag = 0, False
    for i in xrange(n - 1, -1, -1):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = min(dist[i], d)
        d += 1
    ch[max(xrange(n), key = lambda i: dist[i])] = "D"

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    ch = ["#"] * n
    f = {"A":A, "B": B, "C": C, "D": D}
    for _ in xrange(m):
        f[raw_input()]()
    print "".join(ch)

Submission status: Wrong Answer

Solution code:
#Chairs Where Demanding People Sit:
def A():
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "A"
            return

def B():
    for i in xrange(n - 1, 0, -1):
        if ch[i] == "#" and ch[i - 1] != "A":
            ch[i] = "B"
            return
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "B"
            return

def C():
    if ch[0] != "#" and ch[1] == "#":
        ch[1] = "C"
        return
    for i in xrange(1, n - 1):
        if ch[i] == "#" and (ch[i - 1] != "#" or ch[i + 1] != "#"):
            ch[i] = "C"
            return
    if ch[n - 2] != "#" and ch[n - 1] == "#":
        ch[n - 1] = "C"
        return
    ch[((n / 2) + 1 if n % 2 == 0 else (n + 1) / 2) - 1] = "C"

def D():
    if all(map(lambda s: s == "#", ch)):
        ch[0] = "D"
        return
    dist = [1 << 30] * n
    d, flag = 0, False
    for i in xrange(n):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = d
        d += 1
    d, flag = 0, False
    for i in xrange(n - 1, -1, -1):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = min(dist[i], d)
        d += 1
    ch[max(xrange(n), key = lambda i: dist[i])] = "D"

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    ch = ["#"] * n
    f = {"A":A, "B": B, "C": C, "D": D}
    for _ in xrange(m):
        f[raw_input()]()
    print "".join(ch)

Submission status: Wrong Answer

Solution code:
#Chairs Where Demanding People Sit:
def A():
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "A"
            return

def B():
    for i in xrange(n - 1, 0, -1):
        if ch[i] == "#" and ch[i - 1] != "A":
            ch[i] = "B"
            return
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "B"
            return

def C():
    if all(map(lambda s: s == "#", ch)):
        ch[((n / 2) + 1 if n % 2 == 0 else (n + 1) / 2) - 1] = "C"
        return
    if ch[0] == "#" and ch[1] != "#":
        ch[1] = "C"
        return
    for i in xrange(1, n - 1):
        if ch[i] == "#" and (ch[i - 1] != "#" or ch[i + 1] != "#"):
            ch[i] = "C"
            return
    if ch[n - 2] != "#" and ch[n - 1] == "#":
        ch[n - 1] = "C"
        return

def D():
    if all(map(lambda s: s == "#", ch)):
        ch[0] = "D"
        return
    dist = [1 << 30] * n
    d, flag = 0, False
    for i in xrange(n):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = d
        d += 1
    d, flag = 0, False
    for i in xrange(n - 1, -1, -1):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = min(dist[i], d)
        d += 1
    ch[max(xrange(n), key = lambda i: dist[i])] = "D"

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    ch = ["#"] * n
    f = {"A":A, "B": B, "C": C, "D": D}
    for _ in xrange(m):
        f[raw_input()]()
    print "".join(ch)

Submission status: Wrong Answer

Solution code:
#Chairs Where Demanding People Sit:
def A():
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "A"
            return

def B():
    for i in xrange(n - 1, 0, -1):
        if ch[i] == "#" and ch[i - 1] != "A":
            ch[i] = "B"
            return
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "B"
            return

def C():
    if all(map(lambda s: s == "#", ch)):
        ch[((n / 2) + 1 if n % 2 == 0 else (n + 1) / 2) - 1] = "C"
        return
    if ch[0] == "#" and ch[1] != "#":
        ch[0] = "C"
        return
    for i in xrange(1, n - 1):
        if ch[i] == "#" and (ch[i - 1] != "#" or ch[i + 1] != "#"):
            ch[i] = "C"
            return
    if ch[n - 2] != "#" and ch[n - 1] == "#":
        ch[n - 1] = "C"
        return

def D():
    if all(map(lambda s: s == "#", ch)):
        ch[0] = "D"
        return
    dist = [1 << 30] * n
    d, flag = 0, False
    for i in xrange(n):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = d
        d += 1
    d, flag = 0, False
    for i in xrange(n - 1, -1, -1):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = min(dist[i], d)
        d += 1
    ch[max(xrange(n), key = lambda i: dist[i])] = "D"

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    ch = ["#"] * n
    f = {"A":A, "B": B, "C": C, "D": D}
    for _ in xrange(m):
        f[raw_input()]()
    print "".join(ch)

Submission status: Accepted

Solution code:
def left_empty(bench):
    return bench.index('#') 

def a_sit(bench):
    bench[left_empty(bench)] = 'A'
def right_empty(bench):
    for i in reversed(range(len(bench))):
        if bench[i] == '#':
            yield i

def a_next(bench, i):
    if i + 1 < len(bench) and bench[i + 1] == 'A':
        return True
    if 0 <= i - 1 and bench[i - 1] == 'A':
        return True
    return False
            
def b_sit(bench):
    for i in right_empty(bench):
        if not a_next(bench,i):
            bench[i] = 'B'
            return
    bench[left_empty(bench)] = 'B'
def no_people(bench):
    for bi in bench:
        if bi != '#':
            return False
    return True

def not_empty(bench):
    for i in range(len(bench)):
        if bench[i] != '#':
            yield i

def c_sit(bench):
    if no_people(bench):
        bench[len(bench) // 2] = 'C'
        return
    for i in not_empty(bench):
        if i + 1 < len(bench) and bench[i + 1] == '#':
            bench[i + 1] = 'C'
            return
        if 0 <= i - 1 and bench[i - 1] == '#':
            bench[i - 1] = 'C'
            return
def d_sit(bench):
    if no_people(bench):
        bench[0] = 'D'
        return
    tmp = bench[:]
    
    dist = float('inf')
    for i in range(len(tmp)):
        if tmp[i] == '#':
            dist += 1
        else:
            dist = 0
        tmp[i] = dist
    dist = float('inf')
    for i in reversed(range(len(tmp))):
        if tmp[i] != 0:
            dist += 1
        else:
            dist = 0
        tmp[i] = min(tmp[i], dist)
    bench[tmp.index(max(tmp))] = 'D'

import sys
f = sys.stdin


sit = {'A':a_sit,'B':b_sit,'C':c_sit,'D':d_sit}
while True:
    m, n = map(int, f.readline().split())
    if n == 0:
        break
    bench = ['#'] * m
    for i in range(n):
        sit[f.readline().strip()](bench)
    print(''.join(bench))

Submission status: Accepted

Solution code:
INF = 10 ** 20

while True:
  n, m = map(int, input().split())
  if not n:
    break

  chairs = list("#" * n)

  def sit(s):
    if s == "A":
      chairs[chairs.index("#")] = "A"
    
    elif s == "B":
      for i in range(n - 1, -1, -1):
        if chairs[i] == "#" and (i == 0 or chairs[i - 1] != "A") and (i == n - 1 or chairs[i + 1] != "A"):
          chairs[i] = "B"
          break
      else:
        chairs[chairs.index("#")] = "B"

    elif s == "C":
      for i in range(n):
        if chairs[i] != "#":
          if i + 1 <= n - 1 and chairs[i + 1] == "#":
            chairs[i + 1] = "C"
            break
 
          elif i - 1  >= 0 and chairs[i - 1] == "#":
            chairs[i - 1] = "C"
            break

    else:
      score = [INF for _ in range(n)]
      dist = INF
      for i in range(n):
        if chairs[i] == "#":
          dist += 1
        else:
          dist = 0
        score[i] = dist

      dist = INF
      for i in range(n - 1, -1, -1):
        if chairs[i] == "#":
          dist += 1
        else:
          dist = 0
        score[i] = min(score[i], dist)
      high_score = max(score)

      chairs[score.index(high_score)] = "D"
  
  first = input()
  if first in ["A", "D"]:
    chairs[0] = first
  elif first == "B":
    chairs[-1] = "B"
  else:
    chairs[n // 2] = "C"
  
  for _ in range(m - 1):
    sit(input())
  print("".join(chairs))

Submission status: Accepted

Solution code:
INF = 10 ** 20

def main():
  while True:
    n, m = map(int, input().split())
    if not n:
      break
  
    chairs = list("#" * n)
  
    def sit(s):
      if s == "A":
        chairs[chairs.index("#")] = "A"
      
      elif s == "B":
        for i in range(n - 1, -1, -1):
          if chairs[i] == "#" and (i == 0 or chairs[i - 1] != "A") and (i == n - 1 or chairs[i + 1] != "A"):
            chairs[i] = "B"
            break
        else:
          chairs[chairs.index("#")] = "B"
  
      elif s == "C":
        for i in range(n):
          if chairs[i] != "#":
            if i + 1 <= n - 1 and chairs[i + 1] == "#":
              chairs[i + 1] = "C"
              break
   
            elif i - 1  >= 0 and chairs[i - 1] == "#":
              chairs[i - 1] = "C"
              break
  
      else:
        score = [INF for _ in range(n)]
        dist = INF
        for i in range(n):
          if chairs[i] == "#":
            dist += 1
          else:
            dist = 0
          score[i] = dist
  
        dist = INF
        for i in range(n - 1, -1, -1):
          if chairs[i] == "#":
            dist += 1
          else:
            dist = 0
          score[i] = min(score[i], dist)
        high_score = max(score)
  
        chairs[score.index(high_score)] = "D"
    
    first = input()
    if first in ["A", "D"]:
      chairs[0] = first
    elif first == "B":
      chairs[-1] = "B"
    else:
      chairs[n // 2] = "C"
    
    for _ in range(m - 1):
      sit(input())
    print("".join(chairs))

main()

Submission status: Accepted

Solution code:
def downA(C):
    C[C.index("#")]="A"

def downB(C):
    for i in range(n,0,-1):
        if C[i]=="#" and C[i-1]!="A" and C[i+1]!="A":
            C[i]="B"
            return
    C[C.index("#")]="B"

def downC(C):
    if set(C[1:-1])==set(['#']):
        C[n/2+1]="C"
        return
    for i in range(1,n+1):
        if C[i]!="#":
            if C[i+1]=="#":
                C[i+1]="C"
                return
            elif C[i-1]=="#":
                C[i-1]="C"
                return

def getDist(p):
    l,r=0,0
    while C[p+l-1]=="#":l-=1
    if C[p+l-1]=="X":l=-100000
    while C[p+r+1]=="#":r+=1
    if C[p+r+1]=="X":r=100000
    return min(-1*l,r)

def downD(C):
    if set(C[1:-1])==set(["#"]):
        C[1]="D"
        return
    md=-1
    for i in range(1,n+1):
        if C[i]!="#":continue
        d=getDist(i)
        if (d>md):
            md=d
            mi=i
    C[mi]="D"

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    C=["X"]+["#"]*n+["X"]
    for i in range(m):
        p=raw_input()
        if p=="A":downA(C)
        elif p=="B":downB(C)
        elif p=="C":downC(C)
        elif p=="D":downD(C)
    print "".join(C[1:-1])

Submission status: Accepted

Solution code:
#Chairs Where Demanding People Sit:
def A():
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "A"
            return

def B():
    for i in xrange(n - 1, 0, -1):
        if ch[i] == "#" and ch[i - 1] != "A":
            ch[i] = "B"
            return
    for i in xrange(n):
        if ch[i] == "#":
            ch[i] = "B"
            return

def C():
    if all(map(lambda s: s == "#", ch)):
        ch[((n / 2) + 1 if n % 2 == 0 else (n + 1) / 2) - 1] = "C"
        return
    if ch[0] != "#" and ch[1] == "#":
        ch[1] = "C"
        return
    for i in xrange(1, n - 1):
        if ch[i] != "#":
            if ch[i + 1] == "#":
                ch[i + 1] = "C"
                return
            if ch[i - 1] == "#":
                ch[i - 1] = "C"
                return
    ch[-1] = "C"

def D():
    if all(map(lambda s: s == "#", ch)):
        ch[0] = "D"
        return
    dist = [1 << 30] * n
    d, flag = 0, False
    for i in xrange(n):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = d
        d += 1
    d, flag = 0, False
    for i in xrange(n - 1, -1, -1):
        flag = flag or ch[i] != "#"
        if flag == False:
            continue
        if ch[i] != "#":            
            d = 0
        dist[i] = min(dist[i], d)
        d += 1
    ch[max(xrange(n), key = lambda i: dist[i])] = "D"

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    ch = ["#"] * n
    f = {"A":A, "B": B, "C": C, "D": D}
    for _ in xrange(m):
        f[raw_input()]()
    print "".join(ch)

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    ans = ''
    
    while True:
        n, m = map(int, f_i.readline().split())
        
        if n == 0 and m == 0:
            break
        
        chairs = '#' * n
        
        for i in range(m):
            a = f_i.readline().rstrip()
            if a == 'A':
                chairs = chairs.replace('#', 'A', 1)
            elif a == 'B':
                chairs = chairs[::-1]
                idx = chairs.find('#')
                while idx != -1:
                    if idx > 0:
                        if chairs[idx-1] == 'A':
                            idx = chairs.find('#', idx + 1)
                            continue
                    if idx < n - 1:
                        if chairs[idx+1] == 'A':
                            idx = chairs.find('#', idx + 1)
                            continue
                    chairs = chairs[:idx] + 'B' + chairs[idx+1:]
                    chairs = chairs[::-1]
                    break
                else:
                    chairs = chairs[::-1]
                    chairs = chairs.replace('#', 'B', 1)
            elif a == 'C':
                if chairs.count('#') == n:
                    idx = n // 2
                    chairs = chairs[:idx] + 'C' + chairs[idx+1:]
                else:
                    idx = n
                    for c in 'ABCD':
                        i = chairs.find(c)
                        if i != -1:
                            idx = min(idx, i)
                    if idx == 0:
                        idx = chairs.find('#', idx + 1)
                    else:
                        if chairs[idx+1] == '#':
                            idx += 1
                        else:
                            idx -= 1
                    chairs = chairs[:idx] + 'C' + chairs[idx+1:]
            else:
                if chairs.count('#') == n:
                    chairs = 'D' + chairs[1:]
                else:
                    dist1 = [0] * n
                    d = n
                    for i, c in enumerate(chairs):
                        if c == '#':
                            d += 1
                            dist1[i] = d
                        else:
                            d = 0
                            dist1[i] = d
                    
                    dist2 = [0] * n
                    d = n
                    for i, c in enumerate(chairs[::-1], 1):
                        if c == '#':
                            d += 1
                            dist2[-i] = d
                        else:
                            d = 0
                            dist2[-i] = d
                    
                    dist = []
                    for d1, d2 in zip(dist1, dist2):
                        dist.append(min(d1, d2))
                    
                    idx = dist.index(max(dist))
                    
                    chairs = chairs[:idx] + 'D' + chairs[idx+1:]
        
        ans += chairs
        ans += '\n'
    
    print(ans, end='')

solve()

Submission status: Accepted

Solution code:
while 1:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    ans = ["#"]*N
    for i in range(M):
        a = input()
        if a == 'A':
            for j in range(N):
                if ans[j] == '#':
                    ans[j] = 'A'
                    break
        elif a == 'B':
            for j in range(N-1, -1, -1):
                if ans[j] == '#':
                    if (j == 0 or ans[j-1] != 'A') and (j == N-1 or ans[j+1] != 'A'):
                        ans[j] = 'B'
                        break
            else:
                for j in range(N):
                    if ans[j] == '#':
                        ans[j] = 'B'
                        break
        elif a == 'C':
            if i:
                for j in range(N):
                    if ans[j] != '#':
                        if j < N-1 and ans[j+1] == '#':
                            ans[j+1] = 'C'
                            break
                        if j > 0 and ans[j-1] == '#':
                            ans[j-1] = 'C'
                            break
            else:
                ans[N//2] = 'C'
        else:
            if i:
                d = 0; k = -1
                for j in range(N):
                    if ans[j] == '#':
                        d0 = N
                        p = j
                        while p >= 0 and ans[p] == '#':
                            p -= 1
                        if p >= 0:
                            d0 = min(d0, j-p)
                        q = j
                        while q < N and ans[q] == '#':
                            q += 1
                        if q < N:
                            d0 = min(d0, q-j)
                        if d < d0:
                            k = j; d = d0
                ans[k] = 'D'
            else:
                ans[0] = 'D'
    print(*ans, sep='')