A - ヘビがヘビー

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

ヘビーなヘビが N 匹います。
これらのヘビのヘビー度の平均値は W です。

ヘビー度が平均値より真に大きいヘビは最大で何匹いるでしょうか？
ただし、各ヘビのヘビー度は実数値であるものとします。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 100
  • 1 \leq W \leq 100

入力

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

N　W

出力

ヘビー度が平均値より真に大きいヘビの数として考えられる最大値を、1 行に出力してください。

入力例1

1 3

出力例1

0

1 匹のヘビのヘビー度は 3 です。平均値 3 よりもヘビー度が大きいヘビは存在しません。

入力例2

3 2

出力例2

2

例えば、各ヘビのヘビー度が {1, \frac{5}{2}, \frac{5}{2}} であるとき 2 匹のヘビのヘビー度が平均値 2 よりも大きく、これが最大となります。
3 匹以上のヘビのヘビー度が平均値よりも真に大きくなるようなヘビのヘビー度の組み合わせは存在しません。

writer: TMJN

Score: 100 points

問題文

There are N heavy snakes.
The average of heavy-degrees of these snakes is W.

How many snakes which has more heavy-degree than the average are there at most?
It is guaranteed that heavy-degree of each snakes are rational numbers.

Constraints

  • Input are all integers.
  • 1 \leq N \leq 100
  • 1 \leq W \leq 100

Input

Input is given from Standard Input in the following format. 

N　W

Output

Print the maximum number of snakes which has more heavy-degree than the average.

Sample Input 1

1 3

Sample Output 1

0

the heavy-degree of one snake is 3. There's no snake which has more heavy-degree than the average 3.

Sample Input2

3 2

Sample Output2

2

When the heavy-degrees of each snakes are {1, \frac{5}{2}, \frac{5}{2}} , the heavy-degree of two snakes are more than the average 2 and this is the maximum number.
There is no way to heavy-degrees of more than three snakes are more than the average.

writer: TMJN
B - Long Long Ago

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 200 点

問題文

昔々、Paken王国にはアゴが長い王様がいました。
王様が結婚相手を募集したところ、N 人の候補が応募しました。
王様は、「自分よりアゴが短い候補者の中で、最もアゴが長い人」と結婚すると決めました。
王様のアゴの長さは K、i 番目 (1 \leq i \leq N) の応募者ののアゴの長さは a_i です。

王様は何番目の人と結婚するでしょうか？
ただし、王様よりアゴが短い候補者がいない時は -1 と出力してください。
ただし、アゴの長さが王様を含め同じ人はいないものとします。

制約

  • 入力は全て整数である。
  • 1 \leq N\leq2\times10^5
  • 1 \leq K,a_i\leq 10^9
  • a_i \neq a_j (i \neq j)
  • a_i \neq K

入力

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

N K
a_1 a_2 \ldots a_N

出力

王様が結婚相手として選ぶ相手の番号を 1 行に出力してください。
選ぶ相手が存在しない場合、-1 と出力してください。

入力例1

4 10
11 9 15 13

出力例1

2

王様のアゴの長さは　10　です。
これよりアゴの長さが短い中で最もアゴが長い候補者は、アゴの長さが 9 である 2 番目の候補者です。

入力例2

5 10000
763618767 814402216 467921615 163029185 204341760

出力例2

-1

王様よりアゴの長さが短い候補者は存在しません。このような場合、 -1 と出力すれば正解となります。

writer: TMJN
C - 異世界転生

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

kaisei705君は 10 進法で N 円を持ってコンビニに行こうとしていました。
しかし、疲れからか不幸にもトラックに轢かれ、なんと異世界に転生してしまいます。
神様によると、世界にはそれぞれ番号が付いており、番号 M の世界では M 進法が使われているということです。
どうやら、転生した後の所持金は、転生先の表示で X 円のようです。

kaisei705「お願いします、元の世界に戻してください！」
神様「この世界の番号が分かったら、考えてやろう。」
kaisei705「（分からないよ...）」


さて、整数 N と文字列 X が与えられるので、彼の代わりに、転生した先の世界の番号 M を求めてあげてください。
ただし、転生する前と後で所持金額は変わらないものとします。

制約

  • N は整数である。
  • 9 \leq N \leq 10^{18}
  • 1 \leq |X| \leq 60
  • 答え M は 2 以上 10 以下の整数であり、この問題の制約において 1 つに定まることが保証されている。

入力

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

N X

出力

答え M を 1 行に出力してください。

入力例1

334 334

出力例1

10

どうやら、転生先も 10 進法だったようです。
本当に転生したんでしょうか？？

入力例2

5191491411 46533757523

出力例2

8

writer: kaisei705

D - スキップ

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

