実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
長さ N の英小文字からなる文字列 S と英小文字 c_1,c_2 が与えられます。
S の文字のうち c_1 であるもの 以外 を全て c_2 に置き換えた文字列を求めてください。
制約
- 1\le N\le 100
- N は整数
- c_1,c_2 は英小文字
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N c_1 c_2 S
出力
答えを出力せよ。
入力例 1
3 b g abc
出力例 1
gbg
S= abc のうち、 b でない a と c を g に置き換えた結果 gbg になります。したがって、 gbg を出力してください。
入力例 2
1 s h s
出力例 2
s
置き換えた後の文字列が元の文字列と変わらない場合もあります。
入力例 3
7 d a atcoder
出力例 3
aaaadaa
入力例 4
10 b a acaabcabba
出力例 4
aaaabaabba
Score : 100 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters, along with lowercase English letters c_1 and c_2.
Find the string obtained by replacing every character of S that is not c_1 with c_2.
Constraints
- 1\le N\le 100
- N is an integer.
- c_1 and c_2 are lowercase English letters.
- S is a string of length N consisting of lowercase English letters.
Input
The input is given in the following format from Standard Input:
N c_1 c_2 S
Output
Print the answer.
Sample Input 1
3 b g abc
Sample Output 1
gbg
Replacing a and c (which are not b) with g in S= abc results in gbg, so print gbg.
Sample Input 2
1 s h s
Sample Output 2
s
It is possible that the resulting string after replacement is the same as the original string.
Sample Input 3
7 d a atcoder
Sample Output 3
aaaadaa
Sample Input 4
10 b a acaabcabba
Sample Output 4
aaaabaabba
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
正整数 N が与えられます。
i=1,2,\ldots,N について (-1)^i \times i^3 を計算したときの、それら N 個の値の総和を求めてください。
すなわち、 \displaystyle \sum_{i=1}^N (-1)^i \times i^3 を求めてください。
制約
- N は 1 以上 10 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
\displaystyle \sum_{i=1}^N (-1)^i \times i^3 の値を出力せよ。
入力例 1
3
出力例 1
-20
- i=1 のとき： (-1)^i\times i^3=-1 です。
- i=2 のとき： (-1)^i\times i^3=8 です。
- i=3 のとき： (-1)^i\times i^3=-27 です。
したがって、 -1 + 8 - 27 = -20 を出力してください。
入力例 2
9
出力例 2
-425
入力例 3
10
出力例 3
575
Score : 100 points
Problem Statement
You are given a positive integer N.
For i=1,2,\ldots,N, calculate (-1)^i \times i^3, and find the sum of these N values.
That is, find \displaystyle \sum_{i=1}^N (-1)^i \times i^3.
Constraints
- N is an integer between 1 and 10, inclusive.
Input
The input is given from Standard Input in the following format:
N
Output
Output the value of \displaystyle \sum_{i=1}^N (-1)^i \times i^3.
Sample Input 1
3
Sample Output 1
-20
- When i=1: (-1)^i\times i^3=-1.
- When i=2: (-1)^i\times i^3=8.
- When i=3: (-1)^i\times i^3=-27.
Therefore, output -1 + 8 - 27 = -20.
Sample Input 2
9
Sample Output 2
-425
Sample Input 3
10
Sample Output 3
575
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
正整数 X が与えられます。
X を（先頭に 0 を含まない形で）十進表記した際に現れる数字を、先頭に 0 が来ないように 並び替えることで得られる正整数のうち、値が最小のものを求めてください。
制約
- 1\leq X < 10^5
- X は整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを出力せよ。
入力例 1
903
出力例 1
309
X を十進表記した際に現れる数字を先頭に 0 が来ないように並び替えることで得られる正整数は、903, 930, 309, 390 の 4 通りであり、このうち値が最小のものは 309 です。
入力例 2
432
出力例 2
234
入力例 3
100
出力例 3
100
Score : 200 points
Problem Statement
You are given a positive integer X.
Find the minimum value among all positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X (without leading zeros) such that there is no leading zero.
Constraints
- 1\leq X < 10^5
- X is an integer.
Input
The input is given from Standard Input in the following format:
X
Output
Output the answer.
Sample Input 1
903
Sample Output 1
309
There are four positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X such that there is no leading zero: 903, 930, 309, 390; the minimum value among them is 309.
Sample Input 2
432
Sample Output 2
234
Sample Input 3
100
Sample Output 3
100
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
各要素が 0 あるいは 1 である N 行 N 列の行列 A, B が与えられます。
A の i 行目 j 列目の要素を A_{i,j}、B の i 行目 j 列目の要素を B_{i,j} で表します。
A を適切に回転することで、 A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできるか判定してください。
ただし、A を回転するとは、以下の操作を好きな回数（0 回でもよい）繰り返すことをいいます。
- 1 \leq i, j \leq N を満たすすべての整数の組 (i, j) について同時に A_{i,j} を A_{N + 1 - j,i} で置き換える
制約
- 1 \leq N \leq 100
- A, B の各要素は 0 か 1 のいずれか
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1} A_{1,2} \ldots A_{1,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
B_{1,1} B_{1,2} \ldots B_{1,N}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,N}
出力
A を適切に回転することで、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできる場合 Yes を、そうでない場合 No を出力せよ。
入力例 1
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
出力例 1
Yes
はじめ、A は
0 1 1 1 0 0 0 1 0
です。
1 回操作を行うと、A は
0 1 0 1 0 1 0 0 1
となります。
もう 1 度操作を行うと、A は
0 1 0 0 0 1 1 1 0
となります。
このとき、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているので、Yes を出力します。
入力例 2
2 0 0 0 0 1 1 1 1
出力例 2
Yes
入力例 3
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
出力例 3
No
Score : 200 points
Problem Statement
You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:
- for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.
Constraints
- 1 \leq N \leq 100
- Each element of A and B is 0 or 1.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1,1} A_{1,2} \ldots A_{1,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
B_{1,1} B_{1,2} \ldots B_{1,N}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,N}
Output
If it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, print Yes; otherwise, print No.
Sample Input 1
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
Sample Output 1
Yes
Initially, A is :
0 1 1 1 0 0 0 1 0
After performing the operation once, A is :
0 1 0 1 0 1 0 0 1
After performing the operation once again, A is :
0 1 0 0 0 1 1 1 0
Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.
Sample Input 2
2 0 0 0 0 1 1 1 1
Sample Output 2
Yes
Sample Input 3
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
Sample Output 3
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 曲からなるプレイリストがあり、曲には 1, \dots, N の番号が付けられています。
曲 i の長さは A_i 秒です。
プレイリストを再生すると、曲 1、曲 2、\ldots、曲 N の順に流れます。曲 N が流れ終わると、再び曲 1 から順に流れていきます。ある曲の途中で次の曲が流れることはなく、曲が流れ終わると、その瞬間に次の曲が流れ始めます。
プレイリストを再生してから T 秒後に流れているのはどの曲ですか？また、その曲が流れ始めてから何秒の時点ですか？
ただし、T 秒後ちょうどに曲が切り替わるような入力は与えられません。
制約
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^{18}
- 1 \leq A_i \leq 10^9
- プレイリストを再生して T 秒後ちょうどに曲が切り替わることはない
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N T A_1 \ldots A_N
出力
プレイリストを再生してから T 秒後に流れている曲の番号と、その曲が流れ始めてから何秒たったかを表す整数を空白区切りで出力せよ。
入力例 1
3 600 180 240 120
出力例 1
1 60
プレイリストを再生してからの様子は次のようになります。
- 0 秒後から 180 秒後まで曲 1 が流れる。
- 180 秒後から 420 秒後まで曲 2 が流れる。
- 420 秒後から 540 秒後まで曲 3 が流れる。
- 540 秒後から 720 秒後まで曲 1 が流れる。
- 720 秒後から 960 秒後まで曲 2 が流れる。
- \qquad\vdots
600 秒後の時点で流れているのは曲 1 であり、流れ始めて 60 秒の時点です。
入力例 2
3 281 94 94 94
出力例 2
3 93
入力例 3
10 5678912340 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
6 678912340
Score : 300 points
Problem Statement
We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.
When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.
At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^{18}
- 1 \leq A_i \leq 10^9
- The playlist does not change songs at exactly T seconds after it starts playing.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N T A_1 \ldots A_N
Output
Print an integer representing the song that is playing at exactly T seconds after the playlist starts playing, and an integer representing the number of seconds that have passed since the start of that song, separated by a space.
Sample Input 1
3 600 180 240 120
Sample Output 1
1 60
When the playlist is played, the following happens. (Assume that it starts playing at time 0.)
- From time 0 to time 180, song 1 plays.
- From time 180 to time 420, song 2 plays.
- From time 420 to time 540, song 3 plays.
- From time 540 to time 720, song 1 plays.
- From time 720 to time 960, song 2 plays.
- \qquad\vdots
At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.
Sample Input 2
3 281 94 94 94
Sample Output 2
3 93
Sample Input 3
10 5678912340 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
6 678912340