問題文

コード川柳コーナーでは、プロコンに関する「あるある」を五七五の調べに乗せた川柳を募集しています。

そこで、高橋君はコード川柳コーナーに投稿する川柳を作りました。

高橋君が作った川柳が五七五になっているかどうかをチェックするプログラムを作成してください。

ただし五七五になっている川柳とは、5 文字、7 文字、5 文字の文字列をこの順に並べたものを指すこととします。

入力例1

using namespace std

出力例1

invalid

川柳としては素晴らしい作品ですが、この問題においては五七五になっていません。

入力例2

using namespa cestd

出力例2

valid

問題文

ボードゲームにはダイス（サイコロ）を使うゲームが少なくありません。そこで、ダイスについての問題を出したいと思います。

問題： 6 面ダイスを N 個振るとき、ダイスの目の和として出る確率が最も高い値は何か？そのような値が複数ある場合は、そのうち最も小さい値を答えよ。

入力例1

2

出力例1

7

ダイスを 2 個振るとき、ダイスの目の和として出る確率は以下の通りです。

• 2 : 1/36
• 3 : 2/36
• 4 : 3/36
• 5 : 4/36
• 6 : 5/36
• 7 : 6/36
• 8 : 5/36
• 9 : 4/36
• 10 : 3/36
• 11 : 2/36
• 12 : 1/36

このうち最も確率が高い値は 7 であるため、7 と出力します。

入力例2

3

出力例2

10

最も出る確率の高い値は 10 と 11 の 2 つありますが、このうち小さい方の 10 を出力してください。

入力例3

1

出力例3

1

問題文

寿司とは「シャリ」の上に「ネタ」をのせた食べ物です。

りんごさんは N 個の寿司を積み上げることで寿司タワーを作ろうとしています。N 個の寿司があるということは、N 個のシャリと N 個のネタで、合計 2N 個のパーツがあるということですが、これらのパーツをある順番で積んでいきたいと思っています。

寿司を 1 つ積む方法には以下の 3 通りの方法があります。

• そのまま積む：シャリ、ネタの順に積まれることになる。
• ひっくり返して積む：ネタ、シャリの順に積まれることになる。
• 分解して積む：寿司を分解してシャリとネタを分け、それぞれを別々に積む。

例えば、3 個の寿司を下から順に「ネタ、シャリ、ネタ、ネタ、シャリ、シャリ」と積みたい場合は以下のように積むことができます。

1. 寿司を 1 つ分解してネタを積む。シャリの方は後で積むために取っておく。
2. 寿司をそのまま積む。
3. 寿司をひっくり返して積む。
4. 取っておいたシャリを積む。

寿司を分解するのは手間がかかるので、りんごさんはできるだけ分解する寿司の個数を少なくしたいと思っています。目的の寿司タワーを作るために分解する寿司の個数の最小値を求めてください。

入力例1

3
101100

出力例1

1

問題文中の例の通りです。下図は積み方の例を表しており、白い丸はシャリ、赤い長方形はネタを表しています。

入力例2

5
0000111011

出力例2

3

問題文

高橋君は以下のようなリズムゲームに挑戦しようとしています。

• 大きなボタンが N 個ある。このボタンを 1 つ押すには人がちょうど 1 人のる必要があり、他の方法で押すことはできない。
• 1 人の人が同じ時間に 2 つ以上のボタンを押すことはできない。
• i 番目のボタンを時刻 S_i から時刻 T_i までの間押し続けると 1 点が得られる。このとき、必ずしも同じ人が最初から最後まで押し続ける必要はなく、途中で押す人を交代しても構わない。
• ボタンにのったり降りたりするためにかかる時間や、ボタンを押している人を交代するためにかかる時間は無視できるものとする。

高橋君は何人かで協力してこのゲームをプレーすることで N-1 点以上を取りたいと思っています。N-1 点以上を取るために必要な人数の最小値を求めてください。

