実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
とある世界では、今日は 12 月 D 日です。
D = 25 なら Christmas
, D = 24 なら Christmas Eve
, D = 23 なら Christmas Eve Eve
, D = 22 なら Christmas Eve Eve Eve
と出力するプログラムを作ってください。
制約
- 22 \leq D \leq 25
- D は整数である。
入力
入力は以下の形式で標準入力から与えられる。
D
出力
指定された文字列を出力せよ (大文字と小文字は区別される)。
入力例 1
25
出力例 1
Christmas
入力例 2
22
出力例 2
Christmas Eve Eve Eve
単語と単語の間のスペースも出力してください。
Score : 100 points
Problem Statement
In some other world, today is December D-th.
Write a program that prints Christmas
if D = 25, Christmas Eve
if D = 24, Christmas Eve Eve
if D = 23 and Christmas Eve Eve Eve
if D = 22.
Constraints
- 22 \leq D \leq 25
- D is an integer.
Input
Input is given from Standard Input in the following format:
D
Output
Print the specified string (case-sensitive).
Sample Input 1
25
Sample Output 1
Christmas
Sample Input 2
22
Sample Output 2
Christmas Eve Eve Eve
Be sure to print spaces between the words.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
とある世界では、今日はクリスマスイブの前日です。
高羽氏は、デパートで N 個の品物を買おうとしています。i 個目の品物 (1 \leq i \leq N) の定価は p_i 円です。
彼は割引券を持っており、N 個のうち最も定価が高い品物 1 個を定価の半額で買うことができます。残りの N-1 個の品物に対しては定価を支払います。支払金額は合計でいくらになるでしょうか?
制約
- 2 \leq N \leq 10
- 100 \leq p_i \leq 10000
- p_i は偶数である。
入力
入力は以下の形式で標準入力から与えられる。
N p_1 p_2 : p_N
出力
合計支払金額を (整数として) 出力せよ。
入力例 1
3 4980 7980 6980
出力例 1
15950
7980 円の品物が半額になり、合計 4980 + 7980 / 2 + 6980 = 15950 円です。
15950.0
などと出力すると Wrong Answer と判定されるので注意してください。
入力例 2
4 4320 4320 4320 4320
出力例 2
15120
4 個の品物のうち 1 個だけが半額になり、合計 4320 / 2 + 4320 + 4320 + 4320 = 15120 円です。
Score : 200 points
Problem Statement
In some other world, today is the day before Christmas Eve.
Mr. Takaha is buying N items at a department store. The regular price of the i-th item (1 \leq i \leq N) is p_i yen (the currency of Japan).
He has a discount coupon, and can buy one item with the highest price for half the regular price. The remaining N-1 items cost their regular prices. What is the total amount he will pay?
Constraints
- 2 \leq N \leq 10
- 100 \leq p_i \leq 10000
- p_i is an even number.
Input
Input is given from Standard Input in the following format:
N p_1 p_2 : p_N
Output
Print the total amount Mr. Takaha will pay.
Sample Input 1
3 4980 7980 6980
Sample Output 1
15950
The 7980-yen item gets the discount and the total is 4980 + 7980 / 2 + 6980 = 15950 yen.
Note that outputs such as 15950.0
will be judged as Wrong Answer.
Sample Input 2
4 4320 4320 4320 4320
Sample Output 2
15120
Only one of the four items gets the discount and the total is 4320 / 2 + 4320 + 4320 + 4320 = 15120 yen.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
とある世界では、今日はクリスマスイブです。
高羽氏の庭には N 本の木が植えられています。i 本目の木 (1 \leq i \leq N) の高さは h_i メートルです。
彼は、これらの木のうち K 本を選んで電飾を施すことにしました。より美しい光景をつくるために、できるだけ近い高さの木を飾り付けたいです。
より具体的には、飾り付ける木のうち最も高いものの高さを h_{max} メートル、最も低いものの高さを h_{min} メートルとすると、h_{max} - h_{min} が小さいほど好ましいです。h_{max} - h_{min} は最小でいくつにすることができるでしょうか?
制約
- 2 \leq K < N \leq 10^5
- 1 \leq h_i \leq 10^9
- h_i は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K h_1 h_2 : h_N
出力
h_{max} - h_{min} としてありうる最小の値を出力せよ。
入力例 1
5 3 10 15 11 14 12
出力例 1
2
1, 3, 5 本目の木を飾り付けると h_{max} = 12, h_{min} = 10 となり h_{max} - h_{min} = 2 で、これが最適です。
入力例 2
5 3 5 7 5 7 7
出力例 2
0
2, 4, 5 本目の木を飾り付けると h_{max} = 7, h_{min} = 7 となり h_{max} - h_{min} = 0 で、これが最適です。
これらの入力例では木の数がそれほど多くありませんが、最大で 10 万本の木がある可能性に注意してください (ここに 10 万行の入力例を貼るわけにはいかないのです)。
Score : 300 points
Problem Statement
In some other world, today is Christmas Eve.
There are N trees planted in Mr. Takaha's garden. The height of the i-th tree (1 \leq i \leq N) is h_i meters.
He decides to choose K trees from these trees and decorate them with electric lights. To make the scenery more beautiful, the heights of the decorated trees should be as close to each other as possible.
More specifically, let the height of the tallest decorated tree be h_{max} meters, and the height of the shortest decorated tree be h_{min} meters. The smaller the value h_{max} - h_{min} is, the better. What is the minimum possible value of h_{max} - h_{min}?
Constraints
- 2 \leq K < N \leq 10^5
- 1 \leq h_i \leq 10^9
- h_i is an integer.
Input
Input is given from Standard Input in the following format:
N K h_1 h_2 : h_N
Output
Print the minimum possible value of h_{max} - h_{min}.
Sample Input 1
5 3 10 15 11 14 12
Sample Output 1
2
If we decorate the first, third and fifth trees, h_{max} = 12, h_{min} = 10 so h_{max} - h_{min} = 2. This is optimal.
Sample Input 2
5 3 5 7 5 7 7
Sample Output 2
0
If we decorate the second, fourth and fifth trees, h_{max} = 7, h_{min} = 7 so h_{max} - h_{min} = 0. This is optimal.
There are not too many trees in these sample inputs, but note that there can be at most one hundred thousand trees (we just can't put a sample with a hundred thousand lines here).
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
とある世界では、今日はクリスマスです。
高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル L バーガー (L は 0 以上の整数) とは次のようなものです。
- レベル 0 バーガーとは、パティ 1 枚である。
- レベル L バーガー (L \geq 1) とは、バン 1 枚、レベル L-1 バーガー、パティ 1 枚、レベル L-1 バーガー、バン 1 枚、をこの順に下から積み重ねたものである。
例えば、パティを P
、バンを B
で表すと、レベル 1 バーガーは BPPPB
(を 90 度回転したもの)、レベル 2 バーガーは BBPPPBPBPPPBB
といった見た目になります。
高羽氏が作るのはレベル N バーガーです。ダックスフンドのルンルンは、このバーガーの下から X 層を食べます (パティまたはバン 1 枚を 1 層とします)。ルンルンはパティを何枚食べるでしょうか?
制約
- 1 \leq N \leq 50
- 1 \leq X \leq ( レベル N バーガーの層の総数 )
- N, X は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X
出力
レベル N バーガーの下から X 層に含まれるパティの枚数を出力せよ。
入力例 1
2 7
出力例 1
4
レベル 2 バーガー (BBPPPBPBPPPBB
) の下から 7 層にはパティが 4 枚含まれます。
入力例 2
1 1
出力例 2
0
レベル 1 バーガーの一番下の層はバンです。
入力例 3
50 4321098765432109
出力例 3
2160549382716056
レベル 50 バーガーは層の数が 32 ビット整数に収まらない程度に分厚いです。
Score : 400 points
Problem Statement
In some other world, today is Christmas.
Mr. Takaha decides to make a multi-dimensional burger in his party. A level-L burger (L is an integer greater than or equal to 0) is the following thing:
- A level-0 burger is a patty.
- A level-L burger (L \geq 1) is a bun, a level-(L-1) burger, a patty, another level-(L-1) burger and another bun, stacked vertically in this order from the bottom.
For example, a level-1 burger and a level-2 burger look like BPPPB
and BBPPPBPBPPPBB
(rotated 90 degrees), where B
and P
stands for a bun and a patty.
The burger Mr. Takaha will make is a level-N burger. Lunlun the Dachshund will eat X layers from the bottom of this burger (a layer is a patty or a bun). How many patties will she eat?
Constraints
- 1 \leq N \leq 50
- 1 \leq X \leq ( the total number of layers in a level-N burger )
- N and X are integers.
Input
Input is given from Standard Input in the following format:
N X
Output
Print the number of patties in the bottom-most X layers from the bottom of a level-N burger.
Sample Input 1
2 7
Sample Output 1
4
There are 4 patties in the bottom-most 7 layers of a level-2 burger (BBPPPBPBPPPBB
).
Sample Input 2
1 1
Sample Output 2
0
The bottom-most layer of a level-1 burger is a bun.
Sample Input 3
50 4321098765432109
Sample Output 3
2160549382716056
A level-50 burger is rather thick, to the extent that the number of its layers does not fit into a 32-bit integer.