Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
プログラミングでは 16 進数がよく使われます。
16 進数では 0, 1, ..., 9 の数字の他に A, B, C, D, E, F の 6 つのアルファベットを使い，それぞれ 10, 11, 12, 13, 14, 15 を表します。
この問題では 2 つのアルファベット X, Y が与えられます。
X と Y はどちらも A, B, C, D, E, F のうちどれかです。
X と Y を 16 進数として見たとき，どちらのほうが大きいかを判定してください。
制約
- X, Y は
A,B,C,D,E,Fのうちどれかである。
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
X のほうが小さいならば <，Y のほうが小さいならば >，等しいならば = と出力してください。
入力例 1
A B
出力例 1
<
10 < 11 です。
入力例 2
E C
出力例 2
>
14 > 12 です。
入力例 3
F F
出力例 3
=
15 = 15 です。
Score : 100 points
Problem Statement
In programming, hexadecimal notation is often used.
In hexadecimal notation, besides the ten digits 0, 1, ..., 9, the six letters A, B, C, D, E and F are used to represent the values 10, 11, 12, 13, 14 and 15, respectively.
In this problem, you are given two letters X and Y. Each X and Y is A, B, C, D, E or F.
When X and Y are seen as hexadecimal numbers, which is larger?
Constraints
- Each X and Y is
A,B,C,D,EorF.
Input
Input is given from Standard Input in the following format:
X Y
Output
If X is smaller, print <; if Y is smaller, print >; if they are equal, print =.
Sample Input 1
A B
Sample Output 1
<
10 < 11.
Sample Input 2
E C
Sample Output 2
>
14 > 12.
Sample Input 3
F F
Sample Output 3
=
15 = 15.
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
幅 X センチメートルの椅子があります。 この椅子に座りたい人がたくさんおり，人は椅子に座ると必ず Y センチメートルの幅を使って座ります。
出来る限りたくさんの人を椅子に座らせたいですが， 人はみなシャイなので，人と人の間，また椅子の端と人の間には， 少なくとも Z センチメートル間を開ける必要があります。
最大で何人座ることができますか？
制約
- 入力は全て整数
- 1 \leq X, Y, Z \leq 10^5
- Y+2Z \leq X
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
求めた答えを出力してください。
入力例 1
13 3 1
出力例 1
3
下図のように座れば，ぴったし 3 人座ることが出来ます。
図
入力例 2
12 3 1
出力例 2
2
入力例 3
100000 1 1
出力例 3
49999
入力例 4
64146 123 456
出力例 4
110
入力例 5
64145 123 456
出力例 5
109
Score : 200 points
Problem Statement
We have a long seat of width X centimeters. There are many people who wants to sit here. A person sitting on the seat will always occupy an interval of length Y centimeters.
We would like to seat as many people as possible, but they are all very shy, and there must be a gap of length at least Z centimeters between two people, and between the end of the seat and a person.
At most how many people can sit on the seat?
Constraints
- All input values are integers.
- 1 \leq X, Y, Z \leq 10^5
- Y+2Z \leq X
Input
Input is given from Standard Input in the following format:
X Y Z
Output
Print the answer.
Sample Input 1
13 3 1
Sample Output 1
3
There is just enough room for three, as shown below:
Figure
Sample Input 2
12 3 1
Sample Output 2
2
Sample Input 3
100000 1 1
Sample Output 3
49999
Sample Input 4
64146 123 456
Sample Output 4
110
Sample Input 5
64145 123 456
Sample Output 5
109
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
高橋くんはプログラミングコンテストに出ていますが， YES か NO で答える問題でTLEしてしまいました。
提出の詳細を見ると，テストケースは全てで N ケースあり，そのうち M ケースでTLEしていました。
そこで高橋くんは, M ケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し， 残りの N-M ケースではそれぞれ実行に 100 ms かかって必ず正解するプログラムへ書き換えました。
そして，以下の操作を行います。
- このプログラムを提出する。
- 全てのケースの実行が終わるまで待機する。
- もし M ケースのうちどれかで不正解だった場合，もう一度プログラムを提出する。
- これを，一度で全てのケースに正解するまで繰り返す。
この操作が終了するまでの，プログラムの実行時間の総和の期待値を X msとした時，X を出力してください。
なお，X は整数で出力してください。
制約
- 入力は全て整数
- 1 \leq N \leq 100
- 1 \leq M \leq {\rm min}(N, 5)
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
実行時間の総和の期待値 X を整数で出力してください。 なお，X はこの問題の制約下で，10^9 以下の整数となることが証明できます。
入力例 1
1 1
出力例 1
3800
この入力だとケースは 1 ケースだけであり，1900 ms かかって 1/2 の確率で正解するプログラムを投げ続けます。
つまり 1 回で正解する確率は 1/2, 2 回で正解する確率は 1/4, 3 回で正解する確率は 1/8 です。
よって答えは 1900 \times 1/2 + (2 \times 1900) \times 1/4 + (3 \times 1900) \times 1/8 + ... = 3800 です。
入力例 2
10 2
出力例 2
18400
2 ケースで 1900 ms かかり，10-2=8 ケースで 100 ms かかるプログラムを投げ続けます。 全てのケースで正解する確率は 1/2 \times 1/2 = 1/4 です。
入力例 3
100 5
出力例 3
608000
Score : 300 points
Problem Statement
Takahashi is now competing in a programming contest, but he received TLE in a problem where the answer is YES or NO.
When he checked the detailed status of the submission, there were N test cases in the problem, and the code received TLE in M of those cases.
Then, he rewrote the code to correctly solve each of those M cases with 1/2 probability in 1900 milliseconds, and correctly solve each of the other N-M cases without fail in 100 milliseconds.
Now, he goes through the following process:
- Submit the code.
- Wait until the code finishes execution on all the cases.
- If the code fails to correctly solve some of the M cases, submit it again.
- Repeat until the code correctly solve all the cases in one submission.
Let the expected value of the total execution time of the code be X milliseconds. Print X (as an integer).
Constraints
- All input values are integers.
- 1 \leq N \leq 100
- 1 \leq M \leq {\rm min}(N, 5)
Input
Input is given from Standard Input in the following format:
N M
Output
Print X, the expected value of the total execution time of the code, as an integer. It can be proved that, under the constraints in this problem, X is an integer not exceeding 10^9.
Sample Input 1
1 1
Sample Output 1
3800
In this input, there is only one case. Takahashi will repeatedly submit the code that correctly solves this case with 1/2 probability in 1900 milliseconds.
The code will succeed in one attempt with 1/2 probability, in two attempts with 1/4 probability, and in three attempts with 1/8 probability, and so on.
Thus, the answer is 1900 \times 1/2 + (2 \times 1900) \times 1/4 + (3 \times 1900) \times 1/8 + ... = 3800.
Sample Input 2
10 2
Sample Output 2
18400
The code will take 1900 milliseconds in each of the 2 cases, and 100 milliseconds in each of the 10-2=8 cases. The probability of the code correctly solving all the cases is 1/2 \times 1/2 = 1/4.
Sample Input 3
100 5
Sample Output 3
608000
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
N 枚のカードからなる山札があります。カードにはそれぞれ数が書かれており， 上から i 枚目には a_i が書かれています。
この山札を使い，X さんと Y さんが 2 人でゲームをします。 X, Y さんは最初，Z, W が書かれたカードを持っています。 そして X さんから交互に以下を行います。
- 山札から何枚かカードを引く。そして今持っているカードを捨て，最後に引いたカードを代わりに持つ。ただし，必ず 1 枚は引かなくてはならない。
山札がなくなるとゲームは終了で，2 人の持っているカードに書かれた数の差の絶対値がこのゲームのスコアになります。
X さんはスコアを最大化するように，Y さんはスコアを最小化するようにゲームをプレイした時， スコアはいくつになるでしょうか？
制約
- 入力は全て整数
- 1 \leq N \leq 2000
- 1 \leq Z, W, a_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N Z W a_1 a_2 ... a_N
出力
求めたスコアを出力してください。
入力例 1
3 100 100 10 1000 100
出力例 1
900
X さんが最初に 2 枚カードを引くと，次に Y さんが最後のカードを引き，スコアは |1000 - 100| = 900 になります。
入力例 2
3 100 1000 10 100 100
出力例 2
900
X さんが最初に全てのカードを引くと，スコアは |100 - 1000| = 900 になります。
入力例 3
5 1 1 1 1 1 1 1
出力例 3
0
入力例 4
1 1 1 1000000000
出力例 4
999999999
Score : 500 points
Problem Statement
We have a deck consisting of N cards. Each card has an integer written on it. The integer on the i-th card from the top is a_i.
Two people X and Y will play a game using this deck. Initially, X has a card with Z written on it in his hand, and Y has a card with W written on it in his hand. Then, starting from X, they will alternately perform the following action:
- Draw some number of cards from the top of the deck. Then, discard the card in his hand and keep the last drawn card instead. Here, at least one card must be drawn.
The game ends when there is no more card in the deck. The score of the game is the absolute difference of the integers written on the cards in the two players' hand.
X will play the game so that the score will be maximized, and Y will play the game so that the score will be minimized. What will be the score of the game?
Constraints
- All input values are integers.
- 1 \leq N \leq 2000
- 1 \leq Z, W, a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N Z W a_1 a_2 ... a_N
Output
Print the score.
Sample Input 1
3 100 100 10 1000 100
Sample Output 1
900
If X draws two cards first, Y will draw the last card, and the score will be |1000 - 100| = 900.
Sample Input 2
3 100 1000 10 100 100
Sample Output 2
900
If X draws all the cards first, the score will be |1000 - 100| = 900.
Sample Input 3
5 1 1 1 1 1 1 1
Sample Output 3
0
Sample Input 4
1 1 1 1000000000
Sample Output 4
999999999