Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
整数 N が与えられるので、 2^N-2N の値を計算して出力してください。
制約
- N は 1 以上 11 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
1
出力例 1
0
この入力で与えられる N の値は 1 なので、 2^1 - 2 \times 1 の値である 0 を出力してください。
入力例 2
2
出力例 2
0
この入力で与えられる N の値は 2 なので、 2^2 - 2 \times 2 の値である 0 を出力してください。
入力例 3
11
出力例 3
2026
この入力で与えられる N の値は 11 なので、 2^{11} - 2 \times 11 の値である 2026 を出力してください。
Score : 100 points
Problem Statement
You are given an integer N. Compute and output the value of 2^N-2N.
Constraints
- N is an integer between 1 and 11, inclusive.
Input
The input is given from Standard Input in the following format:
N
Output
Output the answer.
Sample Input 1
1
Sample Output 1
0
The value of N given in this input is 1, so output the value of 2^1 - 2 \times 1, which is 0.
Sample Input 2
2
Sample Output 2
0
The value of N given in this input is 2, so output the value of 2^2 - 2 \times 2, which is 0.
Sample Input 3
11
Sample Output 3
2026
The value of N given in this input is 11, so output the value of 2^{11} - 2 \times 11, which is 2026.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。
S の中で a と b が隣接する箇所があれば Yes を、なければ No を出力してください。(a と b の順序は問いません。)
制約
- 2 \leq N \leq 100
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S の中で a と b が隣接する箇所があれば Yes を、なければ No を出力せよ。
入力例 1
3 abc
出力例 1
Yes
文字列 abc は 1 文字目にある a と 2 文字目にある b が隣接しています。よって Yes を出力してください。
入力例 2
2 ba
出力例 2
Yes
文字列 ba は 2 文字目にある a と 1 文字目にある b が隣接しています。(a と b の順番は逆でも良い点に注意してください。)
入力例 3
7 atcoder
出力例 3
No
Score : 100 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters.
If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No. (The order of a and b does not matter.)
Constraints
- 2 \leq N \leq 100
- S is a string of length N consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N S
Output
If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No.
Sample Input 1
3 abc
Sample Output 1
Yes
The string abc has a as the first character and b as the second character, which are adjacent. Thus, print Yes.
Sample Input 2
2 ba
Sample Output 2
Yes
The string ba has a as the second character and b as the first character, which are adjacent. (Note that the order of a and b does not matter.)
Sample Input 3
7 atcoder
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
2 次元座標平面の原点に高橋くんがいます。
高橋くんが座標平面上の点 (a,b) から点 (c,d) に移動するには \sqrt{(a-c)^2+(b-d)^2} のコストがかかります。
高橋くんが原点からスタートし N 個の点 (X_1,Y_1),\ldots,(X_N,Y_N) へこの順に移動したのち原点に戻るときの、コストの総和を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- -10^9 \leq X_i,Y_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 \vdots X_N Y_N
出力
答えを出力せよ。
真の値との相対誤差または絶対誤差が 10^{-6} 以下であれば正解とみなされる。
入力例 1
2 1 2 -1 0
出力例 1
6.06449510224597979401
移動は次の 3 行程からなります。
- (0,0) から (1,2) に移動する。\sqrt{(0-1)^2+(0-2)^2}=\sqrt{5}=2.236067977... のコストがかかる
- (1,2) から (-1,0) に移動する。\sqrt{(1-(-1))^2+(2-0)^2}=\sqrt{8}=2.828427124... のコストがかかる
- (-1,0) から (0,0) に移動する。\sqrt{(-1-0)^2+(0-0)^2}=\sqrt{1}=1 のコストがかかる
コストの総和は 6.064495102... となります。
入力例 2
7 -14142 13562 -17320 50807 -22360 67977 24494 89742 -26457 51311 28284 27124 31622 77660
出力例 2
384694.57587932075868509383
入力例 3
5 -100000 100000 100000 -100000 -100000 100000 100000 -100000 -100000 100000
出力例 3
1414213.56237309504880168872
Score : 150 points
Problem Statement
Takahashi is at the origin on a two-dimensional coordinate plane.
The cost for him to move from point (a, b) to point (c, d) is \sqrt{(a - c)^2 + (b - d)^2}.
Find the total cost when he starts at the origin, visits N points (X_1, Y_1), \ldots, (X_N, Y_N) in this order, and then returns to the origin.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq X_i, Y_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X_1 Y_1 \vdots X_N Y_N
Output
Print the answer.
Your output will be considered correct if its absolute or relative error from the true value is at most 10^{-6}.
Sample Input 1
2 1 2 -1 0
Sample Output 1
6.06449510224597979401
The journey consists of the following three steps:
- Move from (0, 0) to (1, 2). The cost is \sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977....
- Move from (1, 2) to (-1, 0). The cost is \sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124....
- Move from (-1, 0) to (0, 0). The cost is \sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1.
The total cost is 6.064495102....
Sample Input 2
7 -14142 13562 -17320 50807 -22360 67977 24494 89742 -26457 51311 28284 27124 31622 77660
Sample Output 2
384694.57587932075868509383
Sample Input 3
5 -100000 100000 100000 -100000 -100000 100000 100000 -100000 -100000 100000
Sample Output 3
1414213.56237309504880168872
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は英小文字からなる文字列 S をキーボードで入力しようとしました。
高橋君は画面を見ずにキーボードだけを見てタイピングをしていました。
誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキーが壊れていたため誤って入力された文字は消去されず、実際に入力された文字列は文字列 T となりました。
また、英小文字以外のキーを誤って押してしまうことはありませんでした。
T のうち高橋君が誤って入力した文字でないものを正しく入力された文字であると定めます。
正しく入力された文字が T の何文字目であるか答えてください。
制約
- S, T は長さ 1 以上 2 \times 10^5 以下の英小文字からなる文字列
- T は問題文中の手続きにより得られる文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S の長さを |S| として、正しく入力された文字が A_1, A_2, \ldots, A_{|S|} 文字目であるとき A_1, A_2, \ldots, A_{|S|} の値をこの順に空白区切りで出力せよ。
ただし、出力は昇順になるようにせよ。すなわち、各 1 \leq i \leq |S| - 1 に対して A_i < A_{i + 1} を満たすようにせよ。
入力例 1
abc axbxyc
出力例 1
1 3 6
高橋君のタイピングの一連の流れは以下のようになります。
aを入力する。bを入力しようとするが、誤ってxを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
bを入力する。cを入力しようとするが、誤ってxを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
cを入力しようとするが、誤ってyを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
cを入力する。
正しく入力された文字は 1, 3, 6 文字目です。
入力例 2
aaaa bbbbaaaa
出力例 2
5 6 7 8
入力例 3
atcoder atcoder
出力例 3
1 2 3 4 5 6 7
高橋君が誤った文字を入力することはありませんでした。
Score: 200 points
Problem Statement
Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.
He was typing while looking only at the keyboard, not the screen.
Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.
He did not mistakenly press any keys other than those for lowercase English letters.
The characters in T that were not mistakenly typed are called correctly typed characters.
Determine the positions in T of the correctly typed characters.
Constraints
- S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
- T is a string obtained by the procedure described in the problem statement.
Input
The input is given from Standard Input in the following format:
S T
Output
Let |S| be the length of S. If the correctly typed characters are the A_1-th, A_2-th, \ldots, A_{|S|}-th characters of T, print the values of A_1, A_2, \ldots, A_{|S|} in this order, separated by spaces.
Ensure that the output is in ascending order. That is, A_i < A_{i + 1} should hold for each 1 \leq i \leq |S| - 1.
Sample Input 1
abc axbxyc
Sample Output 1
1 3 6
The sequence of Takahashi's typing is as follows:
- Type
a. - Try to type
bbut mistakenly typex. - Press the backspace key, but the character is not deleted.
- Type
b. - Try to type
cbut mistakenly typex. - Press the backspace key, but the character is not deleted.
- Try to type
cbut mistakenly typey. - Press the backspace key, but the character is not deleted.
- Type
c.
The correctly typed characters are the first, third, and sixth characters.
Sample Input 2
aaaa bbbbaaaa
Sample Output 2
5 6 7 8
Sample Input 3
atcoder atcoder
Sample Output 3
1 2 3 4 5 6 7
Takahashi did not mistakenly type any characters.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。 S の各文字は色 1 、色 2 、\ldots 、色 M の M 色のうちのいずれかで塗られており、 i = 1, 2, \ldots, N について、S の i 文字目は色 C_i で塗られています。
各 i = 1, 2, \ldots, M について、この順番に下記の操作を行います。
- S の色 i で塗られた文字からなる部分を、右に 1 つ巡回シフトする。 すなわち、S の 色 i で塗られた文字の位置が先頭のものから順に p_1, p_2, p_3, \ldots, p_k 文字目であるとき、 S の p_1, p_2, p_3, \ldots, p_k 文字目を、それぞれ、S の p_k, p_1,p_2, \ldots, p_{k-1} 文字目で同時に置き換える。
上記の操作をすべて行った後の、最終的な S を出力してください。
なお、M 色あるどの色についても、その色で塗られた S の文字が必ず 1 つ以上存在することが、制約として保証されます。
制約
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq M
- N, M, C_i はすべて整数
- S は英小文字からなる長さ N の文字列
- 任意の整数 1 \leq i \leq M に対して、ある整数 1 \leq j \leq N が存在して C_j = i が成り立つ
入力
入力は以下の形式で標準入力から与えられる。
N M S C_1 C_2 \ldots C_N
出力
答えを出力せよ。
入力例 1
8 3 apzbqrcs 1 2 3 1 2 2 1 2
出力例 1
cszapqbr
はじめ、S = apzbqrcs です。
- i = 1 に対する操作では、S の 1, 4, 7 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cpzaqrbsとなります。 - i = 2 に対する操作では、S の 2, 5, 6, 8 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cszapqbrとなります。 - i = 3 に対する操作では、S の 3 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cszapqbrとなります(操作の前後で S は変わりません)。
よって、最終的な S である cszapqbr を出力します。
入力例 2
2 1 aa 1 1
出力例 2
aa
Score : 300 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.
For each i = 1, 2, \ldots, M in this order, let us perform the following operation.
- Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.
Print the final S after the above operations.
The constraints guarantee that at least one character of S is painted in each of the M colors.
Constraints
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq M
- N, M, and C_i are all integers.
- S is a string of length N consisting of lowercase English letters.
- For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.
Input
The input is given from Standard Input in the following format:
N M S C_1 C_2 \ldots C_N
Output
Print the answer.
Sample Input 1
8 3 apzbqrcs 1 2 3 1 2 2 1 2
Sample Output 1
cszapqbr
Initially, S = apzbqrcs.
- For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S =
cpzaqrbs. - For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S =
cszapqbr. - For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S =
cszapqbr(here, S is not changed).
Thus, you should print cszapqbr, the final S.
Sample Input 2
2 1 aa 1 1
Sample Output 2
aa