問題文

実況「素晴らしい！フィギュアスケート界に彗星の如く現れた埼大選手、魅せました！この演技どうご覧になりましたか？」

解説「えーそうですね。ミスらしいミスもなく、技の完成度も高かったので、かなりの高得点を期待できます。」

実況「そんな埼大選手ですが、彼はファンサービスにも一流のこだわりを持つことで知られていまして、滑走後の挨拶中は以下の動作を行います。」

• 1つあるゲートから滑り始め、1周5000mのスケートリングを丁度時計回りに1周してゲートから退場し、キス&クライに向かいます。
• 常に寸分狂わず 1 m/s の速さで滑ります。
• 滑っている場所に落ちているぬいぐるみを全部自分で拾っていきます。
• 滑っている場所にちょうど投げ入れられたぬいぐるみもキャッチしていきます。

実況「また、観客も訓練されていまして、以下のように洗練されたぬいぐるみの投げ入れを行います。」

• 埼大選手が挨拶周りを開始してから、リストに書いた指定時刻の10秒後にぴったり指定した位置に届くように、ぬいぐるみを投げ込みます。

解説「このぬいぐるみは大きさが無視できる程度に小さいので、同じ場所に複数のぬいぐるみが落ちていることがあるようですね。また、埼大選手はスピードを緩めることなく、いくつでもぬいぐるみを拾う事ができます。すごいですよね。」

実況「それはすごい。さあ埼大選手、いくつのぬいぐるみを拾うのでしょうか！」

入力

入力は以下の形式で標準入力から与えられます。

N
t_{1} d_{1} m_{1}
t_{2} d_{2} m_{2}
:
t_{N} d_{N} m_{N}

• N : ぬいぐるみを投げ入れる人の数
• t : 埼大選手が滑り始めた時を0秒として、それからの経過時間(秒)
• d : 埼大選手が滑り始めた場所を0mとして、それから時計回りにスケートリンクを移動した距離(m)
• m : 投げるぬいぐるみの数
• 1 \leq N \leq 10000, 0 \leq t \leq 4990, 1 \leq d \leq 5000, 1 \leq m \leq 10 (N, t, d, m は整数)

出力

拾う事のできるぬいぐるみの総数を出力してください。

問題文

サイタマでは年に一度の山車のお披露目会がある。もっとも美しい山車には賞金が出ると聞いた埼大くんと埼大くんの友達はお披露目会に参加することにした。
お披露目会の会場に向かう途中、隣街の男衆が山車に乗って邪魔をしてきた。男衆が山車の右側にa人、左側にb人乗っているようだ。
どうしても賞金が欲しい埼大くんたちは完璧な山車を披露したいため、会場に到着するまでに男衆を全員振り払う必要がある。

単位時間内にとりうる山車の動きは次の3パターンである。

1. 左に90度向きを変えてから一マス前進する。

2. 右に90度向きを変えてから一マス前進する。

3. 向きを変えずに一マス前進する。

1.の動きにより右側に乗っている人を、2.の動きにより左側に乗っている人を、一人づつ振り落とすことができる。
しかし必要以上に向きを変えたくないため、1.の動きをa回行った以後は1.の、2.の動きをb回行った以後は2.の動きを行わない。

埼大くんたちは地図を見てルートを決めることにした。

地図の縦の長さは h 、横の長さは w で、通れる場所は '.' 、通れない場所は '#' である。通過する街はマス目状に区切られており、地図上では i行j 列目のマス は c(i,j) で表される。
現在地は c(2,2) 、会場は c(h-1,w-1) である。現在地と、会場は '.' であることが保証されている。
地図の一番外側はすべて '#' で囲まれている。 c(1,1)～c(1,w) に面している方面の方角が北であり、埼大くんたちは最初南を向いている。

埼大くんたちは無事にお披露目会に参加できるかどうかを判定せよ。

制約

• 1 \leq a, b \leq 15
• 3 \leq h, w \leq 15

問題文

天使の中に悪魔が紛れ込んだ。あなたは上司にこれを報告しなければならないが、上司は『最大でどれだけ悪魔が紛れ込んだか調査しろ』と命じてきた。

「一体、誰が悪魔なんですかね」

あなたが言うと、彼らは『あいつが悪魔だ』と指摘し合った。誰も同じ者を指ささずバラバラの者を指摘していた。

どうやら天使は必ず悪魔を、悪魔は必ず天使を指摘しているようだった。