define君は、横に並んだ N 個のマス目で遊んでいます。左から順に、マス 1, 2, 3, ..., N と番号付けられています。
マス i には、整数A_iが書かれています。遊び方は、次の通りです。

  • マス V_1 からスタートし、スキップで M (M \geq 0) 箇所のマス V_1, V_2, V_3, ..., V_M を順に経由し、マス V_M でゴールする。
  • 途中で左に進んでは行けない。すなわち、1 \leq V_1 < V_2 < V_3 < ... < V_M \leq N を満たす必要がある。
  • この時のポイントは |A_{V_2}-A_{V_1}| + |A_{V_3}-A_{V_2}| + ... + |A_{V_M}-A_{V_{M-1}}| 点となる。
  • なお、遊ばないという選択もできる。この場合 M = 0 となり、ポイントは 0 点となる。また、1 箇所しか経由しない場合 (M = 1 の場合) も 0 点となる。

さて、define君はポイントを最大化したいと考えていますが、彼は面倒くさがりなのでなるべく経由するマスの個数を少なくしたいです。
彼の代わりに、経由するマスの個数の最小値を計算してあげてください。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 10^5
  • -10^9 \leq A_i \leq 10^9

入力

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

N
A_1　A_2　\ldots　A_{N-1}　A_N

出力

ポイントを最大化するためには、最小でいくつのマスを通ればいいかを 1 行に出力せよ。

入力例1

5
1 2 1 2 1

出力例1

5

この場合、全てのマスを通ると、ポイントが 4 点になります。
通るマスが 4 カ所以下でポイントを 4 点以上にする遊び方はありません。

入力例2

5
1 3 5 2 1

出力例2

3

この場合は、マス 1, 3, 5 を順に通ると 8 点が得られます。

writer: define
E - Osmium_1008と課題

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 300 点

問題文

PAKEN学園に通うOsmium_1008君は、課題を N 個こなさないといけません。
初め、Osmium_1008君のエネルギーは E あり、 i 個目の課題を終わらせるためには A_i のエネルギーを消費する必要があります。エネルギーが 0 より小さくなるようには行動できません。

どうしても課題が終わりそうにないOsmium_1008君は、エナジードリンクを飲むことにしました。エナジードリンクは M 本あり、j 本目のエナジードリンクを飲むとエネルギーが B_j 増えます。
しかし、Osmium_1008君は健康を気にしているため、できる限りエナジードリンクを飲みたくなく、多くても K 本までしか飲みません。

さて、Osmium_1008君が全ての課題を終えることができるかを判定し、終えることができるなら飲まなければいけないエナジードリンクの本数の最小値、終えることができないなら終わらせられる課題の数の最大値を出力してください。

制約

  • 入力は全て整数である。
  • 1\leq N,M\leq 2\times 10^5
  • 1\leq K\leq M
  • 0\leq E\leq 10^8
  • 1\leq A_i,B_j\leq 10^8
  • A_1+A_2+\ldots +A_{N-1}+A_N>E

入力

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

N M K E
A_1 A_2 \ldots A_{N-1} A_N
B_1 B_2 \ldots B_{M-1} B_M

出力

課題を終えることができるなら Yes と出力し、次の行にエナジードリンクを飲む最低の本数を出力してください。
できないなら No と出力し、次の行に終わらせられる最大の課題の数を出力してください。

入力例1

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

出力例1 

Yes
3

エナジードリンク {1, 2, 4} を飲めばエネルギーが 18 となり、全ての課題を終えるのに必要なエネルギーに達するため課題を終えることができます。
3 本より少ない本数のエナジードリンクを飲むことによって課題を終えることはできません。

入力例2 

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

出力例2 

No
3

エナジードリンクをどのような組み合わせで飲んでもエネルギー量はすべての課題を終えるのに必要なエネルギーに達しないため、全ての課題を終わらせることはできません。エナジードリンク {3, 4} を飲めば課題 {1, 2, 4} を終わらせることができるので、終わらせられる最大の課題の数は 3 つです。

入力例3 

1 15 14 86
92
47 98 3 71 37 46 87 39 75 65 100 44 91 85 52

出力例3

Yes
1

入力例4

20 1 1 91
40 66 82 48 3 46 25 51 65 12 96 66 40 97 100 13 62 98 6 1
68

出力例4

No
8

writer: Osmium_1008
F - 不便な橋

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 300 点

問題文

