A - 帰ってきた器物損壊！高橋君

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

　高橋君はある日、コンピューターのキーボードの中の 1 つのキーが壊れていることに気づきました。
　壊れたキーは押しても文字が出力されません。
　力が強いことで有名な高橋君なので、キーを強く叩きすぎたのでしょう。
　しかし、高橋君は小さいことは気にしない性格なので、そのキーボードを壊れたまま使うことにしました。
　高橋君がタイピングする文字列が与えられるので、壊れたキーボードを用いてタイピングした場合の出力結果を答えなさい。

入力

入力は以下の形式で標準入力から与えられる。 
X
s
  • 入力は 2 行ある。
  • 1 行目には、壊れたキーを表す文字 X が与えられる。
    • X は英字の小文字(a-z)のいずれかである。
  • 2 行目にはタイピングする文字列を表す 1 文字以上 50 文字以下の文字列が与えられる。
    • 文字列は英語の小文字(a-z)のみで成り立っている。

出力

壊れたキーでの入力は出力されない状態で文字列をタイピングした場合に、出力される文字列を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。
もし何も出力されない場合は改行のみを出力せよ。

入力例 1

a
abcdefgabcdefg

出力例 1

bcdefgbcdefg
  • 1 文字目と 8 文字目に含まれる a の文字が出力されないので、bcdefgbcdefgが答えになります。

入力例 2

g
aassddffgg

出力例 2

aassddff
  • 最後の g が 2 文字出力されません。

入力例 3

a
aaaaa

出力例 3
  • 何も表示されない場合は改行のみ出力します。

入力例 4

l
qwertyuiopasdfghjklzxcvbnm

出力例 4

qwertyuiopasdfghjkzxcvbnm

入力例 5

d
qwsdtgcszddddsdfgvbbnj

出力例 5

qwstgcszsfgvbbnj

Source Name

ARC 007
B - 迷子のCDケース

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

　高橋君はCDで音楽を聴くことが好きです。
　CDプレイヤーには先日聴いたCDが入ったままになっているのですが、そのCDに対応するCDケースが見当たらないことに気づきました。
　前回に聴いた時にCDケースをどこに置いたのか、残念ながら高橋君は全く思い出せませんでした。
　仕方がないので高橋君は今から聴こうとしているCDをケースから取り出し、CDプレイヤーに入っていたCDをそのケースへと片付けることにしました。
　さらに別のCDを新たにCDプレイヤーに入れる場合も、CDプレイヤーに入っていたCDは空いたCDケースに片づけます。 　例えば図 1 のように 3 枚のCDがある状態で、黄緑色のCD、オレンジ色のCDの順でCDを聴くと、それぞれのCDは最も下の図のように片付けられることになります。
図 1:黄緑色のCD、オレンジ色のCDの順で聴いた場合のCDの動き
　高橋君が音楽を聴き終わった後、今日聞いたCDのリストが与えられるので、高橋君が所持するCDケースにはそれぞれどのCDが入っているかを答えなさい。

入力

入力は以下の形式で標準入力から与えられる。 
N M
disk_{0}
disk_{1}
:
:
disk_{M-1}
  • 入力は M+1 行ある。
  • 1 行目には、高橋君が所持するCDケースの個数を表す整数 N(1≦N≦100)と、今日聴いたCDの枚数 M(0≦M≦100) が空白区切りで与えられる。
    • CDケースを 1 つ無くしているので、高橋君は計 N+1 枚のCDを所持している。
    • CDと対応するCDケースにはそれぞれ 0 から N までの数が番号付けられている。
    • 現在CDプレイヤーに入ってるCDとそれに対応する見当たらないCDケースは 0 番である。
  • 2 行目からの M 行には今日聴いたCDの番号のリストが与えられる。
    • i+2 行目の整数 disk_{i}(0≦i≦M-1, 0≦disk_i≦N) は i+1 番目に disk_i 番のCDを聴いたことを表している。

出力

