Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます。
S の先頭から a 文字目と b 文字目を入れ替えて得られる文字列を出力してください。
制約
- S は英小文字からなる文字列
- S の長さ |S| は、 2 \leq |S| \leq 10 を満たす
- 1 \leq a < b \leq |S|
- a, b は整数
入力
入力は以下の形式で標準入力から与えられる。
S a b
出力
答えを出力せよ。
入力例 1
chokudai 3 5
出力例 1
chukodai
chokudai の 3 文字目 o と 5 文字目 u を入れ替えると chukodai となります。
入力例 2
aa 1 2
出力例 2
aa
この入力例では、S の 1 文字目と 2 文字目を入れ替えて得られる文字列は、元の S と同じになります。
入力例 3
aaaabbbb 1 8
出力例 3
baaabbba
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English letters.
Swap the a-th and b-th characters from the beginning of S and print the resulting string.
Constraints
- S is a string consisting of lowercase English letters.
- The length of S, |S|, satisfies 2 \leq |S| \leq 10.
- 1 \leq a < b \leq |S|
- a and b are integers.
Input
Input is given from Standard Input in the following format:
S a b
Output
Print the answer.
Sample Input 1
chokudai 3 5
Sample Output 1
chukodai
After swapping the 3-rd character o and 5-th character u of chokudai, we have chukodai.
Sample Input 2
aa 1 2
Sample Output 2
aa
In this sample, after swapping the 1-st and 2-nd characters of S, we have the same string as S.
Sample Input 3
aaaabbbb 1 8
Sample Output 3
baaabbba
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
AtCoder 社は、オンラインショップでグッズを販売しています。
高橋君はそこで N 種類の商品を購入することにしました。
1 以上 N 以下の整数 i について、i 種類目の商品は 1 個 P_i 円で、高橋君は Q_i 個購入します。
また、高橋君は送料を支払う必要があります。
送料は購入する商品の合計金額が S 円以上なら 0 円、そうでないならば K 円です。
高橋君が支払う金額は購入する商品の合計金額と送料の和です。
高橋君が支払う金額を求めてください。
制約
- 1\leq N\leq 100
- 1\leq S\leq 10000
- 1\leq K\leq 10000
- 1\leq P_i\leq 10000
- 1\leq Q_i\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N S K P_1 Q_1 P_2 Q_2 \vdots P_N Q_N
出力
高橋君がオンラインショッピングで支払う金額を出力せよ。
入力例 1
2 2000 500 1000 1 100 6
出力例 1
2100
高橋君は 1 個 1000 円の商品を 1 個と、 1 個 100 円の商品を 6 つ購入します。
よって、購入する商品の合計金額は 1000\times 1+100\times 6=1600 円となります。
このとき購入する商品の合計金額は 2000 円未満であるため、送料は 500 円となります。
よって、高橋君の支払う金額は 1600+500=2100 円となります。
入力例 2
3 2000 500 1000 1 100 6 5000 1
出力例 2
6600
購入する商品の合計金額は 1000\times 1+100\times 6+5000\times 1=6600 円となります。
このとき購入する商品の合計金額は 2000 円以上であるため、送料は 0 円となります。
よって、高橋君の支払う金額は 6600+0=6600 円となります。
入力例 3
2 2000 500 1000 1 1000 1
出力例 3
2000
1 個あたりの価格が同じ商品が複数存在することもあります。
Score : 100 points
Problem Statement
AtCoder Inc. sells merchandise through its online shop.
Takahashi has decided to purchase N types of products from there.
For each integer i from 1 to N, the i-th type of product has a price of P_i yen each, and he will buy Q_i of this.
Additionally, he must pay a shipping fee.
The shipping fee is 0 yen if the total price of the products purchased is S yen or above, and K yen otherwise.
He will pay the total price of the products purchased plus the shipping fee.
Calculate the amount he will pay.
Constraints
- 1\leq N\leq 100
- 1\leq S\leq 10000
- 1\leq K\leq 10000
- 1\leq P_i\leq 10000
- 1\leq Q_i\leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S K P_1 Q_1 P_2 Q_2 \vdots P_N Q_N
Output
Print the amount Takahashi will pay for online shopping.
Sample Input 1
2 2000 500 1000 1 100 6
Sample Output 1
2100
Takahashi buys one product for 1000 yen and six products for 100 yen each.
Thus, the total price of the products is 1000\times 1+100\times 6=1600 yen.
Since the total amount for the products is less than 2000 yen, the shipping fee will be 500 yen.
Therefore, the amount Takahashi will pay is 1600+500=2100 yen.
Sample Input 2
3 2000 500 1000 1 100 6 5000 1
Sample Output 2
6600
The total price of the products is 1000\times 1+100\times 6+5000\times 1=6600 yen.
Since the total amount for the products is not less than 2000 yen, the shipping fee will be 0 yen.
Therefore, the amount Takahashi will pay is 6600+0=6600 yen.
Sample Input 3
2 2000 500 1000 1 1000 1
Sample Output 3
2000
There may be multiple products with the same price per item.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
実数 X が小数点以下第 3 位まで与えられます。
実数 X を以下の条件を満たすように出力してください。
- 小数点以下の部分について、末尾に
0を付けない - 末尾に過剰な小数点を付けない
制約
- 0 \le X < 100
- X は小数点以下第 3 位まで与えられる
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを出力せよ。
入力例 1
1.012
出力例 1
1.012
1.012 はそのまま出力しても構いません。
入力例 2
12.340
出力例 2
12.34
12.340 を末尾に 0 を付けずに出力すると 12.34 となります。
入力例 3
99.900
出力例 3
99.9
99.900 を末尾に 0 を付けずに出力すると 99.9 となります。
入力例 4
0.000
出力例 4
0
0.000 を末尾に 0 や過剰な小数点を付けずに出力すると 0 となります。
Score : 150 points
Problem Statement
A real number X is given to the third decimal place.
Print the real number X under the following conditions.
- The decimal part must not have trailing
0s. - There must not be an unnecessary trailing decimal point.
Constraints
- 0 \le X < 100
- X is given to the third decimal place.
Input
The input is given from Standard Input in the following format:
X
Output
Output the answer.
Sample Input 1
1.012
Sample Output 1
1.012
1.012 can be printed as it is.
Sample Input 2
12.340
Sample Output 2
12.34
Printing 12.340 without the trailing 0 results in 12.34.
Sample Input 3
99.900
Sample Output 3
99.9
Printing 99.900 without the trailing 0s results in 99.9.
Sample Input 4
0.000
Sample Output 4
0
Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
座標平面上に N 枚の長方形のシートが張られています。
各シートが覆う長方形領域の各辺はそれぞれ x 軸または y 軸と平行であり、
具体的には、i 枚目のシートはちょうど A_i \leq x\leq B_i かつ C_i \leq y\leq D_i をみたす領域全体を覆っています。
1 枚以上のシートによって覆われている領域 の面積を S とすると、
S は制約の条件下で整数となる事が証明できます。
S を整数の形で出力してください。
制約
- 2\leq N\leq 100
- 0\leq A_i<B_i\leq 100
- 0\leq C_i<D_i\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
出力
1 枚以上のシートによって覆われている領域の面積 S を整数で出力せよ。
入力例 1
3 0 5 1 3 1 4 0 5 2 5 2 4
出力例 1
20
3 枚のシートによって覆われている領域は次のようになります。
ここで、赤色・黄色・青色はそれぞれ 1 枚目・ 2 枚目・ 3 枚目のシートによって覆われている領域を表しています。