sanada君は島 1 から島 N+1 まで順に橋を使って移動します。
島 i から島 i+1 (1 \leq i \leq N) へは M 本の橋がかけられており、そのうち j 本目の橋を橋 (i, j) とします。
橋 (i, j) の島 i 側の入り口にはゲートがあり、橋 (i, j) のゲートは時刻が A_{i, j} の倍数（0も含む）である瞬間にだけ開きます。
sanada君はこの瞬間にのみ橋を渡り始めることができ、渡り切るのには B_{i, j} の時間がかかります。
時刻 0 にsanada君は島 1 にいます。sanada君が島 N+1 に到着できる最も早い時刻を出力してください。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 500
  • 1 \leq M \leq 500
  • 1 \leq A_{(i,j)} \leq 10^5
  • 1 \leq B_{(i,j)} \leq 10^5

入力

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

N　M
A_{(1,1)}　A_{(1,2)}　\ldots　A_{(1,M)}
A_{(2,1)}　A_{(2,2)}　\ldots　A_{(2,M)}
\vdots
A_{(N,1)}　A_{(N,2)}　\ldots　A_{(N,M)}
B_{(1,1)}　B_{(1,2)}　\ldots　B_{(1,M)}
B_{(2,1)}　B_{(2,2)}　\ldots　B_{(2,M)}
\vdots
B_{(N,1)}　B_{(N,2)}　\ldots　B_{(N,M)}

出力

sanada 君が島 N+1 に到着できる最も早い時刻を 1 行に出力してください。

入力例1

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

出力例1

6

以下のような動きが最適となります。この場合、時刻 6 に目的地の島 4 に到着することができます。

  • 橋 (1, 1) を時刻 0 に渡り始める。渡り切るのに 3 の時間がかかる。
  • 時刻 3 に島 2 に到着する。
  • 橋 (2, 2) を時刻 3 に渡り始める。渡り切るのに 1 の時間がかかる。
  • 時刻 4 に島 3 に到着する。
  • 橋 (3, 3) を時刻 4 に渡り始める。渡り切るのに 2 の時間がかかる。
  • 時刻 6 に島 4 に到着する。

writer: iwaiwaiwa
G - バラバラ掛け算

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

以下の Q 個のクエリに答えてください。

  • i 番目のクエリでは、整数 N_i が与えられる。
  • 長さ M (M \geq 1) の整数列 A = {A_1, A_2, ..., A_M} において、そのポイントを A_1 \times A_2 \times ... \times A_{M-1} \times A_M とする。
  • A_1 + A_2 + A_3 + ... + A_M = N_i かつ A_j\geq 0 を満たす整数列の中でのポイントの最大値を 10^{9}+7 で割ったあまりを出力する。

ただし、ポイントを 10^{9}+7 で割ったあまりの最大値ではなく、ポイントの最大値を 10^{9}+7 で割ったあまりを出力することに注意してください。

制約

  • 入力は全て整数である。
  • 1 \leq Q \leq 10^5
  • 0 \leq N_i \leq 10^{18}

入力

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

Q
N_1　N_2　\ldots　N_{Q-1}　N_Q

出力

それぞれのクエリの答えを順に、空白区切りで出力してください。

入力例1

2
3 4

出力例1

3 4

N_i = 3 の場合、例えば A = {3} という数列のポイントは 3 であり、これが最大です。

N_i = 4 の場合、例えば A = {2, 2} という数列のポイントは 2 \times 2 = 4 であり、これが最大です。

writer: define
H - don't be late

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

この世界には N 個の駅があり、駅 1, 2, 3, ..., N と番号付けられています。駅 i (2 \leq i \leq N-1) では、乗り換えに t_i 単位時間かかります。
また、駅同士を繋ぐ路線は M 本あり、i 本目の路線は以下のようなものとなっています。

  • 駅 a_i から駅 b_i を双方向に結ぶ。
  • 駅 a_i と駅 b_i の間をこの路線で移動するのに c_i 単位時間かかる。なお、どちらの方向でも移動時間は変わらない。
  • この路線では、どちらの方向に向かう電車も d_i の倍数の時刻だけに発車する。

さて、Ebishu0309君は寝坊しました。現在の時刻は 0 であり、彼は駅 1 にいます。
彼は駅 N に行こうと思いました。駅 N に行けるかは分かりませんが、もし行けるのならば時刻 K までに行こうと思っています。


彼が時刻 K まで (時刻 K ちょうどを含む) に駅 N に到着することができるのか判定し、できるのならば最も早い時刻はいつなのか求めてください。

制約

  • 入力は全て整数である。
  • 2 \leq N \leq 2\times10^5
  • 1 \leq M \leq 2\times10^5
  • 1 \leq K \leq 10^{12}
  • 1 \leq t_i \leq 10^9 (2 \leq i \leq N-1)
  • 1 \leq a_i , b_i \leq N (1 \leq i \leq M, a_i ≠ b_i)
  • 1 \leq c_i < d_i \leq 10^9 (1 \leq i \leq M)

