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

問題の概要

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

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

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

入力

入力は
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-
と出力すればよい。

補足

不正な入力に対処する必要はない。
満席になってもまだ人が来るとかいう状況を考慮する必要はない。
実装ができた方は Qiitaの記事のコメント欄からリンクを張っていただくと見つけやすくて助かります。
入力も出力も文字列ないしは標準入出力にするのが望ましい。パースも仕事のうち。
この問題は2017年11月22日に開催されるオフラインリアルタイムどう書くF08 の問題です。イベントについては Doorkeeper のページの方を御覧下さい。

サンプルデータ

#	入力	期待
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 用のテストデータ

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