よって、1 枚以上のシートによって覆われている領域の面積は S=20 となります。
入力例 2
2 0 100 0 100 0 100 0 100
出力例 2
10000
異なるシートが同じ領域を覆っている事があることに注意してください。
入力例 3
3 0 1 0 1 0 3 0 5 5 10 0 10
出力例 3
65
Score : 200 points
Problem Statement
There are N rectangular sheets spread out on a coordinate plane.
Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.
Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.
Constraints
- 2\leq N\leq 100
- 0\leq A_i<B_i\leq 100
- 0\leq C_i<D_i\leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
Output
Print the area S of the region covered by one or more sheets as an integer.
Sample Input 1
3 0 5 1 3 1 4 0 5 2 5 2 4
Sample Output 1
20
The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.
Sample Input 2
2 0 100 0 100 0 100 0 100
Sample Output 2
10000
Note that different sheets may cover the same region.
Sample Input 3
3 0 1 0 1 0 3 0 5 5 10 0 10
Sample Output 3
65
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
N 頂点 N 辺の有向グラフがあります。
i 番目の辺は頂点 i から 頂点 A_i に伸びます。 ( i \neq A_i であることは制約より保証されます )
同一頂点を複数回含まない有向閉路をひとつ求めてください。
なお、この問題の制約下で答えが存在することが示せます。
注釈
この問題では、有向閉路とは以下の条件を全て満たす頂点の列 B=(B_1,B_2,\dots,B_M) であるとします。
- M \ge 2
- B_i から B_{i+1} に辺が伸びている。 ( 1 \le i \le M-1 )
- B_M から B_1 に辺が伸びている。
- i \neq j ならば B_i \neq B_j
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le N
- A_i \neq i
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
以下の形式で出力せよ。
M B_1 B_2 \dots B_M
M は出力する有向閉路の頂点数であり、 B_i は有向閉路の i 番目の頂点である。
出力は以下の条件を満たす必要がある。
- 2 \le M
- B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
- B_{1} = A_{B_M}
- B_i \neq B_j ( i \neq j )
答えとして考えられるものが複数ある場合、どれを出力しても正解となる。
入力例 1
7 6 7 2 1 3 4 5
出力例 1
4 7 5 3 2
7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 は確かに有向閉路になっています。
この入力に対応するグラフは以下の通りです。