入力例1

4
1 4
1 2
2 3
3 4

出力例1

1

下図はそれぞれのボタンについて、押し続けると点が得られる時間を表しています。ボタン 1 以外のボタンを 1 人で全て踏むと 3 点を得ることができます。

入力例2

5
5 11
2 4
3 4
2 7
5 7

出力例2

2

入力例3

4
1 2
1 2015
2015 100000
99999 100000

出力例3

2

問題文

ショートコーディングコンテスト「短縮王」は、いかに短いコードで問題を解けるかを競うコンテストです。短縮王に参加する前に、まずはウォーミングアップをしてみましょう。

以下のようなプログラミング言語「!-! 言語」を考えます。

• プログラムは、単項演算子 -, ! が 0 個以上並んだ文字列として記述される。
• プログラムはちょうど 1 つの -256 以上 256 以下の整数を入力として受け取り、入力値に単項演算子を 後ろから順に 適用して演算を行い、最終的な値を出力する。
• 単項演算子はそれぞれ以下のような計算を行う。
  • -：値の正負を反転させる。例えば 29 を -29 に、-89 を 89 に、0 を 0 にする。
  • !：0 なら 1 に、0 以外なら 0 にする。例えば 29 を 0 に、-89 を 0 に、0 を 1 にする。

例えば、!-!- というプログラムに 5 を入力として与えた場合は以下のように動作します。

• 後ろから 1 個目の演算子は - であり、5 が -5 になります。
• 後ろから 2 個目の演算子は ! であり、-5 が 0 になります。
• 後ろから 3 個目の演算子は - であり、0 が 0 になります。
• 後ろから 4 個目の演算子は ! であり、0 が 1 になります。
• 1 を出力して終了します。

!-! 言語のプログラムが与えられるので、-256 以上 256 以下の全ての整数の入力に対して同じ結果を出力する最も短い !-! 言語のプログラムを出力してください。

入力例1

---!!-!--

出力例1

-!

入力例2

!!

出力例2

!!

入力例3

----------

出力例3

(空文字列)

空文字列もプログラムとして正しいです。なお、答えが空文字列の場合も末尾に改行を出力すること。

問題文

あるピアニストは足でピアノを演奏したいと思い、特別な大きなピアノを用意しました。このピアノには鍵盤が 10^{100} 個あり、それぞれの鍵盤には順にド、レ、ミ、ファ、ソ、ラ、シ、ド、レ・・・と音が割り当てられています。鍵盤を 1 回踏むと、踏んだ鍵盤に割り当てられた音が 1 回鳴ります。

ピアニストが考えている理想の演奏は以下の通りです。

• ド〜シの音をそれぞれちょうど C_1 ～ C_7 回ずつ鳴らす。同じ音であればどの鍵盤を踏んでも良い。
• ある鍵盤を踏んだ直後は、その隣の鍵盤しか踏むことはできない。つまり、i 番目の鍵盤を踏んだ直後は i-1 番目または i+1 番目の鍵盤しか踏むことはできない。
• ドの音から始まって、ドの音で終わる。どのドの音の鍵盤から始めても、どのドの音の鍵盤で終えても良く、それらの鍵盤は一致している必要はない。

ピアニストが理想の演奏を行うことができるかどうかを判定してください。

入力例1

2 1 1 1 1 1 1

出力例1

YES

ド、レ、ミ、ファ、ソ、ラ、シ、ドの順に鍵盤を踏むことで理想の演奏を行うことができます。

入力例2

1 1 1 1 1 1 1

出力例2

NO

入力例3

3 1 0 10000000000 10000000000 0 1

出力例3

NO

入力例4

1 0 0 0 0 0 0

出力例4

YES

問題文

Code Festival 2015 ではスタンプラリーが開催されます。スタンプラリーでは、あるコンテンツに参加するとそのコンテンツに対応するスタンプを 1 つ押してもらえます。

