多段階選抜 2014.8.2 問題

問題

すべての正の整数を小さい順に並べた列がある。
この数列に対して「3の倍数番目を撤去」「平方数の次の値を撤去」などの操作を繰り返す。
出来上がった数列の最初の10件を出力せよ。

入力と詳細

入力は、下表の記号をならべたものである。

記号 意味
2〜9 2〜9 の倍数番目を撤去(先頭が1番目であることに注意)
S 平方数の次を撤去
s 平方数の直前を撤去
C 立方数の直後を撤去
c 立方数の直前を撤去
h 先頭の100件を撤去

具体的には
ss6cc24S
こんな感じ。この入力を受けての処理は

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21
           ↓ s
1,2,4,5,6,7,9,10,11,12,13,14,16,17,18,19,20,21,22,23
           ↓ s
1,4,5,6,9,10,11,12,13,16,17,18,19,20,21,22,25,26,27
           ↓ 6
1,4,5,6,9,11,12,13,16,17,19,20,21,22,25,27,28,29,30
           ↓ c
1,4,5,6,9,11,12,13,16,17,19,20,21,22,27,28,29,30,31
           ↓ c
1,4,5,6,9,11,12,13,16,17,19,20,21,27,28,29,30,31,33
           ↓ 2
1,5,9,12,16,19,21,28,30,33,37,39,42,44,49,51,53,56,58
           ↓ 4
1,5,9,16,19,21,30,33,37,42,44,49,53,56,58,67,70,72,77
           ↓ S
1,9,21,30,33,37,42,44,49,56,58,67,70,72,77,81,89,91

こうなる。

「平方数の直後を撤去」についてちょっと説明しておく。
上記の例の最後の処理で「 1,5,9,16,19,21,30,33,37,42,... 」から「平方数の直後を撤去」している。
元の数列に含まれる平方数は「 1,9,16,49,81,... 」。
撤去するべき値は平方数の次なので、
元の数列で 1 の次ににある 5 、 9 の次ににある 16 、 16 の次ににある 19 、 などになる。
立方数の直前なども同様。

出力

出来上がった数列の先頭10件をコンマ区切りで出力する。
数列の要素は、10進数で。
つまり、
ss6cc24S
という入力に対しては、上にある表のとおりに処理が進む。最初の10件を出力すればよいので
1,9,21,30,33,37,42,44,49,56
を出力すればよい。

補足

サンプルデータ

# 入力 期待
0 ss6cc24S 1,9,21,30,33,37,42,44,49,56
1 h 101,102,103,104,105,106,107,108,109,110
2 hh 201,202,203,204,205,206,207,208,209,210
3 hhh 301,302,303,304,305,306,307,308,309,310
4 2 1,3,5,7,9,11,13,15,17,19
5 22 1,5,9,13,17,21,25,29,33,37
6 222 1,9,17,25,33,41,49,57,65,73
7 3 1,2,4,5,7,8,10,11,13,14
8 33 1,2,5,7,10,11,14,16,19,20
9 333 1,2,7,10,14,16,20,23,28,29
10 s 1,2,4,5,6,7,9,10,11,12
11 ss 1,4,5,6,9,10,11,12,13,16
12 sss 4,5,9,10,11,12,16,17,18,19
13 S 1,3,4,6,7,8,9,11,12,13
14 SS 1,4,7,8,9,12,13,14,15,16
15 SSS 1,8,9,13,14,15,16,20,21,22
16 c 1,2,3,4,5,6,8,9,10,11
17 cc 1,2,3,4,5,8,9,10,11,12
18 ccc 1,2,3,4,8,9,10,11,12,13
19 C 1,3,4,5,6,7,8,10,11,12
20 CC 1,4,5,6,7,8,11,12,13,14
21 CCC 1,5,6,7,8,12,13,14,15,16
22 23 1,3,7,9,13,15,19,21,25,27
23 32 1,4,7,10,13,16,19,22,25,28
24 2h 201,203,205,207,209,211,213,215,217,219
25 h2 101,103,105,107,109,111,113,115,117,119
26 sC 1,4,5,6,7,9,10,11,12,13
27 Cs 1,4,5,6,7,8,10,11,12,13
28 s468 1,2,4,6,7,11,12,16,17,20
29 S468 1,3,4,7,8,12,13,16,18,21
30 cc579 1,2,3,4,8,9,11,13,15,16
31 CC579 1,4,5,6,8,11,13,15,17,18
32 85 1,2,3,4,6,7,9,10,12,13
33 sh 110,111,112,113,114,115,116,117,118,119
34 94h 150,151,154,155,156,158,159,160,163,164
35 h9c8 101,102,103,104,105,106,107,110,111,112
36 Cc3s 1,3,5,6,10,11,13,16,17,19
37 cs4h6 149,150,152,153,154,157,158,160,161,162
38 84523c 1,3,11,15,23,26,34,38,46,49
39 54C78hS 228,231,232,233,236,241,242,243,246,247
40 65h7ccs 151,152,153,154,157,158,160,163,164,165
41 c95hSc2C 145,147,151,153,156,159,162,164,168,171
42 c5h3Ss794 130,131,133,137,138,142,148,150,152,157
43 7ShscC846 129,130,131,134,135,139,141,142,146,148
44 cshSCCS7ch 253,254,256,259,260,261,263,264,265,266
45 hhC7849Ss6C 201,202,203,205,206,211,212,216,220,225
46 hhsc3C987Ccs 201,202,204,205,207,208,214,217,218,220
47 SC7S8hc59ss2 162,169,174,178,182,185,188,194,199,203
48 s7S6c35C9CShc 367,371,377,379,380,385,387,388,392,395
49 4scC3hh982Cc5s 422,426,430,434,447,451,459,463,471,479
50 23h465Ssc9CchC 1027,1033,1045,1047,1057,1069,1071,1075,1081,1093

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