最大で何人の悪魔がいるだろうか。その数を報告してほしい。

ただし、あなたや上司は天使でも悪魔でもなく、入力で与えられる『彼ら』には含まれない。また、『彼ら』はそれぞれ天使か悪魔のどちらかである。

入力

入力は以下の形式で標準入力から与えられる。

N
A_{1}
A_{2}
:
A_{N}

一つの整数 N と N 行の整数からなる。

i+1行目は番号iの者が番号A_{i}の者を指さしたことを示している。

ただし、2 \leq N \leq 10^5、1 \leq A_{i} \leq N であり、 相異なる任意の i, j について A_i≠A_j である。

出力

考えられる悪魔の数として最大のものを一行に出力せよ。

どのように天使と悪魔を決めても矛盾が生じるなら-1を出力せよ。

問題文

ある日 S 君は環状の道路をドライブすることにした。

この環状道路には等間隔に休憩所があり、0 から M - 1 までの番号が振られている。
S 君は0番の休憩所からスタートし、0 → 1 → 2 → … → (M - 2) → (M - 1) → 0 → 1 → 2 → … と巡回する。

S 君の車は，燃料1リットルで休憩所を1つ進むことができる。
しかし燃料の補充の際は、あらかじめ用意した、補充量が a_1 , a_2 , a_3 ,…, a_{N-1} , a_{N} である N 個の燃料タンクから 1 つ以上選んで補充しなけらばならない。
燃料タンクは補充を行うと空になるため、同じ燃料タンクを2回以上選ぶことはできない。 この車は走り出すと燃料を使い切るまで止まらないため、ある特定の休憩所に停まりたい場合は、ぴったりそこで燃料が尽きるように補充する燃料タンクを選ばなければならない。

S 君は番号Lの休憩所で友人と待ち合わせをしており、車の燃料が0の状態で燃料タンクを複数選んで補充し、番号0の休憩所からスタートして番号Lの休憩所に停まりたい。
しかし環状道路をX周以上すると市の交通条例違反になってしまう。

S 君がX周以内に番号Lの休憩所に停まることができるような燃料タンクの選び方は存在するかどうかを判定せよ。

燃料の補充は最初の1回のみである。また、スタート直後は1周目と定義し、再び番号0の休憩所にたどり着いた時点で次の周回とする。

制約

• 1 \leq N \leq 10000
• 3 \leq M \leq 1000
• 1 \leq L \leq M - 1
• 2 \leq X \leq 10000
• 1 \leq a_i \leq 10000

問題文

数列S = { 1 } が渡されます。以下の2種類のクエリを合計q回実行してください。

A,i,j ： S[k] = i を満たすいずれか一つのkに対して、「S[k]を取り除き、その位置に数列V = { i,j,i } を挿入する」という操作を行う。

B,i,j ： 今までのクエリでできる可能性のある数列すべてに対して、 「S[a] = i, S[b] = jを満たし、|a-b|が最小になるときのa, bに対し、{ S[k] | (min(a, b) < k < max(a, b)) } に含まれる数の種類」を求めてから、 その中で最も小さい数を出力する。

制約

3 \leq q \leq 200000

i,jは非負整数です。

1 \leq i,j \leq q

最初の二つは必ずクエリAが渡されます。

クエリAについて、iは数列に存在している数のみ、jは数列に存在しない数のなかで、最も小さい正の整数が出現します。

クエリBについて、i,jは数列に存在している数のみ出現し、i \neq jです。

入力例 1

7
A 1 2
A 1 3
A 2 4
A 2 5
B 3 5
A 1 6
B 3 6

出力例 1

2
1

{ 1 }

これが初期状態です。以降できる可能性のある数列を列挙していきます。

• A,1,2

{ 1,2,1 }

• A,1,3

{ 1,3,1,2,1 } , { 1,2,1,3,1 }

• A,2,4

{ 1,3,1,2,4,2,1 } , { 1,2,4,2,1,3,1 }

• A,2,5

{ 1,3,1,2,5,2,4,2,1 } , { 1,3,1,2,4,2,5,2,1 } , { 1,2,5,2,4,2,1,3,1 } , { 1,2,4,2,5,2,1,3,1 }

• B,3,5

各数列に対して、最も距離の近い3と5の間にある数字の種類を求めていきます。

各数列における値は2,3,3,2なので2を出力します。

• A,1,6