他の正解となる出力の例は以下の通りです。
4 2 7 5 3
3 4 1 6
グラフが連結であるとは限らないことに注意してください。
入力例 2
2 2 1
出力例 2
2 1 2
1 \rightarrow 2 と 2 \rightarrow 1 の辺が双方存在するケースです。
この場合、 1 \rightarrow 2 \rightarrow 1 は確かに有向閉路になっています。
この入力に対応するグラフは以下の通りです。
図中 1 \leftrightarrow 2 で 1 \rightarrow 2 と 2 \rightarrow 1 の辺が双方あることを表現しています。

入力例 3
8 3 7 4 7 3 3 8 2
出力例 3
3 2 7 8
この入力に対応するグラフは以下の通りです。

Score : 350 points
Problem Statement
There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.
Notes
The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:
- M \geq 2
- The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
- The edge from vertex B_M to vertex B_1 exists.
- If i \neq j, then B_i \neq B_j.
Constraints
- All input values are integers.
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le N
- A_i \neq i
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print a solution in the following format:
M B_1 B_2 \dots B_M
M is the number of vertices, and B_i is the i-th vertex in the directed cycle.
The following conditions must be satisfied:
- 2 \le M
- B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
- B_{1} = A_{B_M}
- B_i \neq B_j ( i \neq j )
If multiple solutions exist, any of them will be accepted.
Sample Input 1
7 6 7 2 1 3 4 5
Sample Output 1
4 7 5 3 2
7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.
Here is the graph corresponding to this input:

Here are other acceptable outputs:
4 2 7 5 3
3 4 1 6
Note that the graph may not be connected.
Sample Input 2
2 2 1
Sample Output 2
2 1 2
This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.
Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3
8 3 7 4 7 3 3 8 2
Sample Output 3
3 2 7 8
Here is the graph corresponding to this input:
