Time Limit: 2 sec / Memory Limit: 256 MB
問題文
天下一王国では整数は辞書順比較で表します。入国したばかりのダイキ君はとりあえず 1000 までの整数を書き出すことにしました。
1 以上 1000 以下のすべての整数を十進数で表した文字列を辞書順比較で昇順にソートして、1 行ずつ出力してください。
辞書順比較について
文字列 A に対して、 A_i で i 番目の文字を表し、 |A| で文字列 A の文字数を表すことにすると、文字列 A と文字列 B を辞書順比較で比較するとは、
- A_i \neq B_i となる最小の i (1 \leq i \leq {\rm min}(|A|,\ |B|)) に対して
- A_i \lt{} B_i であれば、文字列 A は文字列 B より小さい
- A_i \gt{} B_i であれば、文字列 A は文字列 B より大きい
- そのような i が存在しなければ、文字数が少ない方を小さいとする
として文字列 A と文字列 B の大小関係を決めることである。
例えば、 1, 2, 11, 12, 21 を辞書順比較で昇順にソートすると 1, 11, 12, 2, 21 となる。
入力
この問題では入力は与えられない。
出力
1 以上 1000 以下のすべての整数を十進数で表した文字列を辞書順比較で昇順にソートして、1 行ずつ出力せよ。
なお、行の終端には改行が必要である。
1 から 10 までの出力例
1 10 2 3 4 5 6 7 8 9
Source Name
天下一プログラマーコンテスト2014 予選ATime Limit: 2 sec / Memory Limit: 256 MB
“ぶん投げRPG『かぶりん！』”とは、袋をかぶった不思議な生き物かぶりんを投げて敵を倒すアクションRPGです。
問題文
かぶりんに熱中している王国民のダイキ君は、敵に与えるダメージを計算するプログラムを作成することにしました。
かぶりんのゲームのルールは以下の様になります。
ゲーム開始時点で、手元に 5 袋のかぶりんがいる。
手元のかぶりんを投げて敵にダメージを与えることができる。投げたかぶりんはしばらくすると手元に戻ってくる。
投げ方には「通常投げ」「ため投げ」の 2 種類があり、投げて敵にダメージを与えるとコンボ数が増える。
通常投げ
- 1 袋のかぶりんを投げる
- 手元に 1 袋以上のかぶりんが必要
- 投げるまでに 0.5 秒かかる
- 投げてから 1 秒後にダメージを与える
- 基本ダメージは 10 で、投げる際のコンボ数によって増加する
- ダメージを与えてから 5 秒後に手元に戻ってくる
ため投げ
- 3 袋のかぶりんを投げる
- 手元に 3 袋以上のかぶりんが必要
- 投げるまでに 2.5 秒かかり、その間は他の行動はできない
- 投げてから 1 秒後にダメージを与える
- 基本ダメージは 50 で、投げる際のコンボ数によって増加する
- ダメージを与えてから 5 秒後に手元に戻ってくる
コンボについて
- ゲーム開始時点でコンボ数は 0 である
- 通常投げ、ため投げ共に、1 回ダメージを与えるとコンボ数が 1 増える
- 10 コンボごとに、与えるダメージが、基本ダメージの 10 %増加する
- 与えるダメージは、基本ダメージを A、コンボ数を C としたとき、A \times (1 + {\rm floor}(C / 10) \times 0.1) で計算される
- {\rm floor}(x) は x を超えない最大の整数を意味する。
- 攻撃力の増加は、コンボ達成後に投げはじめるかぶりんから適用される
ユーザの入力について
- 1 秒に 1 回 通常投げ、ため投げ、何もしない のいずれかが入力がなされる
- 投げの入力時、手元に必要なかぶりんがいない場合は無視される
- ため時間中の投げ入力は無視される
ユーザの入力が与えられるので、敵に与えたダメージの合計を計算して下さい。
なお、ユーザの入力が終わった際に投げられているかぶりんのダメージも計算に含みます。
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 … S_n
- ユーザの入力を表す長さ n (1 \leq{} n \leq{} 1000000) の文字列が 1 行で与えられる
- i 番目文字 S_i は i 秒目のユーザーの入力を表わしている
- S_i は次のいずれかである
-入力なしN通常投げCため投げ
出力
敵に与えたダメージの合計を 1 行の整数で出力せよ。
なお、行の終端には改行が必要であり、ダメージの合計は 10^{11} 以下になることが保証されている。
一般的な 32 bit整数型に収まらないことに注意せよ。
入力例1
NNNNNNNN
出力例1
60
かぶりんを通常投げで 8 回投げようとしますが、6 秒目と 7 秒目には手元にかぶりんがおらず、8 秒目に 1 秒目に投げたかぶりんが帰ってきているので、6 回投げることができ 60 ダメージを与えます。
入力例2
CCCCC
出力例2
50
1 秒目の入力で、3 袋のかぶりんのため投げを開始します。
2, 3 秒目の入力は、ため投げ中なので無視されます。
4, 5 秒目の入力は、手元に 3 袋以上かぶりんがいないため無視されます。
入力例3
NNC------NNC------NNC------NNC------NNC------NNC
出力例3
439
コンボによるダメージの増加は、実際に投げるタイミングではなく、ため始めるタイミングです。(22:20 追記)
10 コンボ到達後に投げ始めるかぶりんに対して、ダメージが増加することに注意して下さい。
Source Name
天下一プログラマーコンテスト2014 予選ATime Limit: 5 sec / Memory Limit: 256 MB
問題文
英小文字 (a～z) と、英小文字 1 文字と一致するワイルドカード (*) からなる m 文字の文字列のパターンが n 個与えられる。
この文字列のパターンは、 m 文字の英小文字からなる文字列の集合 X のいずれかの要素に一致するようにように作られたものである。
集合 X の要素数の最小値を求めよ、ダイキ君。
入力
入力は、以下の形式で標準入力から与えられる。
n m P1 P2 : Pn
1 行目に文字列のパターンの数を表す整数 n( 1 ≦ n ≦ 14 ) と文字列の長さを表す整数 m( 1 ≦ m ≦ 100000 ) が与えられる。 その後、長さ m の文字列のパターン P_i が n 行で与えられる。
部分点
- 1 ≦ n ≦ 4, 1 ≦ m ≦ 4 の全てのテストケースに正解した場合、部分点として20点が与えられる
- 1 ≦ n ≦ 14, 1 ≦ m ≦ 10 の全てのテストケースに正解した場合、部分点としてさらに30点が与えられる
出力
集合 X としてありうる要素数のうち最小の値を1行で出力せよ。 なお、行の終端には改行が必要である。
入力例1
5 4 a*x* *xx* *x*b **cb ****
出力例1
2
集合 X の例としては、
axxb oocb
がありうる。
Source Name
天下一プログラマーコンテスト2014 予選ATime Limit: 5 sec / Memory Limit: 256 MB
問題文
天下一王国では兵器開発の成果としてレールガン (ElectroMagneticLauncher) の試射が行われます。試射では障害物として配置された N 枚の鉄板を全て打ち抜く実験を行います。
設計段階ではいくらでも障害物を貫通させるだけの威力を、レールガンは備えています。
しかし、レールガンを用いて弾体を射出するには膨大な電力が必要りなります。
ダイキ君は前もって全ての障害物を破壊するために必要な最小の発射回数を計算する仕事を任されました。
また、レールガンは専用の砲座も開発されており、任意の方角へ向けての射出が可能です。
簡単のために、障害物は平面上の線分、レールガンは原点 (0, 0) として表現されます。
発射された弾体の軌道は原点から延びる半直線として表され、交差または接した障害物を全て破壊します。
入力
入力は以下の形式で標準入力から与えられる。
N
X_{1,1} Y_{1,1} X_{1,2} Y_{1,2}
X_{2,1} Y_{2,1} X_{2,2} Y_{2,2}
:
X_{N,1} Y_{N,1} X_{N,2} Y_{N,2}
- 1 行目には配置される障害物の数 N ( 1 ≦ N ≦ 2000 ) が与えられる
- 2 行目から N 行目には4つの整数 ( -1000 ≦ X_{i,1}, Y_{i,1}, X_{i,2}, Y_{i,2} ≦ 1000 ) が与えられ、 i 行目は i 番目の障害物の端点が (X_{i,1}, Y_{i,1}) と (X_{i,2}, Y_{i,2}) であることを表しています
- 障害物（端点を含む）が原点に接することはない
- 障害物（端点を含む）が互いに交差したり接したりすることはない
部分点
- N ≦ 20 の全てのテストケースに正解した場合、部分点として 45 点があたえられる
- N ≦ 200 の全てのテストケースに正解した場合、部分点として さらに 40 点があたえられる
出力
全ての障害物を破壊するために必要な試射の回数を 1 行に出力せよ。出力の末尾には改行を入れること。入力例1
2 10 10 10 -10 -10 10 -10 -10
出力例1
2
入力例2
2 5 -10 5 0 10 0 10 10
出力例2
1
入力例3
8 1 5 6 1 6 -1 1 -6 -1 -6 -5 -1 -5 1 -1 5 7 5 7 -6 -5 -7 6 -7 -6 -6 -6 5 -5 6 6 6
出力例3
4
Source Name
天下一プログラマーコンテスト2014 予選ATime Limit: 5 sec / Memory Limit: 256 MB
問題文
天下一王国では、あるパズルが大流行しています。 このパズルにおいて、 1 × 1 の正方形のブロックを辺でつなげた多角形をピースと呼び、与えられたピースを H × W の長方形に敷き詰めると完成です。
高橋君は、このパズルを完成させました！
しかし、彼は完成させたパズルを人差し指 1 本でどれだけ破壊できるか試したくなったので、左から x 番目、上から y 番目のブロックだけを人差し指で押さえ、下へ引きずるつもりです。 あるピースが下に引きずられるブロックを含むとき、そのピースのブロックは全て下に引きずられます。
また、引きずられるブロックの底辺に接続するブロックも一緒に下へ引きずられます。
彼はこの引きずる動作をしたとき、 1 × 1 の正方形のブロックがいくつ動くことになるか、引きずる前に調べたいです。
あなたに高橋君が人差し指で引きずるブロックの位置の候補を Q 個与えます。 それぞれの候補に対し、高橋君の動作に伴って引きずられるであろうブロックの数を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
H W
c_{1,1} c_{1,2} ... c_{1,W}
c_{2,1} c_{2,2} ... c_{2,W}
:
c_{H,1} c_{H,2} ... c_{H,W}
Q
x_1 y_1
x_2 y_2
:
x_Q y_Q
- 1 行目には、パズルの縦のブロック数を表す整数 H (1 ≦ H ≦ 20000)、横のブロック数を表す整数 W (1 ≦ W ≦ 16) がスペース区切りで与えられる
- 2 行目から H 行は、パズルの情報が与えられる。そのうち i(1 ≦ i ≦ H) 行目には、 W 文字の文字列が与えられる。 このうち j(1 ≦ j ≦ W) 番目の文字 c_{i,j} は、上から i 番目、左からj 番目におけるブロックの種類を表す。縦または横に隣り合うブロックが同じ種類の時、その 2 つのブロックは同じピースであることを表す。なお、 c_{i,j} は、必ず大文字アルファベットである
- H + 2 行目には、高橋君が引きずる候補の場所の数を表す整数 Q (1 ≦ Q ≦ 100000) が与えられる
- H + 3 行目から Q 行は、高橋君が引きずる候補のブロックの場所を表す情報が 1 行ごとに与えられる。 そのうち i(1 ≦ i ≦ Q) 行目には i 番目の候補のブロックの場所を表す 2 つの整数 x_i, y_i (1 ≦ x_i ≦ W, 1 ≦ y_i ≦ H) が、スペース区切りで与えられる
部分点
Q=1 の全てのテストケースに正解した場合、部分点として 30 点が与えられる。
出力
高橋君が引っ張る場所ごとに、いくつのブロックを引っ張ることが出来るかを、 1 行ずつ Q 行で出力せよ。出力の末尾には改行をいれること。
入力例1
5 3 AAB ABB CDE FFH GHH 2 1 1 2 3
出力例1
15 7
(x,y) を、左から x 番目、上から y 番目のブロックとします。
(1,1) のブロックは A です。 A を下に引きずると、すべてのブロックが引きずられます。 (2,3) は D です。 D を下に引きずると、D,F,G,H が引きずられます。
入力例2
2 2 AB BA 2 1 1 2 1
出力例2
2 2
同じアルファベットが使われていても、別のピースである可能性があることに注意してください。
入力例3
5 5 AABAA ACDEA AFGHA AIJKA AAAAA 1 3 1
出力例3
25
Bのブロックを引きずることで、全てのブロックを引きずることが出来ます。