Time Limit: 2 sec / Memory Limit: 256 MB
問題文
Codefes大学の競技プログラミングの授業では、成績評価のために、N 回の試験を行うことにしています。 各試験での成績は、0 以上 M 以下の整数値です。 N 個の試験成績のうち、上位 K 個の平均が R 点以上であれば、めでたく単位が認定されます。 上位 K 個の平均が R 点未満の場合には不合格となり、単位は認定されません。
N-1 回の試験を終えたヘイホー君は、最終試験に臨もうとしています。 最終試験を除く N-1 回の試験におけるヘイホー君の成績は、それぞれ S_1, S_2, …, S_{N-1} 点でした。 ヘイホー君は、最終試験で何点以上取れば単位が認定されるでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N K M R
S_1
S_2
:
S_{N-1}
- 1 行目には、整数 N (1 ≦ N ≦ 100), K (1 ≦ K ≦ N), M (1 ≦ M ≦ 10^9), R (0 ≦ R ≦ M) が、空白区切りで与えられる。 ここで、N は試験の回数、K は成績評価に用いる試験の個数、M は各試験の満点、R は単位認定に必要な平均点を表す。
- 2 行目以降の N-1 行には、整数 S_i (0 ≦ S_i ≦ M) が与えられる。これは i 回目の試験におけるヘイホー君の成績を表す。
- S_N が与えられないことに注意せよ。
出力
出力は 1 行からなる。
- 最終試験の結果が何点であってもヘイホー君に単位が認定されるならば、0 を出力せよ。
- 最終試験の結果が何点であってもヘイホー君に単位が認定されないならば、-1 を出力せよ。
- どちらでもない場合、ヘイホー君が最終試験で取る必要のある最低点を出力せよ。
いずれの場合も、出力の末尾には改行をいれること。
入力例1
5 3 100 60 86 23 49 39
出力例1
45
ヘイホー君が最終試験で 45 点を取った場合、上位 3 個の平均は (86+49+45)/3=60 となり、単位が認定されます。 もちろん、46 点以上取っても単位は認定されます。 一方、44 点以下の場合には単位が認定されません。
入力例2
5 3 100 60 92 100 95 99
出力例2
0
最終試験で 0 点でも単位が認定されます。
入力例3
5 3 100 60 18 42 29 31
出力例3
-1
残念ながら、最終試験が満点でも単位は認定されません。
入力例4
13 10 1000000000 645245296 492014535 611893452 729291030 392019922 293849201 474839528 702912832 341845861 102495671 908590572 812912432 129855439
出力例4
986132796
大きな数が入力されることもあります。オーバーフローに注意しましょう。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ある文字列を 2 回繰り返してできる文字列を、平方と呼びます。
たとえば、abcabc や abababab は平方ですが、
abc や ababab は平方ではありません。
なお、長さ 0 の文字列も、平方とみなすことにします。
ヘイホー君はある日、英小文字のみからなる文字列 S を、道端で拾いました。 平方が好きなヘイホー君は、 文字列 S に以下の操作を繰り返すことで、平方を得ようと考えました。
- 1 ≦ p ≦ |S| を満たす整数 p を選ぶ。その後、S の p 文字目を削除する。ここで、|S| は S の長さを表すものとする。
ヘイホー君が平方を得るために必要な操作回数の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N S
- 1 行目には、整数 N (1 ≦ N ≦ 100) が与えられる。これはヘイホー君が拾った文字列の長さを表す。
- 2 行目には、ヘイホー君が拾った文字列 S が与えられる。S は英小文字のみからなる N 文字の文字列であることが保証される。
出力
ヘイホー君が平方を得るために必要な最小の操作回数を 1 行に出力せよ。 出力の末尾には改行をいれること。
入力例1
8 abacbabc
出力例1
2
以下のように 2 回の操作を行うことで、abcabc という平方を得ることができます。
- 5 文字目を削除し、
abacabcにする。 - 3 文字目を削除し、
abcabcにする。
入力例2
8 abababab
出力例2
0
abababab は平方なので、一度も操作を行う必要はありません。
入力例3
5 abcde
出力例3
5
すべての文字を削除することで、長さ 0 の平方を得ることができます。
入力例4
26 codefestivaltwozeroonefive
出力例4
14
oefiveoefive という平方を得ることができます。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
りんごさんは一次元オセロで遊んでいます。一次元オセロとは、無限に長い 1 列に並んだマス目と、特殊なコマを使って遊ぶゲームです。一次元オセロで用いるコマは表が黒色で裏が白色のコマで、黒のコマを裏返すと白のコマに、白のコマを裏返すと黒のコマになります。一次元オセロは以下のように進行します。
- まず、白のコマ A_1 個、黒のコマ A_2 個、白のコマ A_3 個、...、白のコマ A_N 個をこの順に連続したマス目に置く。
- 黒のコマをいずれかの空きマスに置く。このとき、隣の 2 マスのうちちょうど 1 マスに白のコマがなければならない。
- 2. で置いた黒のコマに最も近い別の黒のコマ（そのようなコマは常に一意に定まる）との間にある白のコマを全て裏返して黒のコマにする。
- 2. と 3. の黒と白を入れ替えた操作を行う。
- 2. 〜 4. を繰り返す。
- 3. または 4. を終えた時点で、全てのコマが同じ色になった場合はその時点で終了となる。
たくさんのコマを裏返すのは大変なので、りんごさんはコマを裏返す回数を少なくしたいと思っています。ゲームが終了するまでにりんごさんが裏返すコマの個数の和の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
- 1 行目には、整数 N (3 ≦ N < 10^5, N は奇数) が与えられる。
- 2 行目には、コマの初期配置の情報を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目には A_i (1 ≦ A_i ≦ 10^8) が与えられる。
出力
ゲームが終了するまでにりんごさんが裏返すコマの個数の和の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
5 1 2 3 4 5
出力例1
20
下図のようにコマを置いていくと、全部で 1+4+5+10 = 20 回コマをひっくり返すことになります。
入力例2
9 100000000 20 15 11 14 20 15 11 15
出力例2
554
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
りんごさんは 1 辺の長さが 1 の立方体を積んで遊んでいます。りんごさんは地面に 1 辺の長さが 1 の正方形を横に並べて N 個描き、左から i 個目の正方形の上に立方体を A_i 個積みました。
りんごさんは立方体の表面にペンキを塗ることにしました。別の立方体や地面と接している面にはペンキを塗りません。しかし、りんごさんはペンキの量が足りるか不安になりました。そこで、K 個の立方体を取り除いてからペンキを塗ることにしました。このとき、いずれの正方形の上にも 1 個以上の立方体がなければなりません。
りんごさんは必要なペンキの量をできるだけ少なくしたいです。ペンキを塗る面積の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 ... A_N
- 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), K (1 ≦ K ≦ 10^{14}) が空白区切りで与えられる。これは、地面に描いた正方形の個数が N 個、取り除く立方体の個数が K 個であることを表す。
- 2 行目には、各正方形の上に積む立方体の個数を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 A_i (1 ≦ A_i ≦ 10^9) は、左から i 個目の正方形の上に積む立方体の個数を表す。ただし、いずれの正方形の上にも 1 個以上の立方体を残して K 個の立方体を取り除くことができること、すなわち Σ A_i ≧ N+K が保証される。
出力
ペンキを塗る面積の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
7 6 2 3 2 1 2 3 4
出力例1
35
下図は、はじめに積んだ立方体を正面から見たときの様子を表しています。
下図のように 6 個の立方体を取り除くと、ペンキを塗る面積は 35 となります。
入力例2
10 919924177 114777581 900857217 199708389 41623648 586160911 824291566 209849198 803644124 355106148 180322764
出力例2
9307626516