入力

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

N M K
t_2
\vdots
t_{N-1}
a_1 b_1 c_1 d_1
\vdots
a_M b_M c_M d_M

出力

Ebishu0309君が時刻 K 以前に駅 N に到着することが可能ならば、その時刻を 1 行に出力してください。
不可能ならば、-1 と出力してください。

入力例1

3 2 8
2
1 2 3 4
2 3 1 2

出力例1

7
以下のように動けば、時刻 7 に目的地の駅 3 に到着することができます。
  • 駅 1 を時刻 0 に出発する。1 本目の路線を使って、駅 2 に移動する。
  • 駅 2 に時刻 3 に到着する。
  • 駅 2 での乗換に 2 単位時間かかる。時刻 5 に乗換が完了する。
  • 駅 2 を時刻 6 に出発する。2 本目の路線を使って、駅 3 に移動する。
  • 駅 3 に時刻 7 に到着する。

入力例2

5 5 8
2
1
2
1 2 2 3
1 3 2 3
2 5 4 5
3 4 1 2
4 5 1 3

出力例2

-1

Ebishu0309君は駅 5 に到着するのに最短でも 9 単位時間かかりますが、これは K より長いので -1 を出力してください。

入力例3

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

出力例3

-1

Ebishu0309君は駅 N に行くことができません。
時刻 K までに到着できない場合だけではなく、そもそも電車を使って駅 N まで行けない場合に関しても、-1 を出力してださい。

writer: Ebishu0309
I - school competition 1

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

Paken島には 2 つの小学校、anmichi校とsanada校があり、島の人々はどちらかの学校に通って日々競プロの精進をしています。
これらの人々は、毎週行われるPatCoder社のコンテストに出ており、各人には能力を表すレーティングという値がついています。
anmichi校に通う N 人の生徒のうち i 番目の人のレーティングは A_i、sanada校に通う M 人の生徒のうち j 番目の人のレーティングは B_j です。

ある日、この 2 校で今年も伝統の対抗戦が行われることとなりました。
対抗戦では各校から 2 名ずつ選抜し、チーム戦を行うこととなっています。
この対抗戦の主催者であるdefineは 2 校で選ばれる人たちの実力差をなるべくなくすため、次の条件を満たすように 2 人を選ぶことを各校に伝えました。

  • anmichi校から選んだ 2 名のレーティングを低い方から順に P,Q、sanada校から選んだ 2 名のレーティングを低い方から順に R,S としたとき、R < P < Q < S となる。

define君は条件を満たす選び方が何通りあるのか気になっています。
define君のためにこの条件を満たすような 4 人の選び方の通り数を 10^9+7 で割った余りを求めてください。
なお、4 人のレーティングの通り数を求めるわけではないことに注意してください。

制約

  • 入力は全て整数である。
  • 2 \leq N,M \leq 2\times 10^5
  • 1 \leq A_i,B_j \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
  • A_i は全て異なる。
  • B_j は全て異なる。

入力

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

N M
A_1 A_2 \ldots A_{N-1}  A_N
B_1 B_2 \ldots B_{M-1} B_M

出力

4 人の選び方の通り数を 10^9+7 で割った余りを 1 行に出力してください。

入力例1

4 4
40 60 20 10
25 30 80 50

出力例1 

2

anmichi校からはレーティングが 40 と 60 の人しか選べず、sanada校からはレーティングが 25 と 80 の人、レーティングが 30 と 80 の人の 2 通りの選び方があります。
よって、1 \times 2 を 10^9+7 で割った余りである 2 を出力してください。

入力例2 

5 3
112 76 50 35 22
15 60 50

出力例2 

4

anmichi校とsanada校にレーティングが同じ人がいる場合もあります。ただし 1 つの学校内には同じレーティングの人はいません。

入力例3 

2 2
8 69
1 20

出力例3

0

大会が開けません。悲しいですね。まずは学校の生徒数を増やしましょう。

writer: sanadayukimura73
J - school competition 2

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

さて、Paken島の人々は、学校対抗戦に各校 2 人しか出られないことは問題であると考え学校対抗戦のルールを改めることにしました。(school competition 1)

anmichi校に通う N 人の生徒のうち i 番目の人のレーティングは A_i、sanada校に通う M 人の生徒のうち j 番目の人のレーティングは B_j です。
ここで、以下のようなルールがあります。

  • 両校ともAチームとBチームの 2 チームに分かれ、anmichi校のAチームとsanada校のAチーム、anmichi校のBチームとsanada校のBチームがそれぞれ対決する。
  • 両校ともに、Aチームに所属する生徒のレーティングの総和は、Bチームに所属する生徒のレーティングの総和よりも真に大きくなければならない。
  • 2 チームが対決するとき、チームに所属する生徒のレーティングの総和が大きいチームが勝つ。また、レーティングの総和が等しい場合は引き分けとなる。
  • どのチームにも 1 人以上の生徒がいなくてはならない。
  • AチームとBチーム両方に所属する生徒がいてはならず、AチームとBチームどちらにも所属しない生徒がいてもならない。