1 から N 番までのCDケースに入ってるCDの番号を順に標準出力に 1 行に 1 ケース分ずつ出力せよ。
なお、最後には改行を出力せよ。

入力例 1

5 6
2
3
5
0
1
3

出力例 1

0
5
2
4
1
  • まず 2番のCDを聴くので、0 番のCDは 2 番のCDケースに入れます。
  • 次に 3番のCDを聴くので、2 番のCDは 3 番のCDケースに入れます。
  • このように各CDを順に聴いては片付けるを繰り返すと、下図のようにCDの位置が入れ替わります。

入力例 2

3 5
0
1
1
1
2

出力例 2

0
1
3
  • 同じCDを連続して聴いた場合もあります。
  • この場合は 1 枚目としてCDプレイヤーに入っている 0 番のCDを聴くので、CDケースに入っているCDは入れ替わりません。
  • 2 枚目としては 1 番のCDを聴くので、1 番のCDケースに 0 番のCDが入ります。
  • 3 枚目と 4 枚目は 2 枚目でCDケースに入れた 1 番のCDを聴くので入れ替わりは起きません。
  • 最後に 2 番のCDを聴くので 2 番のCDケースに 3 番のCDが入ります。

入力例 3

5 0

出力例 3

1
2
3
4
5
  • 何もCDを聴かなかった場合は入れ替わりは起きません。

入力例 4

10 7
2
8
5
3
3
8
1

出力例 4

8
0
5
4
3
6
7
2
9
10

入力例 5

5 7
3
4
3
1
2
2
0

出力例 5

3
1
2
4
5

Source Name

ARC 007
C - 節約生活

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

　高橋君は有料の衛星放送を見ようとしています。有料衛星放送はお金を払わないと見ることが出来ませんが、高橋君はその契約を行なっていません。
　しかし、有料衛星放送はどのような内容を放送しているか視聴者がわかるように、無料でも視聴可能な時間が定期的に存在し、視聴可能な時間とできない時間が交互に繰り返されます。このような視聴可能な時間とそうでない時間を視聴パターンと呼ぶことにします。
　視聴パターンは o と x から成り立っており、図 1 で示すように視聴可能な時間を o の個数、視聴できない時間を x の個数で表しています。
図 1:視聴パターンの例(入力は10文字以下なので、この入力はテストに存在しません)
　一度テレビを点けると途切れることなくこの視聴パターンが繰り返される。また、テレビは一度点けると消すことはできません。
　高橋君は複数のテレビを点けるタイミングをずらして並行して利用することで、無料でも常にいずれかのテレビで視聴ができる方法を思いつきました。
　例えば図 1 の視聴パターンの場合は図 2 で示すように 5 分後にもう 1 台テレビを点ければ常に視聴ができます。
図 2:2 台のテレビで常に視聴する例
　その場合高橋君が用意しなければいけない最低限のテレビの台数を答えなさい。
　なお、必要なテレビを全て点け終えるまでの間には視聴できない時間があっても構いませんが、全てのテレビを点けてからは常にいずれかのテレビで視聴ができないといけません。

入力

入力は以下の形式で標準入力から与えられる。 
c_0c_1‥‥c_{N-1}
  • 入力は 1 行のみで視聴パターンを表す長さ N(1≦N≦10) の文字列が与えられる。
    • 視聴パターンは o と x から成り、i+1(0≦i≦N-1) 番目の文字 c_i はテレビを点けてから i 分から i+1 分の間はテレビが以下の状態であることを意味する。
      • o:視聴可能である。
      • x:視聴できない。
    • 視聴パターンは少なくとも 1 つの o を含む。
    • テレビは最初にテレビをつけてから j(j : 正の整数) 分後にのみ点けることができる。

出力

常にいずれかのテレビが視聴可能であるために用意しなければいけないテレビの台数の最小値を標準出力に 1 行で出力せよ。
必要なテレビを全て点け終えるまでの間は視聴できない時間があっても構わないが、全てのテレビを点けてからは常にいずれかのテレビが視聴できないといけない。
なお、最後には改行を出力せよ。