高橋君は全てのコンテンツのスタンプを集めたいと思っています。そこで高橋君は、以下のような状況を想定してスタンプラリーの予行演習を行いました。

• 会場は N 個の部屋と、2 つの部屋を繋ぐ N-1 本の通路からなる。
• どの 2 つの部屋の間も、いくつかの通路を辿ることで移動することができる。
• コンテンツは N 種類あり、部屋 i (1 ≦ i ≦ N) ではコンテンツ i が行なわれている。

高橋君はこの予行演習で、以下の疑似コードのようなアルゴリズムでスタンプラリーを進めました。なお、このアルゴリズムは必ず全てのスタンプを 1 つずつ押してもらった後に停止することが保証されています。

部屋 1 に入る
以下を繰り返す：
  今いる部屋のスタンプをまだ押してもらっていない場合：スタンプを押してもらう
  X = 今いる部屋からちょうど 1 本の通路を辿って移動できる部屋の集合
  X の中にまだ訪れていない部屋がある場合：
    そのうち最も番号が小さい部屋に移動する
  そうでない場合：
    今いる部屋が部屋 1 である場合：スタンプラリーを終了する
    そうでない場合：X のうち最も部屋 1 に近い部屋に移動する

高橋君が i (1 ≦ i ≦ N) 番目に押してもらったスタンプはコンテンツ C_i のスタンプでした。このとき、予行演習で用いた会場の構造として考えられるものは何通りあるでしょうか？会場の構造は N-1 本の通路が繋いでいる部屋の組の集合で表されるものとします。なお、答えは非常に大きな数となることがあるため、10^9+7 で割った余りを求めてください。

入力例1

4
1
2
4
3

出力例1

3

下図のような 3 通りの構造が考えられます。

入力例2

2
2
1

出力例2

0

入力例3

30
1
28
14
7
27
17
25
4
26
2
10
19
11
12
13
23
29
20
18
3
16
24
22
5
30
9
15
6
21
8

出力例3

348275800

問題文

Aさんは焼肉の達人です。

Aさんは N 枚の肉と、長さが M の細長い網と、炭で焼肉をしようとしています。肉 i の長さは L_i です。網の片方の端の座標を 0、もう片方の端の座標を M とします。

最初、肉 i は座標 S_i の位置に置いてあります。つまり、網の座標 S_i から座標 S_i+L_i までの区間を肉 i が覆っていることになります。Aさんは、いくつかの肉を取り除いてから網の下の炭に火をつけて焼くことにしました。

肉を焼くとき、肉が 2 枚以上重なっている部分は生焼けになってしまいます。また、当然ですが焼く前に取り除いた肉は食べられません。

取り除く肉をうまく選んだとき、生焼けにならずに食べられる部分の長さの和の最大値を求めてください。生焼けにならずに食べられる部分の長さの和を別の言い方で表すと、ちょうど 1 枚の肉で覆われた網の区間の長さの和と同じです。

入力例1

3 7
0 4
3 4
1 5

出力例1

6

下図はそれぞれ、最初に肉の並べたときの様子、肉 3 を取り除いて焼いたときの様子を表しています。緑の枠で囲った部分が生焼けにならずに食べられる部分となります。

入力例2

8 13
7 2
7 2
1 4
2 5
4 2
11 1
10 1
10 2

出力例2

9

問題文

りんごさんは、ヒモの付いた N 個の風船を繋げて遊んでいます。風船 i (1 ≦ i ≦ N) のヒモの長さは L_i です。りんごさんは風船 1 のヒモを手に持ち、風船 i (2 ≦ i ≦ N) のヒモを風船 P_i にくくりつけました。このようにいくつかの風船が繋がったものを「風船ツリー」と呼ぶことにします。

風船ツリーの高さは、風船ツリーに含まれる風船のうち最も高いものの高さとします。ただし、風船 1 の高さは L_1 であり、風船 i (2 ≦ i ≦ N) の高さは風船 P_i の高さに L_i を足した値であるとします。