anmichi校は、sanada校にAチームBチーム両方で勝ちたいです。そこで、最善にチーム分けをしたときに両チームとも勝てる確率を求めてください。
なお、sanada校のチーム分けは、上の条件を満たす分け方をすべて挙げた上でその中から等確率で選ぶものとします。
ただし、ある 2 つのsanada校のチーム分けが異なるとは、一方の分け方で所属するチームともう一方の分け方で所属するチームが異なる生徒が存在することを指します。
また、anmichi 校、sanada 校の両校において、1 通り以上のチーム分けの組合せが存在することが保証されています。

制約

  • 入力は全て整数である。
  • 2\leq N,M \leq 20
  • 0 \leq A_i,B_i \leq 10^{9}
  • anmichi 校, sanada 校の両校において、条件を満たすチーム分けが 1 通り以上存在する。

入力

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

N M
A_1 A_2 \ldots A_{N-1}  A_N
B_1 B_2 \ldots B_{M-1} B_M

出力

anmichi校が最適なチーム分けを行なったとき、anmichi校がsanada校に両チームとも勝つ確率を 1 行に出力してください。
絶対誤差または相対誤差が 10^{-6} 未満の場合正解となります。
ただし、自分チームと相手チームのレーティングの総和が同じ場合は勝ちにならないことに注意してください。

入力例1

2 2
3 2
4 1

出力例1

0.0000000000

anmichi校はAチームには 1 番目の生徒、Bチームには 2 番目の生徒が出ます。
また、sanada校はAチームには 1 番目の人、Bチームには 2 番目の人が出ます。
この場合、Bチームは勝てますがAチームは勝てないので、AチームBチーム両方で勝つ確率は 0 です。

入力例2

2 3
3 7
2 2 4

出力例2

1.0000000000

anmichi校はAチームには2番目の人、Bチームには1番目の人が出ます。
また、sanada校のチーム分けの仕方は以下の 2 通り存在します。

  • Aチームには 1, 3 番目の人、Bチームには 2 番目の人が出る。
  • Aチームには 2, 3 番目の人、Bチームには 1 番目の人が出る。
どちらの場合でもanmichi校は、AチームBチーム両方で勝てるので、確率は 1 です。
sanada校の分け方において、同じレーティングの人を区別すること、また、同じレーティングのチーム分けを区別することに注意してください。

writer: mutuhuhihusenonu

K - 天使と宿題

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 500 点

問題文

天使のGさんと、悪魔のVさんは、人間界の高校に通っています。
今日、二人には夏休みの宿題が課されました！夏休みは N 日間、課題は N ページあります。
悪魔のVさんは、計画性があるため、宿題を毎日 1 ページずつ行うことにしました。
しかし、天使のGさんは、人間界に祝福をもたらす (という名目) で忙しいため、宿題をやる余裕がありません！
そこで、Vさんの宿題を写してもらうことにしました。

i 日目にGさんがVさんの元を訪れたときのVさんの機嫌は a_i であり、その日には最大で a_i ページ分の宿題を写してもらうことができます。
天使のGさんは忙しいため、なるべくVさんの元を訪れたくありません。Gさんが宿題を完遂するために、最小でVさんの元を何回訪れる必要があるでしょうか？

ただし、i 日目にGさんがVさんの元を訪れたとき、Vさんは既に宿題の i ページ目を終わらせているものとします。
なお、i 日目の時点で宿題の i+1 ページ以降を写してもらうことはできないことに注意してください。
また、同じ日に二度以上GさんがVさんの元を訪れることはできません。

制約

  • 入力は全て整数である。
  • 1\leq N\leq2\times10^5
  • 1\leq a_i\leq 10^9

入力

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

N
a_1 a_2 \ldots a_{N-1} a_N

出力

GさんがVさんの元を訪れる最小の回数を標準出力に出力してください。

入力例1

5
1 1 3 2 2

出力例1

2

3 日目と 5 日目に訪れればよいです。

入力例2

6
1 1 2 1 1 2

出力例2

4

例えば、1 日目、3 日目、4 日目、6 日目に訪れればよいです。

入力例3

8
1 1 2 1 2 3 1 3

出力例3

3

例えば 3 日目、6 日目、8 日目に訪れれば良いです。

