1 3 5 7 9 8 6 4 2

のんびり座りたい strikes back 2017.11.22 問題

問題の概要

丸く並んだ椅子がある。椅子には、右図のように番号が振られている。
最初は誰も座っていない。
そこにひとりずつ人が現れ、あるいは立ち去る。
人が座る席は以下のルールで決まる:

  1. どちら側の隣にも人が座っていない席を選ぶ。
  2. それが無理なら、片側にしか人が座っていない席を選ぶ。
  3. それも無理なら、両側に人が座っている席を選ぶ。
  4. 上記の条件で一つに決まらない場合は、候補のうちもっとも小さい番号の席に座る人と、最も大きい番号の席に座る人がいる。

一度座ったら立ち去るまでその場を動かない。
指定された順序で人が来たり立ち去ったりした結果、それぞれの椅子に誰が座っているのかを出力せよ。

入力

入力は
NABETanI
こんな感じ。区切り文字なしで人の出入りを示す文字が並んでいる。
A〜Z は、それぞれの人の到着を意味し、a〜z は、対応する大文字の人が立ち去ったことを意味する。
A〜M は、小さい番号の席を好む人。N〜Z は大きい番号の席を好む人。

出力

出力は、席に座っている人を 1 から順に時計回りで並べる。誰も座っていない席は - で示す。

先ほどの入力の場合、

記号 説明 席の状態
N N が現れた ----N----
A A が現れた A---N----
B B が現れた A---N--B-
E E が現れた A-E-N--B-
T T が現れた A-E-NT-B-
a A が立ち去った --E-NT-B-
n N が立ち去った --E--T-B-
I I が現れた I-E--T-B-


なので、
I-E--T-B-
と出力すればよい。

補足

サンプルデータ

# 入力 期待
0 NABETanI I-E--T-B-
1 A A--------
2 Aa ---------
3 Z ----Z----
4 Zz ---------
5 AaB B--------
6 ABa -------B-
7 ABCDEFGHI AGCEIDHBF
8 OPQRSTUVW WSQUOTPVR
9 F F--------
10 L L--------
11 Mm ---------
12 JQ J---Q----
13 ACP A---P--C-
14 GgS ----S----
15 USLE L-E-U-S--
16 XJZY J-Y-X-Z--
17 NnJXx J--------
18 AJjQa ----Q----
19 HGThgQ ----T-Q--
20 NJRErI J-E-N--I-
21 ZzWwDYG D---Y--G-
22 ZGgKQHM K-H-Z-Q-M
23 OZYSAsHP A-Y-OPZ-H
24 VNnEISAW E-S-VWAI-
25 HhYAKkCOE A-O-Y-EC-
26 KAkHJTSWV H-JWTSVA-
27 WNTYKHZhMQ KMTQWZN-Y
28 YyJHFGfgTh J---T----
29 NRWPLBZAOpC LBWONZRAC
30 IORiTMXHUCF MCTFOURXH
31 AEeHGBEJUNZn AZGEUB-HJ
32 GgKGSOsZTLYS K-OYZTSGL
33 VZvPOpWPMzHGF MGO-W-HFP
34 CMmcUuLTWADFQ LFA-TQW-D
35 HUGZMLzlNgTLDd H-N-U-MTL
36 CFKEkHeJShUDTf C-UTSJ--D
37 QJjGPMAICHKqWcY GIMHWKPYA
38 HhIiQCIBiUMZcVv --B-QZU-M
39 VMvEmFOPANIBUiVb F-PUONAEV
40 EDCJUINdLPVnFpGe -VCFUJGLI
41 FGQINTEnLMAlBbPpV FMITQAVGE
42 WSVCORUMXsvNBuTtT CXBTWRNOM
43 HJTjRVIQAXqDGxCtUh -AVCUGRDI
44 ZzHXIEKQYUuBTxLlCq HTEYC-KIB
45 RGDCAEBVrgFbTJUePjc -T-FUVADP
46 WBIRSALCVvsbwalYBJP B-R-YPCIJ
47 HKFZGEPAIphLRarAOaHo LHFIZ-GKE
48 WFNwBfbSAXCZzMDJUcKx AM-JSUNDK

C/C++/Java 用のテストデータ