Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
英小文字のみからなる 2 つの文字列 S, T が与えられます。これらの文字列を T, S の順に空白を空けずに連結し、できる文字列を出力してください。
制約
- S, T は英小文字のみからなる文字列
- S, T の長さは 1 以上 100 以下
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
できる文字列を出力せよ。
入力例 1
oder atc
出力例 1
atcoder
S = oder
, T = atc
のとき、T, S の順に連結してできる文字列は atcoder
です。
入力例 2
humu humu
出力例 2
humuhumu
Score : 100 points
Problem Statement
Given are two strings S and T consisting of lowercase English letters. Concatenate T and S in this order, without space in between, and print the resulting string.
Constraints
- S and T are strings consisting of lowercase English letters.
- The lengths of S and T are between 1 and 100 (inclusive).
Input
Input is given from Standard Input in the following format:
S T
Output
Print the resulting string.
Sample Input 1
oder atc
Sample Output 1
atcoder
When S = oder
and T = atc
, concatenating T and S in this order results in atcoder
.
Sample Input 2
humu humu
Sample Output 2
humuhumu
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋君は A 枚、青木君は B 枚のクッキーを持っています。
高橋君は以下の行動を K 回繰り返します。
- もし高橋君がクッキーを 1 枚以上持っているなら、高橋君のクッキーを 1 枚食べる。
- そうでなく、もし青木君がクッキーを 1 枚以上持っているなら、青木君のクッキーを 1 枚食べる。
- 高橋君も青木君もクッキーを持っていないなら、何もしない。
高橋君と青木君が最終的に持っているクッキーの枚数をそれぞれ求めてください。
制約
- 0 \leq A \leq 10^{12}
- 0 \leq B \leq 10^{12}
- 0 \leq K \leq 10^{12}
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B K
出力
高橋君と青木君のそれぞれが最終的に持っているクッキーの枚数を出力せよ。
入力例 1
2 3 3
出力例 1
0 2
高橋君は次のように行動します。
- 高橋君はクッキーを 2 枚持っているので、自分のクッキーを 1 枚食べる。
- 高橋君はクッキーを 1 枚持っているので、自分のクッキーを 1 枚食べる。
- 高橋君はクッキーを持っておらず、青木君はクッキーを 3 枚持っているので、青木君のクッキーを 1 枚食べる。
したがって、最終的に持っているクッキーの枚数は、高橋君が 0 枚、青木君が 2 枚になります。
入力例 2
500000000000 500000000000 1000000000000
出力例 2
0 0
オーバーフローに注意してください。
Score : 200 points
Problem Statement
Takahashi has A cookies, and Aoki has B cookies. Takahashi will do the following action K times:
- If Takahashi has one or more cookies, eat one of his cookies.
- Otherwise, if Aoki has one or more cookies, eat one of Aoki's cookies.
- If they both have no cookies, do nothing.
In the end, how many cookies will Takahashi and Aoki have, respectively?
Constraints
- 0 \leq A \leq 10^{12}
- 0 \leq B \leq 10^{12}
- 0 \leq K \leq 10^{12}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B K
Output
Print the numbers of Takahashi's and Aoki's cookies after K actions.
Sample Input 1
2 3 3
Sample Output 1
0 2
Takahashi will do the following:
- He has two cookies, so he eats one of them.
- Now he has one cookie left, and he eats it.
- Now he has no cookies left, but Aoki has three, so Takahashi eats one of them.
Thus, in the end, Takahashi will have 0 cookies, and Aoki will have 2.
Sample Input 2
500000000000 500000000000 1000000000000
Sample Output 2
0 0
Watch out for overflows.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 300 点
問題文
X 以上の素数のうち、最小のものを求めよ。
注記
素数とは、2 以上の整数であって、1 と自分自身を除くどの正の整数でも割り切れないようなもののことです。
例えば、2, 3, 5 は素数ですが、4, 6 は素数ではありません。
制約
- 2 \le X \le 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
X 以上の素数のうち、最小のものを出力せよ。
入力例 1
20
出力例 1
23
20 以上の素数のうち、最小のものは 23 です。
入力例 2
2
出力例 2
2
X が素数である場合もあります。
入力例 3
99992
出力例 3
100003
Score: 300 points
Problem Statement
Find the minimum prime number greater than or equal to X.
Notes
A prime number is an integer greater than 1 that cannot be evenly divided by any positive integer except 1 and itself.
For example, 2, 3, and 5 are prime numbers, while 4 and 6 are not.
Constraints
- 2 \le X \le 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
Output
Print the minimum prime number greater than or equal to X.
Sample Input 1
20
Sample Output 1
23
The minimum prime number greater than or equal to 20 is 23.
Sample Input 2
2
Sample Output 2
2
X itself can be a prime number.
Sample Input 3
99992
Sample Output 3
100003
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋君は、ゲームセンターで「じゃんけんバトル」というゲームをプレイすることにしました。このゲームのルールは以下の通りです。
- プレイヤーは筐体と N 回じゃんけんを行う (あいこの場合も 1 回のジャンケンと数える)。
- プレイヤーがじゃんけんで勝った場合、プレイヤーは出した手に応じて以下のスコアを得る (あいこや負けは 0 点)。
- グーで勝った場合、 R 点
- チョキで勝った場合、 S 点
- パーで勝った場合、 P 点
- ただし、ちょうど K 回前のじゃんけんで出した手と同じ手を出すことはできない。( K 回目までのじゃんけんでは好きな手を出せる。)
筐体は、各回のジャンケンで出す手をゲーム開始前に決定します。能力者である高橋君は、ゲーム開始前にこれをすべて読み取りました。
高橋君が読み取った情報は文字列 T として与えられます。T の i(1 \leq i \leq N) 文字目が r
のときは i 回目のじゃんけんで筐体がグーを出すことを、s
のときはチョキを出すことを、p
のときはパーを出すことを表します。
高橋君が N 回のじゃんけんで出す手を最適に選んだとき、ゲーム終了までに最大で合計何点を得られるでしょうか。
制約
- 2 \leq N \leq 10^5
- 1 \leq K \leq N-1
- 1 \leq R,S,P \leq 10^4
- N,K,R,S,P は全て整数である。
- |T| = N
- T に含まれる文字は
r
,s
,p
のいずれかである。
入力
入力は以下の形式で標準入力から与えられる。
N K R S P T
出力
得られる最大の合計スコアを出力せよ。
入力例 1
5 2 8 7 6 rsrpr
出力例 1
27
筐体は、{グー、チョキ、グー、パー、グー} と手を出します。
これに対して、例えば {パー、グー、グー、チョキ、パー} と出せば、27 点を獲得できます。 これより大きい点は獲得できないので、27 を出力します。
入力例 2
7 1 100 10 1 ssssppr
出力例 2
211
入力例 3
30 5 325 234 123 rspsspspsrpspsppprpsprpssprpsr
出力例 3
4996
Score : 400 points
Problem Statement
At an arcade, Takahashi is playing a game called RPS Battle, which is played as follows:
- The player plays N rounds of Rock Paper Scissors against the machine. (See Notes for the description of Rock Paper Scissors. A draw also counts as a round.)
- Each time the player wins a round, depending on which hand he/she uses, he/she earns the following score (no points for a draw or a loss):
- R points for winning with Rock;
- S points for winning with Scissors;
- P points for winning with Paper.
- However, in the i-th round, the player cannot use the hand he/she used in the (i-K)-th round. (In the first K rounds, the player can use any hand.)
Before the start of the game, the machine decides the hand it will play in each round. With supernatural power, Takahashi managed to read all of those hands.
The information Takahashi obtained is given as a string T. If the i-th character of T (1 \leq i \leq N) is r
, the machine will play Rock in the i-th round. Similarly, p
and s
stand for Paper and Scissors, respectively.
What is the maximum total score earned in the game by adequately choosing the hand to play in each round?
Notes
In this problem, Rock Paper Scissors can be thought of as a two-player game, in which each player simultaneously forms Rock, Paper, or Scissors with a hand.
- If a player chooses Rock and the other chooses Scissors, the player choosing Rock wins;
- if a player chooses Scissors and the other chooses Paper, the player choosing Scissors wins;
- if a player chooses Paper and the other chooses Rock, the player choosing Paper wins;
- if both players play the same hand, it is a draw.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq K \leq N-1
- 1 \leq R,S,P \leq 10^4
- N,K,R,S, and P are all integers.
- |T| = N
- T consists of
r
,p
, ands
.
Input
Input is given from Standard Input in the following format:
N K R S P T
Output
Print the maximum total score earned in the game.
Sample Input 1
5 2 8 7 6 rsrpr
Sample Output 1
27
The machine will play {Rock, Scissors, Rock, Paper, Rock}.
We can, for example, play {Paper, Rock, Rock, Scissors, Paper} against it to earn 27 points. We cannot earn more points, so the answer is 27.
Sample Input 2
7 1 100 10 1 ssssppr
Sample Output 2
211
Sample Input 3
30 5 325 234 123 rspsspspsrpspsppprpsprpssprpsr
Sample Output 3
4996
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
高橋君は、あるパーティに特別ゲストとしてやってきました。 そこには一般ゲストが N 人おり、一般ゲスト i (1 \leq i \leq N) の パワー は A_i です。
高橋君は 握手 を M 回行うことで、パーティ全体の 幸福度 を上げることにしました(握手開始前の幸福度を 0 とします)。 握手は、以下の手順によって行われます。
- 高橋君が左手で手を握る (一般) ゲスト x と右手で手を握るゲスト y を決める (両手で同じゲストの手を握っても良い)。
- 高橋君が実際にこれら二本の手を握ることで、幸福度が A_x+A_y 上がる。
ただし、全く同じ握手を二回以上行ってはいけません。厳密には、次の条件を満たす必要があります。
- k 回目の握手で、左手でゲスト x_k と、右手でゲスト y_k と手を握ったとする。このとき、 (x_p,y_p)=(x_q,y_q) を満たすような p,q(1 \leq p < q \leq M) が存在しない。
M 回の握手を行った後、最終的な幸福度は最大でいくらにできるでしょうか。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq N^2
- 1 \leq A_i \leq 10^5
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N
出力
M 回の握手を行った後の最終的な幸福度の最大値を出力せよ。
入力例 1
5 3 10 14 19 34 33
出力例 1
202
例えば、
- 1 回目の握手で左手でゲスト 4、右手でゲスト 4 と握手し、
- 2 回目の握手で左手でゲスト 4、右手でゲスト 5 と握手し、
- 3 回目の握手で左手でゲスト 5、右手でゲスト 4 と握手する
ことで、幸福度を (34+34)+(34+33)+(33+34)=202 とすることができます。
幸福度を 203 以上にはできないので、答えは 202 となります。
入力例 2
9 14 1 3 5 110 24 21 34 5 3
出力例 2
1837
入力例 3
9 73 67597 52981 5828 66249 75177 64141 40773 79105 16076
出力例 3
8128170
Score : 500 points
Problem Statement
Takahashi has come to a party as a special guest. There are N ordinary guests at the party. The i-th ordinary guest has a power of A_i.
Takahashi has decided to perform M handshakes to increase the happiness of the party (let the current happiness be 0). A handshake will be performed as follows:
- Takahashi chooses one (ordinary) guest x for his left hand and another guest y for his right hand (x and y can be the same).
- Then, he shakes the left hand of Guest x and the right hand of Guest y simultaneously to increase the happiness by A_x+A_y.
However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:
- Assume that, in the k-th handshake, Takahashi shakes the left hand of Guest x_k and the right hand of Guest y_k. Then, there is no pair p, q (1 \leq p < q \leq M) such that (x_p,y_p)=(x_q,y_q).
What is the maximum possible happiness after M handshakes?
Constraints
- 1 \leq N \leq 10^5
- 1 \leq M \leq N^2
- 1 \leq A_i \leq 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N
Output
Print the maximum possible happiness after M handshakes.
Sample Input 1
5 3 10 14 19 34 33
Sample Output 1
202
Let us say that Takahashi performs the following handshakes:
- In the first handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 4.
- In the second handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 5.
- In the third handshake, Takahashi shakes the left hand of Guest 5 and the right hand of Guest 4.
Then, we will have the happiness of (34+34)+(34+33)+(33+34)=202.
We cannot achieve the happiness of 203 or greater, so the answer is 202.
Sample Input 2
9 14 1 3 5 110 24 21 34 5 3
Sample Output 2
1837
Sample Input 3
9 73 67597 52981 5828 66249 75177 64141 40773 79105 16076
Sample Output 3
8128170
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点の木 T が与えられます。i 番目の辺は頂点 A_i と B_i (1 \leq A_i,B_i \leq N) を結びます。
T の各頂点を、それぞれ独立に確率 1/2 で黒く、確率 1/2 で白く塗り、黒く塗られた頂点を全て含むような T の最小の部分木 (連結な部分グラフ) を S とします。(黒く塗られた頂点がないときは、S は空グラフとします。)
S の穴あき度を、S に含まれる白く塗られた頂点の個数とします。S の穴あき度の期待値を求めてください。
答えは有理数となるので、注記で述べるように \bmod 10^9+7 で出力してください。
注記
有理数を出力する際は、まずその有理数を分数 \frac{y}{x} として表してください。ここで、x,y は整数であり、 x は 10^9+7 で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。
そして、xz \equiv y \pmod{10^9+7} を満たすような 0 以上 10^9+6 以下の唯一の整数 z を出力してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i,B_i \leq N
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 : A_{N-1} B_{N-1}
出力
S の穴あき度の期待値を \bmod 10^9+7 で出力せよ。
入力例 1
3 1 2 2 3
出力例 1
125000001
頂点 1,2,3 の色がそれぞれ 黒,白,黒 となったとき、S の穴あき度は 1 です。
それ以外の塗り方では S の穴あき度は 0 であるため、穴あき度の期待値は 1/8 です。
8 \times 125000001 \equiv 1 \pmod{10^9+7} より、125000001 を出力します。
入力例 2
4 1 2 2 3 3 4
出力例 2
375000003
期待値は 3/8 です。
8 \times 375000003 \equiv 3 \pmod{10^9+7} より、375000003 を出力します。
入力例 3
4 1 2 1 3 1 4
出力例 3
250000002
期待値は 1/4 です。
入力例 4
7 4 7 3 1 2 6 5 2 7 1 2 7
出力例 4
570312505
Score : 600 points
Problem Statement
Given is a tree T with N vertices. The i-th edge connects Vertex A_i and B_i (1 \leq A_i,B_i \leq N).
Now, each vertex is painted black with probability 1/2 and white with probability 1/2, which is chosen independently from other vertices. Then, let S be the smallest subtree (connected subgraph) of T containing all the vertices painted black. (If no vertex is painted black, S is the empty graph.)
Let the holeyness of S be the number of white vertices contained in S. Find the expected holeyness of S.
Since the answer is a rational number, we ask you to print it \bmod 10^9+7, as described in Notes.
Notes
When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers, and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible).
Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i,B_i \leq N
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 : A_{N-1} B_{N-1}
Output
Print the expected holeyness of S, \bmod 10^9+7.
Sample Input 1
3 1 2 2 3
Sample Output 1
125000001
If the vertices 1, 2, 3 are painted black, white, black, respectively, the holeyness of S is 1.
Otherwise, the holeyness is 0, so the expected holeyness is 1/8.
Since 8 \times 125000001 \equiv 1 \pmod{10^9+7}, we should print 125000001.
Sample Input 2
4 1 2 2 3 3 4
Sample Output 2
375000003
The expected holeyness is 3/8.
Since 8 \times 375000003 \equiv 3 \pmod{10^9+7}, we should print 375000003.
Sample Input 3
4 1 2 1 3 1 4
Sample Output 3
250000002
The expected holeyness is 1/4.
Sample Input 4
7 4 7 3 1 2 6 5 2 7 1 2 7
Sample Output 4
570312505