CODE FESTIVAL 2015 予選A

A - CODE FESTIVAL 2015

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

このコンテストの名前はCODE FESTIVAL 2015です。

しかし、高橋君はいつもCODE FESTIVAL 2014というように年度を間違えてしまいます。

そこで高橋君は、文字列の末尾の2014を2015に書き換えるソフトを作ろうと思いました。

末尾が2014である文字列 S が与えられます。文字列 S の末尾の2014を2015に書き換えた文字列を出力してください。

入力

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

1 行目には、文字列 S (5 ≦ |S| ≦ 100) が与えられる。ただし、|S| は文字列 S の長さを表す。
S の末尾 4 文字は2014であり、それ以外の文字は全て大文字アルファベットであることが保証されている。

出力

文字列 S の末尾の2014を2015に書き換えた文字列を 1 行で出力せよ。出力の末尾には改行をいれること。

入力例1

CODEFESTIVAL2014

出力例1

CODEFESTIVAL2015

入力例2

CHOKUDAI2014

出力例2

CHOKUDAI2015

B - とても長い数列

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は長さ N の数列 A = \{A_1, A_2, ..., A_N\} を用意しました。高橋君は数列 A を元に「とても長い数列」を、以下のような手順で作ろうとしています。

まず長さ 0 の数列を用意し、これを S と呼ぶことにする。
S、A_1、S をこの順につなげた数列を新たな S とする。
S、A_2、S をこの順につなげた数列を新たな S とする。
（中略）
S、A_N、S をこの順につなげた数列を新たな S とする。
この時点での S を「とても長い数列」とする。

例えば N = 3, A_1 = 1, A_2 = 2, A_3 = 3 なら、S は \{\}　→ \{1\} → \{1,2,1\} → \{1,2,1,3,1,2,1\} と変化し、「とても長い数列」は \{1,2,1,3,1,2,1\} となります。

高橋君はこの手順によって作られる「とても長い数列」に含まれる数の和を知りたがっています。これを高橋君の代わりに計算するプログラムを作成してください。

入力

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

N
A_1 A_2 ... A_N

1 行目には、整数 N (1 ≦ N ≦ 30) が与えられる。
2 行目には、N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目には、整数 A_i (0 ≦ A_i ≦ 100) が与えられる。
「とても長い数列」に含まれる数の和は 10^9 以下となることが保証されている。

出力

「とても長い数列」に含まれる数の和を 1 行に出力せよ。出力の末尾に改行を入れること。

部分点

この問題には部分点が設定されている。

N ≦ 10 を満たすデータセットに正解した場合は、60 点が与えられる。
追加の制約のないデータセットに正解した場合は、上記とは別に 40 点が与えられる。

入力例1

3
1 2 3

出力例1

この入力例は問題文中の例と同じです。

「とても長い数列」は \{1,2,1,3,1,2,1\} となり、1+2+1+3+1+2+1 = 11 であるため 11 を出力します。

入力例2

8
0 1 3 6 12 25 50 100

出力例2

入力例3

30
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例3

536870912

「とても長い数列」はとても長くなることがあるので注意してください。

C - 8月31日

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

とある星のとある 8 月 31 日のことです。とある星の高橋君はあることに気づいてしまいました。今日で夏休みが終わりであるにもかかわらず、宿題が全く終わっていないのです！

宿題のタイムリミットまではあと T 分あります。そして、高橋君がやらなければいけない宿題は N 個あります。i 番目の宿題を高橋君が解くには A_i 分かかりますが、高橋君の友達である青木君が解いた宿題を丸写ししてしまうことで B_i 分で終わらせることもできます。しかし友達の宿題を写すのはあまり良くないことなので、高橋君はできるだけ写さないようにしたいと思っています。

タイムリミットまでに全ての宿題を終わらせるために高橋君が写す必要のある宿題の個数の最小値を出力してください。ただし、全ての宿題を写してもタイムリミットまでに終わらせることができない場合は代わりに -1 を出力してください。

入力

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

N T
A_1 B_1
A_2 B_2
:
A_N B_N

1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), T (0 ≦ T ≦ 10^9) が空白区切りで与えられる。これは、宿題が N 個あり、タイムリミットまでの時間が T 分であることを表す。
2 行目からの N 行には、宿題にかかる時間の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、2 つの整数 A_i, B_i (0 ≦ B_i < A_i ≦ 10^4) が空白区切りで与えられる。これは、i 番目の宿題を高橋君が解くと A_i 分かかり、写すと B_i 分かかることを表す。B_i < A_i であることに注意せよ。

部分点

この問題には部分点が設定されている。

B_i = 0 を満たすデータセットに正解した場合は、30 点が与えられる。
追加の制約のないデータセットに正解した場合は、上記とは別に 70 点が与えられる。

出力

T 分以内に全ての宿題を終わらせるために高橋君が写す必要のある宿題の個数の最小値を 1 行に出力せよ。ただし、全ての宿題を写しても T 分以内に終わらせることができない場合は代わりに -1 を出力せよ。出力の末尾に改行を入れること。

入力例1

出力例1

例えば、2 番目と 3 番目の宿題を写せば 7(=1+0+0+2+4) 分で全ての宿題を終わらせることができます。

入力例2

1 1000000000
5 0

出力例2

宿題を写さなくてもタイムリミットに間に合います。

入力例3

1 0
100 99

出力例3

-1

宿題を写してもタイムリミットに間に合いません。

入力例4

出力例4

入力例5

出力例5

D - 壊れた電車

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋鉄道では、N 両編成の電車の一部が壊れてしまったため、M 人の整備士が点検をすることになりました。

i 人目の整備士ははじめ、X_i 両目の車両にいます。それぞれの整備士は、今いる車両を点検することと、隣の車両に移動することができます。車両の点検には時間はかかりませんが、隣の車両に移動するには 1 分かかります。

全ての車両を少なくとも 1 人の整備士が点検した状態になると点検作業は終了となります。点検作業は最短何分で終了させることができるでしょうか。

入力

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

N M
X_1
X_2
:
X_M

1 行目には、2 つの整数 N (1 ≦ N ≦ 10^9), M (1 ≦ M ≦ 10^5, M ≦ N) が空白区切りで与えられる。これは、電車が N 両の車両からなり、整備士が M 人いることを表す。
2 行目からの M 行には、整備士の情報が与えられる。このうち i (1 ≦ i ≦ M) 行目には、整数 X_i (1 ≦ X_i ≦ N) が与えられる。これは、i 人目の整備士がはじめ X_i 両目の車両にいることを表す。ただし、X_i は全て相異なることが保証される。また、整備士の情報は 1 両目の車両に近い順に与えられる、つまり X_j < X_{j+1} (1 ≦ j ≦ M-1) であることが保証される。

部分点

この問題には部分点が設定されている。

N ≦ 100 を満たすデータセットに正解した場合は、20 点が与えられる。
N ≦ 500,000 を満たすデータセットに正解した場合は、上記とは別に 60 点が与えられる。
追加の制約のないデータセットに正解した場合は、上記とは別に 20 点が与えられる。

出力

点検作業にかかる時間の最小値を分単位で 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

出力例1

下の図のように整備士が移動すれば 3 分で点検作業を終了させることができます。

入力例2