writer: TMJN
L - じゃんけん

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 個の頂点と M 本の辺からなるグラフが与えられます。
i 番目の辺は A_i と B_i を双方向に結んでいます。
そして、各頂点には G,C,P のいずれかの文字が書かれています。
さて、anmichiくんとdefineくんは次のようなじゃんけんゲームをします。

【じゃんけんのルール】

(☆) 勝ちとなる場合
  • 自分が G と書かれた頂点にいるかつ相手が C と書かれた頂点にいる
  • 自分が C と書かれた頂点にいるかつ相手が P と書かれた頂点にいる
  • 自分が P と書かれた頂点にいるかつ相手が G と書かれた頂点にいる
(★) 負けとなる場合
  • 自分が C と書かれた頂点にいるかつ相手が G と書かれた頂点にいる
  • 自分が P と書かれた頂点にいるかつ相手が C と書かれた頂点にいる
  • 自分が G と書かれた頂点にいるかつ相手が P と書かれた頂点にいる
(△) あいことなる場合
  • 自分のいるマスに書かれた文字と相手のいるマスに書かれた文字が同じ

初め、anmichiくんは頂点 1 に、defineくんは頂点 N にいます。
また、初めの両者の得点は 0 点です。
二人は次のような動作を K 回行います。

  1. 辺で隣接する頂点に移動する、もしくは今いる頂点から移動しない。二人が同じ頂点に移動することもできる。
  2. じゃんけんに勝ったら X 点、あいこなら Y 点、負けたら 0 点が加算される。

また、defineくんはどのように動くかを事前に決めており、 i (1 \leq i \leq K) 手目には頂点 D_i に移動します。
なお、anmichiくんはdefineくんがどのように動くかを知っています。
さて、anmichiくんは自分のスコアを最大化するように動くとき、何点もらえるか出力してください。
ただし、二人はどのマスに何の文字が書かれているか知っているものとします。

制約

  • 入力で与えられる数は全て整数である。
  • 2 \leq N \leq 2000
  • 1 \leq M \leq 5000
  • 1 \leq K \leq 2000
  • 1 \leq Y < X \leq 100
  • 1 \leq A_i,B_i \leq N
  • C_i は G, C, P のいずれかである。
  • 1 \leq D_i \leq N
  • N = D_1 であるか、頂点 N と頂点D_1を結ぶ辺は存在する。
  • 1 \leq i \leq K-1 を満たす全ての i について、D_i = D_{i+1} であるか、頂点 D_i と頂点 D_{i+1} を結ぶ辺は存在する。
  • 入力で与えられるグラフは単純であるが、連結であるとは限らない。

入力

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

N M K X Y
A_1 B_1
A_2 B_2
\vdots
A_M B_M
C_1 C_2  \ldots  C_N
D_1  D_2  \ldots  D_K

出力

anmichiくんのスコアの最大値を 1 行に出力してください。

入力例1

4 5 2 3 2
1 2
1 3
1 4
2 4
3 4
G C P P
1 2

出力例1

6

頂点 1 -> 3 -> 1 と動くと 2 回勝つことができ、3 \times 2 = 6 点を得ることができます。
7 点以上を得る方法は存在しません。

入力例2

5 4 3 5 3
1 2
2 3
3 4
4 5
G C C G G
4 5 4

出力例2

9

頂点 1 から動かないのが最適となります。動かないことも可能なことに注意してください。

writer: anmichi

M - Pakenのうさぎ

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

これはインタラクティブな問題です。

今年のPakenでは、いつでももふもふできるうさぎを置くことになりました。
しかし、手頃なうさぎが見つからないので、一時的に部員であるanmichiをうさぎにしようと決まりました。

今ここに、人間をうさぎに変えるためのドロップが N 種類あり、1 から N までの番号が振られています。
このうち効果があるのは 2 種類だけであり、これらを 2 つ両方食べた場合にのみ人間はうさぎになりますが、効果がある 2 種類がどれかは分かりません。他のドロップは人間に何ら影響を及ぼしません。
ドロップはとても苦いので、anmichiが食べるのは効果のある 2 つだけにしたいです。

anmichiが食べるべきドロップを識別するため、25 人の他の部員たちがそれぞれドロップを食べ、うさぎになったかどうか実験することで目的のドロップを識別することにしました。
1 回の実験では、ある部員が N 個のドロップのうち 0 個以上のいくつかのドロップを選び、一気に食べることによって、うさぎになったかどうかを判定します。
ただし、1 人の部員を 2 回以上の実験に使う事はできないので、高々 25 回しか実験を行えません。

適切に他の部員が食べるドロップを決めることで、効果のあるドロップを特定してください。
なお、それぞれのドロップは他の部員が全員食べられるくらい十分な量あるものとします。

制約

  • 2 \leq N \leq 6000

入出力

最初に、N が次の形式で標準入力から与えられます。

N

次に、クエリを繰り返し送ります。この回数は 25 回以内でなければなりません。
部員に飲ませるドロップの数を K 個として、K と部員に飲ませるドロップの番号を K 個空白区切りで昇順に出力し、最後に改行してください。 

? K A1 A2 \ldots AK

これに対するクエリの答えは、次の形式で与えられます。

s

s は Rabbit,Humanのいずれかです。Rabbit の場合部員がうさぎになった事、Human の場合部員がうさぎにならなかった事を意味します。


答えを出力する際は、効果のあるドロップの番号をそれぞれ x,y (x < y)として、次のように出力してください。

! x y

なお、答えの出力は部員へのクエリ回数に含まれないことに注意してください。

注意

  • 出力の最後に改行を含めて出力しなければなりません。その後、標準出力を flush しなければなりません。 そうでない場合は TLE の可能性があります。
  • 答えを出力した後、プログラムをすぐに終了しなければならなりません。そうでないときの挙動は定義されていません。
  • 出力の答えが間違っている場合の挙動は定義されていません (WAとは限りません)。

入出力例

この入出力例では、N = 4 であり、ドロップ 1 と 3 に効果がある場合のジャッジ側とのやり取りの一例を示しております。
なお、これはあくまでも入出力例であり、意味のあるやりとりをしているとは限らない事に注意してください。

自分のプログラムへの入力（ジャッジ側の出力） 自分のプログラムの出力
4
? 2 1 3
Rabbit
? 3 1 2 4
Human
? 0
Human
? 4 1 2 3 4
Rabbit
! 1 3
ここで、最後に ! 3 1 と出力した場合に正解にならない事に注意してください。x < y を満たす必要があります。

writer: kaage

Score : 600 points

Problem Statement

This is an interactive task.

Today, a rabbit to pat is needed by members of Paken.
However, they haven't found apt rabbits. Then, it has been decided to equip anmichi who is one of the members as a rabbit.

Now, there are N kinds of pills to transform a human into a rabbit.
Only two pills of them are effective and only if anmichi takes both of two pills, anmichi becomes a rabbit. We don't know which are the effective pills. Other pills don't influence on him.
The pills don't taste good, so anmichi want to take only effective pills.

To recognize the effective pills, other 25 members taking them and confirm whether they are rabbits or humans.

Each members have to take the pills at once because they must achieve this mission urgently.

Your tasks is to recognize the effective pills by deciding the pills for other members to take.
You can assume that there is enough pills for other each members to take.

Constraints

  • 2 \leq N \leq 6000

Input and Output

First, N is given from Standard Input in the following format.

N

Next, you send queries repeatedly. This frequency have not to be more than 25. Let the number of pills for a member to take be K and print K and number of pills to take in ascending order to Standard Output. In addition, print linefeed code in the end of line.

? K A1 A2 … AK

The answers to this queries is given from Standard Input in the following format.

s

s is Rabbit or Human。These mean whether the member becomes a rabbit.

Finally, you answer to this problem. Let the numbers of effective pills be x and y ( x < y ) and print x and y to Standard Output in the following format.

! x y

Besides, printing the answer is not included in the number of queries.

Judgement

  • You have to flush Standard Output after each output. Otherwise, you can get TLE .
  • After you print the answer, the program has to be terminated immediately. Otherwise, the behavior of the judge is undefined.
  • When your output is invalid or incorrect, the behavior of the judge is undefined.

writer: kaage
N - multiple

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 600 点

問題文

anmichiくんは誕生日に長さ N の数列 A をプレゼントされました。彼は D という数が好きなので、数列 A の中から A_l,A_{l+1},\ldots ,A_r(1 \leq l \leq r \leq N) の和も積も D の倍数である (l,r) の組み合わせを探そうとしました。その組み合わせの個数を求めてください。


制約

  • 入力は全て整数である。
  • 1 \leq N \leq 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq A_i \leq 10^9

入力

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

N D
A_1 A_2 \ldots A_N

出力

数列 A の中から A_l,A_{l+1},\ldots ,A_r(1 \leq l \leq r \leq N) の和も積も D の倍数である (l, r) の組み合わせの個数を出力してください。

入力例1

5 3
1 2 1 3 2

出力例1

4
(l,r) = (1,5),(2,4),(3,5),(4,4)の 4 つが条件を満たします。

入力例2

5 3
8 6 9 1 20

出力例2

6

入力例3

8 1
1 10 100 1000 10000 1000000 10000000 100000000

出力例3

36

writer: anmichi
O - Height Changer

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