りんごさんは、いくつかのヒモをほどくことで風船ツリーの高さをちょうど天井の高さと同じにしたいと思いました。また、そのためにほどく必要のあるヒモの本数の最小値を知りたいと思いました。風船 i (2 ≦ i ≦ N) のヒモをほどくと、風船 i とそれに繋がった風船が全て飛んで行ってしまい、風船ツリーから取り除かれます。

天井の高さとして考えられる値が Q 個あるので、それぞれについて、風船ツリーの高さをちょうど天井の高さと同じにするためほどく必要のあるヒモの本数の最小値を求めてください。

入力例1

5
1 1 2 2 2
1 2 2 1
2
2
3

出力例1

3
1

下図はそれぞれ、最初の風船ツリー、高さを 2 にした風船ツリー、高さを 3 にした風船ツリーの様子を表しています。赤い×印は、ヒモをほどく箇所を表しています。

入力例2

10
10 5 6 4 2 2 3 1 1 5
1 1 2 2 3 5 7 7 2
5
10
12
15
17
21

出力例2

2
-1
4
4
0

問題文

高橋君は Bucket Festival という大会に参加しようとしています。Bucket Festival ではバケツを使った様々な競技が行われますが、力に自信がある高橋君は「N 個のバケツ」という競技に参加することにしました。

「N 個のバケツ」のルールは以下の通りです。

• N 人 1 チームで参加する。チームのメンバーには 1～N の番号を割り振る。
• チームメンバー N 人は番号順に時計回りに円周上に並んで立つ。i (1 ≦ i ≦ N-1) 番のメンバーと i+1 番のメンバー、N 番のメンバーと 1 番のメンバーは隣り合うことになる。
• 隣り合った 2 人のメンバーの間には水の入った合計 N 個のバケツが置かれる。どのバケツにどれくらいの量の水を入れるかはチームで相談して決めることができる。ただし、水の量は全て整数値となっていなければならない。
• チームのメンバーは、自分の両側にある 2 つのバケツを持ち上げる。それぞれのバケツは 2 人のメンバーが協力して持ち上げることになる。N 個のバケツを全て持ち上げられれば成功となり、バケツに入った水の量の合計がスコアとなる。

高橋君はできるだけ高いスコアを取るためにはどのバケツにどれくらいの量の水を入れれば良いかを考えています。そのためにまず、チームメンバーの力を測りました。そして、i (1 ≦ i ≦ N) 番のメンバーの力が S_i であることが分かりました。力が p のメンバーは、自分が持つ 2 つのバケツの水の量の平均が p 以下であればバケツを持ち上げることができます。つまり、2 つのバケツの水の量をそれぞれ w,v とすると、(w+v)/2 ≦ p であれば持ち上げることができます。

高橋君のチームは即席のチームであるため、チームメンバーが変更になることがあります。メンバー変更は合計 Q 回行われ、i (1 ≦ i ≦ Q) 回目の変更では P_i 番のメンバーが変更となり、力が X_i であるメンバーが新たに P_i 番のメンバーとして加わります。それぞれのメンバー変更ごとに、変更後の時点で高橋君のチームが取ることのできるスコアの最大値を求めてください。

入力例1

4
2 2 2 2
2
1 3
3 0

出力例1

8
6

下図はそれぞれのメンバー変更の直後に最大スコアを取るためにどのバケツにどれくらいの量の水を入れれば良いかを表しています。丸はメンバーを表しており、丸の中の数はメンバーの力、丸の左上の数はメンバーの番号を表しています。バケツの絵の中に書かれた数は、バケツに入れる水の量を表しています。

入力例2

6
0 0 0 0 0 0
6
3 10000
4 10000
6 10000
2 10000
5 10000
1 10000

出力例2

0
20000
20000
20000
40000
60000