{ 1,6,1,3,1,2,5,2,4,2,1 } , { 1,6,1,3,1,2,4,2,5,2,1 } , { 1,6,1,2,5,2,4,2,1,3,1 } , { 1,6,1,2,4,2,5,2,1,3,1 } , { 1,3,1,6,1,2,5,2,4,2,1 } , { 1,3,1,6,1,2,4,2,5,2,1 } , { 1,2,5,2,4,2,1,6,1,3,1 } , { 1,2,4,2,5,2,1,6,1,3,1 } , { 1,3,1,2,5,2,4,2,1,6,1 } , { 1,3,1,2,4,2,5,2,1,6,1 } , { 1,2,5,2,4,2,1,3,1,6,1 } , { 1,2,4,2,5,2,1,3,1,6,1 }

• B,3,6

各数列における値は1,1,4,4,1,1,4,4,1,1,4,1なので、1を出力します。

問題文

埼大君はMaximum小学校の職員で、給食の献立作成担当をしています。
そろそろ献立表を作らなくてはいけない時期になってきたので、埼大君は献立表を考えることにしました。
献立はバランスが大事です。和食ばかりの献立や、洋食ばかりの献立では生徒に飽きられてしまいます。

そこで、まずその日に出すメニューのジャンルを決めることにしました。メニューは、

• 和食のメニュー
• 洋食のメニュー
• 中華のメニュー
• 和食洋食混合のメニュー
• 和食中華混合のメニュー
• 洋食中華混合のメニュー
• 和・洋・中ごちゃまぜメニュー

の7種類です。

今回考えたいのは「どの連続したK日間でも同じジャンルが含まれるメニューを出す日をL日以下」という条件を満たしたN日間の給食の献立です。

ここで、混合メニューやごちゃまぜメニューを出すと、その中に含まれるすべてのジャンルを出したことになります。
例えば和洋混合メニューを出したとすると、その日は和食メニューと洋食メニューを両方出したことになります。
詳しくは下の表を参照してください。

さて、それを見ていた組み合わせマスターのあなたはふと思いました。

「これは、何通り考えられるだろう、、、？？？」

この条件を満たす献立の組み合わせの総数を求めてください。

なお、答えは非常に大きくなる可能性があるため、1000000007の余りの形で出力してください。

条件について

N = 5, K = 5, L = 3として考えます。

この時、例1ではすべてのジャンル(和食・洋食・中華)が5日間のうち3日以内になってい るので、条件を満たしています。

一方、例2では洋食が5日間のうち4日間登場してしまっているので、条件を満たせていないこと になります。

制約

• K \leq N \leq 365
• 2 \leq K \leq 5
• 1 \leq L \leq K

入力例 1

3 3 1

出力例 1

6

入力例 2

15 3 2

出力例 2

213221133

1000000007の余りの形で出力してください。

入力例 3

365 5 3

出力例 3

792323641

入力例 4

5 5 1

出力例 4

0

献立が作れない可能性もあります。

問題文

巷では「Saitoon」という二人対戦ゲームが流行っています。

今年も「Saitoon」の大会「Maximum-Saitoon-cup」(Maximum-cup-2018とは無関係です)が大盛況のうち無事に幕を閉じました。

この大会の運営の1人である埼大君は同運営の記録係から送られてきた大会の対戦結果の確認作業を行おうとしています。

大会の対戦結果はBNF記法で以下のように管理されています。

また、大会の対戦結果についての詳細は以下の通りです。

• 大会はトーナメント形式で行われています。
• 対戦結果は <CompetitionLog> として送られてきます。
• 大会の各試合は <GameResults> で表されます。また、各試合は必ずどちらかが負け、どちらかが勝ちます。
• 各試合の対戦相手は隣り合った <PlayerData> で表されます。
• <PlayerID> は選手固有のIDについて表しています。中身が <number> のときはその数字が、 <GameResults> のときはその試合の勝者の <PlayerID> が当てはまります。
• <WinningOrLosing> はその試合でその選手が勝ったかどうかを表していて、oのときは勝ち、xのときは負けを表しています。
• 参加選手のIDは対戦結果を左から見ていった際に、各選手の <number> で表現される <PlayerID> の出現順に1～Nまで割り振られています。

この対戦結果と手元にある「各選手が何勝したかについてのデータ」を照合させて、正しかったら埼大君の仕事は完了です。

さて、さっそく照合を行おうとした埼大君ですが、ここで大変なことが起きていることに気が付きました。

送られてきた対戦結果の一部の情報がなくなっているのです。

幸い、手元に｢各選手が何勝したかについてのデータ｣があるため、なんとか復元できそうですが、埼大君の力では難しいようです。

そこで、埼大君は優秀なプログラマであるあなたに復元を頼むことにしました。

あなたの仕事は「各選手が何勝したかについてのデータ」が正しいと仮定した際の対戦結果の復元することです。

欠落した箇所は｢?｣で表されているので、そこにもともと何があったかを調べてください。

制約

• 12 \leq |S| \leq 200
• 2 \leq N \leq 16
• ?の数は1個以上min( \frac{|S|}{2},50)個以下です。
• 対戦結果の復元は一意に定まることが保証されています。

入力例 1

[([(1)o][(2)x]??][([(?)x][(4)o])x]
4
2 0 0 1

出力例 1

[([(1)o][(2)x])o][([(3)x][(4)o])x]

選手のIDは左から1～Nと振られるので、3つ目の「?」には「3」が入ります。

復元した対戦結果は1の選手が2勝、2の選手が0勝、3の選手が0勝、4の選手が1勝となり、手元にあるデータと一致します。

入力例 2

?([?[(?)o]?(?([(2?o]??[?3)o][?4?x??x])?]??5)x??x???][????])x?[??)o?
7
1 2 1 0 0 1 1

出力例 2

[([([(1)o][([([(2)o][([(3)o][(4)x])x])o][(5)x])x])x][(6)o])x][(7)o]

復元先は必ず一意に定まります。

問題文

N の地点と M 個の通路があります。 N 個の地点は 1 から N まで 1 つずつ番号が振られていて、 i 個目の通路は地点 v_{i} と地点 u_{i} を長さ w_{i} [m]で結んでいます。

埼大君は、そこである一風変わったスタンプラリーに参加しようとしています。
内容は、地点 a_{1} でスタートして最初にスタンプを押した後、地点 a_{2} から 地点 a_{K} まで、 K 個の地点を順番にめぐり、スタンプを押していくというものです。

このスタンプラリーには成績が付き、その成績は

• s_{i} :=地点a_{i} でスタンプを押してから地点a_{i+1} でスタンプを押すまでに移動した道のり[m]

と定義したときに、max({s_{i} | 1 ≤ i ≤ K-1})で表され、この値が小さいほど成績がよくなります。

地点同士は高々一本の通路で繋がっていて、通路同士は地点以外では交わりません。また、一方通行の通路はありません。すべての地点は、どの地点からでも徒歩で通路をたどれば必ずたどり着くことができます。

このスタンプラリーの変わった点は、参加者にはスタート時に Q 個の魔法の石が渡されることにあります。

この石にはそれぞれ相異なる数字 b_{1} ~ b_{Q} が書かれていて、この石を割ることで、その石が書かれている数字の地点までワープできます。
割った石は二度と使うことはできません。そして、ワープ中に移動した道のりは 0 メートルとして記録されます。
また、魔法の石はどの場所にいても使うことができます。したがって、対応する魔法の石があれば、ある地点からその次の地点に直接ワープすることもできます。
魔法の石は必ずしも使い切る必要はありません。

魔法の石を上手く活用することで、どこまで成績をよくできるか求めてください。

制約

• 2 \leq N \leq 300
• N-1 \leq M \leq N(N-1)/2
• 1 \leq v_i,u_i \leq N(1 \leq i \leq M)
• v_i \neq u_i(1\leq i \leq M)
• 1 \leq w_i \leq 10^9(1 \leq i \leq M)
• 2 \leq K \leq N
• 1 \leq a_i \leq N(1 \leq i \leq K)
• i \neq j なら a_i \neq a_j(1 \leq i,j \leq K)
• 0 \leq Q \leq N
• 1 \leq b_i \leq N(1 \leq i \leq Q)
• i \neq j なら b_i \neq b_j(1 \leq i,j \leq Q)

入力例 1

6 5
1 2 5
1 3 2
2 4 3
2 5 2
5 6 1
3
1 3 6
2
2 4

出力例 1

3

最初に地点1でスタートして、スタンプを押します。

その後、地点3まで徒歩で移動して、スタンプを押します。(s_1 = 2)

その後、2と書かれた魔法の石を割り、地点2までワープしたのち、地点6まで徒歩で移動してスタンプを押します。(s_2 = 3)

この行動がこのケースでは最適で、答えは3となります。