今年のPaken合宿には、N 人が参加します。さて、今部員全員が講義会場に到着しました。左端の画面にはスライドが映っています。しかし、会場が狭く、部員たちは左から右へ一列に並ぶことになりました。このとき、各部員には左から順に、1 から Nという番号がついています。
この集団では、スライドに近い方からレートの高い順に並ぶ文化があるため、並びを変えることはできません。しかし、参加者たちの身長は様々なので、このままだと身長の低い人が画面を見られなくなってしまうかもしれません。

そこで、魔法少年のOsmium_1008君は、いくつかの部員の身長を縮める魔法を使うことにしました（Osmium_1008君は魔法によって身長を縮めることはできますが、伸ばすことはできません）。

部員 i の身長は A_i で、スライドを見られた時の嬉しさは B_i で表されます。 また、自分より左側 (自分より番号が小さい) にいる人の中で自分より身長が真に高い人がいる場合（同じ場合は見られます）、その人はスライドを見られず、嬉しさは 0 になります。
また、Osmium_1008君が魔法を使った場合、身長を縮められた部員は縮められた長さ分だけ嬉しさがさらに減ります。

全員の嬉しさの合計の最大値を求めてください。ただし、Osmium_1008君は一度も魔法を使わないこともできます。また、各人の嬉しさの値が負になることもあります。

制約

  • 入力は全て整数である。
  • 1\leq N\leq 10^5
  • 1\leq A_i,B_i\leq 10^9

小課題

この課題には 2 つの小課題があります。

  1. (400 点) N \leq 5000
  2. (600 点) 追加の制約はない。

入力

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

N
A_1　A_2　\ldots　A_{N-1}　A_N
B_1　B_2　\ldots　B_{N-1}　B_N

出力

全員の嬉しさの合計の最大値を 1 行に出力してください。

注意

小課題 1 のみを狙ったコードを提出する際には、N が 5000 より大きいならすぐ終了するといった処理を書き加えることを勧めます。

入力例1

4
40 60 20 10
25 30 80 50

出力例1 

95

Osmium_1008君は部員 1 の身長を 30、部員 2 の身長を 50、部員 3 の身長を 10 縮めることで、嬉しさの合計 95 を実現できます。

入力例2 

5
112 76 50 35 22
15 60 40 120 90

出力例2 

140

入力例3 

5
151 162 155 161 170
4 8 23 10 15

出力例3

53

writer: iwaiwaiwa
P - Flip Cards

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

ある日、sanadaはkaageに N 枚のカードを引くように言われました。
sanadaはとりあえず、言われるがままにカードを引きました。
このカードには表と裏にそれぞれ数が書かれており、2 面に書かれた数の合計は常に M でした。sanadaが引いた N 枚のカードにおいて、i 枚目の表に書かれていた数は A_i です。

次に、kaageは以下の操作を K 回以内の任意の回数（0 回でも可）することを指示しました。

  • 1 \leq x\leq y\leq N を満たす任意の整数 x,y を選び、x 枚目から y 枚目までの全てのカードの表裏を反転する。

不審に思ったsanadaは、kaageの家にスパイを送り込み、N 枚のカードの表に書かれた数の合計が多いほどkaageが勉強しなくてはいけないことを知りました。
kaageを勉強させたいsanadaのために、適切な回数・適切な操作を行うことで N 枚のカードの表に書かれた数の合計を最大いくつにできるか求めてください。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 10^6
  • 0 \leq K \leq N
  • 1 \leq M \leq 10^9
  • 1 \leq A_i \leq M-1

小課題

この課題には 3 つの小課題があります。
  1. (400 点) N \leq 2000
  2. (400 点) N \leq 10^5
  3. (300 点) 追加の制約はない。

入力

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

N  M  K
A_1  A_2 \ldots  A_N

出力

適切な回数、適切な操作を行ったとき、全てのカードの表に書かれた数の合計の最大値を 1 行に出力してください。

注意

小課題 1 のみを狙ったコードを提出する際にはN が 2000より大きいならすぐ終了するといった処理を書き加えることを勧めます。

入力例1

3 6 1
3 3 4

出力例1

10

この場合、例えば一度も操作を行わないときに、カードの表にある数全ての合計を最大の 10 にできます。

入力例2

8 9 2
1 3 8 7 5 3 5 1

出力例2

52

例えば次のように区間を選んで操作することで、最大値 52 を達成できます。

  • 1 回目: 1 枚目から 5 枚目のカードの表裏を反転させる。操作後のカードの並びは {8, 6, 1, 2, 4, 3, 5, 1} となる。
  • 2 回目: 3 枚目から 8 枚目のカードの表裏を反転させる。操作後のカードの並びは {8, 6, 8, 7, 5, 6, 4, 8} となる。

writer: sanadayukimura73