入力例 1

oxoxx

出力例 1

3
  • 以下の図のタイミングでテレビを点けることで 3 台のテレビで常に視聴ができます。

入力例 2

oxxxxoooo

出力例 2

2
  • 1 台目のテレビを点けてから 4 分目に 2 台目のテレビを点けることで 1 分目から 5 分目直前までは視聴が不可能だが、5 分目以降は視聴が可能になります。

入力例 3

ox

出力例 3

2
  • 1 台目のテレビを点けてから 1 分後に 2 台目のテレビを点けることで 2 台で視聴可能です。

入力例 4

o

出力例 4

1
  • 視聴パターンに視聴できない時間が含まれない場合もあります。

入力例 5

xxxoxo

出力例 5

4

Source Name

ARC 007
D - 破れた宿題

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

　高橋君は数学の宿題で出された、等差数列の初項と公差を答える問題を解いています。
　隣接する 2 つの数字間の差が定数である数字の連続のことを等差数列といい、最初の数字を初項、定数である数字間の差を公差、最後の数字を末項と呼びます。
　ただ高橋君はうっかり宿題の数列を空白やカンマで区切ることなく 0から 9 の数字で構成された 1 つの文字列としてノートに写しとってしまいました。
　さらにそのノートの扱いが雑だったので、ノートの一部を破って切り離してしまいました。
　破れて切り離されてしまったのは初項と末項の部分だけで、少なくとも初項の一部分が残っているのを確認しました。
　そのような文字列が与えられるので、元の数列を推測してその初項と公差を答えなさい。

　なお、初項と公差は 1 以上の整数であり、解が複数ある場合は初項が最も小さいものを答え、初項が等しい解が複数ある場合は公差が最も小さいものを答えなさい。
　また、003 や 012 のように不必要な 0 が前に付属している数字は写しとった数列には含まれていませんでした。

入力

入力は以下の形式で標準入力から与えられる。 
c_{0}c_{1}‥‥c_{N-1}
  • 入力は 1 行のみで等差数列の一部である長さ N の文字列が与えられる。
  • 文字列は 0-9 から成り立っている。

部分点

テストデータには以下の 4 種類のテストデータセットのいずれかに含まれており、それぞれのデータセットに含まれているテストデータは以下に示すように与えられる文字列 N の範囲が異なっている。
あるテストデータセットに含まれているテストデータ全てに対して正しい解を出力できると、それ以外のテストデータセットで不正解を出力しても以下のように部分点が与えられる。
  • level1 ( 25 点) : 1≦N≦4
  • level2 ( 25 点) : 1≦N≦6
  • level3 ( 25 点) : 1≦N≦200
  • level4 ( 25 点) : 1≦N≦1,000

出力

初項と末項の一部が切り離されている可能性のある等差数列に対して考えうる初項と公差を空白区切りで標準出力に 1 行で出力せよ。
解が複数ある場合は初項が最も小さいものを答え、初項が等しい解が複数ある場合は公差が最も小さいものを出力せよ。
なお、最後には改行を出力せよ。

入力例 1

1

出力例 1

1 1
  • 前後に文字が続く 1 つの数字の可能性もありますが、最も小さい初項は数字が切り離されていない場合の 1 です。
  • 公差も任意の正の整数が考えられますが、最も小さい公差は 1 です。

入力例 2

0203

出力例 2

10 10
  • 02 は数字として認められないので 2 は初項ではありません。
  • 初項の 10 の 1 が切り離されており、末項として 30 の 0 が切り離された数列であり、元の数列は 102030です。

入力例 3

456789101112131415

出力例 3

4 1
  • 数列のどこも欠けていない初項 4、公差 1 の等差数列です。

入力例 4

579111315171921232

出力例 4

5 2
  • 末項の 25 の 5 の部分が欠けている等差数列です。

入力例 5

001131261391521651

出力例 5

100 13
  • 初項の 100 と末項の 178 の一部が欠けています。

Source Name

ARC 007