Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
高橋君はあるプログラミングコンテストが行われているサイトに参加しています。
ここでは, コンテストに出場した時にこの順位に応じて「パフォーマンス」というものがつき、それによってレーティング (整数とは限らない) が次のように変化します。
- 現在のレーティングを a とする。
- 次のコンテストで, パフォーマンス b を取ったとする。
- そのとき, レーティングは a と b の平均まで変化する。
例えば, レーティングが 1 の人が次のコンテストでパフォーマンス 1000 を取ったら, レーティングは 1 と 1000 の平均である 500.5 になります。
高橋君は, 現在のレーティングが R で, 次のコンテストでレーティングをちょうど G にしたいと思っています。
そのとき, 高橋君が取るべきパフォーマンスを求めなさい。
制約
- 0 \leq R, G \leq 4500
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
R G
出力
高橋君が取るべきパフォーマンスを出力しなさい。
入力例 1
2002 2017
出力例 1
2032
高橋君の今のレーティングは 2002 です。
次のコンテストでパフォーマンス 2032 を取ると、レーティングは 2002 と 2032 の平均である 2017 となり、目標を達成することができます。
入力例 2
4500 0
出力例 2
-4500
現在のレーティングと目標のレーティングは 0 以上 4500 以下ですが、0 未満のパフォーマンスも取ることができます。
Score : 100 points
Problem Statement
Takahashi is a user of a site that hosts programming contests.
When a user competes in a contest, the rating of the user (not necessarily an integer) changes according to the performance of the user, as follows:
- Let the current rating of the user be a.
- Suppose that the performance of the user in the contest is b.
- Then, the new rating of the user will be the avarage of a and b.
For example, if a user with rating 1 competes in a contest and gives performance 1000, his/her new rating will be 500.5, the average of 1 and 1000.
Takahashi's current rating is R, and he wants his rating to be exactly G after the next contest.
Find the performance required to achieve it.
Constraints
- 0 \leq R, G \leq 4500
- All input values are integers.
Input
Input is given from Standard Input in the following format:
R G
Output
Print the performance required to achieve the objective.
Sample Input 1
2002 2017
Sample Output 1
2032
Takahashi's current rating is 2002.
If his performance in the contest is 2032, his rating will be the average of 2002 and 2032, which is equal to the desired rating, 2017.
Sample Input 2
4500 0
Sample Output 2
-4500
Although the current and desired ratings are between 0 and 4500, the performance of a user can be below 0.
Time Limit: 2 sec / Memory Limit: 256 MB
配点：200 点
問題文
square1001 は、電光掲示板に整数 1 が表示されているのを見ました。
彼は、電光掲示板に対して、以下の操作 A, 操作 B をすることができます。
- 操作 A： 電光掲示板に表示する整数を「今の電光掲示板の整数を 2 倍にしたもの」に変える。
- 操作 B： 電光掲示板に表示する整数を「今の電光掲示板の整数に K を足したもの」に変える。
square1001 は、操作 A, 操作 B 合計で N 回 行わなければなりません。 そのとき、N 回の操作後の、電光掲示板に書かれている整数として考えられる最小の値を求めなさい。
制約
- 1 \leq N, K \leq 10
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
square1001 が N 回操作を行った後の、電光掲示板に書かれている整数として考えられる最小値を出力しなさい。
入力例 1
4 3
出力例 1
10
高橋君は、操作 A, A, B, B の順でやると、整数を最小化できます。 この時、電光掲示板に書かれている整数は 1 → 2 → 4 → 7 → 10 と変わり、最終的に 10 となります。
入力例 2
10 10
出力例 2
76
高橋君は、操作 A, A, A, A, B, B, B, B, B, B の順にやると、整数を最小化できます。 この時、電光掲示板に書かれている整数は 1 → 2 → 4 → 8 → 16 → 26 → 36 → 46 → 56 → 66 → 76 と変わり、最終的に 76 となります。
なお、今日のコンテストは、AtCoder Beginner Contest 076 です。
Score : 200 points
Problem Statement
Square1001 has seen an electric bulletin board displaying the integer 1. He can perform the following operations A and B to change this value:
- Operation A: The displayed value is doubled.
- Operation B: The displayed value increases by K.
Square1001 needs to perform these operations N times in total. Find the minimum possible value displayed in the board after N operations.
Constraints
- 1 \leq N, K \leq 10
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the minimum possible value displayed in the board after N operations.
Sample Input 1
4 3
Sample Output 1
10
The value will be minimized when the operations are performed in the following order: A, A, B, B.
In this case, the value will change as follows: 1 → 2 → 4 → 7 → 10.
Sample Input 2
10 10
Sample Output 2
76
The value will be minimized when the operations are performed in the following order: A, A, A, A, B, B, B, B, B, B.
In this case, the value will change as follows: 1 → 2 → 4 → 8 → 16 → 26 → 36 → 46 → 56 → 66 → 76.
By the way, this contest is AtCoder Beginner Contest 076.
Time Limit: 2 sec / Memory Limit: 256 MB
配点：300 点
問題文
E869120 は、宝物が入ってそうな箱を見つけました。
しかし、これには鍵がかかっており、鍵を開けるためには英小文字からなる文字列 S が必要です。
彼は文字列 S' を見つけ、これは文字列 S の 0 個以上 |S| 個以内の文字が ? に置き換わった文字列であることも分かりました。
ただし、文字列 A に対して、|A| を「文字列 A の長さ」とします。
そこで、E869120 はヒントとなる紙を見つけました。
- 条件1：文字列 S の中に連続する部分文字列として英小文字から成る文字列 T が含まれている。
- 条件2：S は、条件1を満たす文字列の中で辞書順最小の文字列である。
そのとき、鍵となる文字列 S を出力しなさい。
ただし、そのような文字列 S が存在しない場合は代わりに UNRESTORABLE と出力しなさい。
制約
- 1 \leq |S'|, |T| \leq 50
- S' は英小文字と
?から成る - T は英小文字から成る
入力
入力は以下の形式で標準入力から与えられる。
S' T
出力
鍵となる文字列 S を出力しなさい。
ただし、そのような文字列 S が存在しない場合は、代わりに UNRESTORABLE と出力しなさい。
入力例 1
?tc???? coder
出力例 1
atcoder
条件1 を満たす文字列は atcoder, btcoder, ctcoder,..., ztcoder の 26 個がありますが、その中で最も辞書順で小さいものは atcoder なので、S = atcoder と特定できます。
入力例 2
??p??d?? abc
出力例 2
UNRESTORABLE
条件1を満たすような文字列 S が存在しないので、鍵となる文字列 S は存在しません。
Score : 300 points
Problem Statement
E869120 found a chest which is likely to contain treasure.
However, the chest is locked. In order to open it, he needs to enter a string S consisting of lowercase English letters.
He also found a string S', which turns out to be the string S with some of its letters (possibly all or none) replaced with ?.
One more thing he found is a sheet of paper with the following facts written on it:
- Condition 1: The string S contains a string T as a contiguous substring.
- Condition 2: S is the lexicographically smallest string among the ones that satisfy Condition 1.
Print the string S.
If such a string does not exist, print UNRESTORABLE.
Constraints
- 1 \leq |S'|, |T| \leq 50
- S' consists of lowercase English letters and
?. - T consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S T'
Output
Print the string S.
If such a string does not exist, print UNRESTORABLE instead.
Sample Input 1
?tc???? coder
Sample Output 1
atcoder
There are 26 strings that satisfy Condition 1: atcoder, btcoder, ctcoder,..., ztcoder.
Among them, the lexicographically smallest is atcoder, so we can say S = atcoder.
Sample Input 2
??p??d?? abc
Sample Output 2
UNRESTORABLE
There is no string that satisfies Condition 1, so the string S does not exist.
Time Limit: 2 sec / Memory Limit: 256 MB
配点：400 点
問題文
2168年、AtCoder 社は成長し、ついに "AtCoder特急" という鉄道を建設することを決めた。
さて、社長の高橋君は、"AtCoder特急" の列車を以下のように運行することを計画した。
- 列車の走行時間は、(t_1 + t_2 + t_3 + ... + t_N) 秒である。
- 最初の t_1 秒間は、列車は速度 v_1 m/s 以内で走っていなければならない。また、次の t_2 秒間は、列車は速度 v_2 m/s 以内で走っていなければならない。 次の t_3 秒間、またそれ以降についても同様である。
- 最後の t_N 秒間は、列車は速度 v_N m/s 以内で走っていなければならない。
ただし、列車の性能上、加速度は ±1m/s^2 以内でなければならない。また、走行開始時と走行終了時には列車は止まっていなければならない。
列車が発車してから停車するまでに走れる最大の距離を求めなさい。
制約
- 1 \leq N \leq 100
- 1 \leq t_i \leq 200
- 1 \leq v_i \leq 100
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N t_1 t_2 t_3 … t_N v_1 v_2 v_3 … v_N
出力
列車が発車してから停車するまでに走ることのできる最大の距離を出力しなさい。 ただし、絶対誤差が 10^{-3} 以内であれば、正解となります。
入力例 1
1 100 30
出力例 1
2100.000000000000000
- 最初の 30 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 450m 走ります。
- 次の 40 秒は、速度 30m/s を保ちます。その間に列車は 1200m 走ります。
- 最後の 30 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 450m 走ります。
合計で、450 + 1200 + 450 = 2100m 走ることができます。
入力例 2
2 60 50 34 38
出力例 2
2632.000000000000000
- 最初の 34 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 578m 走ります。
- 次の 26 秒は、速度 34m/s を保ちます。その間に列車は 884m 走ります。
- 次の 4 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 144m 走ります。
- 次の 8 秒は、速度 38m/s を保ちます。その間は列車は 304m 走ります。
- 最後の 38 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 722m 走ります。
合計で、578 + 884 + 144 + 304 + 722 = 2632m 走ることができます。
入力例 3
3 12 14 2 6 2 7
出力例 3
76.000000000000000
- 最初の 6 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 18m 走ります。
- 次の 2 秒は、速度 6m/s を保ちます。その間に列車は 12m 走ります。
- 次の 4 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 16m 走ります。
- 次の 14 秒は、速度 2m/s を保ちます。その間は列車は 28m 走ります。
- 最後の 2 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 2m 走ります。
合計で、18 + 12 + 16 + 28 + 2 = 76m 走ることができます。
入力例 4
1 9 10
出力例 4
20.250000000000000000
- 最初の 4.5 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 10.125m 走ります。
- 最後の 4.5 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 10.125m 走ります。
合計で、10.125 + 10.125 = 20.25m 走ることができます。
入力例 5
10 64 55 27 35 76 119 7 18 49 100 29 19 31 39 27 48 41 87 55 70
出力例 5
20291.000000000000
Score : 400 points
Problem Statement
In the year 2168, AtCoder Inc., which is much larger than now, is starting a limited express train service called AtCoder Express.
In the plan developed by the president Takahashi, the trains will run as follows:
- A train will run for (t_1 + t_2 + t_3 + ... + t_N) seconds.
- In the first t_1 seconds, a train must run at a speed of at most v_1 m/s (meters per second). Similarly, in the subsequent t_2 seconds, a train must run at a speed of at most v_2 m/s, and so on.
According to the specifications of the trains, the acceleration of a train must be always within ±1m/s^2. Additionally, a train must stop at the beginning and the end of the run.
Find the maximum possible distance that a train can cover in the run.
Constraints
- 1 \leq N \leq 100
- 1 \leq t_i \leq 200
- 1 \leq v_i \leq 100
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N t_1 t_2 t_3 … t_N v_1 v_2 v_3 … v_N
Output
Print the maximum possible that a train can cover in the run.
Output is considered correct if its absolute difference from the judge's output is at most 10^{-3}.
Sample Input 1
1 100 30
Sample Output 1
2100.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first 30 seconds, it accelerates at a rate of 1m/s^2, covering 450 meters.
- In the subsequent 40 seconds, it maintains the velocity of 30m/s, covering 1200 meters.
- In the last 30 seconds, it decelerates at the acceleration of -1m/s^2, covering 450 meters.
The total distance covered is 450 + 1200 + 450 = 2100 meters.
Sample Input 2
2 60 50 34 38
Sample Output 2
2632.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first 34 seconds, it accelerates at a rate of 1m/s^2, covering 578 meters.
- In the subsequent 26 seconds, it maintains the velocity of 34m/s, covering 884 meters.
- In the subsequent 4 seconds, it accelerates at a rate of 1m/s^2, covering 144 meters.
- In the subsequent 8 seconds, it maintains the velocity of 38m/s, covering 304 meters.
- In the last 38 seconds, it decelerates at the acceleration of -1m/s^2, covering 722 meters.
The total distance covered is 578 + 884 + 144 + 304 + 722 = 2632 meters.
Sample Input 3
3 12 14 2 6 2 7
Sample Output 3
76.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first 6 seconds, it accelerates at a rate of 1m/s^2, covering 18 meters.
- In the subsequent 2 seconds, it maintains the velocity of 6m/s, covering 12 meters.
- In the subsequent 4 seconds, it decelerates at the acceleration of -1m/s^2, covering 16 meters.
- In the subsequent 14 seconds, it maintains the velocity of 2m/s, covering 28 meters.
- In the last 2 seconds, it decelerates at the acceleration of -1m/s^2, covering 2 meters.
The total distance covered is 18 + 12 + 16 + 28 + 2 = 76 meters.
Sample Input 4
1 9 10
Sample Output 4
20.250000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first 4.5 seconds, it accelerates at a rate of 1m/s^2, covering 10.125 meters.
- In the last 4.5 seconds, it decelerates at the acceleration of -1m/s^2, covering 10.125 meters.
The total distance covered is 10.125 + 10.125 = 20.25 meters.
Sample Input 5
10 64 55 27 35 76 119 7 18 49 100 29 19 31 39 27 48 41 87 55 70
Sample Output 5
20291.000000000000