Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ある整数を 2 乗した整数を、平方と呼びます。 たとえば、1, 4, 9などは平方ですが、 2, 6 などは平方ではありません。
ヘイホー君はある日、整数 N を道端で拾いました。 平方が好きなヘイホー君は、 整数 N に以下の操作を繰り返すことで、平方を得ようと考えました。
- N に 1 を加算する。
ヘイホー君が平方を得るために必要な操作回数の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N
- 1 行目には、ヘイホー君が拾った整数 N (1 ≦ N ≦ 10,000) が与えられる。
出力
ヘイホー君が平方を得るために必要な最小の操作回数を 1 行に出力せよ。 出力の末尾には改行をいれること。
入力例1
7
出力例1
2
2 回の操作で 9 という平方を得ることができます。
入力例2
16
出力例2
0
16 は平方なので、一度も操作を行う必要はありません。
入力例3
82
出力例3
18
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ある文字列を 2 回繰り返してできる文字列を、平方と呼びます。
たとえば、abcabc や abababab は平方ですが、
abc や ababab は平方ではありません。
ヘイホー君はある日、英小文字のみからなる N 文字の文字列 S を、道端で拾いました。 平方が好きなヘイホー君は、 文字列 S に以下の操作を繰り返すことで、平方を得ようと考えました。
- 1 ≦ p ≦ N を満たす整数 p と、英小文字 c を選ぶ。その後、S の p 文字目を c に置き換える。
ヘイホー君が平方を得るために必要な操作回数の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N S
- 1 行目には、整数 N (1 ≦ N ≦ 100) が与えられる。これはヘイホー君が拾った文字列の長さを表す。
- 2 行目には、ヘイホー君が拾った文字列 S が与えられる。S は英小文字のみからなる N 文字の文字列であることが保証される。
出力
もしヘイホー君が平方を得ることができないならば、-1 を 1 行に出力せよ。 平方を得ることができるならば、そのために必要な最小の操作回数を 1 行に出力せよ。 いずれの場合も、出力の末尾には改行をいれること。
入力例1
8 abacbabc
出力例1
3
以下のように 3 回の操作を行うことで、aabcaabc という平方を得ることができます。
- 2 文字目を
aに置き換え、aaacbabcにする。 - 3 文字目を
bに置き換え、aabcbabcにする。 - 5 文字目を
aに置き換え、aabcaabcにする。
入力例2
8 abababab
出力例2
0
abababab は平方なので、一度も操作を行う必要はありません。
入力例3
5 abcde
出力例3
-1
どのように操作を行っても平方を得ることはできません。
入力例4
26 codefestivaltwozeroonefive
出力例4
11
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 という平方を得ることができます。